runtime: Speed up heapBitsForObject

Optimized heapBitsForObject by special casing
objects whose size is a power of two. When a
span holding such objects is initialized I
added a mask that when &ed with an interior pointer
results in the base of the pointer. For the garbage
benchmark this resulted in CPU_CLK_UNHALTED in
heapBitsForObject going from 7.7% down to 5.9%
of the total, INST_RETIRED went from 12.2 -> 8.7.

Here are the benchmarks that were at lease plus or minus 1%.

benchmark                          old ns/op      new ns/op      delta
BenchmarkFmtFprintfString          249            221            -11.24%
BenchmarkFmtFprintfInt             247            223            -9.72%
BenchmarkFmtFprintfEmpty           76.5           69.6           -9.02%
BenchmarkBinaryTree17              4106631412     3744550160     -8.82%
BenchmarkFmtFprintfFloat           424            399            -5.90%
BenchmarkGoParse                   4484421        4242115        -5.40%
BenchmarkGobEncode                 8803668        8449107        -4.03%
BenchmarkFmtManyArgs               1494           1436           -3.88%
BenchmarkGobDecode                 10431051       10032606       -3.82%
BenchmarkFannkuch11                2591306713     2517400464     -2.85%
BenchmarkTimeParse                 361            371            +2.77%
BenchmarkJSONDecode                70620492       68830357       -2.53%
BenchmarkRegexpMatchMedium_1K      54693          53343          -2.47%
BenchmarkTemplate                  90008879       91929940       +2.13%
BenchmarkTimeFormat                380            387            +1.84%
BenchmarkRegexpMatchEasy1_32       111            113            +1.80%
BenchmarkJSONEncode                21359159       21007583       -1.65%
BenchmarkRegexpMatchEasy1_1K       603            613            +1.66%
BenchmarkRegexpMatchEasy0_32       127            129            +1.57%
BenchmarkFmtFprintfIntInt          399            393            -1.50%
BenchmarkRegexpMatchEasy0_1K       373            378            +1.34%

Change-Id: I78e297161026f8b5cc7507c965fd3e486f81ed29
Reviewed-on: https://go-review.googlesource.com/8980
Reviewed-by: Austin Clements <austin@google.com>

1 files changed, 14 insertions, 3 deletions

diff --git a/src/runtime/msize.go b/src/runtime/msize.go
index 9ba145dbf6..bc735beb42 100644
--- a/src/runtime/msize.go
+++ b/src/runtime/msize.go
@@ -215,14 +215,24 @@ func roundupsize(size uintptr) uintptr {
 // http://ridiculousfish.com/blog/posts/labor-of-division-episode-i.html
 // http://ridiculousfish.com/blog/posts/labor-of-division-episode-iii.html
 type divMagic struct {
-	shift  uint8
-	mul    uint32
-	shift2 uint8
+	shift    uint8
+	mul      uint32
+	shift2   uint8
+	baseMask uintptr
 }
 
 func computeDivMagic(d uint32) divMagic {
 	var m divMagic
 
+	// If the size is a power of two, heapBitsForObject can divide even faster by masking.
+	// Compute this mask.
+	if d&(d-1) == 0 {
+		// It is a power of 2 (assuming dinptr != 1)
+		m.baseMask = ^(uintptr(d) - 1)
+	} else {
+		m.baseMask = 0
+	}
+
 	// Compute pre-shift by factoring power of 2 out of d.
 	for d&1 == 0 {
 		m.shift++
@@ -239,5 +249,6 @@ func computeDivMagic(d uint32) divMagic {
 	}
 	m.mul = uint32(((1 << k) + d64 - 1) / d64) //  ⌈2^k / d⌉
 	m.shift2 = k
+
 	return m
 }