Some Prehistory

So, what’s the story behind the Slab List? How did it come to be, and why does it have such a strange name? In 2012, I wanted to make a NoSQL database, because that was the trendy thing back then. In particular, I wanted it to be an in-memory database, so that I wouldn’t have to care about swapping. I knew that I’d need to store data in sorted order and in unsorted order. I ran some tests, and used an AVL tree for the former and a doubly-linked list for the latter. The tests were run on a laptop with a mere 4GB of RAM. Simply put, I couldn’t store as much data as I thought I should be able to.

Sure, servers have lots of RAM, but I figured that more and more people — including myself — would be hosting their apps’ data and computing on it in the cloud. The cost of a VM on AWS or Joyent Public Cloud is linearly correlated with the VM’s RAM. So minimizing RAM-usage was a top priority. Also important were efficient insertion and removal into both sorted and unsorted sets. The former being much harder than the latter.

As is my habit, when approaching a new problem, I ignore all recent research on the topic, and try to derive a solution from the established principles that I had already mastered. This, I believe, forces one to be original, and that originality helps one find new ways of doing things. Even if the new way is not superior, knowing that it is possible to do something in another way, could send one down an unexplored path where even more interesting and unsolved problems lurk. As an obvious example, setting out to make a new data base took me down the path of making a new data structure.

I spent a while contemplating how to attack this problem. As it turned out, I had implemented a Slab Allocator as a final project for a class and the notion of the slab seemed like a good launch-point so I went with it. And so the name: the slab list. In spite of its ambiguity, I kept it because it is a well-deserved homage to an engineer greater than myself — and because I think it sounds cool.

There were many ideas in the initial stages. For example, instead of shifting elements up or down a slab when the slab was modified, I intended for there to be a bitmap that indicated where the gaps in the slab were. This idea didn’t make it in, because that bitmap costs precious RAM. There were so many ideas and paths to consider, that I had to keep a private journal on the development of the Slab List in order to keep track of them. It is essentially a record of all the possible paths the project could have taken, and can still take — a deliberation with myself on whether or not some new trick or hack or rewrite is a blind alley. Sometimes one never knows until they try, and believe me I’ve tried repeatedly.

I spent two and a half months of summer writing the slab list library. The first release was crude — it had met the goal of memory efficiency, but the performance on sorted sets was lacking. It was 1.5x slower than a highly optimized AVL tree. Though I was relieved that I found a way to make it logarithmic, by realizing that having multiple levels of slabs would allow binary search at each level.

It also took a while to build up an infrastructure for validating the internal state of the slab list. Unit tests simply didn’t cut it as they merely indicated the presence of a problem, but not its origin. That solution was truly a eureka moment — I ended up with a test-suite like none I’ve ever seen. It made off-color use of DTrace, to change the value of a register from 0 to 1 (from False to True), which in turn made the library take a series of branches into code that would sanity-test the slab list, without stopping the execution of the code. That testing code totally saved my butt, and wouldn’t have been possible without DTrace — I can think of no better substitute.

Speaking of DTrace, it was also instrumental in helping me figure out where to venture next in the hunt for performance bottlenecks. I’ve used it for the entire development of libslablist. Brendan Gregg’s flame-graphs, were also an important advance in visualizing the hot code-paths. I shudder to think where the Slab List would be today, two years later, had I been content with using a popular, good-enough operating system (who’s name rhymes with either Shmindows or Binux). Maybe I’d still be fighting last year’s battles.

And then came the benchmarks. The chore of collecting a dozen or so other logarithmic-time trees and lists, and wiring them all together so that very detailed data can be collected on how they perform for various operations, was excruciatingly boring. But it payed off, in that now there is a way of keeping score — and Slab Lists fare pretty well. I’ve also developed a new-found admiration for B-Trees, and Dr. Bayer and Mr. McCreight have earned my respect.

And even then, there was so much data that had to be compared. At first the structures were compared visually, in pairs, with simple Gnuplot scripts. But that produced hundreds of plots, for there were different kinds of insertion patterns. Then figuring out how to sensibly put all of that data on as few plots as possible (this time using R with ggplot), was itself a time-consuming exercise in trial-and-error. The generated new plots now look presentable and grokable. The initial version of this R code would take more the 40 minutes to run, though some shell-job hackery, awk-powered R-code generation brought it down to a mere 2 minutes.

The algorithm for implementing the slab list can be described as follows:

1: WRITE crippled / wrong code
2: COLLECT measurements and test-feedback
3: FIX crippled / wrong code
4: GOTO 1

In other words, instead of taking existing work and methodically extending it to suite my needs, I repeatedly — and luckily — stumbled onto some enhancement or nifty hack that could save the Slab List from being a total embarrassment. In short, it wasn’t an easy birth — it was painful and fraught with many complications, deficiencies, and abnormalities that had to be resolved with a surgeon’s knife. And I would do it all over again.