LCPC 2008 - A Fully Parallel LISP2 Compactor Preserving the Sliding Properties

A Fully Parallel LISP2 Compactor Preserving the Sliding Properties

Xiao-Feng Li, Ligang Wang and Chen Yang

21th Annual Workshop on Languages and Compilers for Parallel Computing (LCPC 2008)
Edmonton, Alberta, Canada, July 31 - August 2, 2008

Summary

Compacting garbage collector (GC) is widely used due to its good properties of in-place collection and heap de-fragmentation, which supports fast allocation and has good access locality. Most known commercial JVM or CLR implementations use compacting algorithm in certain garbage collection scenarios, such as in the full heap collections or mature object space collections.

The LISP2 compactor is one of the best-known GC algorithms. As multi-core architecture becomes prevailing, several efficient parallel compactors have been proposed. But there is no parallel LISP2 compactor available that can preserve all the sliding properties of its sequential counterpart. That is, to compact the live data in-place into a single contiguous region in one end of the heap, and still maintaining the original object order.

In this paper, we propose a fully parallel LISP2 compactor that keeps all the sliding properties. We also prove the correctness of the design. This parallel LISP2 compactor is fully parallel because all of its four phases are parallelized and the workloads are well balanced among the collector threads.

The compactor supports fall-back compaction and adjustable boundaries that help to deliver the best performance. We have implemented the parallel LISP2 compactor in Apache Harmony, a product-quality open source Java SE implementation. We evaluate and discuss the design on an 8-core platform with representative benchmark.

START Conference Manager (V2.54.5)