Historical note: the Lisp Machines had true incremental collection, supported by microcode and hardware. Words in memory had a tag field, and a certain value o

Historical note: the Lisp Machines had true incremental collection, supported by microcode and hardware. Words in memory had a tag field, and a certain value of the tag field indicated that the word was "GC-forwarded". When the GC moved an object (it was a copying collector) it would leave behind these GC-forward pointers in each word of the old location of the object, pointing to the corresponding word of the new location. Subsequent references to one of the old words would automatically indirect to the new one -- note that this is an indirection triggered by the contents of memory, not by an explicit instruction. The point was, it was no longer necessary to find all references to the old location and update them just to move one object. (The GC algorithm guaranteed that all references to old objects would be updated eventually, so that the space could be actually reclaimed.) It's hard to do this without hardware support, and even harder on a multiprocessor. Still, I do recall seeing a paper presenting a fully incremental GC with a very short maximum-pause guarantee. The problem was (IIRC) that it made such heavy use of CAS (compare-and-swap) instructions that the overhead of these would be unacceptable. I wonder how much effort Intel and AMD have been putting into making CAS faster.