Technical Report MSC-2012-13

Title: A Study of Data Structures with a Deep Heap Shape
Authors: Haggai Eran
Supervisors: Erez Petrank
Abstract: Computing environments become increasingly parallel, and it seems likely that we will see more cores on tomorrow's desktops and server platforms. In a highly parallel system, tracing garbage collectors may not scale well due to deep heap structures. Such structures can hurt the load balancing of the parallel trace, and that may hinder parallel tracing. In this work we start by analyzing which data structures make current Java benchmarks create deep heap shapes. We analyze benchmarks of four common benchmark suites, measuring how well they might scale under a parallel garbage collector. We use a simulated multiprocessor garbage collection trace for our measurements, allowing us to estimate the scalability of the garbage collector on massively parallel machines. It turns out that the problem is manifested mostly with benchmarks that employ queues and linked-lists. We discuss existing alternatives for these data structures, that would improve the garbage collector scalability. Then we propose a new construction of the queue data structure that enables better garbage collector parallelism. We modify an existing lock-free unbounded queue by adding extra references that allow the garbage collector to distribute the tracing of the queue among multiple threads. The new queue incurs a low overhead, and provides the same progress guarantees as the original queue.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2012
To the main CS technical reports page

Computer science department, Technion