14f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen/* 24f7f559a4b744258a796dd591b11bd88e4a6dc7Dan WillemsenRedistribution and use in source and binary forms, with or without 34f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsenmodification, are permitted provided that the following conditions are met: 44f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen 54f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen * Redistributions of source code must retain the above copyright 64f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen notice, this list of conditions and the following disclaimer. 74f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen 84f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen * Redistributions in binary form must reproduce the above copyright 94f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen notice, this list of conditions and the following disclaimer in the 104f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen documentation and/or other materials provided with the distribution. 114f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen 124f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen * Neither the name of "The Computer Language Benchmarks Game" nor the 134f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen name of "The Computer Language Shootout Benchmarks" nor the names of 144f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen its contributors may be used to endorse or promote products derived 154f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen from this software without specific prior written permission. 164f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen 174f7f559a4b744258a796dd591b11bd88e4a6dc7Dan WillemsenTHIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 184f7f559a4b744258a796dd591b11bd88e4a6dc7Dan WillemsenAND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 194f7f559a4b744258a796dd591b11bd88e4a6dc7Dan WillemsenIMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 204f7f559a4b744258a796dd591b11bd88e4a6dc7Dan WillemsenARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 214f7f559a4b744258a796dd591b11bd88e4a6dc7Dan WillemsenLIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 224f7f559a4b744258a796dd591b11bd88e4a6dc7Dan WillemsenCONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 234f7f559a4b744258a796dd591b11bd88e4a6dc7Dan WillemsenSUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 244f7f559a4b744258a796dd591b11bd88e4a6dc7Dan WillemsenINTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 254f7f559a4b744258a796dd591b11bd88e4a6dc7Dan WillemsenCONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 264f7f559a4b744258a796dd591b11bd88e4a6dc7Dan WillemsenARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 274f7f559a4b744258a796dd591b11bd88e4a6dc7Dan WillemsenPOSSIBILITY OF SUCH DAMAGE. 284f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen*/ 294f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen 304f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen/* The Computer Language Benchmarks Game 314f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen * http://shootout.alioth.debian.org/ 324f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen * 334f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen * contributed by The Go Authors. 344f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen * based on C program by Kevin Carson 354f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen */ 364f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen 374f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsenpackage main 384f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen 394f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsenimport ( 404f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen "flag" 414f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen "fmt" 424f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen "time" 434f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen) 444f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen 454f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsenvar n = flag.Int("n", 16, "depth") 464f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen 474f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsentype Node struct { 484f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen item int 494f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen left, right *Node 504f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen} 514f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen 524f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsenfunc bottomUpTree(item, depth int) *Node { 534f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen if depth <= 0 { 544f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen return &Node{item: item} 554f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen } 564f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen return &Node{item, bottomUpTree(2*item-1, depth-1), bottomUpTree(2*item, depth-1)} 574f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen} 584f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen 594f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsenfunc (n *Node) itemCheck() int { 604f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen if n.left == nil { 614f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen return n.item 624f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen } 634f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen return n.item + n.left.itemCheck() - n.right.itemCheck() 644f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen} 654f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen 664f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsenconst minDepth = 4 674f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen 684f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsenfunc main() { 694f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen flag.Parse() 704f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen 714f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen t0 := time.Now() 724f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen 734f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen maxDepth := *n 744f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen if minDepth+2 > *n { 754f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen maxDepth = minDepth + 2 764f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen } 774f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen stretchDepth := maxDepth + 1 784f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen 794f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen check := bottomUpTree(0, stretchDepth).itemCheck() 804f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen fmt.Printf("stretch tree of depth %d\t check: %d\n", stretchDepth, check) 814f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen 824f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen longLivedTree := bottomUpTree(0, maxDepth) 834f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen 844f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen for depth := minDepth; depth <= maxDepth; depth += 2 { 854f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen iterations := 1 << uint(maxDepth-depth+minDepth) 864f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen check = 0 874f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen 884f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen for i := 1; i <= iterations; i++ { 894f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen check += bottomUpTree(i, depth).itemCheck() 904f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen check += bottomUpTree(-i, depth).itemCheck() 914f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen } 924f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen fmt.Printf("%d\t trees of depth %d\t check: %d\n", iterations*2, depth, check) 934f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen } 944f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen fmt.Printf("long lived tree of depth %d\t check: %d\n", maxDepth, longLivedTree.itemCheck()) 954f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen 964f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen t1 := time.Now() 974f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen 984f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen // Standard gotest benchmark output, collected by build dashboard. 994f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen gcstats("BenchmarkTree", *n, t1.Sub(t0)) 1004f7f559a4b744258a796dd591b11bd88e4a6dc7Dan Willemsen} 101