3 ms·
To add on top of this: This is a tracing GC. It only ever visits the live data, not the dead data. In other words, it would need a lot more special support if i
by writebetterc 1y ago
To add on top of this: This is a tracing GC. It only ever visits the live data, not the dead data. In other words, it would need a lot more special support if it wanted to report the dead objects.
- kragen 1y agoReally? How does a non-moving GC make dead objects available for reallocation without visiting them?
- torginus 1y agoWhy would it need to visit them? It just marks the address ranges as available in its internal bookkeeping (bitmaps etc).
- kragen 1y agoIn the general case there are as many newly available address ranges as dead objects, so that counts as visiting them in this context.
- torginus 1y agoI don't think that's a definition of 'visit' most people would agree with. I'm actually working on my own language that has a non-moving GC. It uses size classes (so 16 byte objects, 32 byte objects etc.), each of which is allocated in a continous slab of memory. Occupancy is determined by a bitmap, 1 bit for each slot in the slab. The GC constructs a liveness bitmap for the size class, and the results are ANDed together, 'freeing' the memory. If you fill the slab with dead objects, then run the GC, it will not walk anywhere on this slab, create an all zero liveness bitmap, and free the memory.
- kragen 1y agoThat's an awesome project! Is your GC generational despite being non-moving? What are your main objectives for the project? The liveness bitmap approach is pretty widespread at this point; jemalloc works the same way IIRC. Still, I think that counts as "visiting" in the context of this discussion: https://news.ycombinator.com/item?id=45137139 https://news.ycombinator.com/item?id=45137139
- writebetterc 1y agoI don't think it counts as visiting, as you never look at the dirtied bitmap during GC, only during allocation. That means, you don't actually know if a dirty bit represents a different object or not (if a 16-byte size class is allowed to have 32-byte objs in it, for example). To know that you'd either have to have strict size classes, or you'd have to have object headers for specifying the start of an object. I agree that it's easy to add in a visitation pass, where you take the bitmap of live objects after marking and diff it with the currently existing one in order to signal that you might have a leak. So basically, I think we're like 99% in agreement.
- kragen 1y agoIt's always nice when the impact of collision of opposing opinions gives rise to the spark of mutual understanding rather than merely inflaming base emotions. Typically bitmap-based allocators don't actually allow a 16-byte size class to have 32-byte objects in it, but I haven't looked at FUGC to see if that's true of it.
- torginus 1y agoI toyed with the idea of allowing this, in bitmaps, it's pretty easy and efficient to find contiguous areas with bit twiddling hacks, for example //assume free map is the bitmap where 1 means free uint32_t free_map; uint32_t free_map_2 = (free_map & (free_map >> 1)); // so on and so forth I haven't really done anything like this yet, it has certain disadvantages, but you can pack multiple size classes into the same bitmap, you do a bit more work during alloc and resolving interior pointers is a bit more costly (if you have those), in exchange for having less size classes.
- thomasmg 1y ago> there are as many newly available address ranges as dead objects Well, when using a bitmap (as they seem to do in the article), then multiple subsequent dead objects are considered to be in the same range, because multiple subsequent bits in the bitmap have the value zero. There is no need to visit each zero bit in the bitmap separately.
- thomasmg 1y agoIf you want to use a standard malloc / free implementation (dlmalloc etc.) then dead object need to be known, yes. But the malloc library could be fully integrated into the GC mechanism. In this case, there is no need. That's probably much easier, and faster, because the malloc can be simplified to bumping a pointer.
- kragen 1y agoThat works if you use a copying garbage collector, but not a non-moving collector like FUGC.
- thomasmg 1y agoOK, I did not read the source code of the FUGC, but the article mentions "FUGC relies on a sweeping algorithm based on bitvector SIMD." So, assuming there is just one bit per block of memory, then there is no need to visit the memory of the dead objects in the sweep phase. The bit of the dead object is zero, and so that memory block is considered free and available for reallocation. There is no need to visit the free block.
- kragen 1y agoIt's true that it doesn't dirty up your dcache, but it's "visiting" enough that it wouldn't "need a lot more special support if it wanted to report the dead objects," which is the context of the discussion here.
- tomp 1y agoA non-moving GC must visit dead objects.
- writebetterc 1y agoI forgot that this GC is non-moving (I'm not used to that assumption, and it was a bit of a quick comment). I do find the statement dubious still, do you mind clearing it up for me? Given a page { void* addr; size_t size; size_t alignment; BitMap used; } where used's size in bits is page.size / page.alignment, surely we only need to visit the used bitmap for marking a memory slot as free?
- pizlonator 1y agoNot quite. FUGC used a bit vector SIMD sweep using a bit vector on the side so it doesn’t visit the dead objects at all in the sense that it doesn’t touch their contents. And it only visits them in the sense that a single instruction deals with many dead or alive objects at once.