Paralel version of shootout binarytrees benchmark

binarytrees.go

/* The Computer Language Benchmarks Game
 * http://shootout.alioth.debian.org/
 *
 * contributed by The Go Authors.
 * based on C program by Kevin Carson
 * flag.Arg hack by Isaac Gouy
 */

package main

import (
	"flag"
	"fmt"
	"strconv"
	"runtime"
)

var n = 0

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

func bottomUpTree(item, depth int) *Node {
	if depth <= 0 {
		return &Node{item: item}
	}
	return &Node{item, bottomUpTree(2*item-1, depth-1), bottomUpTree(2*item, depth-1)}
}

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

const minDepth = 4

func check_depth(depth int, iterations int) chan string {
	check := 0
	out := make(chan string)
	go func() {
		for i := 1; i <= iterations; i++ {
			check += bottomUpTree(i, depth).itemCheck()
			check += bottomUpTree(-i, depth).itemCheck()
		}
		out <- fmt.Sprintf("%d\t trees of depth %d\t check: %d\n", iterations*2, depth, check)
		return
	}()
	return out
}

func main() {
	runtime.GOMAXPROCS(8)
	flag.Parse()
	if flag.NArg() > 0 {
		n, _ = strconv.Atoi(flag.Arg(0))
	}

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

	check := bottomUpTree(0, stretchDepth).itemCheck()
	fmt.Printf("stretch tree of depth %d\t check: %d\n", stretchDepth, check)

	longLivedTree := bottomUpTree(0, maxDepth)
	outs := [](chan string){}
	for depth := minDepth; depth <= maxDepth; depth += 2 {
		iterations := 1 << uint(maxDepth-depth+minDepth)
		out := check_depth(depth, iterations)
		outs = append(outs, out)
	}
	for _, out := range outs {
		fmt.Printf(<-out)
		close(out)
	}
	fmt.Printf("long lived tree of depth %d\t check: %d\n", maxDepth, longLivedTree.itemCheck())
}