Technical Program
  Invited Speakers
  Technical Papers
  Practitioner Reports
Educators' Symposium
Doctoral Symposium
Student Research Comp.
Turing Lecture
Social Events
Week at a Glance
Final Program (1.5M .pdf)

Find in Program


view, help

"An Efficient Parallel Heap Compaction Algorithm"
Object-Oriented Programming, Systems, Languages and Applications
Home    Program    Housing & Transportation    Registration    Submissions    Wiki    Maps
  > Technical Program > Technical Papers > Java Technologies

 : Wednesday

An Efficient Parallel Heap Compaction Algorithm

Meeting Rooms 1-3
Wednesday, 11:00, 30 minutes


Diab Abuaiadh, IBM Haifa Research Lab
Yoav Ossia, IBM Haifa Research Lab
Erez Petrank, Technion, Israel Institute of Technology
Uri Silbershtein, IBM Haifa Research Lab

We propose a heap compaction algorithm appropriate for modern computing environments. Our algorithm is targeted at SMP platforms. It demonstrates high scalability when running in parallel but is also extremely efficient when running single-threaded on a uniprocessor. Instead of using the standard forwarding pointer mechanism for updating pointers to moved objects, the algorithm saves information for a pack of objects. It then does a small computation to process this information and determine each object's new location.

In addition, using a smart parallel moving strategy, the algorithm achieves (almost) perfect compaction in the lower addresses of the heap, whereas previous algorithms achieved parallelism by compacting within several predetermined segments.

Next, we investigate a method that trades compaction quality for a further reduction in time and space overhead.

Finally, we propose a modern version of the two-finger compaction algorithm. This algorithm fails, thus, re-validating traditional wisdom asserting that retaining the order of live objects significantly improves the quality of the compaction.

The parallel compaction algorithm was implemented on the IBM production Java Virtual Machine. We provide measurements demonstrating high efficiency and scalability. Subsequently, this algorithm has been incorporated into the IBM production JVM.