Even faster version of http://benchmarksgame.alioth.debian.org/u64q/program.php?test=binarytrees&lang=go&id=4

even_faster_binary_trees.go

package main

import (
	"flag"
	"fmt"
	"log"
	"os"
	"runtime/pprof"
	"strconv"
	"sync"
	"time"
)

var minDepth = 4
var n = 0

var cpuprofile = flag.String("cpuprofile", "", "write cpu profile to file")

var (
	nodeBuf    []Node
	nodeBufIdx int32
)

type Allocator struct {
	nodes []Node
	idx   int
}

func calcNodeCount(depth int) int {
	res := 1 << (uint(depth + 1))
	return res - 1
}

func NewAllocatorWithCount(cap int) *Allocator {
	return &Allocator{
		nodes: make([]Node, cap, cap),
		idx:   0,
	}
}

func (a *Allocator) PrintUnused() {
	left := cap(a.nodes) - a.idx
	if left > 0 {
		fmt.Printf("left: %d out of %d\n", left, cap(a.nodes))
	}
}

func NewAllocatorWithDepth(depth int) *Allocator {
	cap := calcNodeCount(depth)
	return NewAllocatorWithCount(cap)
}

func (a *Allocator) Reset() {
	a.idx = 0
}

func (a *Allocator) allocNode(item int, left, right *Node) *Node {
	res := &a.nodes[a.idx]
	a.idx++
	res.item = item
	res.left = left
	res.right = right
	return res
}

func main() {
	timeStart := time.Now()

	flag.Parse()
	if flag.NArg() > 0 {
		n, _ = strconv.Atoi(flag.Arg(0))
	}

	if *cpuprofile != "" {
		f, err := os.Create(*cpuprofile)
		if err != nil {
			log.Fatal(err)
		}
		pprof.StartCPUProfile(f)
		defer pprof.StopCPUProfile()
	}

	maxDepth := n
	if minDepth+2 > n {
		maxDepth = minDepth + 2
	}
	stretchDepth := maxDepth + 1

	a := NewAllocatorWithDepth(stretchDepth)
	check_l := bottomUpTree(a, 0, stretchDepth).ItemCheck()
	fmt.Printf("stretch tree of depth %d\t check: %d\n", stretchDepth, check_l)
	a.PrintUnused()

	a = NewAllocatorWithDepth(maxDepth)
	longLivedTree := bottomUpTree(a, 0, maxDepth)
	a.PrintUnused()

	result_trees := make([]int, maxDepth+1)
	result_check := make([]int, maxDepth+1)

	var wg sync.WaitGroup
	for depth_l := minDepth; depth_l <= maxDepth; depth_l += 2 {
		wg.Add(1)
		go func(depth int) {
			iterations := 1 << uint(maxDepth-depth+minDepth)
			check := 0
			//n := calcNodeCount(depth) * 2 * iterations
			//fmt.Printf("depth: %d, iterations: %d, nodes: %d\n", depth, iterations, n)
			a := NewAllocatorWithDepth(depth)
			for i := 1; i <= iterations; i++ {
				a.Reset()
				check += bottomUpTree(a, i, depth).ItemCheck()
				a.Reset()
				check += bottomUpTree(a, -i, depth).ItemCheck()
			}
			result_trees[depth] = iterations * 2
			result_check[depth] = check
			a.PrintUnused()
			wg.Done()
		}(depth_l)
	}
	wg.Wait()

	for depth := minDepth; depth <= maxDepth; depth += 2 {
		fmt.Printf("%d\t trees of depth %d\t check: %d\n",
			result_trees[depth], depth, result_check[depth],
		)
	}
	fmt.Printf("long lived tree of depth %d\t check: %d\n",
		maxDepth, longLivedTree.ItemCheck(),
	)
	fmt.Printf("dur: %s\n", time.Since(timeStart))
}

func bottomUpTree(a *Allocator, item, depth int) *Node {
	if depth <= 0 {
		return a.allocNode(item, nil, nil)
	}
	left := bottomUpTree(a, 2*item-1, depth-1)
	right := bottomUpTree(a, 2*item, depth-1)
	return a.allocNode(item, left, right)
}

type Node struct {
	item        int
	left, right *Node
}

func (self *Node) ItemCheck() int {
	if self.left == nil {
		return self.item
	}
	return self.item + self.left.ItemCheck() - self.right.ItemCheck()
}