I was interested to learn more about garbage collection. The idea is not complex, but obviously writing a fast, portable implementation that deals with all the edge cases is a challenge.
However, I just wanted to try something simple - detecting when pointers are no longer directly on the stack is a good starting point, so I implemented that with a very basic mark and sweep algorithm.
This garbage collector will only scan the stack for allocated memory pointers. It isn't portable or efficient. However, I enjoyed writing the code and trying it out. Maybe I'll make something more complete in the future.
Limitations (Update)
Because this garbage collector is designed to be very simple, it has many limitations:
Assumes pointers on the stack will be aligned.
Doesn't consider global variables (including class/function static variables).
Only works with a single stack/thread.
Doesn't consider pointers in registers, or attempt to flush these to the stack before collecting.
The calculation of the stack is probably not portable.
Feel free to improve the code and send suggestions. Ideally, I want to keep it as easy to understand as possible.
Interesting post. I started writing some sample precise garbage collectors at: https://github.com/ioddly/gc-zoo. Tracking roots is kind of a pain compared to just scanning the stack but ultimately worth the effort, in my opinion.
@Kostya It works by getting the address of the local variable on the stack. We make the assumption that this is allocated on the stack at line #101. By writing &top which is effectively &this, we are taking the address of the top of the stack. It is a bit of a hack but it works fine for demonstration purposes - and I’ve also (surprisingly) seen this type of construct in non-trivial garbage collection implementations.
Leave a comment
Please note, comments must be formatted using Markdown. Links can be enclosed in angle brackets, e.g. <www.codeotaku.com>.
Comments
Interesting post. I started writing some sample precise garbage collectors at: https://github.com/ioddly/gc-zoo. Tracking roots is kind of a pain compared to just scanning the stack but ultimately worth the effort, in my opinion.
On what OS/arch did you test it on? It crashes on my school computer (Win XP). I haven’t tested it yet on my home machine which runs Linux.
Also, I don’t really understand how
works. I think it has something to do with crashing the computer ;)
@Kostya It works by getting the address of the local variable on the stack. We make the assumption that
this
is allocated on the stack at line #101. By writing&top
which is effectively&this
, we are taking the address of the top of the stack. It is a bit of a hack but it works fine for demonstration purposes - and I’ve also (surprisingly) seen this type of construct in non-trivial garbage collection implementations.Leave a comment
Please note, comments must be formatted using Markdown. Links can be enclosed in angle brackets, e.g.
<www.codeotaku.com>
.