4 ms·
That book is an absolute treasure and you should be proud. At a personal level, this book contained so much that I had always wanted to know, from how hashmaps
by kerkeslager 2y ago
That book is an absolute treasure and you should be proud.
At a personal level, this book contained so much that I had always wanted to know, from how hashmaps work, to how to compile in a single pass. And I connected with your note on getting into writing languages partly due to a feeling of being less-than programmers who could create their own language.
One thing I wanted to share: I found a small design change to Clox that eliminates an entire class of hard-to-debug GC bugs.
Basically, the change is that garbage collection never occurs during the execution of an instruction.
Instead, garbage collection is an instruction which is never emitted by the compiler. When the heap size crosses the garbage collection threshold, we schedule a garbage collection, which will occur after the current instruction is done executing, and before the next instruction executes.
To implement this, in the Self-Adjusting Heap[1] section, we set a global variable (let's call it "resume pointer") to the next instruction, similar to the return pointer in a call frame. Then we set the instruction pointer to point to a global constant which contains only the garbage collection instruction.
The way this works: let's say the current instruction allocates something, and the allocation needs to trigger a GC. To trigger the GC, we set the resume pointer to the next instruction, and the instruction pointer to the global constant garbage collection instruction (let's call this GCGCI). When the current instruction completes, the VM goes to the instruction pointer to get the next instruction, and finds it pointing to the GCGCI. It then executes the garbage collection instruction, which runs the garbage collection. The final step of the garbage collection instruction is to set the instruction pointer to the resume pointer (similar to a return pointer) so that when the VM goes to execute the next instruction it resumes the execution of the user program right where it left off.
This adds a bit of performance overhead to garbage collection, but I would guess we more than get it back from the fact that it's no longer necessary to temporarily push objects onto the stack to prevent them from getting GCed mid-instruction. And this eliminates that entire class of GC bugs; code stability and programmer time are worth something!
An alternative implementation might observe that the resume pointer is basically a return pointer, so you could potentially store this on the call stack. I didn't really think through the pros and cons of this as it seemed like just adding a global resume pointer solved the problem more simply. However, one thing I was working on is making my interpreter multithreaded, and this means that most of the global variables used by the VM get stuffed into a "Thread" struct. Keeping the size of this thread struct low is a high priority because that memory usage is a limiting factor in the number of threads you can reasonably run simultaneously, so in this case moving the resume pointer onto the call stack starts to look like a bigger benefit.
[1] https://craftinginterpreters.com/garbage-collection.html#self-adjusting-heap https://craftinginterpreters.com/garbage-collection.html#sel...
- munificent 2y agoThis is a really really cool idea. Thank you for writing this up. Yes, that sounds like it would work fine to me. The only downside to keep in mind is that you will periods of time where you need to allocate more memory and have to do that first and then only free up memory in a GC after that allocation takes place. If you're very memory constrained or you need to allocate a lot, that could potentially be a problem. But if I'm totally honest, I'm not sure how big of a problem that is in practice. One of the really annoying things about garbage collectors is how little literature there is on real-world collection strategies. You can find plenty of papers on collection algorithms, but it's hard to find material on when a GC should run.
- kerkeslager 2y agoYeah, "When to schedule?" is a really good question. Have you ever contacted the authors of The Garbage Collection Handbook[1]? It seems like they intend that book to have the most breadth of knowledge about GC, and if there's anybody out there who has studied when to collect they might know who. [1] https://gchandbook.org/index.html https://gchandbook.org/index.html
- munificent 2y agoI haven't. That's a good idea. I'm pretty good at tracking down resources, but really bad at actually contacting humans.
- kerkeslager 2y agoAs a hobbyist freelancer with no access to resources like JSTOR, contacting the authors is often the only way I can obtain access to academic papers. It works great! Incidentally, that book might contain information on when to GC; I haven't actually finished it yet.
- nathan_douglas 2y agoThat's a really neat idea! I think I'll try to work that into my own Lox derivative :)