Why this simple Go program is slower than its Node.js counterpart?

Question

I'm attempting to use Go to implement a binary tree with values on the leaf, i.e., equivalent to:

data Tree a 
  = Node {left: Tree, right: Tree} 
  | Leaf {value: a}

I had two problems: 1, I couldn't figure a way to make a type with multiple constructors, so I had to fit all data in one. 2, I couldn't make it polymorphic, so I had to use interface{} (which I guess is an "opt-out" of the type-system?). This is the best I could make:

package main

import ("fmt")

type Tree struct {
  IsLeaf bool
  Left *Tree
  Value interface{}
  Right *Tree
}

func build(n int) *Tree {
  if (n == 0) {
    return &Tree{IsLeaf: true, Left: nil, Value: 1, Right: nil}
  } else {
    return &Tree{IsLeaf: false, Left: build(n - 1), Value: 0, Right: build(n - 1)}
  }
}

func sum(tree *Tree) int {
  if (tree.IsLeaf) {
    return tree.Value.(int)
  } else {
    return sum(tree.Left) + sum(tree.Right)
  }
}

func main() {
  fmt.Println(sum(build(23)))
}

It implements the type and tests it by summing over a huge generated tree. I've proceeded to make an equivalent implementation in JavaScript (including the redundant data on constructors, for fairness):

const build = n => {
  if (n === 0) {
    return {IsLeaf: true, Value: 1, Left: null, Right: null};
  } else {
    return {IsLeaf: false, Value: 0, Left: build(n - 1), Right: build(n - 1)};
  }
}

const sum = tree => {
  if (tree.IsLeaf) {
    return tree.Value;
  } else {
    return sum(tree.Left) + sum(tree.Right);
  }
}

console.log(sum(build(23)));

I've compiled the Go code with go build test.go and ran it with time ./test. I've ran the Node.js code with node test.js. After several tests, the Go program ran in about 2.5 seconds in average, versus 1.0 seconds of the Node.js one.

That makes Go 2.5x slower than Node.js for this simple program, which can't be correct, given that Go is a statically-typed, compiled language with a mature compiler, whereas JavaScript is an untyped, interpreted one.

Why is my Go program so slow? Am I missing some compiler flag, or is the code problematic?

Answer 1

Summary

This code is slower because of the type assertion, and reduntant data.

Go doesn't encourage you to write type assertions in hot places:

tree.Value.(int) 

Take out this type assertion (and accordingly change Value to an int type), and your code will perform about twice as fast (which should be around the speed of your node example).

Take out the redundant data as well, and your code will perform about three times as fast. See the playground example at the end of the post.

Details

I think this is a mistake of design, rather than implementation. Reading your question, I think there is some confusion about how Go's type system works.

Go's object model doesn't encourage you to do polymorphism using catch-all types (see the top half of this excellent answer for a discussion of Go's polymorphism).

In a JavaScript world, each object is a specific type. In Go, a struct can be treated as a specific interface type if it fulfils the interface's contract. Note that structs are not objects - what you called constructors are just struct initialisers.

It is possible to write Go code that operates on interface{} as a placeholder for all types, but the language doesn't really encourage you to write code this way (as you pointed out in your question, it was a challenge to write clean code in the way you would write it in JavaScript).

Because Go doesn't really have objects, trying to write code that feels very object-oriented in Go will be challenging (additionally, Go doesn't have standard inheritance or method overloading). For this reason, I don't think that your code is the kind of code that Go encourages the programmer to write. So, it's not a fair test.

Type assertion is slow. (I'm not across the design of Go's internals, but certainly this indicates that the programmer is not expected to write a lot of type assertions). Because of this, it's not surprising that your code is not performant. I changed your code to:

type Tree struct {
  IsLeaf bool
  Left *Tree
  Value int
  Right *Tree
} 
 .....
func sum(tree *Tree) int {
  if (tree.IsLeaf) {
    return tree.Value
  } else {
    return sum(tree.Left) + sum(tree.Right)
  }
}

And achieved a 2x speed up on my machine.

There are probably other optimisations - you might be able to remove IsLeaf, and you don't need to store values at non-leaf nodes (or alternatively, you could distribute values throughout the tree, so never waste the Value). I don't know whether JavaScript optimises out these unnecessary Values, but I don't believe Go does.

So, I think your code is using much more memory than it needs, which won't help performance either.

Does it matter?

I'm not personally convinced by "I wrote this program in X and Y, and found that Y was slower", especially as it's hard to compare fairly across frameworks. There are so many other sources of variance - programmer knowledge, machine load, spin-up time, etc.

To do a fair test you'd need to write code that's idiomatic in each language, but also use the same code. I don't think it's realistic to achieve both.

If this code is your specific scenario, and performance is the primary goal, then this test might be helpful. But, otherwise I don't think it's a very meaningful comparison.

At scale, I would expect other considerations to beat how fast you can create and traverse a tree. There are technical concerns like data throughput and performance under load, but also softer concerns like programmer time, and maintenance effort.

The academic exercise is interesting, though. And writing code like this is a good way to find the edges of a framework.

---

Edit: I tried making your code more Go-like, which has the added advantage of a 3x speedup over the original.:

https://play.golang.org/p/mWaO3WR6pw

The tree is a bit heavy for the playground, but you can copy and paste the code to run locally.

There are more optimisations possible that I haven't tried, such as parallel construction of the tree.

You may be able to extend this design to have the polymorphic behaviour that you want (by providing alternative Leaf implementations), but I'm not sure what Sum() means for non-number types. Not knowing how to define Sum() is a good example of the kind of thinking that leads to not deciding to include polymorphism through generics.