By Simon Hem Pedersen | July 2, 2009
When my companion and I wrote our Master’s Thesis “Garbage Collection in a gbeta Virtual Machine with the Train Algorithm” we read one of Urs Hölzle’s articles – “A Fast Write Barrier for Generational Garbage Collectors”. The article described how to implement an efficient write barrier, more specifically how to use a card-marking write barrier scheme. It was a short article without a lot of complex theory and it treated the subject in a clear way making it easy to understand and inspiring to read – like candy for the brain .
The purpose of a write barrier is to ensure that the garbage collector keeps track of the object heap each time a pointer is updated.
The write barrier in a generational garbage collector ensures that the remembered set of each generation is updated (in the train algorithm the remembered set is used between cars (mini generations within a train) and between trains (macro generations)). A remembered set (proposed by David Ungar) keeps track of which objects of a younger generations is referenced (kept alive) from an object residing in an older generation.
The card-marking write barrier scheme does this by dividing the heap into cards of size 2kwords. Every card has an associated bit in a separate bit vector. A store check simply marks the bit corresponding to the location being updated. At garbage collection time, the collector scans the bit vector and, whenever it ﬁnds a marked bit, examines all pointers in the corresponding card in the heap.
At JAOO Urs Hölzle will be speaking about “Energy-efficient cloud computing” and telling us how Google made their infrastructure scalable, cost effective and energy efficient.JAOO | Tags: David Ungar, Google, JAOO Aarhus, JAOO Aarhus 2009, Urs Hölzle | No Comments »