runtime: speed up stack copying

I was surprised to see readvarint show up in a cpu profile.

Use a few simple optimizations to speed up stack copying:

* Avoid making a copy of the cache.entries array or any of its elements.
* Use a shift instead of a signed division in stackmapdata.
* Change readvarint to return the number of bytes consumed
  rather than an updated slice.
* Make some minor optimizations to readvarint to help the compiler.
* Avoid called readvarint when the value fits in a single byte.

The first and last optimizations are the most significant,
although they all contribute a little.

Add a benchmark for stack copying that includes lots of different
functions in a recursive loop, to bust the cache.

This might speed up other runtime operations as well;
I only benchmarked stack copying.

name                old time/op  new time/op  delta
StackCopy-8         96.4ms ± 2%  82.7ms ± 1%  -14.24%  (p=0.000 n=20+19)
StackCopyNoCache-8   167ms ± 1%   131ms ± 1%  -21.58%  (p=0.000 n=20+20)

Change-Id: I13d5c455c65073c73b656acad86cf8e8e3c9807b
Reviewed-on: https://go-review.googlesource.com/43150
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Austin Clements <austin@google.com>

1 files changed, 172 insertions, 0 deletions

diff --git a/src/runtime/stack_test.go b/src/runtime/stack_test.go
index 965c4e6838..485e327c41 100644
--- a/src/runtime/stack_test.go
+++ b/src/runtime/stack_test.go
@@ -453,3 +453,175 @@ func count(n int) int {
 	}
 	return 1 + count(n-1)
 }
+
+func BenchmarkStackCopyNoCache(b *testing.B) {
+	c := make(chan bool)
+	for i := 0; i < b.N; i++ {
+		go func() {
+			count1(1000000)
+			c <- true
+		}()
+		<-c
+	}
+}
+
+func count1(n int) int {
+	if n == 0 {
+		return 0
+	}
+	return 1 + count2(n-1)
+}
+
+func count2(n int) int {
+	if n == 0 {
+		return 0
+	}
+	return 1 + count3(n-1)
+}
+
+func count3(n int) int {
+	if n == 0 {
+		return 0
+	}
+	return 1 + count4(n-1)
+}
+
+func count4(n int) int {
+	if n == 0 {
+		return 0
+	}
+	return 1 + count5(n-1)
+}
+
+func count5(n int) int {
+	if n == 0 {
+		return 0
+	}
+	return 1 + count6(n-1)
+}
+
+func count6(n int) int {
+	if n == 0 {
+		return 0
+	}
+	return 1 + count7(n-1)
+}
+
+func count7(n int) int {
+	if n == 0 {
+		return 0
+	}
+	return 1 + count8(n-1)
+}
+
+func count8(n int) int {
+	if n == 0 {
+		return 0
+	}
+	return 1 + count9(n-1)
+}
+
+func count9(n int) int {
+	if n == 0 {
+		return 0
+	}
+	return 1 + count10(n-1)
+}
+
+func count10(n int) int {
+	if n == 0 {
+		return 0
+	}
+	return 1 + count11(n-1)
+}
+
+func count11(n int) int {
+	if n == 0 {
+		return 0
+	}
+	return 1 + count12(n-1)
+}
+
+func count12(n int) int {
+	if n == 0 {
+		return 0
+	}
+	return 1 + count13(n-1)
+}
+
+func count13(n int) int {
+	if n == 0 {
+		return 0
+	}
+	return 1 + count14(n-1)
+}
+
+func count14(n int) int {
+	if n == 0 {
+		return 0
+	}
+	return 1 + count15(n-1)
+}
+
+func count15(n int) int {
+	if n == 0 {
+		return 0
+	}
+	return 1 + count16(n-1)
+}
+
+func count16(n int) int {
+	if n == 0 {
+		return 0
+	}
+	return 1 + count17(n-1)
+}
+
+func count17(n int) int {
+	if n == 0 {
+		return 0
+	}
+	return 1 + count18(n-1)
+}
+
+func count18(n int) int {
+	if n == 0 {
+		return 0
+	}
+	return 1 + count19(n-1)
+}
+
+func count19(n int) int {
+	if n == 0 {
+		return 0
+	}
+	return 1 + count20(n-1)
+}
+
+func count20(n int) int {
+	if n == 0 {
+		return 0
+	}
+	return 1 + count21(n-1)
+}
+
+func count21(n int) int {
+	if n == 0 {
+		return 0
+	}
+	return 1 + count22(n-1)
+}
+
+func count22(n int) int {
+	if n == 0 {
+		return 0
+	}
+	return 1 + count23(n-1)
+}
+
+func count23(n int) int {
+	if n == 0 {
+		return 0
+	}
+	return 1 + count1(n-1)
+}