Six Degrees of Bacon!

This programming assignment, Six Degrees of  Bacon, by Steve Hodges has inspired me for the last two weeks. So on my first day off (yes, really) I have forgone food and a shower to make this homage.

The code is on GitHub: https://github.com/mike-matera/Six-Degrees

The Candle is Here!

It's Here

Setup

It's a fun day when you receive the first copy of a new circuit board. What did you forget to order? Are all the parts right? No. They never are. So here's what I missed:

1. Forgot to order my 3.3v regulators 
2. Forgot to order my 22k resistors
3. Ordered the level translator in the TSSOP instead of the SOIC package

There's a little silk screen error that's different between my gerbers and what the fab made. It cutoff the name of my website! Oh no. I'm getting everything ready for assembly. Now I just have to figure out how I'm going to use the wireless connectivity. 

Candle Controller

My prototype digital candle looked really good. The prototype used a separate power board wired to the Teensy3.0. That was cost effective but cost a lot of labor and delicate soldering to complete. This new board swallows the Teensy and incorporates the power supply. Better still it has a slot to swallow an XBee. That means this board will be able to communicate with the outside world. I'm not sure what I'm going to do with that just yet. I'll think of something.

Benchmarks

I got Cznic's code to work with very little trouble. I spent much more time thinking about how to make benchmark results comparable. The issues I considered are:

1. The trees must be of the same order (I used 128)
2. The trees must use the same key type (I used uint64)
3. The trees must be pre-filled with a large number of elements

Let me take a moment to explain #3. The benchmarking engine in Go works by calling your code with an iteration count. It times your code and then divides the time by the count to determine the number of nanoseconds per iteration. It starts with a small iteration count and increases the value until the sample is statistically valid. This has a poor property for comparing b-trees: The more elements in the tree the slower most operations will proceed. I can't control the iteration counts, instead I pre-filled the trees with 4 million elements. Why 4 million elements? Because inserting another million elements is not likely to change depth of the tree. 

The results of the benchmark:

BenchmarkRandomPut  200000      11836 ns/op
BenchmarkCznicRandomPut   1000000       1556 ns/op
BenchmarkRandomGet 5000000        652 ns/op
BenchmarkCznicRandomGet   2000000        797 ns/op
BenchmarkRandomDelete   200000      12581 ns/op
BenchmarkCznicRandomDelete 1000000 1228 ns/op

There's clearly a severe penalty for the Load() and Store() operations making my implementation an order of magnitude slower for operations that alter the tree. The good news is that my fetch implementation is somewhat faster. Since the expected mix of operations on a b-tree heavily favors lookups I believe that this offsets my poor update performance somewhat. 

How do I know that Load() and Store() eat up a lot of time? Go has a built-in profiling tool. Here's how it works. First you add some profiling code to a test harness. This is what I did:

file, _ := os.Create("insertions.out")

pprof.StartCPUProfile(file)

for i:=0; i<5000000; i++ {

tree.Put(uint64(src.Int63()), i)

}

pprof.StopCPUProfile()

You can then open your profile result (insertions.out) like this:

$ go tool pprof bin/main insertions.out

Welcome to pprof!  For help, type 'help'.

(pprof) 

In this case "bin/main" is the name of my executable. Much more information on how to use Go's pprof can be found here. The first command you're likely to use is the "top" command which shows you your top 10 CPU users. 

(pprof) top

Total: 5291 samples

    1289  24.4%  24.4%     2563  48.4% github.com/mike-matera/Go/btree.(*SimpleNode).Store

    1069  20.2%  44.6%     1069  20.2% github.com/mike-matera/Go/btree.(*SimpleNode).Load

     272   5.1%  49.7%      285   5.4% github.com/mike-matera/Go/btree.(*SimpleNode).Find

     240   4.5%  54.2%      809  15.3% runtime.assertE2T

     233   4.4%  58.6%      233   4.4% runtime.memcopy64

     209   4.0%  62.6%      584  11.0% assertE2Tret

     200   3.8%  66.4%      433   8.2% copyout

     196   3.7%  70.1%      344   6.5% sweepspan

     195   3.7%  73.8%      195   3.7% flushptrbuf

     141   2.7%  76.4%      344   6.5% scanblock

You can see that the top CPU hogs were Store() and Load(). The right most percentage is the percent of samples where those functions were on the call stack. A whopping 68.6% of the time. The 'web' command creates a nice SVG image of the result. Below are the results of the loop above and a similar one that fetches values.

Insertions Profile

Fetches Profile

Working toward a more generic implementation

The purpose of this project is to help me understand effective patterns in Go. It's been a very fun journey. After I completed the first B-tree implementation I looked around for existing implementations that I could compare it to. I found these two:

• https://github.com/cznic/b/blob/master/btree.go
• https://bitbucket.org/santucco/btree

cznic's is an in-memory implementation that appears to be a part of an SQL project in Go. A very nice piece of work. cznic's approach to polymorphism is to search/replace in the file to create a specialization --Just like C++ used to do-- which isn't very satisfying to me. He/she seems to have done extensive benchmarking on the code. 

santucco's implementation is an on-disk implementation, which really got me thinking. The B-tree is meant to be an on-disk index with its nodes sized to match disk blocks. What would it take to make a tree that was suitably generic so that client code could choose an in-memory or on-disk implementation? 

After a lot of thought and several trial implementations I came up with these design parameters:

1. Generic code should implement as much of the algorithm as possible. Type-specific code should not be hard to write and you should not have to re-validate the algorithm for each specific type.
2. Allocation and disposal of node memory must be done in client code. This gives client code the flexibility to use any type of backing storage. 

Over the next month (that I have off!!) I'll compare all three implementations more completely. The latest commit can be found on GitHub.

Delete works

The delete operation would fail if the key was located outside of a leaf node (i.e. it was being used as a median.) This was the broken code:

        if pos > 0 && node.Values[pos-1].Key == index {
                // Found the delete value
                if node.Nodes != nil {
                        // Lost median, will balance
                        tree.balance(node, pos)
                }else{

The problem is that when I lost a median I just rebalanced two subtrees, resulting in no change. What was I thinking?

if pos > 0 && node.Values[pos-1].Key == index {
// Found the delete value
tree.Stats.Size--
if node.Nodes != nil {
// Lost median, must borrow
var remaining int
node.Values[pos-1], remaining =                                                             tree.borrow(node.Nodes[pos-1])
if remaining < (tree.N/2) {
tree.balance(node, pos-1)
}

The new code implements the borrow() routine. That operates similar to the del() routine except that it always descends down the right-most tree or value, returning the largest value in the subtree.

Better testing reveals broken delete...

The latest commit on GitHub has an updated test implementation. It's a big improvement over what I had before because it uses Go's map type as a reference implementation. First I created an interface "TreeLike" that defines the basic operations on a tree:

type Treelike interface {
Insert(uint64, interface{})
Fetch(uint64) interface{}
Delete(uint64)
Iterate() chan uint64
}

I know Iterate() is basically useless, it's still a work in progress. TreeLike is already implemented by Btree. Now I make a struct that implements checking. 

type BtreeTest struct {

test *testing.T

tree Treelike 

reference map[uint64] interface{}

}

The class contains a test so that I can testing.T.Fail() when a problem is detected. The TreeLike is kept in sync with the map[] by implementing methods that operate on both structures. This is the implementation of Insert():

func (self *BtreeTest) Insert(key uint64, value interface{}) {

self.reference[key] = value

self.tree.Insert(key, value)

}

The Insert() function does no checking. The Delete() function does:

func (self *BtreeTest) Delete(key uint64) {

delete(self.reference, key)

self.tree.Delete(key)

verify := self.tree.Fetch(key) 

if (verify != nil) {

self.test.Fail()

}

}

The struct BtreeTest itself implements TreeLike so any code that requires TreeLike can be easily instrumented to be testing code. Thanks to that I found a serious bug in Delete(). My delete function fails to delete values that are not stored in leaf nodes. I'm fixing it.