Papers 1-1 Generation Scavenging by David Ungar (1984)

Generation Scavenging: A Non-disruptlve High Performance Storage Reclamation Algorithm

I came to this paper from TGCH. This paper has been mentioned multiple times in the book, and was one of the most important piece of works in the early years of Generational GC. It won the ACM SIGSOFT Impact Paper Award in 2008.

David Ungar was a PhD student of David Patterson at UC Berkely at the time, and was working on the high performance Smalltalk-80 on RISC project funded by IBM and DoD. One of the tasks was to replace the reference counting in Smalltalk with a traversing GC. He had been at Sun between 1991 and 2007 which means Bernd must know him...

There were 3 noticeable previous works on Generational GC:

Baker's work was an incremental concurrent copying collector on LISP. Ballard use Baker's copying scheme on Smalltalk, but divided the memory into young and old generations. Each space is further divided into from and to semispaces. Lieberman and Hewitt first claimed "Most Objects Die Young", and had forwarding pointer and reference tables between generations.

Ungar's work is important in several areas:

  • He further divided Young generation into 3 spaces: New Space (Eden), PastSurvivorSpace (S0), FutureSurvivorSpace (S1). The is basically the same layout for ParallelGC and CMS.
  • He invented the tenuring and tenuring threshold between S0 and S1.
  • He introduced remembered set and the post-write barrier on updating remembered set to replace the forward pointers and reference tables in Lieberman's algorithm.

The most astonishing thing to me was that he suggested to use 'adaptive tenuring policy' and 'hint from executing program' to improve tenuring, and it was 1984...

At the time, people worried a lot about the speed diff between the main memory and backing store, and also page faults. Young Generation was on the main memory, while the Old Generation was on the demand paged backing store.