M.Sc Thesis

M.Sc StudentAzatchi Hezi
SubjectIntegrating Generations with Advanced Reference Counting
DepartmentDepartment of Computer Science
Supervisor PROF. Erez Petrank


We study an incorporation of generations into a modern reference counting collector. We start with the two on-the-fly collectors suggested by Levanoni and Petrank: a reference counting collector and a tracing (mark and sweep) collector. We then propose three designs for combining them so that the reference counting collector collects the young generation or the old generation or both. Our designs maintain the good properties of the Levanoni-Petrank collector. In particular, it is adequate for multithreaded environment and a multiprocessor platform, and it has an efficient write barrier with no synchronization operations. To the best of our knowledge, the use of generations with reference counting has not been tried before. In addition to the new study of generations with reference counting, our work is also interesting as yet another attempt to run generations with an on-the-fly collector.

We have implemented these algorithms with the Jikes JVM and compared them against the concurrent reference counting collector supplied with the Jikes package. As expected, the best combination is the one that lets the tracing collector work on the young generation (where most objects die) and the reference counting work on the old generation (where many objects survive).  Matching the expected survival rate with the nature of the collector yields a large improvement in throughput while maintaining the pause times around a couple of milliseconds.

An abridged version of this work has appeared in the proceeding of ETAPS 2003, 12th International Conference on Compiler Construction, April 5 - 13, 2003, Warsaw, Poland.