Paper: on-the-fly reference-counting GC
Reference-counting is traditionally considered unsuitable for multi-processor systems. According to conventional wisdom, the update of reference slots and reference-counts requires atomic or synchronized operations. In this work we demonstrate this is not the case by presenting a novel reference-counting algorithm suitable for a multi-processor system that does not require any syn- chronized operation in its write barrier (not even a compare-and-swap type of synchronization). A second novelty of this algorithm is that it allows eliminating a large fraction of the reference- count updates, thus, drastically reducing the reference-counting traditional overhead. This paper includes a full proof of the algorithm showing that it is safe (does not reclaim live objects) and live (eventually reclaims all unreachable objects).