41–50 of 174 posts
if you need code to understand garbage collection, there is walkthrough of garbage collector and C code at http://maplant.com/gc.html is really helpful. I tweaked it to work on amd64 and started adding register scanning based on what eatonphil's discord people told me to do. https://github.com/samsquire/garbage-collector It's not fit for any purpose but more of a learning exercise.
Earlier quoted context omitted.
Bob Nystrom (of Game Programming Patterns , Crafting Interpreters , and dartfmt fame) also wrote a tutorial implementation[1], of a precise tracing GC as opposed to a conservative one. Regarding register scanning in a conservative GC, Andreas Kling has made (or at least quoted) the amusing observation[2] that your C runtime already has a primitive to dump all callee-save registers to memory: setjmp(). So all you have…
Implementations are unfortunately allowed to do whatever they want to that jmp_buf, they could xor the contents for all you know. Hopefully no implementation does something silly like that.
Who would usually need this book?
One was for an in memory cache of data relationships. Another was to clean up soft references with an RDF graph. Neither were, nor needed to be, particularly sophisticated.
The cache was a compacting collector, the RDF one was mostly a “connectedness” test, pruning those nodes fallen from the graph.
Recall that malloc has a simple garbage collector for its free space, and arguably the level of sophistication that ranks a modern malloc implementation is how it manages its free space.
In the end detritus must be identified and resources reclaimed. So you see how GC like systems can occur in divergent areas of work.
On a related note, I found ART's implementation of Concurrent copying and compaction GC to be pretty novel. Here's a nice write up detailing how handling page faults in userspace come in handy to accomplish that: https://www.tdcommons.org/cgi/viewcontent.cgi?article=4751&c... (pdf) / https://web.archive.org/web/20230216233459/https://www.tdcom... For context, here's a brief overview of the evolution of the Android Ru…
Using page faults (and/or page protection) to perform compaction instead of barriers is a pretty old technique (see the 1988 paper by Appel, Ellis, and Li [1]; see also the Compressor by Kermany and Petrank [2]). But handling page faults were very expensive (at least on Linux) until the addition of userfaultfd recently.
[1]: https://dl.acm.org/doi/10.1145/960116.53992 [2]: https://dl.acm.org/doi/10.1145/1133255.1134023
Earlier quoted context omitted.
Rust also uses reference counting, probably the worst sort of garbage collection.
The increment/decrement calls only occur on an explicit call to .clone(). No .clone(), no increment/decrement. You won't see many clones in rust code.
Also it'd be nice if the reference counts were stored separately from the objects. Storing them alongside the object being tracked is a classic mistake made by reference count implementations (it spreads the writes over a large number of cache lines). I was actually surprised that Rust doesn't get this right.
Another issue with manual memory management is that you can't compact the heap.
Rust has left the building
Rust also uses reference counting, probably the worst sort of garbage collection.
I feel the need for garbage collection is a language design mis-feature. That is to say, producing garbage is a language design-mis-feature. To quote Bjarne Stroustrup: > I don't like garbage. I don't like littering. My ideal is to eliminate the > need for a garbage collector by not producing any garbage. That is now > possible. and it's indeed possible. For example It's become pretty much a non-issue in modern C++:…
That said I much prefer deterministic resource cleanup even in a janky language like C++ over a tracing GC.
What I really want out of a garbage collector is a "Collect" function with a deadline. Pick a max time it's allowed to run before stopping and returning to the program.
What I really want out of a garbage collector is a "Collect" function with a deadline. Pick a max time it's allowed to run before stopping and returning to the program.
The magic trick is to intentionally collect as often as reasonably possible (i.e. at batch/frame/tick processing boundaries) and avoid using sophisticated GC schemes that involve multiple threads or asynchrony.
Oh, and obviously you need to minimize allocations throughout or it won't matter.