I’m surprised the hash for the detached marking was abandoned so quickly. Yes, the unordered set in standard c++ is slow. But that didn’t mean all set implementations are - there’s even a few sparse-bitmap-specific ones.
Was the whole idea dropped without further testing?
A contributor actually replaced the unordered_set with his own hash table, which was indeed faster. But it didn’t yet support resizing, and crashed on some test cases
Hash table resizing is problematic IMO, because it’s another parameter to tune. I’d like the GC to have as few parameters as possible
It also causes a pause of its own – you’re reinserting everything into the hash table.
But my question is: is there any benefit to the hash table?
The bitmap seems strictly better – the only potential downside is the 3 byte object ID in the common object header.
But our header is either going to be 4 bytes or 8 bytes – and I can’t see any way to fit it in 4. So those 3 bytes sort of come “for free”, since it has to be 8 bytes anyway.
Oh, I’m not advocating for hash tables. Just curious how the experiment went. Based on the post, it sounded like it was dropped very quickly, but it turns out the custom solution was attempted after all.
Did you have a look at MPS? I’m experimenting with it for my Oberon implementation and it has interesting features. Currently the generated C code just uses the Boehm GC, which works very well. I saw in your post that you considered it too, but I didn’t understand why you discarded it; I think it’s an elegant solution to the rooting problem.
It was used in some commercial products; if it works I consider using it instead of writing my own
similar work, by Henderson (2002)
Thanks for the references, I will have a look at them; I would rather like to avoid writing my own GC
Oh Boehm, the more I look at it, the less I like it
I remember we had a lot of crashes in one of the projects many years ago and these stopped when we removed the Boehm GC, but the reason could have been anything; I didn’t have problems in other projects, and also the C99 code generated with my Oberon+ compiler seems to work just fine with Boehm; and it runs on all platforms I’m interested in so far, both 32 and 64 bit; I’m even using it as a “drop-in” with no problems.
Yeah I definitely understand not wanting to write a GC
I think I started ours in late 2020, and I studied implementations and read about it for years before, and it’s STILL not done!
It’s not that much code, but somehow it’s challenging. The bugs are challenging.
The design tradeoffs are challenging.
On the other hand, GC is tightly intertwined with data structures, so there is a reason almost everybody does their own, and few “major implementations” use Boehm these days
If shells didn’t have some constraints like fork() friendliness, I would consider generating Go code or something. Go has a GC with 10+ years of professional work on it …
I’m surprised the hash for the detached marking was abandoned so quickly. Yes, the unordered set in standard c++ is slow. But that didn’t mean all set implementations are - there’s even a few sparse-bitmap-specific ones.
Was the whole idea dropped without further testing?
A contributor actually replaced the
unordered_setwith his own hash table, which was indeed faster. But it didn’t yet support resizing, and crashed on some test casesHash table resizing is problematic IMO, because it’s another parameter to tune. I’d like the GC to have as few parameters as possible
It also causes a pause of its own – you’re reinserting everything into the hash table.
But my question is: is there any benefit to the hash table?
The bitmap seems strictly better – the only potential downside is the 3 byte object ID in the common object header.
But our header is either going to be 4 bytes or 8 bytes – and I can’t see any way to fit it in 4. So those 3 bytes sort of come “for free”, since it has to be 8 bytes anyway.
Oh, I’m not advocating for hash tables. Just curious how the experiment went. Based on the post, it sounded like it was dropped very quickly, but it turns out the custom solution was attempted after all.
Did you have a look at MPS? I’m experimenting with it for my Oberon implementation and it has interesting features. Currently the generated C code just uses the Boehm GC, which works very well. I saw in your post that you considered it too, but I didn’t understand why you discarded it; I think it’s an elegant solution to the rooting problem.
People have mentioned MPS to me, but who uses it? I tend to lift techniques from “known” codebases.
FWIW, two Reddit users pointed out the most relevant / similar work, by Henderson (2002), and follow-ups by Vitek et-al
https://old.reddit.com/r/ProgrammingLanguages/comments/y93yvv/oil_0127_garbage_collector_problems/it9uv1h/
Accurate Garbage Collection in Uncooperative Environments
The idea is pretty simple – just associate a struct with each stack frame, and put the pointers there. It supports moving collection.
For non-moving collection, you can do something even simpler (which we are doing)
Oil is somewhat unique in that it has the
f(g(), h())problem, because it’s doing a very shallow translation from PythonOh Boehm, the more I look at it, the less I like it ! :-/ Added a FAQ here: https://github.com/oilshell/oil/wiki/FAQ:-Why-Not-Write-Oil-in-X%3F#why-not-use-boehm-gc
It was used in some commercial products; if it works I consider using it instead of writing my own
Thanks for the references, I will have a look at them; I would rather like to avoid writing my own GC
I remember we had a lot of crashes in one of the projects many years ago and these stopped when we removed the Boehm GC, but the reason could have been anything; I didn’t have problems in other projects, and also the C99 code generated with my Oberon+ compiler seems to work just fine with Boehm; and it runs on all platforms I’m interested in so far, both 32 and 64 bit; I’m even using it as a “drop-in” with no problems.
Yeah I definitely understand not wanting to write a GC
I think I started ours in late 2020, and I studied implementations and read about it for years before, and it’s STILL not done!
It’s not that much code, but somehow it’s challenging. The bugs are challenging.
The design tradeoffs are challenging.
On the other hand, GC is tightly intertwined with data structures, so there is a reason almost everybody does their own, and few “major implementations” use Boehm these days
If shells didn’t have some constraints like
fork()friendliness, I would consider generating Go code or something. Go has a GC with 10+ years of professional work on it …