Thread: Garbage Collection is not so complicated

  1. #1
    Registered User
    Join Date
    Oct 2007

    Cool 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:

    - 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?
    Last edited by Nalpdii; 10-07-2007 at 12:12 PM.

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    New Zealand
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Oct 2007


    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. garbage collection enabled c++
    By manav in forum C++ Programming
    Replies: 42
    Last Post: 02-15-2008, 01:42 PM
  2. C++ Garbage Collection
    By vaibhav in forum C++ Programming
    Replies: 1
    Last Post: 11-27-2005, 10:26 AM
  3. Garbage Collection
    By Orborde in forum C++ Programming
    Replies: 4
    Last Post: 05-10-2005, 11:18 PM
  4. SDL: Garbage collection (?) screwing me
    By Brian in forum Game Programming
    Replies: 4
    Last Post: 05-08-2005, 09:13 AM
  5. garbage collection
    By joed in forum C Programming
    Replies: 4
    Last Post: 04-01-2004, 01:47 PM