...
Run Format

Source file test/bench/go1/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