zerogc

zerogc copied to clipboard

This would remove the sweep phase of the collection and implicitly mark the arenas as dead instead of adding them to the free list. Instead of searching the free list, allocations would search for a free slot in the dead memory. This would amortize the sweeping cost across future allocations.

As of to 9a9634d68a493, the binary_trees benchmark spent 30% of total time compacting (I accidentally said tracing). This would actually make the mark/sweep collector noticeably faster than the old copying collector.

This actually reduces the theoretical complexity of the algorithm :open_mouth: Normally, the collection is proportional to total objects (live + dead), while now it's only proportional to live objects.

This is discussed in Section 2.5 of The Garbage Collection Handbook (Jones, 2012). In addition to the obvious reduction in collection time, it improves the locality of sweeping. They state that it offers good throughput, especially when there are many dead objects (the same workloads copying collectors are best at).

This threatens to increase complexity, so I'm not quite sure about whether it's a great idea... It should probably be optional, although I'd put it on by default (eager sweeping could return memory to the operating system: #6).

If issues ever arise with the simple collector's pause times, this is definitely the most obvious optimization opportunity... However, this is currently not a very high priority for me.

Note to self (based on some playing around and reading): Lazy sweeping should be done a chunk at a time, using the free list most of the time. This has the added advantage that we can count live objects per chunk, freeing a chunk when there are zero (See #6).

NOTE: Once again losing interest in this :laughing:

I'm going to defer this to a later release. I want to get a working prototype in DuckLogic ASAP :wink: