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
(manual memory management system calls in STS),
I spent considerable time tracking down bugs
in the heap defragmentation code.
Note that both
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.
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!
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:
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.