runtime: make span map sparse

This splits the span map into separate chunks for every 64MB of the
heap. The span map chunks now live in the same indirect structure as
the bitmap.

Updates #10460.

This causes a slight improvement in compilebench and the x/benchmarks
garbage benchmark. I'm not sure why it improves performance.

name       old time/op     new time/op     delta
Template       185ms ± 1%      184ms ± 1%    ~            (p=0.315 n=9+10)
Unicode       86.9ms ± 1%     86.9ms ± 3%    ~            (p=0.356 n=9+10)
GoTypes        602ms ± 1%      599ms ± 0%  -0.59%         (p=0.002 n=9+10)
Compiler       2.89s ± 0%      2.87s ± 1%  -0.50%          (p=0.003 n=9+9)
SSA            7.25s ± 0%      7.29s ± 1%    ~            (p=0.400 n=9+10)
Flate          118ms ± 1%      118ms ± 2%    ~            (p=0.065 n=10+9)
GoParser       147ms ± 2%      147ms ± 1%    ~            (p=0.549 n=10+9)
Reflect        403ms ± 1%      401ms ± 1%  -0.47%         (p=0.035 n=9+10)
Tar            176ms ± 1%      175ms ± 1%  -0.59%         (p=0.013 n=10+9)
XML            211ms ± 1%      209ms ± 1%  -0.83%        (p=0.011 n=10+10)

(https://perf.golang.org/search?q=upload:20171231.1)

name                       old time/op  new time/op  delta
Garbage/benchmem-MB=64-12  2.24ms ± 1%  2.23ms ± 1%  -0.36%  (p=0.001 n=20+19)

(https://perf.golang.org/search?q=upload:20171231.2)

Change-Id: I2563f8704ab9812434947faf293c5327f9b0d07a
Reviewed-on: https://go-review.googlesource.com/85885
Run-TryBot: Austin Clements <austin@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Rick Hudson <rlh@golang.org>

1 files changed, 6 insertions, 10 deletions

diff --git a/src/runtime/malloc.go b/src/runtime/malloc.go
index 4562e82c37..5584d7ddef 100644
--- a/src/runtime/malloc.go
+++ b/src/runtime/malloc.go
@@ -187,6 +187,8 @@ const (
 	// heapArenaBitmapBytes is the size of each heap arena's bitmap.
 	heapArenaBitmapBytes = heapArenaBytes / (sys.PtrSize * 8 / 2)
 
+	pagesPerArena = heapArenaBytes / pageSize
+
 	// Max number of threads to run garbage collection.
 	// 2, 3, and 4 are all plausible maximums depending
 	// on the hardware details of the machine. The garbage
@@ -284,10 +286,6 @@ func mallocinit() {
 	var p, pSize uintptr
 	var reserved bool
 
-	// The spans array holds one *mspan per _PageSize of arena.
-	var spansSize uintptr = (_MaxMem + 1) / _PageSize * sys.PtrSize
-	spansSize = round(spansSize, _PageSize)
-
 	// Set up the allocation arena, a contiguous area of memory where
 	// allocated data will be found.
 	if sys.PtrSize == 8 {
@@ -318,7 +316,7 @@ func mallocinit() {
 		// translation buffers, the user address space is limited to 39 bits
 		// On darwin/arm64, the address space is even smaller.
 		arenaSize := round(_MaxMem, _PageSize)
-		pSize = spansSize + arenaSize + _PageSize
+		pSize = arenaSize + _PageSize
 		for i := 0; i <= 0x7f; i++ {
 			switch {
 			case GOARCH == "arm64" && GOOS == "darwin":
@@ -377,7 +375,7 @@ func mallocinit() {
 			// away from the running binary image and then round up
 			// to a MB boundary.
 			p = round(firstmoduledata.end+(1<<18), 1<<20)
-			pSize = spansSize + arenaSize + _PageSize
+			pSize = arenaSize + _PageSize
 			if p <= procBrk && procBrk < p+pSize {
 				// Move the start above the brk,
 				// leaving some room for future brk
@@ -400,8 +398,6 @@ func mallocinit() {
 	p1 := round(p, _PageSize)
 	pSize -= p1 - p
 
-	spansStart := p1
-	p1 += spansSize
 	if sys.PtrSize == 4 {
 		// Set arena_start such that we can accept memory
 		// reservations located anywhere in the 4GB virtual space.
@@ -415,7 +411,7 @@ func mallocinit() {
 	mheap_.arena_reserved = reserved
 
 	if mheap_.arena_start&(_PageSize-1) != 0 {
-		println("bad pagesize", hex(p), hex(p1), hex(spansSize), hex(_PageSize), "start", hex(mheap_.arena_start))
+		println("bad pagesize", hex(p), hex(p1), hex(_PageSize), "start", hex(mheap_.arena_start))
 		throw("misrounded allocation in mallocinit")
 	}
 
@@ -427,7 +423,7 @@ func mallocinit() {
 	}
 
 	// Initialize the rest of the allocator.
-	mheap_.init(spansStart, spansSize)
+	mheap_.init()
 	_g_ := getg()
 	_g_.m.mcache = allocmcache()
 }