Garbage Collection is not so complicated

[Nalpdii]

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:

- 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?

[iMalc]

That kind of thing works best when you're actually writing an interpreter to a higher level language. In such a case the higher level language has no way of directly allocating memory except through objects that derive from your garbage-collectable type.
In C it wont work so well with other code because any of that code might make its own calls to malloc etc. Works fine if you don't have any such code though. I imagine it is much like what goes on under the hood with VB versions prior to VB6.

Now a "non-intrusive" garbage collector, as is used in some languages e.g. 'D' would be somewhat harder to write.

[Nalpdii]

Yes, you are right. Someone said that Lisp is "reinvented" every time a very dynamic system is being developed.

I just was very surprised how easy garbage collection was given the prerequisites. Now I can boast to my boss that I implemented garbage collection in C. Cool.