binarytree_test.go

     1  // Copyright 2011 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // This benchmark, taken from the shootout, tests garbage collector
     6  // performance by generating and discarding large binary trees.
     7  
     8  package go1
     9  
    10  import "testing"
    11  
    12  type binaryNode struct {
    13  	item        int
    14  	left, right *binaryNode
    15  }
    16  
    17  func bottomUpTree(item, depth int) *binaryNode {
    18  	if depth <= 0 {
    19  		return &binaryNode{item: item}
    20  	}
    21  	return &binaryNode{item, bottomUpTree(2*item-1, depth-1), bottomUpTree(2*item, depth-1)}
    22  }
    23  
    24  func (n *binaryNode) itemCheck() int {
    25  	if n.left == nil {
    26  		return n.item
    27  	}
    28  	return n.item + n.left.itemCheck() - n.right.itemCheck()
    29  }
    30  
    31  const minDepth = 4
    32  
    33  func binarytree(n int) {
    34  	maxDepth := n
    35  	if minDepth+2 > n {
    36  		maxDepth = minDepth + 2
    37  	}
    38  	stretchDepth := maxDepth + 1
    39  
    40  	check := bottomUpTree(0, stretchDepth).itemCheck()
    41  	//fmt.Printf("stretch tree of depth %d\t check: %d\n", stretchDepth, check)
    42  
    43  	longLivedTree := bottomUpTree(0, maxDepth)
    44  
    45  	for depth := minDepth; depth <= maxDepth; depth += 2 {
    46  		iterations := 1 << uint(maxDepth-depth+minDepth)
    47  		check = 0
    48  
    49  		for i := 1; i <= iterations; i++ {
    50  			check += bottomUpTree(i, depth).itemCheck()
    51  			check += bottomUpTree(-i, depth).itemCheck()
    52  		}
    53  		//fmt.Printf("%d\t trees of depth %d\t check: %d\n", iterations*2, depth, check)
    54  	}
    55  	longLivedTree.itemCheck()
    56  	//fmt.Printf("long lived tree of depth %d\t check: %d\n", maxDepth, longLivedTree.itemCheck())
    57  }
    58  
    59  func BenchmarkBinaryTree17(b *testing.B) {
    60  	for i := 0; i < b.N; i++ {
    61  		binarytree(17)
    62  	}
    63  }
    64
View as plain text