5 ms·

What I love about the Boehm collector is the hack that enables it to work in a language with no runtime typing like C. It literally guesses what's a pointer. In

What I love about the Boehm collector is the hack that enables it to work in a language with no runtime typing like C. It literally guesses what's a pointer. In C pointers are basically integers but they're unusual numbers, often quite large, and you know the entire set of valid numbers if you control malloc(). Surprisingly this worked even in 32 bit architectures.

chubot 3y ago
I don't see that this is something to "love", and what you describe doesn't capture the full extent of the approximation. What scared me off of Boehm GC is that there a bazillion config options -- e.g. it requires tuning and blacklisting to avoid memory leaks -- and probably even correctness because register scanning isn't portable. The codebase is large and a bit scary, and there are seemingly lots of ways to use it poorly. People kept saying it's "drop in", but that seems like a myth. At least personally it doesn't seem like the kind of thing I want to debug. The opinions on Boehm generally seem very split -- a bunch of bad stories resulting in ripping it out of the codebase, and also people who think it's surprisingly good, and codebases that have used it for a very long time. I think the Nix evaluator uses it and is carrying around patches, and Guile Scheme uses it. Though I think there is some desire to move away from it in both cases. But again people have used it for a very long time, which isn't nothing! --- e.g. https://www.hboehm.info/gc/gcdescr.html https://www.hboehm.info/gc/gcdescr.html Recent versions of the collector use an approximate best fit algorithm by keeping free lists for several large block sizes. The actual implementation of GC_allochblk is significantly complicated by black-listing issues (see below). ... The collector implements black-listing of pages, as described in Boehm, ``Space Efficient Conservative Collection'', PLDI '93, also available here. During the mark phase, the collector tracks ``near misses'', i.e. attempts to follow a ``pointer'' to just outside the garbage-collected heap, or to a currently unallocated page inside the heap. Pages that have been the targets of such near misses are likely to be the targets of misidentified ``pointers'' in the future. To minimize the future damage caused by such misidentifications they will be allocated only to small pointerfree objects. The collector understands two different kinds of black-listing. A page may be black listed for interior pointer references (GC_add_to_black_list_stack), if it was the target of a near miss from a location that requires interior pointer recognition, e.g. the stack, or the heap if GC_all_interior_pointers is set. In this case, we also avoid allocating large blocks that include this page.
- NelsonMinar 3y ago
  "love" in the sense of someone loving their snaggletooth mutt. What's remarkable to me is despite the obviously terrible idea at the core of it, it seems to work pretty well for some practical use. (IIRC it was at the core of GNU Java as well, and I could have sworn the earliest Sun JVMs used it.) I don't doubt it caused all sorts of problems too. It's just an interesting reminder that sometimes a really wacky hack can be pretty useful.
- matheusmoreira 3y ago
  > register scanning isn't portable Certainly not but it wasn't particularly hard to implement either, I managed to do it with some simple inline assembly. Here's my programming language's register spilling code: https://github.com/lone-lang/lone/blob/master/architecture/x86_64/include/lone/architecture/garbage_collector.c https://github.com/lone-lang/lone/blob/master/architecture/x... https://github.com/lone-lang/lone/blob/master/architecture/aarch64/include/lone/architecture/garbage_collector.c https://github.com/lone-lang/lone/blob/master/architecture/a...
matheusmoreira 3y ago
It walks the entire native stack and marks every pointer it finds! Handles pointers in registers by spilling them on the stack and just letting the stack scanner find them like all the others. It guesses pointers but in a way that makes false negatives impossible. I assume everything must be properly aligned to work. Interestingly, it uses jmpbuf to spill the registers. There's also a compiler builtin to get the current stack frame which can be used to obtain the stack root if called at the beginning of the program. Really neat, and educational.

chubot 3y ago

I don't see that this is something to "love", and what you describe doesn't capture the full extent of the approximation. What scared me off of Boehm GC is that there a bazillion config options -- e.g. it requires tuning and blacklisting to avoid memory leaks -- and probably even correctness because register scanning isn't portable. The codebase is large and a bit scary, and there are seemingly lots of ways to use it poorly. People kept saying it's "drop in", but that seems like a myth. At least personally it doesn't seem like the kind of thing I want to debug. The opinions on Boehm generally seem very split -- a bunch of bad stories resulting in ripping it out of the codebase, and also people who think it's surprisingly good, and codebases that have used it for a very long time. I think the Nix evaluator uses it and is carrying around patches, and Guile Scheme uses it. Though I think there is some desire to move away from it in both cases. But again people have used it for a very long time, which isn't nothing! --- e.g. https://www.hboehm.info/gc/gcdescr.html https://www.hboehm.info/gc/gcdescr.html Recent versions of the collector use an approximate best fit algorithm by keeping free lists for several large block sizes. The actual implementation of GC_allochblk is significantly complicated by black-listing issues (see below). ... The collector implements black-listing of pages, as described in Boehm, ``Space Efficient Conservative Collection'', PLDI '93, also available here. During the mark phase, the collector tracks ``near misses'', i.e. attempts to follow a ``pointer'' to just outside the garbage-collected heap, or to a currently unallocated page inside the heap. Pages that have been the targets of such near misses are likely to be the targets of misidentified ``pointers'' in the future. To minimize the future damage caused by such misidentifications they will be allocated only to small pointerfree objects. The collector understands two different kinds of black-listing. A page may be black listed for interior pointer references (GC_add_to_black_list_stack), if it was the target of a near miss from a location that requires interior pointer recognition, e.g. the stack, or the heap if GC_all_interior_pointers is set. In this case, we also avoid allocating large blocks that include this page.

NelsonMinar 3y ago
"love" in the sense of someone loving their snaggletooth mutt. What's remarkable to me is despite the obviously terrible idea at the core of it, it seems to work pretty well for some practical use. (IIRC it was at the core of GNU Java as well, and I could have sworn the earliest Sun JVMs used it.) I don't doubt it caused all sorts of problems too. It's just an interesting reminder that sometimes a really wacky hack can be pretty useful.
matheusmoreira 3y ago
> register scanning isn't portable Certainly not but it wasn't particularly hard to implement either, I managed to do it with some simple inline assembly. Here's my programming language's register spilling code: https://github.com/lone-lang/lone/blob/master/architecture/x86_64/include/lone/architecture/garbage_collector.c https://github.com/lone-lang/lone/blob/master/architecture/x... https://github.com/lone-lang/lone/blob/master/architecture/aarch64/include/lone/architecture/garbage_collector.c https://github.com/lone-lang/lone/blob/master/architecture/a...

matheusmoreira 3y ago

It walks the entire native stack and marks every pointer it finds! Handles pointers in registers by spilling them on the stack and just letting the stack scanner find them like all the others. It guesses pointers but in a way that makes false negatives impossible. I assume everything must be properly aligned to work. Interestingly, it uses jmpbuf to spill the registers. There's also a compiler builtin to get the current stack frame which can be used to obtain the stack root if called at the beginning of the program. Really neat, and educational.