Understanding the current GC, conclusion
by Leandro Lucarella on 2009- 04- 11 19:36 (updated on 2009- 04- 11 19:36)- with 0 comment(s)
Now that I know fairly deeply the implementation details about the current GC, I can compare it to the techniques exposed in the GC Book.
Tri-colour abstraction
Since most literature speaks in terms of the tri-colour abstraction, now it's a good time to translate how this is mapped to the D GC implementation.
As we all remember, each cell (bin) in D has several bits associated to them. Only 3 are interesting in this case:
- mark
- scan
- free (freebits)
So, how we can translate this bits into the tri-colour abstraction?
- Black
Cells that were marked and scanned (there are no pointer to follow) are coloured black. In D this cells has the bits:
mark = 1 scan = 0 free = 0
- Grey
Cells that has been marked, but they have pointers to follow in them are coloured grey. In D this cells has the bits:
mark = 1 scan = 1 free = 0
- White
Cells that has not been visited at all are coloured white (all cells should be colored white before the marking starts). In D this cells has the bits:
mark = 0 scan = X
Or:
free = 1
The scan bit is not important in this case (but in D it should be 0 because scan bits are cleared before the mark phase starts). The free bit is used for the cells in the free list. They are marked before other cells get marked with bits mark=1 and free=1. This way the cells in the free list don't get scanned (mark=1, scan=0) and are not confused with black cells (free=1), so they can be kept in the free list after the mark phase is done. I think this is only necessary because the free list is regenerated.
Improvements
Here is a summary of improvements proposed by the GC Book, how the current GC is implemented in regards to this improvements and what optimization opportunities can be considered.
Mark stack
The simplest version of the marking algorithm is recursive:
mark(cell)
if not cell.marked
cell.marked = true
for child in cell.children
mark(child)
The problem here is, of course, stack overflow for very deep heap graphs (and the space cost).
The book proposes using a marking stack instead, and several ways to handle stack overflow, but all these are only useful for relieving the symptom, they are not a cure.
As a real cure, pointer reversal is proposed. The idea is to use the very same pointers to store the mark stack. This is constant in space, and needs only one pass through the help, so it's a very tempting approach. The bad side is increased complexity and probably worse cache behavior (writes to the heap dirties the entire heap, and this can kill the cache).
Current implementation
The D GC implementation does none of this. Instead it completes the mark phase by traversing the heap (well, not really the heap, only the bit sets) in several passes, until no more data to scan can be found (all cells are painted black or white). While the original algorithm only needs one pass through the heap, this one need several. This trades space (and the complexity of stack overflow handling) for time.
Optimization opportunities
This seems like a fair trade-off, but alternatives can be explored.
Bitmap marking
The simplest mark-sweep algorithm suggests to store marking bits in the very own cells. This can be very bad for the cache because a full traversal should be done across the entire heap. As an optimization, a bitmap can be used, because they are much small and much more likely to fit in the cache, marking can be greatly improved using them.
Current implementation
Current implementation uses bitmaps for mark, scan, free and other bits. The bitmap implementation is GCBits and is a general approach.
The bitmap stores a bit for each 16 bytes chunks, no matter what cell size (Bins, or bin size) is used. This means that 4096/16 = 256 bits (32 bytes) are used for each bitmap for every page in the GC heap. Being 5 bitmaps (mark, scan, freebits, finals and noscan), the total spaces per page is 160 bytes. This is a 4% space overhead in bits only.
This wastes some space for larger cells.
Optimization opportunities
The space overhead of bitmaps seems to be fairly small, but each byte counts for the mark phase because of the cache. A heap with 64 MiB uses 2.5 MiB in bitmaps. Modern processors come with about that much cache, and a program using 64 MiB doesn't seems very rare. So we are pushing the limits here if we want our bitmaps to fit in the cache to speed up the marking phase.
I think there is a little room for improvement here. A big object, lets say it's 8 MiB long, uses 640 KiB of memory for bitmaps it doesn't need. I think some specialized bitmaps can be used for large object, for instance, to minimize the bitmaps space overhead.
There are some overlapping bits too. mark=0 and scan=1 can never happen for instance. I think it should be possible to use that combination for freebits, and get rid of an entire bitmap.
Lazy sweep
The sweep phase is done generally right after the mark phase. Since normally the collection is triggered by an allocation, this can be a little disrupting for the thread that made that allocation, that has to absorb all the sweeping itself.
Another alternative is to do the sweeping incrementally, by doing it lazy. Instead of finding all the white cells and linking them to the free list immediately, this is done on each allocation. If there is no free cells in the free list, a little sweeping is done until new space can be found.
This can help minimize pauses for the allocating thread.
Current implementation
The current implementation does an eager sweeping.
Optimization opportunities
The sweeping phase can be made lazy. The only disadvantage I see is (well, besides extra complexity) that could make the heap more likely to be fragmented, because consecutive requests are not necessarily made on the same page (a free() call can add new cells from another page to the free list), making the heap more sparse, (which can be bad for the cache too). But I think this is only possible if free() is called explicitly, and this should be fairly rare in a garbage collected system, so I guess this could worth trying.
Lazy sweeping helps the cache too, because in the sweep phase, you might trigger cache misses when linking to the free list. When sweeping lazily, the cache miss is delayed until it's really necessary (the cache miss will happen anyway when you are allocating the free cell).
Conclusion
Even when the current GC is fairly optimized, there is plenty of room for improvements, even preserving the original global design.