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 Value
s, 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.