ISMM 2007 START Conference Manager    

Mark-Sweep or Copying? A "Best of Both Worlds" Algorithm and a Hardware-Supported Real-Time Implementation

Sylvain Stanchina and Matthias Meyer

The 2007 International Symposium on Memory Management (ISMM 2007)
Montreal, Canada, 21-22 October, 2007


Copying collectors offer a number of advantages over their mark-sweep counterparts. First, they do not have to deal with mark stacks and potential mark stack overflows. Second, they do not suffer from unpredictable fragmentation overheads since they inherently compact the heap. Third, the tospace invariant maintained by many copying collectors allows for incremental compaction and provides the basis for efficient real-time implementations. Unfortunately, however, copying collectors depend on two semispaces and therefore need at least twice as much memory as required for the maximum amount of live data.

In this paper, we introduce a novel mark-compact algorithm that combines the elegance and simplicity of Baker's copying algorithm with the memory efficiency of mark-sweep algorithms. Furthermore, we present a hardware-supported implementation for real-time applications in the framework of an object-based RISC architecture.

Measurements of Java programs on an FPGA-based prototype show that our novel mark-compact algorithm outperforms a corresponding copying collector in every respect. It requires far less memory space for real-time behavior and, at the same time, reduces the overall runtime overhead under typical operating conditions.

START Conference Manager (V2.54.5)