test/garbage: move to test/bench/garbage

(These are benchmarks for the garbage collector, not tests.)

R=golang-dev, adg
CC=golang-dev
http://codereview.appspot.com/5484070

6 files changed, 522 insertions, 1 deletions

diff --git a/test/bench/garbage/Makefile b/test/bench/garbage/Makefile
new file mode 100644
index 000000000..916add779
--- /dev/null
+++ b/test/bench/garbage/Makefile
@@ -0,0 +1,27 @@
+# Copyright 2010 The Go Authors.  All rights reserved.
+# Use of this source code is governed by a BSD-style
+# license that can be found in the LICENSE file.
+
+include ../../../src/Make.inc
+
+ALL=\
+	parser\
+	peano\
+	tree\
+
+all: $(addsuffix .out, $(ALL))
+
+%.$O: %.go stats.go
+	$(GC) $*.go stats.go
+
+%.out: %.$O
+	$(LD) -o $@ $*.$O
+
+%.bench: %.out
+	time ./$*.out
+
+bench: $(addsuffix .bench, $(ALL))
+
+clean:
+	rm -f *.[$(OS)] $(addsuffix .out, $(ALL))
+
diff --git a/test/bench/garbage/parser.go b/test/bench/garbage/parser.go
new file mode 100644
index 000000000..d0f4e09ba
--- /dev/null
+++ b/test/bench/garbage/parser.go
@@ -0,0 +1,227 @@
+// Copyright 2010 The Go Authors.  All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Garbage collection benchmark: parse Go packages repeatedly.
+
+package main
+
+import (
+	"flag"
+	"fmt"
+	"go/ast"
+	"go/parser"
+	"go/token"
+	"log"
+	"net/http"
+	_ "net/http/pprof"
+	"os"
+	"path"
+	"runtime"
+	"strings"
+	"time"
+)
+
+var serve = flag.String("serve", "", "serve http on this address at end")
+
+func isGoFile(dir *os.FileInfo) bool {
+	return dir.IsRegular() &&
+		!strings.HasPrefix(dir.Name, ".") && // ignore .files
+		path.Ext(dir.Name) == ".go"
+}
+
+func isPkgFile(dir *os.FileInfo) bool {
+	return isGoFile(dir) &&
+		!strings.HasSuffix(dir.Name, "_test.go") // ignore test files
+}
+
+func pkgName(filename string) string {
+	file, err := parser.ParseFile(token.NewFileSet(), filename, nil, parser.PackageClauseOnly)
+	if err != nil || file == nil {
+		return ""
+	}
+	return file.Name.Name
+}
+
+func parseDir(dirpath string) map[string]*ast.Package {
+	// the package name is the directory name within its parent
+	// (use dirname instead of path because dirname is clean; i.e. has no trailing '/')
+	_, pkgname := path.Split(dirpath)
+
+	// filter function to select the desired .go files
+	filter := func(d *os.FileInfo) bool {
+		if isPkgFile(d) {
+			// Some directories contain main packages: Only accept
+			// files that belong to the expected package so that
+			// parser.ParsePackage doesn't return "multiple packages
+			// found" errors.
+			// Additionally, accept the special package name
+			// fakePkgName if we are looking at cmd documentation.
+			name := pkgName(dirpath + "/" + d.Name)
+			return name == pkgname
+		}
+		return false
+	}
+
+	// get package AST
+	pkgs, err := parser.ParseDir(token.NewFileSet(), dirpath, filter, parser.ParseComments)
+	if err != nil {
+		println("parse", dirpath, err.Error())
+		panic("fail")
+	}
+	return pkgs
+}
+
+func main() {
+	st := &runtime.MemStats
+	packages = append(packages, packages...)
+	packages = append(packages, packages...)
+	n := flag.Int("n", 4, "iterations")
+	p := flag.Int("p", len(packages), "# of packages to keep in memory")
+	flag.BoolVar(&st.DebugGC, "d", st.DebugGC, "print GC debugging info (pause times)")
+	flag.Parse()
+
+	var lastParsed []map[string]*ast.Package
+	var t0 int64
+	pkgroot := runtime.GOROOT() + "/src/pkg/"
+	for pass := 0; pass < 2; pass++ {
+		// Once the heap is grown to full size, reset counters.
+		// This hides the start-up pauses, which are much smaller
+		// than the normal pauses and would otherwise make
+		// the average look much better than it actually is.
+		st.NumGC = 0
+		st.PauseTotalNs = 0
+		t0 = time.Nanoseconds()
+
+		for i := 0; i < *n; i++ {
+			parsed := make([]map[string]*ast.Package, *p)
+			for j := range parsed {
+				parsed[j] = parseDir(pkgroot + packages[j%len(packages)])
+			}
+			if i+1 == *n && *serve != "" {
+				lastParsed = parsed
+			}
+		}
+		runtime.GC()
+		runtime.GC()
+	}
+	t1 := time.Nanoseconds()
+
+	fmt.Printf("Alloc=%d/%d Heap=%d Mallocs=%d PauseTime=%.3f/%d = %.3f\n",
+		st.Alloc, st.TotalAlloc,
+		st.Sys,
+		st.Mallocs, float64(st.PauseTotalNs)/1e9,
+		st.NumGC, float64(st.PauseTotalNs)/1e9/float64(st.NumGC))
+
+	/*
+		fmt.Printf("%10s %10s %10s\n", "size", "#alloc", "#free")
+		for _, s := range st.BySize {
+			fmt.Printf("%10d %10d %10d\n", s.Size, s.Mallocs, s.Frees)
+		}
+	*/
+	// Standard gotest benchmark output, collected by build dashboard.
+	gcstats("BenchmarkParser", *n, t1-t0)
+
+	if *serve != "" {
+		log.Fatal(http.ListenAndServe(*serve, nil))
+		println(lastParsed)
+	}
+}
+
+var packages = []string{
+	"archive/tar",
+	"asn1",
+	"big",
+	"bufio",
+	"bytes",
+	"cmath",
+	"compress/flate",
+	"compress/gzip",
+	"compress/zlib",
+	"container/heap",
+	"container/list",
+	"container/ring",
+	"container/vector",
+	"crypto/aes",
+	"crypto/blowfish",
+	"crypto/hmac",
+	"crypto/md4",
+	"crypto/md5",
+	"crypto/rand",
+	"crypto/rc4",
+	"crypto/rsa",
+	"crypto/sha1",
+	"crypto/sha256",
+	"crypto/sha512",
+	"crypto/subtle",
+	"crypto/tls",
+	"crypto/x509",
+	"crypto/xtea",
+	"debug/dwarf",
+	"debug/macho",
+	"debug/elf",
+	"debug/gosym",
+	"ebnf",
+	"encoding/ascii85",
+	"encoding/base64",
+	"encoding/binary",
+	"encoding/git85",
+	"encoding/hex",
+	"encoding/pem",
+	"exec",
+	"exp/datafmt",
+	"expvar",
+	"flag",
+	"fmt",
+	"go/ast",
+	"go/doc",
+	"go/parser",
+	"go/printer",
+	"go/scanner",
+	"go/token",
+	"gob",
+	"hash",
+	"hash/adler32",
+	"hash/crc32",
+	"hash/crc64",
+	"http",
+	"image",
+	"image/jpeg",
+	"image/png",
+	"io",
+	"io/ioutil",
+	"json",
+	"log",
+	"math",
+	"mime",
+	"net",
+	"os",
+	"os/signal",
+	"patch",
+	"path",
+	"rand",
+	"reflect",
+	"regexp",
+	"rpc",
+	"runtime",
+	"scanner",
+	"sort",
+	"smtp",
+	"strconv",
+	"strings",
+	"sync",
+	"syscall",
+	"syslog",
+	"tabwriter",
+	"template",
+	"testing",
+	"testing/iotest",
+	"testing/quick",
+	"testing/script",
+	"time",
+	"unicode",
+	"utf8",
+	"utf16",
+	"websocket",
+	"xml",
+}
diff --git a/test/bench/garbage/peano.go b/test/bench/garbage/peano.go
new file mode 100644
index 000000000..231359688
--- /dev/null
+++ b/test/bench/garbage/peano.go
@@ -0,0 +1,122 @@
+// $G $F.go && $L $F.$A && ./$A.out
+
+// Copyright 2009 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package main
+
+import (
+	"fmt"
+	"runtime"
+	"time"
+)
+
+type Number struct {
+	next *Number
+}
+
+// -------------------------------------
+// Peano primitives
+
+func zero() *Number { return nil }
+
+func is_zero(x *Number) bool { return x == nil }
+
+func add1(x *Number) *Number {
+	e := new(Number)
+	e.next = x
+	return e
+}
+
+func sub1(x *Number) *Number { return x.next }
+
+func add(x, y *Number) *Number {
+	if is_zero(y) {
+		return x
+	}
+
+	return add(add1(x), sub1(y))
+}
+
+func mul(x, y *Number) *Number {
+	if is_zero(x) || is_zero(y) {
+		return zero()
+	}
+
+	return add(mul(x, sub1(y)), x)
+}
+
+func fact(n *Number) *Number {
+	if is_zero(n) {
+		return add1(zero())
+	}
+
+	return mul(fact(sub1(n)), n)
+}
+
+// -------------------------------------
+// Helpers to generate/count Peano integers
+
+func gen(n int) *Number {
+	if n > 0 {
+		return add1(gen(n - 1))
+	}
+
+	return zero()
+}
+
+func count(x *Number) int {
+	if is_zero(x) {
+		return 0
+	}
+
+	return count(sub1(x)) + 1
+}
+
+func check(x *Number, expected int) {
+	var c = count(x)
+	if c != expected {
+		panic(fmt.Sprintf("error: found %d; expected %d", c, expected))
+	}
+}
+
+// -------------------------------------
+// Test basic functionality
+
+func verify() {
+	check(zero(), 0)
+	check(add1(zero()), 1)
+	check(gen(10), 10)
+
+	check(add(gen(3), zero()), 3)
+	check(add(zero(), gen(4)), 4)
+	check(add(gen(3), gen(4)), 7)
+
+	check(mul(zero(), zero()), 0)
+	check(mul(gen(3), zero()), 0)
+	check(mul(zero(), gen(4)), 0)
+	check(mul(gen(3), add1(zero())), 3)
+	check(mul(add1(zero()), gen(4)), 4)
+	check(mul(gen(3), gen(4)), 12)
+
+	check(fact(zero()), 1)
+	check(fact(add1(zero())), 1)
+	check(fact(gen(5)), 120)
+}
+
+// -------------------------------------
+// Factorial
+
+
+func main() {
+	t0 := time.Nanoseconds()
+	verify()
+	for i := 0; i <= 9; i++ {
+		print(i, "! = ", count(fact(gen(i))), "\n")
+	}
+	runtime.GC()
+	t1 := time.Nanoseconds()
+
+	gcstats("BenchmarkPeano", 1, t1-t0)
+}
diff --git a/test/bench/garbage/stats.go b/test/bench/garbage/stats.go
new file mode 100644
index 000000000..aa9db1dbc
--- /dev/null
+++ b/test/bench/garbage/stats.go
@@ -0,0 +1,45 @@
+// Copyright 2010 The Go Authors.  All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package main
+
+import (
+	"fmt"
+	"runtime"
+	"sort"
+)
+
+func gcstats(name string, n int, t int64) {
+	st := &runtime.MemStats
+	fmt.Printf("garbage.%sMem Alloc=%d/%d Heap=%d NextGC=%d Mallocs=%d\n", name, st.Alloc, st.TotalAlloc, st.Sys, st.NextGC, st.Mallocs)
+	fmt.Printf("garbage.%s %d %d ns/op\n", name, n, t/int64(n))
+	fmt.Printf("garbage.%sLastPause 1 %d ns/op\n", name, st.PauseNs[(st.NumGC-1)%uint32(len(st.PauseNs))])
+	fmt.Printf("garbage.%sPause %d %d ns/op\n", name, st.NumGC, int64(st.PauseTotalNs)/int64(st.NumGC))
+	nn := int(st.NumGC)
+	if nn >= len(st.PauseNs) {
+		nn = len(st.PauseNs)
+	}
+	t1, t2, t3, t4, t5 := tukey5(st.PauseNs[0:nn])
+	fmt.Printf("garbage.%sPause5: %d %d %d %d %d\n", name, t1, t2, t3, t4, t5)
+
+	//	fmt.Printf("garbage.%sScan: %v\n", name, st.ScanDist)
+}
+
+type T []uint64
+
+func (t T) Len() int           { return len(t) }
+func (t T) Swap(i, j int)      { t[i], t[j] = t[j], t[i] }
+func (t T) Less(i, j int) bool { return t[i] < t[j] }
+
+func tukey5(raw []uint64) (lo, q1, q2, q3, hi uint64) {
+	x := make(T, len(raw))
+	copy(x, raw)
+	sort.Sort(T(x))
+	lo = x[0]
+	q1 = x[len(x)/4]
+	q2 = x[len(x)/2]
+	q3 = x[len(x)*3/4]
+	hi = x[len(x)-1]
+	return
+}
diff --git a/test/bench/garbage/tree.go b/test/bench/garbage/tree.go
new file mode 100644
index 000000000..c5eae9760
--- /dev/null
+++ b/test/bench/garbage/tree.go
@@ -0,0 +1,100 @@
+/*
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+    * Redistributions of source code must retain the above copyright
+    notice, this list of conditions and the following disclaimer.
+
+    * Redistributions in binary form must reproduce the above copyright
+    notice, this list of conditions and the following disclaimer in the
+    documentation and/or other materials provided with the distribution.
+
+    * Neither the name of "The Computer Language Benchmarks Game" nor the
+    name of "The Computer Language Shootout Benchmarks" nor the names of
+    its contributors may be used to endorse or promote products derived
+    from this software without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+POSSIBILITY OF SUCH DAMAGE.
+*/
+
+/* The Computer Language Benchmarks Game
+ * http://shootout.alioth.debian.org/
+ *
+ * contributed by The Go Authors.
+ * based on C program by Kevin Carson
+ */
+
+package main
+
+import (
+	"flag"
+	"fmt"
+	"time"
+)
+
+var n = flag.Int("n", 16, "depth")
+
+type Node struct {
+	item        int
+	left, right *Node
+}
+
+func bottomUpTree(item, depth int) *Node {
+	if depth <= 0 {
+		return &Node{item: item}
+	}
+	return &Node{item, bottomUpTree(2*item-1, depth-1), bottomUpTree(2*item, depth-1)}
+}
+
+func (n *Node) itemCheck() int {
+	if n.left == nil {
+		return n.item
+	}
+	return n.item + n.left.itemCheck() - n.right.itemCheck()
+}
+
+const minDepth = 4
+
+func main() {
+	flag.Parse()
+
+	t0 := time.Nanoseconds()
+
+	maxDepth := *n
+	if minDepth+2 > *n {
+		maxDepth = minDepth + 2
+	}
+	stretchDepth := maxDepth + 1
+
+	check := bottomUpTree(0, stretchDepth).itemCheck()
+	fmt.Printf("stretch tree of depth %d\t check: %d\n", stretchDepth, check)
+
+	longLivedTree := bottomUpTree(0, maxDepth)
+
+	for depth := minDepth; depth <= maxDepth; depth += 2 {
+		iterations := 1 << uint(maxDepth-depth+minDepth)
+		check = 0
+
+		for i := 1; i <= iterations; i++ {
+			check += bottomUpTree(i, depth).itemCheck()
+			check += bottomUpTree(-i, depth).itemCheck()
+		}
+		fmt.Printf("%d\t trees of depth %d\t check: %d\n", iterations*2, depth, check)
+	}
+	fmt.Printf("long lived tree of depth %d\t check: %d\n", maxDepth, longLivedTree.itemCheck())
+
+	t1 := time.Nanoseconds()
+
+	// Standard gotest benchmark output, collected by build dashboard.
+	gcstats("BenchmarkTree", *n, t1-t0)
+}
diff --git a/test/bench/shootout/timing.sh b/test/bench/shootout/timing.sh
index 473c9b312..3e190e15c 100755
--- a/test/bench/shootout/timing.sh
+++ b/test/bench/shootout/timing.sh
@@ -5,7 +5,7 @@
 
 set -e
 
-eval $(gomake --no-print-directory -f ../../src/Make.inc go-env)
+eval $(gomake --no-print-directory -f ../../../src/Make.inc go-env)
 PATH=.:$PATH
 
 havegccgo=false