gopherwood

Go maps are not thread safe.

You can implement maps with binary trees.

Binary trees are pretty.

Thread safe trees are hard to implement effeciently (because you need to write-lock sections of the tree and other tricks).

...

Do not communicate by sharing memory; instead, share memory by communicating.

What if every tree node was handled by a goroutine?

Bang! Gopherwood. (some trees are made of wood)

Dialogue

You: OMG. That doesn't scale.

Me: very probably. But goroutines are cheap so this thing should behave ok for small Ns.

You: is it fast?

Me: don't know yet. but I hope so because there are no locks.. but maybe a large number of goroutines running may slow things.

Cool tricks

1

Its common on textbook binary tree implemantations to define a node like

type Node struct {
  key string
  left *Node
  right *Node
}

Gopherwood does nothing of this!

Data is stored on local variables "inside" the goroutine.

By data I mean the "key" and channels. Yep. No pointers to other nodes. The goroutine saves 4 channels: leftTo, leftFro, rightTo, rightFro.

These are used to send messages to and fro.

2

When doing a change to a node like adding a key code normally looks like

func (v *Tree) Add(n *Node, key string) {
  if n.key > key {
    if n.right == nil {
      n.right = &Node{key: key}
    } else {
      v.Add(n.right, key)
    }
  } else {
    if n.left == nil {
      n.left = &Node{key: key}
    } else {
      v.Add(n.left, key)
    }
  }
}

But that's not so DRY. Pointers to the rescue. Pointers to channels on gopherwood:

        sideTo := &rightTo
        sideFro := &rightFro
        if key > newKey {
          sideTo = &leftTo
          sideFro = &leftFro
        } else if key == newKey {
          continue
        }

        if *sideTo == nil {
          *sideTo, *sideFro = createNode(newKey)
        } else {
          *sideTo <- "add"
          *sideTo <- newKey
        }

Benchmarks

Comparing Gopherwood with a textbook implementation of binary tree. Adding N random keys with one goroutine.

go test -bench=.
PASS
BenchmarkGopherwoodAdd-8       10000        395670 ns/op
BenchmarkGotreeAdd-8           10000        344732 ns/op
ok      github.com/marcelcorso/gopherwood   8.073s

TODO

• rm nodes
• rebalance the tree
• informal benchmark