What do you get when you mix threads and red black trees?

I was reading through Robert Sedgewick's 2008 paper on left leaning red black trees last week, and I had a sudden flash of inspiration. Of course, the flash of inspiration had nothing to do with my current project, so I was going to set it aside. Unfortunately I mentioned it to Rob, who convinced me I should actually implement it. Sometimes I wonder what happens to my weekends...

This post is pretty tech heavy and I am going to assume people reading this know a binary search tree is, and have heard of a red black tree. If you haven't this may be pretty harsh read.

Anyway, I was thinking to myself about how when would implement LLRB trees in Lisp. When I looked at must of the implementations out there they used commands that broke referential transparency, so I spent a bit of time thinking about how to implement the trees using immutable objects, and I came to a realization, a copy on write LLRB is a substantially more powerful data structure that would solve a lot of problems. I just had to implement one.

Consider the below red black tree:

In the above image the top number in each node is the nodes key, the bottom number is a reference count for how many other nodes point to that node. So long as the root node is held it will stabilize the entire subtree of nodes underneath it, and since the structure is immutable it is safe to walk through them from multiple threads without taking locks so long as we know we hold a reference to the root node.

Now imagine we want to do an insert. Since we cannot mutate the objects since other threads may be walking around in them, we instead figure out what changes would need to happen to the tree during the insert, and clone the appropriate nodes, creating an alternate root for the tree:

You will note that most of the nodes remain exactly the same as before, they are the same color, have the same value, and the same children. The new root node keeps the entire left subtree, but it does have to increase the reference count on the 2 node. Similiar relations happen through out the whole tree. Once we complete building this new root we can substitute it for the old root atomically (it actually requires a lock to bump the ref on the extant root node because of some arcane issues with atomic CPU operations), and all new accesses will go through the old tree. Once all extant users of the old tree release their references to the old root it is deallocated and cascades down the releases, leaving us with the final, updated tree:

Okay, so we have this fancy new data structure, so lets do something fun with it:

#include <pthread.h>
#include <libkern/OSAtomic.h>

#import <Foundation/Foundation.h>
#import "LGTSMutableDictionary.h"

LGTSMutableDictionary *dict = nil;

void *dumper(__unused void *unused) {
  while(1) {
    NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];
    uint32_t x = rand();
    [dict setObject:[NSNumber numberWithInteger:x] forKey:[NSNumber numberWithInteger:x]];
    [pool drain];
  }
}

void *sweeper(__unused void *unused) {
  while(1) {
    NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];

    for (id key in dict) {
      [dict removeObjectForKey:key];
    }
    [pool drain];
  }
}

int main(int argc, const char * argv[]) {
  NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];
  dict = [[LGTSMutableDictionary alloc] init];
  pthread_t dumper_thread;
  pthread_t sweeper_thread;

  (void)pthread_create(&dumper_thread, (const pthread_attr_t *)NULL, &dumper, (void *)NULL);
  (void)pthread_create(&sweeper_thread, (const pthread_attr_t *)NULL, &sweeper, (void *)NULL);
  [pool drain];
  sleep(120);

  return 0;
}

Conventional wisdom says the above code is really, really bad.

1. We have a thread mutating collection while another is reading it
2. That mutation going on while we are in the middle of a foreach style enumeration
3. And we are mutating the underlying collection inside of the iterator, that isn't safe even single thread

Guess what, LGTSMutableDictionary handles all of those things correctly, it just works, and it is based on the data structure above. So let me try to explain what is going on. The way the thread safety works should be pretty obvious, it does mutations as described above, then swaps the root node of the tree in that instance of LGTSMutableDictionary. If multiple conflicting mutations happen whichever one is committed first happens and the other are rolled back and then redone against the new tree.

The mutation safe iterators are possible because they take advantage of the copy on write nature of the data structure. When an LGTSEnumerator is created it stashes a reference to the root node of the tree it was created against. That means so long as it uses that root node it has a stable view of the data set, no matter what mutations are happening. Once the collector is released it drops it reference, and which point that view of the world disappears, but in the mean time all the changes it was making have been live to all new accessors of the data structure. That is also why we can safely remove elements from inside the for loop itself.

So, here are some of the other facts:

1. It supports NSFastEnumertion, but because of some limitations calling break inside the loop can cause a leak. As a work around you can create a keyEnumerator and pass that into the for loop.
2. Lookups are pretty fast, and on MP systems it handily beats locking and looking up things a hot NSMutableDictionary
3. Inserts are about 10x slower than NSMutableDictionary on a single thread, that number gets better the more CPUs and threads there are contesting the dictionary
4. -copy and -mutableCopy or O(1) operations, they just copy the root node of the tree
5. The code doesn't have unit tests, though it does have internal functions for validating trees
6. The code also can generate Graphviz commands to visually debug trees (the above pictures are generated from debug code)
7. The code has never been used for anything, it is a weekend hack job, so it does have bugs
8. There are some obvious cleanups and refactors that should be done

9. I am not guaranteeing anything I put up at the moment is totally working, but I thought it was interesting enough that I should post it and see what people thing

10. It is up on my github if you want to take a look