OOPSLA '04

Program
Technical Program
  Invited Speakers
  Technical Papers
  Onward!
  Panels
  Practitioner Reports
  Tutorials
Workshops
DesignFest
Educators' Symposium
Demonstrations
Posters
Doctoral Symposium
Exhibits
Student Research Comp.
FlashBoF
 
Turing Lecture
 
Social Events
 
Week at a Glance
 
Final Program (1.5M .pdf)

Find in Program
 

Page
Printer-friendly

Basket
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
 


 
7·8·9·10·11·12·13·14·15·16·17·18·19·20·21

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.