runtime: faster version of findfunc

Use a lookup table to find the function which contains a pc.  It is
faster than the old binary search.  findfunc is used primarily for
stack copying and garbage collection.

benchmark              old ns/op     new ns/op     delta
BenchmarkStackCopy     294746596     255400980     -13.35%

(findfunc is one of several tasks done by stack copy, the findfunc
time itself is about 2.5x faster.)

The lookup table is built at link time.  The table grows the binary
size by about 0.5% of the text segment.

We impose a lower limit of 16 bytes on any function, which should not
have much of an impact.  (The real constraint required is <=256
functions in every 4096 bytes, but 16 bytes/function is easier to
implement.)

Change-Id: Ic315b7a2c83e1f7203cd2a50e5d21a822e18fdca
Reviewed-on: https://go-review.googlesource.com/2097
Reviewed-by: Russ Cox <rsc@golang.org>

1 files changed, 36 insertions, 21 deletions

diff --git a/src/runtime/symtab.go b/src/runtime/symtab.go
index 305d54588d..db20ab11e1 100644
--- a/src/runtime/symtab.go
+++ b/src/runtime/symtab.go
@@ -34,7 +34,9 @@ var (
 	ftab      []functab
 	filetab   []uint32
 
-	pclntab, epclntab struct{} // linker symbols
+	pclntab, epclntab, findfunctab struct{} // linker symbols
+
+	minpc, maxpc uintptr
 )
 
 type functab struct {
@@ -42,6 +44,22 @@ type functab struct {
 	funcoff uintptr
 }
 
+const minfunc = 16 // minimum function size
+const pcbucketsize = 256*minfunc // size of bucket in the pc->func lookup table
+
+// findfunctab is an array of these structures.
+// Each bucket represents 4096 bytes of the text segment.
+// Each subbucket represents 256 bytes of the text segment.
+// To find a function given a pc, locate the bucket and subbucket for
+// that pc.  Add together the idx and subbucket value to obtain a
+// function index.  Then scan the functab array starting at that
+// index to find the target function.
+// This table uses 20 bytes for every 4096 bytes of code, or ~0.5% overhead.
+type findfuncbucket struct {
+	idx uint32
+	subbuckets [16]byte
+}
+
 func symtabinit() {
 	// See golang.org/s/go12symtab for header: 0xfffffffb,
 	// two zero bytes, a byte giving the PC quantum,
@@ -96,6 +114,9 @@ func symtabinit() {
 	sp.cap = 1
 	sp.len = int(filetab[0])
 	sp.cap = sp.len
+
+	minpc = ftab[0].entry
+	maxpc = ftab[nftab].entry
 }
 
 // FuncForPC returns a *Func describing the function that contains the
@@ -126,32 +147,26 @@ func (f *Func) FileLine(pc uintptr) (file string, line int) {
 }
 
 func findfunc(pc uintptr) *_func {
-	if len(ftab) == 0 {
+	if pc < minpc || pc >= maxpc {
 		return nil
 	}
+	const nsub = uintptr(len(findfuncbucket{}.subbuckets))
 
-	if pc < ftab[0].entry || pc >= ftab[len(ftab)-1].entry {
-		return nil
-	}
+	x := pc - minpc
+	b := x / pcbucketsize
+	i := x % pcbucketsize / (pcbucketsize/nsub)
 
-	// binary search to find func with entry <= pc.
-	lo := 0
-	nf := len(ftab) - 1 // last entry is sentinel
-	for nf > 0 {
-		n := nf / 2
-		f := &ftab[lo+n]
-		if f.entry <= pc && pc < ftab[lo+n+1].entry {
-			return (*_func)(unsafe.Pointer(&pclntable[f.funcoff]))
-		} else if pc < f.entry {
-			nf = n
-		} else {
-			lo += n + 1
-			nf -= n + 1
-		}
+	ffb := (*findfuncbucket)(add(unsafe.Pointer(&findfunctab), b * unsafe.Sizeof(findfuncbucket{})))
+	idx := ffb.idx + uint32(ffb.subbuckets[i])
+	if pc < ftab[idx].entry {
+		throw("findfunc: bad findfunctab entry")
 	}
 
-	throw("findfunc: binary search failed")
-	return nil
+	// linear search to find func with pc >= entry.
+	for ftab[idx+1].entry <= pc {
+		idx++
+	}
+	return (*_func)(unsafe.Pointer(&pclntable[ftab[idx].funcoff]))
 }
 
 func pcvalue(f *_func, off int32, targetpc uintptr, strict bool) int32 {