Comment by kragen
5 months ago
In the general case there are as many newly available address ranges as dead objects, so that counts as visiting them in this context.
5 months ago
In the general case there are as many newly available address ranges as dead objects, so that counts as visiting them in this context.
I 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.
That'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
I 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.
4 replies →
It's not generational, because unlike Java, but like C or C++, programs aren't supposed to generate a lot of ephemeral objects while they run. I also wanted to keep things as simple as possible to have a chance of actually shipping something in my lifetime :D
2 replies →
> 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.