Having read the rules it's difficult to know what's considered "fair" for this test - all GC tuning is off the table, sure. But what's bugging me is "Leaf nodes must be the same as interior nodes - the same memory allocation." So what constitutes "the same memory allocation" - literally the exact same call to some opaque internal allocator? If so, shouldn't Java also have to disable JIT to be fair?
Let me offer an alternate interpretation: I will do the same memory allocation if I need to allocate a node, but if my language lets me not allocate a node yet still use that node why should I? Or an alternate argument if you don't like that one: Why must my "node" be `Tree`, rather than `*Tree`?
A central idiom of Go is that zero-values of a type can be useful; a two-line change, no new special-cases, no pooling or such gauche hacks:
// Count the nodes in the given complete binary tree.
func (t *Tree) Count() int {
if t == nil {
return 1
}
return 1 + t.Right.Count() + t.Left.Count()
}
// Create a complete binary tree of `depth` and return it as a pointer.
func NewTree(depth int) *Tree {
if depth > 0 {
return &Tree{Left: NewTree(depth - 1), Right: NewTree(depth - 1)}
} else {
return nil
}
}
I'm sure someone will tell me I "optimized away the work" - but in the end I believe I'm making exactly the same number of method calls on the same type of receiver. If that's not the work, what is?
And then the Java etc programs are re-written to do the same and the test value is increased (to compensate for the reduced memory allocation) and we're back where we started?
- Practically, Java would rather have to `return 3` when it detects a null child, effectively precomputing the penultimate level.
- Semantically, Java could no longer distinguish between an absent child and a child with no children.
Honestly, I have other variants that still don't use pooling but are less idiomatic; I find this exercise is begging the question hard. Any tools, however idiomatic, the language is giving you to reduce the effects of allocation seem to be off-limits for GCd languages. Whereas then e.g. C can just throw them all in a third-party pool library. And JIT languages are presumably allowed to fuse anything they want.
The answer to "… but if my language lets me not allocate a node yet still use that node why should I?" is — Because allocate a node is the basis of comparison with the other programs!
Change that for the Go programs and you change that for all the other programs; otherwise just special pleading for Go lang.
If you look at other examples on that site, Go and Java are roughly the same, but with some variance:
https://benchmarksgame-team.pages.debian.net/benchmarksgame/...