Understanding the Connectivity of Heap Objects Technical Report: CU-CS-923-01

Modern garbage collectors partition the set of heap objects to achieve the best performance. For exam- ple, generational garbage collectors partition objects by age and focus their e orts on the youngest objects. Partitioning by age works well for many programs because younger objects usually have short lifetimes and thus garbage collection of young objects is of- ten able to free up many objects. However, genera- tional garbage collectors are typically much less e- cient for longer-lived objects, and thus prior work has proposed many enhancements to generational collec- tion. Our work explores whether the connectivity of ob- jects can yield useful partitions or improve existing partitioning schemes. We look at both direct (e.g., object A points to object B) and transitive (e.g., ob- ject A is reachable from object B) connectivity. Our results indicate that connectivity correlates strongly with object lifetimes and deathtimes and is therefore likely to be useful for partitioning objects.