Writing My First Program in Golang

This post serves to confirm what the internets have been claiming for years. Go is really fast. At least relative to Python…which is pretty slow.

For me, the most difficult thing in learning a new language is to find something practical to do. Writing the next “Hello World” program isn’t very satisfactory, but making the leap to production code requires a reasonable degree of competence and knowledge of things like built in libraries. Compared to your language of choice, it’s a much more painstaking process. So I took an existing side project, trying to create purely functional data structures, and writing them in Go instead of Python.

The Problem

In my other post I certainly mentioned how cool and hip it was to write immutable data structures from scratch, but what I didn’t reveal was that Python was too slow to do anything practical. Even if we have a logarithmic run time complexity, that’s not very helpful if we have Log(n) * some very large factor K. Even with data sets in the tens of thousands, iterating over a datastructure could take seconds.

My initial train of thought, which still holds true, is that we could find practicality even with that degree of slowness because we could take advantage of the immutability aspect and do some abusive caching and avoid what would otherwise be costly database queries. The difference is that the program would be CPU bound instead of IO bound, and the super slow processing would still be possibly faster than an IO bound program. Sprinkle in some consistent hashing, a little bit of sharding, maybe some LRU cache action, a few mutexes here and there, and bam, I’ll be getting high fives in the office daily.

But. It would be much nicer if things simply…weren’t so slow. So this paired nicely with my current effort to learn Go, giving me a practical project with no dependencies.

The Results

Code samples are pasted below, but up front, Go was up to 10x faster than Python when we started increasing the data set to fairly high values. This exercise was done by implementing random access lists, where insertion is done in constant time, and updates and reads are done in logarithmic time. I measured just by time. For fun, one of my colleagues Tagir Magomedov also wrote the random access implementation in Scala to see how well it held up:

Insert Elements

Number of Elements Python Go Scala
10,000 0m0.057s 0m0.008s 0m0.361s
1,000,000 0m8.089s 0m0.164s 0m1.048s
10,000,000 1m33.492s 0m1.332s java.lang.OutOfMemoryError: GC overhead limit exceeded (meh, not going to take the effort to fix)

Insert Then Individually Retrieve Every Element

Number of Elements Python Go Scala
10,000 0m0.128s 0m0.010s 0m0.393s
100,000 0m1.413s 0m0.035s 0m0.394s
1,000,000 0m17.396s 0m0.311s 0m1.241s

The Code

We can compare the code below for reference:

Go

package main

import "fmt"


type Node struct {
    index int
    value int
    leftChild *Node
    rightChild *Node
    length int
}


func (n *Node) GetItem(index int) int {
    if index == n.index {
        return n.value
    }
    if index <= n.rightChild.index {
        return n.rightChild.GetItem(index)
    }
    return n.leftChild.GetItem(index)
}


func (n *Node) SetItem(index int, value int) *Node {
    switch {
    case index == n.index:
        return &Node{
            index,
            value,
            n.leftChild,
            n.rightChild,
            n.leftChild.Length() + n.rightChild.Length() + 1,
        }
    case index <= n.rightChild.index:
        return &Node{
            index,
            value,
            n.leftChild,
            n.rightChild.SetItem(index, value),
            n.leftChild.Length() + n.rightChild.Length() + 1,
        }
    default:
        return &Node{
            index,
            value,
            n.leftChild.SetItem(index, value),
            n.rightChild,
            n.leftChild.Length() + n.rightChild.Length() + 1,
        }
    }

}

func (n *Node) Length() int {
    if n == nil {
        return 0
    }
    return n.length
}


type RandomAccessList struct {
    head *Node
    rightSibling *RandomAccessList
}

func (list *RandomAccessList) GetItem(index int) int {

    // TODO refactor
    rightIndex := -1
    if list.rightSibling.head != nil {
        rightIndex = list.rightSibling.head.index
    }
    if index > rightIndex {
        return list.head.GetItem(index)
    }
    return list.rightSibling.GetItem(index)
}

func (list *RandomAccessList) SetItem(index, value int) *RandomAccessList{
    if index > list.rightSibling.head.index {
        return &RandomAccessList{
            list.head.SetItem(index, value),
            list.rightSibling,
        }
    }
    return &RandomAccessList{
        list.head,
        list.rightSibling.SetItem(index, value),
    }
}

func (list *RandomAccessList) Append(value int) *RandomAccessList{
    if list.firstTwoTreesEqualHeight() {
        return &RandomAccessList{
            &Node{
                list.head.index + 1,
                value,
                list.head,
                list.rightSibling.head,
                list.head.Length() + list.rightSibling.head.Length() + 1,
            },
            list.rightSibling.rightSibling,
        }
    }

    // TODO refactor
    index := 0
    if list.head != nil {
        index = list.head.index + 1
    }

    return &RandomAccessList{
        &Node{
            index,
            value,
            nil,
            nil,
            1,
        },
        list,
    }
}

func (list *RandomAccessList) firstTwoTreesEqualHeight() bool {
    if list.head == nil {
        return false
    }
    return list.rightSibling.head.Length() == list.head.Length() && list.rightSibling.head.Length() > 0
}

func (list *RandomAccessList) Length() int {
    if list == nil {
        return 0
    }
    return list.head.Length() + list.rightSibling.Length()
}



func main() {
    list := &RandomAccessList{}

    for i := 0; i < 10000000; i++ {
        list = list.Append(i)
    }
    fmt.Printf("%v\n", list.GetItem(50000))
}

Python

class NullObject(object):

    def __init__(self):
        self.index = -1
        self.value = None

    @property
    def left_child(self):
        return NullObject()

    @property
    def right_child(self):
        return NullObject()

    @property
    def right_sibling(self):
        return NullObject()

    @property
    def head(self):
        return NullObject()

    def __len__(self):
        return 0

    def __setitem__(self, index, value):
        raise IndexError("Assignment index out of range")

    def __getitem__(self, index):
        raise IndexError("list index out of range")


class Node(object):

    def __init__(self,
                 index,
                 value,
                 left_child=NullObject(),
                 right_child=NullObject()):

        self.index = index
        self.left_child = left_child
        self.right_child = right_child
        self.value = value
        self._length = len(self.left_child) + len(self.right_child) + 1

    def __getitem__(self, index):
        if index == self.index:
            return self.value
        if index <= self.right_child.index:
            return self.right_child[index]
        return self.left_child[index]

    def __setitem__(self, index, value):
        if index == self.index:
            return Node(
                index,
                value,
                left_child=self.left_child,
                right_child=self.right_child
            )
        if index <= self.right_child.index:
            return Node(
                self.index,
                self.value,
                left_child=self.left_child,
                right_child=self.right_child.__setitem__(index, value)
            )
        return Node(
            self.index,
            self.value,
            left_child=self.left_child.__setitem__(index, value),
            right_child=self.right_child,
        )

    def __len__(self):
        return self._length


class RandomAccessList(object):

    def __init__(self, head=NullObject(), right_sibling=NullObject()):
        self.head = head
        self.right_sibling = right_sibling

    def __getitem__(self, index):
        if index > self.right_sibling.head.index:
            return self.head[index]
        return self.right_sibling[index]

    def __setitem__(self, index, value):
        if index > self.right_sibling.head.index:
            return RandomAccessList(
                head=self.head.__setitem__(index, value),
                right_sibling=self.right_sibling
            )
        return RandomAccessList(
            head=self.head,
            right_sibling=self.right_sibling.__setitem__(index, value),
        )

    def append(self, value):
        if self._first_two_trees_equal_height():
            return RandomAccessList(
                head=Node(
                    index=self.head.index + 1,
                    value=value,
                    left_child=self.head,
                    right_child=self.right_sibling.head,
                ),
                right_sibling=self.right_sibling.right_sibling
            )
        else:
            return RandomAccessList(
                head=Node(
                    index=self.head.index + 1,
                    value=value,
                ),
                right_sibling=self,
            )

    def _first_two_trees_equal_height(self):
        return len(self.right_sibling.head) == len(self.head) and len(self.right_sibling.head) > 0

    def __nonzero__(self):
        return not isinstance(self.head, NullObject)

    def __len__(self):
        return len(self.head) + len(self.right_sibling)

Scala

#!/bin/sh
exec scala "$0" "$@"
!#

object FastNode {
  def len[T](fastNode: FastNode[T]): Int = if (fastNode == null) 0 else fastNode.len
}

case class FastNode[+T](index: Int, value: T, left: FastNode[T], right: FastNode[T]) {

  val len: Int =
    (if (left == null) 0 else left.len) +
      (if (right == null) 0 else right.len) +
      1

  def apply(index: Int): T =
    if (index == this.index) value
    else if (index <= right.index) right(index)
    else left(index)

  def update[X >: T](index: Int, value: X): FastNode[X] =
    if (index == this.index) FastNode(index, value, left, right)
    else if (index <= right.index) FastNode(index, value, left, right.update(index, value))
    else FastNode(index, value, left.update(index, value), right)
}

object FastRandomAccessList {
  def len[T](fastRandomAccessList: FastRandomAccessList[T]) = if (fastRandomAccessList == null) 0 else fastRandomAccessList.len
}

case class FastRandomAccessList[+T](head: FastNode[T], right: FastRandomAccessList[T]) {

  def apply(index: Int): T =
    if (right.head == null || index > right.head.index) head(index)
    else right(index)

  def update[X >: T](index: Int, value: X): FastRandomAccessList[X] =
    if (index > right.head.index)
      FastRandomAccessList(head.update(index, value), right)
    else
      FastRandomAccessList(head, right.update(index, value))

  def append[X >: T](value: X): FastRandomAccessList[X] =
    if (firstTwoTreesEqualHeight)
      FastRandomAccessList(FastNode(head.index + 1, value, head, right.head), right.right)
    else
      FastRandomAccessList(
        FastNode(
          if (head != null) head.index + 1 else 0,
          value, null, null),
        this)

  private val firstTwoTreesEqualHeight =
    if (head == null) false
    else FastNode.len(right.head) == FastNode.len(head) && FastNode.len(right.head) > 0

  val len: Int = FastNode.len(head) + FastRandomAccessList.len(right)
}

object FastRandomAccessListFastApp extends App {
  val nElements = 1000000
  val emptyList: FastRandomAccessList[Int] = FastRandomAccessList[Int](null, null)

  val list = (0 until nElements).foldLeft(emptyList)(_ append _)

}
FastRandomAccessListFastApp.main(args)