runtime: make garbage collector faster by deleting code

Suggested by Sanjay Ghemawat.  5-20% faster depending
on the benchmark.

Add tree2 garbage benchmark.
Update other garbage benchmarks to build again.

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

6 files changed, 128 insertions, 42 deletions

diff --git a/test/bench/garbage/Makefile b/test/bench/garbage/Makefile
index cf6568f9e..8002a2017 100644
--- a/test/bench/garbage/Makefile
+++ b/test/bench/garbage/Makefile
@@ -8,6 +8,7 @@ ALL=\
 	parser\
 	peano\
 	tree\
+	tree2\
 
 all: $(addsuffix .out, $(ALL))
 
diff --git a/test/bench/garbage/parser.go b/test/bench/garbage/parser.go
index d0f4e09ba..9e15f6c0f 100644
--- a/test/bench/garbage/parser.go
+++ b/test/bench/garbage/parser.go
@@ -24,15 +24,15 @@ import (
 
 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 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 {
+func isPkgFile(dir os.FileInfo) bool {
 	return isGoFile(dir) &&
-		!strings.HasSuffix(dir.Name, "_test.go") // ignore test files
+		!strings.HasSuffix(dir.Name(), "_test.go") // ignore test files
 }
 
 func pkgName(filename string) string {
@@ -49,7 +49,7 @@ func parseDir(dirpath string) map[string]*ast.Package {
 	_, pkgname := path.Split(dirpath)
 
 	// filter function to select the desired .go files
-	filter := func(d *os.FileInfo) bool {
+	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
@@ -57,7 +57,7 @@ func parseDir(dirpath string) map[string]*ast.Package {
 			// found" errors.
 			// Additionally, accept the special package name
 			// fakePkgName if we are looking at cmd documentation.
-			name := pkgName(dirpath + "/" + d.Name)
+			name := pkgName(dirpath + "/" + d.Name())
 			return name == pkgname
 		}
 		return false
@@ -82,7 +82,7 @@ func main() {
 	flag.Parse()
 
 	var lastParsed []map[string]*ast.Package
-	var t0 int64
+	var t0 time.Time
 	pkgroot := runtime.GOROOT() + "/src/pkg/"
 	for pass := 0; pass < 2; pass++ {
 		// Once the heap is grown to full size, reset counters.
@@ -91,7 +91,7 @@ func main() {
 		// the average look much better than it actually is.
 		st.NumGC = 0
 		st.PauseTotalNs = 0
-		t0 = time.Nanoseconds()
+		t0 = time.Now()
 
 		for i := 0; i < *n; i++ {
 			parsed := make([]map[string]*ast.Package, *p)
@@ -105,7 +105,7 @@ func main() {
 		runtime.GC()
 		runtime.GC()
 	}
-	t1 := time.Nanoseconds()
+	t1 := time.Now()
 
 	fmt.Printf("Alloc=%d/%d Heap=%d Mallocs=%d PauseTime=%.3f/%d = %.3f\n",
 		st.Alloc, st.TotalAlloc,
@@ -120,7 +120,7 @@ func main() {
 		}
 	*/
 	// Standard gotest benchmark output, collected by build dashboard.
-	gcstats("BenchmarkParser", *n, t1-t0)
+	gcstats("BenchmarkParser", *n, t1.Sub(t0))
 
 	if *serve != "" {
 		log.Fatal(http.ListenAndServe(*serve, nil))
@@ -130,18 +130,17 @@ func main() {
 
 var packages = []string{
 	"archive/tar",
-	"asn1",
-	"big",
+	"encoding/asn1",
+	"math/big",
 	"bufio",
 	"bytes",
-	"cmath",
+	"math/cmplx",
 	"compress/flate",
 	"compress/gzip",
 	"compress/zlib",
 	"container/heap",
 	"container/list",
 	"container/ring",
-	"container/vector",
 	"crypto/aes",
 	"crypto/blowfish",
 	"crypto/hmac",
@@ -161,16 +160,14 @@ var packages = []string{
 	"debug/macho",
 	"debug/elf",
 	"debug/gosym",
-	"ebnf",
+	"exp/ebnf",
 	"encoding/ascii85",
 	"encoding/base64",
 	"encoding/binary",
 	"encoding/git85",
 	"encoding/hex",
 	"encoding/pem",
-	"exec",
-	"exp/datafmt",
-	"expvar",
+	"os/exec",
 	"flag",
 	"fmt",
 	"go/ast",
@@ -179,18 +176,18 @@ var packages = []string{
 	"go/printer",
 	"go/scanner",
 	"go/token",
-	"gob",
+	"encoding/gob",
 	"hash",
 	"hash/adler32",
 	"hash/crc32",
 	"hash/crc64",
-	"http",
+	"net/http",
 	"image",
 	"image/jpeg",
 	"image/png",
 	"io",
 	"io/ioutil",
-	"json",
+	"encoding/json",
 	"log",
 	"math",
 	"mime",
@@ -199,29 +196,29 @@ var packages = []string{
 	"os/signal",
 	"patch",
 	"path",
-	"rand",
+	"math/rand",
 	"reflect",
 	"regexp",
-	"rpc",
+	"net/rpc",
 	"runtime",
-	"scanner",
+	"text/scanner",
 	"sort",
-	"smtp",
+	"net/smtp",
 	"strconv",
 	"strings",
 	"sync",
 	"syscall",
-	"syslog",
-	"tabwriter",
-	"template",
+	"log/syslog",
+	"text/tabwriter",
+	"text/template",
 	"testing",
 	"testing/iotest",
 	"testing/quick",
 	"testing/script",
 	"time",
 	"unicode",
-	"utf8",
-	"utf16",
+	"unicode/utf8",
+	"unicode/utf16",
 	"websocket",
-	"xml",
+	"encoding/xml",
 }
diff --git a/test/bench/garbage/peano.go b/test/bench/garbage/peano.go
index 231359688..f1ad6ed69 100644
--- a/test/bench/garbage/peano.go
+++ b/test/bench/garbage/peano.go
@@ -108,15 +108,14 @@ func verify() {
 // -------------------------------------
 // Factorial
 
-
 func main() {
-	t0 := time.Nanoseconds()
+	t0 := time.Now()
 	verify()
 	for i := 0; i <= 9; i++ {
 		print(i, "! = ", count(fact(gen(i))), "\n")
 	}
 	runtime.GC()
-	t1 := time.Nanoseconds()
+	t1 := time.Now()
 
-	gcstats("BenchmarkPeano", 1, t1-t0)
+	gcstats("BenchmarkPeano", 1, t1.Sub(t0))
 }
diff --git a/test/bench/garbage/stats.go b/test/bench/garbage/stats.go
index aa9db1dbc..985e7eaf5 100644
--- a/test/bench/garbage/stats.go
+++ b/test/bench/garbage/stats.go
@@ -8,12 +8,13 @@ import (
 	"fmt"
 	"runtime"
 	"sort"
+	"time"
 )
 
-func gcstats(name string, n int, t int64) {
+func gcstats(name string, n int, t time.Duration) {
 	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.%s %d %d ns/op\n", name, n, t.Nanoseconds()/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)
diff --git a/test/bench/garbage/tree.go b/test/bench/garbage/tree.go
index c5eae9760..0a3ec234d 100644
--- a/test/bench/garbage/tree.go
+++ b/test/bench/garbage/tree.go
@@ -68,7 +68,7 @@ const minDepth = 4
 func main() {
 	flag.Parse()
 
-	t0 := time.Nanoseconds()
+	t0 := time.Now()
 
 	maxDepth := *n
 	if minDepth+2 > *n {
@@ -93,8 +93,8 @@ func main() {
 	}
 	fmt.Printf("long lived tree of depth %d\t check: %d\n", maxDepth, longLivedTree.itemCheck())
 
-	t1 := time.Nanoseconds()
+	t1 := time.Now()
 
 	// Standard gotest benchmark output, collected by build dashboard.
-	gcstats("BenchmarkTree", *n, t1-t0)
+	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 000000000..6d78f72c5
--- /dev/null
+++ b/test/bench/garbage/tree2.go
@@ -0,0 +1,88 @@
+// 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"
+	"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
+)
+
+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.UpdateMemStats()
+	pause := runtime.MemStats.PauseTotalNs
+	inuse := runtime.MemStats.Alloc
+	free := runtime.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.UpdateMemStats()
+	lastPauseNs = runtime.MemStats.PauseTotalNs
+	lastFree = runtime.MemStats.TotalAlloc - runtime.MemStats.Alloc
+	if *cpuprofile != "" {
+		f, err := os.Create(*cpuprofile)
+		if err != nil {
+			log.Fatal(err)
+		}
+		pprof.StartCPUProfile(f)
+		defer pprof.StopCPUProfile()
+	}
+	for i := 0; i < 10; i++ {
+		gc()
+	}
+}