M.Sc Thesis

M.Sc StudentEran Haggai
SubjectA Study of Data Structures with a Deep Heap Shape
DepartmentDepartment of Computer Science
Supervisor PROF. Erez Petrank
Full Thesis textFull thesis text - English Version


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.