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

faster_binary_tree.go

package main

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

var minDepth = 4
var n = 0

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

const nodesCount = 1024 * 32

var (
	nodeBuf    []Node
	nodeBufIdx int32
)

type Allocator struct {
	nodes []Node
	idx   int
	cap   int
}

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

func NewAllocator() *Allocator {
	return NewAllocatorWithCapacity(nodesCount)
}

func (a *Allocator) allocNode(item int, left, right *Node) *Node {
	if a.idx >= a.cap-1 {
		a.nodes = make([]Node, a.cap)
		a.idx = 0
	}
	res := &a.nodes[a.idx]
	a.idx++
	res.item = item
	res.left = left
	res.right = right
	return res
}

func main() {
	//runtime.GOMAXPROCS(runtime.NumCPU() * 2)
	debug.SetGCPercent(-1)
	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 := NewAllocator()
	check_l := bottomUpTree(a, 0, stretchDepth).ItemCheck()
	fmt.Printf("stretch tree of depth %d\t check: %d\n", stretchDepth, check_l)

	longLivedTree := bottomUpTree(a, 0, maxDepth)

	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
			a := NewAllocator()
			for i := 1; i <= iterations; i++ {
				check += bottomUpTree(a, i, depth).ItemCheck()
				check += bottomUpTree(a, -i, depth).ItemCheck()
			}
			result_trees[depth] = iterations * 2
			result_check[depth] = check

			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()
}