Talk:Deterministic garbage collector

The idea that the author is describing is commonly called `incremental' garbage collection. The simplest version is that each time you allocate, say, N memory cells, you should also GC (mark, move, or reclaim) at least 2N cells. This way, GC is performed incrementally in very small chunks - once per allocation - and is hence very predictable. Since the rate at which cells are collected exceeds, on average, the rate at which new memory is allocated, the GC is guaranteed to periodically `catch up' to the memory allocator, so that it can start scanning again from the roots.

In a copying GC, the usual strategy would be to allocate new objects in the `to' space, and simultaneously (with each allocation) copy a few additional objects in from the `from' space, flipping the spaces and restarting from the roots whenever the last reachable `from' object has been found. The minimum factor of 2 (as in 2N above) guarantees that copying will catch up to allocation quickly enough to require equal sized from and to spaces - making this a minor modification to Cheney's algorithm. Modern GCs are doubtless much cleverer.

NB: `deterministic' GC commonly refers to determinism in when objects are deallocated - for managing resources and such - rather than in the time taken to do the deallocations.

This stuff is adequately covered in the main GC page.