Hacker News Reader

Comment by writebetterc | Hacker News Reader

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.

View on HN

It'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.

I 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.

Sure, to find contiguous chunks of 6 slots within a single word, you can do

    t &= t << 1;
    t &= t << 2;
    t &= t << 2;

and that sort of thing is pretty appealing, but you lose the ability to know what size an object is just by looking at an address, and it's still a lot slower than scanning for an open slot in a page of 5× bigger objects.

Should I assume from your use of uint32_t that you're targeting embedded ARM microcontrollers?

FUGC is size segregated. 16 byte size class will only have 16 byte objects.

A bunch of other optimizations fall out from doing that

Reply on news.ycombinator.com