6 files changed, 671 insertions, 0 deletions
diff --git a/test/bench/garbage/Makefile b/test/bench/garbage/Makefile
new file mode 100644
index 0000000..c10ef0a
--- /dev/null
+++ b/test/bench/garbage/Makefile
@@ -0,0 +1,23 @@
+# 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.
+
+ALL=\
+	parser\
+	peano\
+	tree\
+	tree2\
+
+all: $(ALL)
+
+%: %.go
+	go build $*.go stats.go
+
+%.bench: %
+	time ./$*
+
+bench: $(addsuffix .bench, $(ALL))
+
+clean:
+	rm -f $(ALL)
+
diff --git a/test/bench/garbage/parser.go b/test/bench/garbage/parser.go
new file mode 100644
index 0000000..817afa9
--- /dev/null
+++ b/test/bench/garbage/parser.go
@@ -0,0 +1,280 @@
+// 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.IsDir() &&
+		!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 := new(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 time.Time
+	var numGC uint32
+	var pauseTotalNs uint64
+	pkgroot := runtime.GOROOT() + "/src/"
+	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.
+		runtime.ReadMemStats(st)
+		numGC = st.NumGC
+		pauseTotalNs = st.PauseTotalNs
+		t0 = time.Now()
+
+		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.Now()
+
+	runtime.ReadMemStats(st)
+	st.NumGC -= numGC
+	st.PauseTotalNs -= pauseTotalNs
+	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.Sub(t0))
+
+	if *serve != "" {
+		log.Fatal(http.ListenAndServe(*serve, nil))
+		println(lastParsed)
+	}
+}
+
+// find . -type d -not -path "./exp" -not -path "./exp/*" -printf "\t\"%p\",\n" | sort | sed "s/\.\///" | grep -v testdata
+var packages = []string{
+	"archive",
+	"archive/tar",
+	"archive/zip",
+	"bufio",
+	"builtin",
+	"bytes",
+	"compress",
+	"compress/bzip2",
+	"compress/flate",
+	"compress/gzip",
+	"compress/lzw",
+	"compress/zlib",
+	"container",
+	"container/heap",
+	"container/list",
+	"container/ring",
+	"crypto",
+	"crypto/aes",
+	"crypto/cipher",
+	"crypto/des",
+	"crypto/dsa",
+	"crypto/ecdsa",
+	"crypto/elliptic",
+	"crypto/hmac",
+	"crypto/md5",
+	"crypto/rand",
+	"crypto/rc4",
+	"crypto/rsa",
+	"crypto/sha1",
+	"crypto/sha256",
+	"crypto/sha512",
+	"crypto/subtle",
+	"crypto/tls",
+	"crypto/x509",
+	"crypto/x509/pkix",
+	"database",
+	"database/sql",
+	"database/sql/driver",
+	"debug",
+	"debug/dwarf",
+	"debug/elf",
+	"debug/gosym",
+	"debug/macho",
+	"debug/pe",
+	"encoding",
+	"encoding/ascii85",
+	"encoding/asn1",
+	"encoding/base32",
+	"encoding/base64",
+	"encoding/binary",
+	"encoding/csv",
+	"encoding/gob",
+	"encoding/hex",
+	"encoding/json",
+	"encoding/pem",
+	"encoding/xml",
+	"errors",
+	"expvar",
+	"flag",
+	"fmt",
+	"go",
+	"go/ast",
+	"go/build",
+	"go/doc",
+	"go/format",
+	"go/parser",
+	"go/printer",
+	"go/scanner",
+	"go/token",
+	"hash",
+	"hash/adler32",
+	"hash/crc32",
+	"hash/crc64",
+	"hash/fnv",
+	"html",
+	"html/template",
+	"image",
+	"image/color",
+	"image/draw",
+	"image/gif",
+	"image/jpeg",
+	"image/png",
+	"index",
+	"index/suffixarray",
+	"io",
+	"io/ioutil",
+	"log",
+	"log/syslog",
+	"math",
+	"math/big",
+	"math/cmplx",
+	"math/rand",
+	"mime",
+	"mime/multipart",
+	"net",
+	"net/http",
+	"net/http/cgi",
+	"net/http/cookiejar",
+	"net/http/fcgi",
+	"net/http/httptest",
+	"net/http/httputil",
+	"net/http/pprof",
+	"net/mail",
+	"net/rpc",
+	"net/rpc/jsonrpc",
+	"net/smtp",
+	"net/textproto",
+	"net/url",
+	"os",
+	"os/exec",
+	"os/signal",
+	"os/user",
+	"path",
+	"path/filepath",
+	"reflect",
+	"regexp",
+	"regexp/syntax",
+	"runtime",
+	"runtime/cgo",
+	"runtime/debug",
+	"runtime/pprof",
+	"runtime/race",
+	"sort",
+	"strconv",
+	"strings",
+	"sync",
+	"sync/atomic",
+	"syscall",
+	"testing",
+	"testing/iotest",
+	"testing/quick",
+	"text",
+	"text/scanner",
+	"text/tabwriter",
+	"text/template",
+	"text/template/parse",
+	"time",
+	"unicode",
+	"unicode/utf16",
+	"unicode/utf8",
+	"unsafe",
+}
diff --git a/test/bench/garbage/peano.go b/test/bench/garbage/peano.go
new file mode 100644
index 0000000..6c7e523
--- /dev/null
+++ b/test/bench/garbage/peano.go
@@ -0,0 +1,121 @@
+// run
+
+// 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.Now()
+	verify()
+	for i := 0; i <= 9; i++ {
+		print(i, "! = ", count(fact(gen(i))), "\n")
+	}
+	runtime.GC()
+	t1 := time.Now()
+
+	gcstats("BenchmarkPeano", 1, t1.Sub(t0))
+}
diff --git a/test/bench/garbage/stats.go b/test/bench/garbage/stats.go
new file mode 100644
index 0000000..937e00f
--- /dev/null
+++ b/test/bench/garbage/stats.go
@@ -0,0 +1,52 @@
+// 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"
+	"time"
+)
+
+func gcstats(name string, n int, t time.Duration) {
+	st := new(runtime.MemStats)
+	runtime.ReadMemStats(st)
+	nprocs := runtime.GOMAXPROCS(-1)
+	cpus := ""
+	if nprocs != 1 {
+		cpus = fmt.Sprintf("-%d", nprocs)
+	}
+	fmt.Printf("garbage.%sMem%s Alloc=%d/%d Heap=%d NextGC=%d Mallocs=%d\n", name, cpus, st.Alloc, st.TotalAlloc, st.Sys, st.NextGC, st.Mallocs)
+	fmt.Printf("garbage.%s%s %d %d ns/op\n", name, cpus, n, t.Nanoseconds()/int64(n))
+	fmt.Printf("garbage.%sLastPause%s 1 %d ns/op\n", name, cpus, st.PauseNs[(st.NumGC-1)%uint32(len(st.PauseNs))])
+	fmt.Printf("garbage.%sPause%s %d %d ns/op\n", name, cpus, 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%s: %d %d %d %d %d\n", name, cpus, 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 0000000..524cfeb
--- /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
+ * https://benchmarksgame-team.pages.debian.net/benchmarksgame/
+ *
+ * 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.Now()
+
+	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.Now()
+
+	// Standard gotest benchmark output, collected by build dashboard.
+	gcstats("BenchmarkTree", *n, t1.Sub(t0))
+}
diff --git a/test/bench/garbage/tree2.go b/test/bench/garbage/tree2.go
new file mode 100644
index 0000000..a70a106
--- /dev/null
+++ b/test/bench/garbage/tree2.go
@@ -0,0 +1,95 @@
+// Copyright 2012 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 (
+	"flag"
+	"fmt"
+	"log"
+	"os"
+	"runtime"
+	"runtime/pprof"
+	"time"
+	"unsafe"
+)
+
+const BranchingFactor = 4
+
+type Object struct {
+	child [BranchingFactor]*Object
+}
+
+var (
+	cpus       = flag.Int("cpus", 1, "number of cpus to use")
+	heapsize   = flag.Int64("heapsize", 100*1024*1024, "size of the heap in bytes")
+	cpuprofile = flag.String("cpuprofile", "", "write cpu profile to file")
+
+	lastPauseNs uint64 = 0
+	lastFree    uint64 = 0
+	heap        *Object
+	calls       [20]int
+	numobjects  int64
+	memstats    runtime.MemStats
+)
+
+func buildHeap() {
+	objsize := int64(unsafe.Sizeof(Object{}))
+	heap, _ = buildTree(float64(objsize), float64(*heapsize), 0)
+	fmt.Printf("*** built heap: %.0f MB; (%d objects * %d bytes)\n",
+		float64(*heapsize)/1048576, numobjects, objsize)
+}
+
+func buildTree(objsize, size float64, depth int) (*Object, float64) {
+	calls[depth]++
+	x := &Object{}
+	numobjects++
+	subtreeSize := (size - objsize) / BranchingFactor
+	alloc := objsize
+	for i := 0; i < BranchingFactor && alloc < size; i++ {
+		c, n := buildTree(objsize, subtreeSize, depth+1)
+		x.child[i] = c
+		alloc += n
+	}
+	return x, alloc
+}
+
+func gc() {
+	runtime.GC()
+	runtime.ReadMemStats(&memstats)
+	pause := memstats.PauseTotalNs
+	inuse := memstats.Alloc
+	free := memstats.TotalAlloc - inuse
+	fmt.Printf("gc pause: %8.3f ms; collect: %8.0f MB; heapsize: %8.0f MB\n",
+		float64(pause-lastPauseNs)/1e6,
+		float64(free-lastFree)/1048576,
+		float64(inuse)/1048576)
+	lastPauseNs = pause
+	lastFree = free
+}
+
+func main() {
+	flag.Parse()
+	buildHeap()
+	runtime.GOMAXPROCS(*cpus)
+	runtime.ReadMemStats(&memstats)
+	lastPauseNs = memstats.PauseTotalNs
+	lastFree = memstats.TotalAlloc - memstats.Alloc
+	if *cpuprofile != "" {
+		f, err := os.Create(*cpuprofile)
+		if err != nil {
+			log.Fatal(err)
+		}
+		pprof.StartCPUProfile(f)
+		defer pprof.StopCPUProfile()
+	}
+	const N = 10
+	var t0 time.Time
+	for i := 0; i < N; i++ {
+		t0 = time.Now()
+		gc()
+	}
+	// Standard gotest benchmark output, collected by build dashboard.
+	gcstats("BenchmarkTree2", N, time.Now().Sub(t0))
+}