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
