The "Garbage Collection" chapter in the OP's recent book <i>Crafting Interpreters</i> goes into this in a bunch more detail (in the context of a language VM): <a href="https://craftinginterpreters.com/garbage-collection.html" rel="nofollow">https://craftinginterpreters.com/garbage-collection.html</a> -- so well written, both this and the 2013 blog post.
Like his other work, Crafting Interpreters, this is so much more approachable, understandable, and actionable than any academic textbooks or courses on the equivalent subjects are. It sometimes amazes me that one can learn anything at all without material like this.
Would it make sense to have the VM to do partial mark and sweeps instead?<p>Let's say the references are a lot. Like tens of millions order of magnitude.<p>Would it make sense to GC sweeping it in chunks?
Something else from the author that I recently stumbled upon: his LISP2 Mark Compact garbage collector [0].<p>I was in need of a simple garbage collector for a toy project of mine and settled on a copying collector based on Cheney's algorithm at first [1]. The author's mark compact code is so easy to read that I was able to grok it immediately and replace my original GC without trouble and save half my memory.<p>[0] <a href="https://github.com/munificent/lisp2-gc" rel="nofollow">https://github.com/munificent/lisp2-gc</a>
[1] <a href="https://en.wikipedia.org/wiki/Cheney%27s_algorithm" rel="nofollow">https://en.wikipedia.org/wiki/Cheney%27s_algorithm</a>
Not its first thread though:<p><i>Baby’s First Garbage Collector (2013)</i> - <a href="https://news.ycombinator.com/item?id=21462190" rel="nofollow">https://news.ycombinator.com/item?id=21462190</a> - Nov 2019 (29 comments)<p><i>Baby's First Garbage Collector (2013)</i> - <a href="https://news.ycombinator.com/item?id=10794026" rel="nofollow">https://news.ycombinator.com/item?id=10794026</a> - Dec 2015 (17 comments)<p><i>Baby's First Garbage Collector</i> - <a href="https://news.ycombinator.com/item?id=6871202" rel="nofollow">https://news.ycombinator.com/item?id=6871202</a> - Dec 2013 (84 comments)
My favorite article from that blog, I always cite it whenever I see someone asking about garbage collectors. The other posts about programming language design and implementation are really great too, they made a huge impression on me.
For a long time I had an idea I thought was great - a lock free garbage collector that could be run on its own core to achieve zero latency. I've got 32 cores busy doing nothing and thought I could throw hardware at the problem and get garbage collection for free.<p>A bunch of people much smarter than me all chimed in on how this was a terrible idea. They argued it would destroy the cache and result in worse performance than a traditional garbage collector. Locality matters, apparently. I still sometimes think of this idea but it doesn't fit very well into the actual hardware.
This motivated me to crack open Crafting Interpreters, which has been sitting on my shelf for a couple of months.<p>It is truly a wonderful book, and a much needed (IMHO) addition to the literature. I have a bunch of the classic language books and this is such a good addition, and way easier and more fun to read! If you've been on the fence about ordering, do it!
Nice read. BTW, is there any reason to implement sweep with an Object** instead of just an Object*?<p>edit: Like this, <a href="https://gist.github.com/Dietr1ch/a636578fe9f06faa5d46e1b78aa7ba4e/revisions" rel="nofollow">https://gist.github.com/Dietr1ch/a636578fe9f06faa5d46e1b78aa...</a>
I want to know if Peter Norvig has written a First GC. I’m still just blown away by his sudoku solver. I thought I was good at paring accidental complexity from code…<p>I also want to know if Norvig has a biographer, and if not, why not?