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
Abstract
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.