Garbage Collection is not so complicated
DIY and if you start small you have a working solution in a day. That was my experience.
I am developing a very dynamic program. I have half a dozen "objects" (structs) containing each other. Memory management was a problem, of course. I prefer simplicity and linked my software with Boehm's garbage collector first. Works okay and code is much simpler. No "ownership" issues and remembering freeing things. :) So far, so good. But could I not program garbage collection myself?
After some thinking I cooked up following simple scheme: :cool:
- The dynamic objects are stored in an union with a type tag and a mark bit
- Use double indirection for the objects
- Maintain an array of pointers to all objects
- When the array is full, start garbage collection, then enlarge the array, if neccessary
- Garbage collection is mark-and-sweep
- mark() knows how to iterate through the sub-objects recursively
- Start with marking the root(s)
- Then sweep: Free() all unmarked objects in array, then compact
- Other (not-so-dynamic) data is allocated and freed through malloc() and free()
I first thought that garbage collection is much more complicated. But after 8h of coding and 160 lines of code and 40 lines of header, I had a working garbage collection. Prerequisites for the objects:
- an union so all objects have the same interface for mark()
- type tags (or mark() cannot mark the sub-objects)
- mark bit (of course)
- double indirection (or don't compact the array after sweep)
If you have that for your objects, you get most basic garbage collection almost for free. Highly optimized garbage collection schemes can be implemented later as long as the basic scheme is fast enough.
What do you think?