Lessons Learned #3: Garbage Collection

10 Dec 2015

Now that I’ve completed substantial amounts of work on the STS V1.5 operating system for the Kestrel-3, I feel emboldened, perhaps foolishly, to document the lessons I’ve learned from the project. From today until Christmas, I’ll be posting at least one lesson learned from working on STS.

Today’s lesson is very brief: the value of garbage collection.

When implementing the filesystem dispatch mechanism in STS V1.5, I ran into a surprising number of double-free bugs. Individually, none were too difficult to debug and fix; but, collectively, it wasted a significant amount of time. Fixing one bug often uncovered another.

In a seemingly unrelated area of experience, during the implementation of getmem and fremem (manual memory management system calls in STS), I spent considerable time tracking down bugs in the heap defragmentation code. Note that both getmem and fremem incrementally defragment free chunks of memory.

Considering I spend maybe four hours a week on Kestrel work, I’m not happy with the level of debugging effort the filesystem required. If I could automate memory management all-together, that would greatly simplify the software using the memory allocator, while simultaneously simplifying the implementation of the allocator as well. Less code means fewer bugs, and that means more time to spend with my wife.

Lesson Learned

If your project deals with a potentially complex web of related entities, you should consider using garbage collection for those entities. Even if nothing else in your project relies on GC, you can at least be confident that your web of entities will never have stray pointers which can be double-freed.

In particular, I recommend a Cheney-style collector. It’s a semi-space, compacting collector which should be plenty sufficient for nearly anything you throw at it. It’s also pretty trivial to write from scratch. My experiments with this collector suggests you can implement one in only half the amount of code needed to write a manual memory manager.

So, not only would it help eliminate the possibility of screwing up your entity relationships, but it actually uses less code in the process.

The only two disadvantages I can think of are that a naive implementation requires double the amount of RAM you expect to maximally allocate, and that a naive implemention cannot gaurantee real-time performance. However, if you keep your pools small and focused, the total pool size(s) should be small enough to ameliorate these effects.

For example, with STS, I could maintain a managed memory pool just for the in-core filesystem layout, relying on manual memory management for other aspects of the system.

Besides, if you’re opening files by walking name by name in a mount hierarchy, you’ve already destroyed any hope for real-time performance anyway.

Alas, I don’t have time to expound on what a Cheney algorithm implementation looks like now; I will need to make a separate blog article about that some day. If I forget, someone remind me!


Samuel A. Falvo II
Twitter: @SamuelAFalvoII
Google+: +Samuel A. Falvo II

About the Author

Software engineer by day. Amateur computer engineer by night. Founded the Kestrel Computer Project as a proof-of-concept back in 2007, with the Kestrel-1 computer built around the 65816 CPU. Since then, he's evolved the design to use a simple stack-architecture CPU with the Kestrel-2, and is now in the process of refining the design once more with a 64-bit RISC-V compatible engine in the Kestrel-3.

Samuel is or was:

  • a Forth, Oberon, J, and Go enthusiast.
  • an amateur radio operator (KC5TJA/6).
  • an amateur photographer.
  • an intermittent amateur astronomer, astrophotographer.
  • a student of two martial arts (don't worry; he's still rather poor at them, so you're still safe around him. Or not, depending on your point of view).
  • a former semiconductor verification technician for the HIPP-II and HIPP-III line of Hifn, Inc. line-speed compression and encryption VLSI chips.
  • the co-founder of Armored Internet, a small yet well-respected Internet Service Provider in Carlsbad, CA that, sadly, had to close its doors after three years.
  • the author of GCOM, an open-source, Microsoft COM-compatible component runtime environment. I also made a proprietary fork named Andromeda for Amiga, Inc.'s AmigaDE software stack. It eventually influenced AmigaOS 4.0's bizarre "interface" concept for exec libraries. (Please accept my apologies for this architectural blemish; I warned them not to use it in AmigaOS, but they didn't listen.)
  • the former maintainer and contributor to Gophercloud.
  • a contributor to Mimic.

Samuel seeks inspirations in many things, but is particularly moved by those things which moved or enabled him as a child. These include all things Commodore, Amiga, Atari, and all those old Radio-Electronics magazines he used to read as a kid.

Today, he lives in the San Francisco Bay Area with his beautiful wife, Steph, and four cats; 13, 6.5, Tabitha, and Panther.