Friday, December 13, 2013

Baby's First Garbage Collector (journal.stuffwithstuff.com)

There’s a bunch of different ways you can implement the process of finding and reclaiming all of the unused objects, but the simplest and first algorithm ever invented for it is called “mark-sweep”. It was invented by John McCarthy, the man who invented Lisp and beards, so you implementing it now is like communing with one of the Elder Gods, but hopefully not in some Lovecraftian way that ends with you having your mind and retinas blasted clean. It works almost exactly like our definition of reachability:
  • Starting at the roots, traverse the entire object graph. Every time you reach an object, set a “mark” bit on it to true.
  • Once that’s done, find all of the objects whose mark bits are not set and delete them.
That’s it. Read more....