performance measurements

Each table row shows performance measurements for this Go program with a particular command-line input value N.

 N  CPU secs Elapsed secs Memory KB Code B ≈ CPU Load
120.110.12?814  0% 0% 0% 100%
162.532.5423,692814  1% 0% 0% 100%
2055.2855.35264,284814  0% 1% 1% 100%

Read the ↓ make, command line, and program output logs to see how this program was run.

Read binary-trees benchmark to see what this program should do.

 notes

go version go1.4 linux/amd64

 binary-trees Go #8 program source code

/* The Computer Language Benchmarks Game
 * http://benchmarksgame.alioth.debian.org/
 *
 * based on Go program by The Go Authors.
 * based on C program by Kevin Carson
 * flag.Arg hack by Isaac Gouy
 * modified by Jamil Djadala to use goroutines
 * modified by Chai Shushan
 * modified by Chandra Sekar S to use arenas
 */
package main

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

var minDepth = 4
var n = 0

type NodeArena []Node

func (na *NodeArena) Get() *Node {
	if len(*na) == 0 {
		*na = make([]Node, 10000)
	}

	n := &(*na)[len(*na)-1]
	*na = (*na)[:len(*na)-1]
	return n
}

func main() {
	runtime.GOMAXPROCS(runtime.NumCPU() * 2)

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

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

	mainArena := new(NodeArena)

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

	longLivedTree := bottomUpTree(0, maxDepth, mainArena)

	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) {
			localArena := new(NodeArena)
			iterations := 1 << uint(maxDepth-depth+minDepth)
			check := 0

			for i := 1; i <= iterations; i++ {
				check += bottomUpTree(i, depth, localArena).ItemCheck()
				check += bottomUpTree(-i, depth, localArena).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())
}

func bottomUpTree(item, depth int, arena *NodeArena) *Node {
	n := arena.Get()
	if depth <= 0 {
		*n = Node{item, nil, nil}
	} else {
		*n = Node{
			item,
			bottomUpTree(2*item-1, depth-1, arena),
			bottomUpTree(2*item, depth-1, arena),
		}
	}
	return n
}

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

 make, command-line, and program output logs

Thu, 11 Dec 2014 20:48:27 GMT

MAKE:
/usr/local/src/go/bin/go build -o binarytrees.go-8.go_run
0.52s to complete and log all make actions

COMMAND LINE:
./binarytrees.go-8.go_run 20

PROGRAM OUTPUT:
stretch tree of depth 21	 check: -1
2097152	 trees of depth 4	 check: -2097152
524288	 trees of depth 6	 check: -524288
131072	 trees of depth 8	 check: -131072
32768	 trees of depth 10	 check: -32768
8192	 trees of depth 12	 check: -8192
2048	 trees of depth 14	 check: -2048
512	 trees of depth 16	 check: -512
128	 trees of depth 18	 check: -128
32	 trees of depth 20	 check: -32
long lived tree of depth 20	 check: -1

Revised BSD license

  Home   Conclusions   License   Play