Hacker News Reader

Comment by amatus | Hacker News Reader

This would fail badly on a http://en.wikipedia.org/wiki/XOR_linked_list

You really shouldn't be using a XOR linked list anyway. It has a lot of disadvantages and none of them weigh up to the only advantage of a lower memory footprint per list item.

The point is that this garbage collector is unsound. It may collect memory that is still in use. That's bad.

To be clearer: safety is no longer compositional in this system. To safely use the Boehm garbage collector, it's not sufficient that my own code doesn't use "disguised" pointers: I have to verify that my libraries don't either. That's impractical and contrary to good software engineering at best, impossible at worst.

No, you have to verify that your libraries don't keep disguised pointers to objects you allocated via the GC, that you don't yourself keep pointers to. It's quite unusual in C to give a reference to an object to another piece of code then drop all the pointers to it that you hold, because the usual discipline is that the module that allocates an object frees it.

Not if you build the GC with --enable-redirect-malloc to use with existing libraries/code bases. Which should be fine because, after all, this is a "conservative" garbage collector. Right?

If RAM is precious, you shouldn't use GC anyway. It typically has 2x memory use overhead to reduce GC performance cost.

I don't see how it would be 2x: a minimal GC would just require an additional pointer per allocation (in the worst case) for the GC roots.

malloc() has overhead too, typically immediately before the pointer it returns there's data about the allocation, such as the size of the alloc, magic for detecting bad free()'s, etc (though I guess a simple slab allocator would just need a single bit for each allocation, plus a pointer per slab).

Reply on news.ycombinator.com