From 9dc6764d3c780cf302a8a7521d27e61102d701fc Mon Sep 17 00:00:00 2001
From: Keith Randall <khr@golang.org>
Date: Tue, 14 Oct 2014 09:22:47 -0700
Subject: [PATCH] runtime: a few optimizations of scanblock.

Lowers gc pause time by 5-10% on test/bench/garbage

LGTM=rsc, dvyukov
R=rsc, dvyukov
CC=golang-codereviews
https://golang.org/cl/157810043
---
 src/runtime/mgc0.c | 35 ++++++++++++++++++-----------------
 1 file changed, 18 insertions(+), 17 deletions(-)

diff --git a/src/runtime/mgc0.c b/src/runtime/mgc0.c
index 0de7b1bf4a..05cabe7085 100644
--- a/src/runtime/mgc0.c
+++ b/src/runtime/mgc0.c
@@ -215,8 +215,7 @@ scanblock(byte *b, uintptr n, byte *ptrmask)
 			for(i = 0; i < nelem(scanbuf); i++) {
 				b = scanbuf[scanbufpos];
 				scanbuf[scanbufpos++] = nil;
-				if(scanbufpos == nelem(scanbuf))
-					scanbufpos = 0;
+				scanbufpos %= nelem(scanbuf);
 				if(b != nil) {
 					n = arena_used - b; // scan until bitBoundary or BitsDead
 					ptrmask = nil; // use GC bitmap for pointer info
@@ -267,10 +266,13 @@ scanblock(byte *b, uintptr n, byte *ptrmask)
 					break;
 				// Consult GC bitmap.
 				bits = *ptrbitp;
-				if((((uintptr)b+i)%(PtrSize*wordsPerBitmapByte)) != 0) {
-					ptrbitp--;
-					bits >>= gcBits;
-				}
+
+				if(wordsPerBitmapByte != 2)
+					runtime·throw("alg doesn't work for wordsPerBitmapByte != 2");
+				j = ((uintptr)b+i)/PtrSize & 1;
+				ptrbitp -= j;
+				bits >>= gcBits*j;
+
 				if((bits&bitBoundary) != 0 && i != 0)
 					break; // reached beginning of the next object
 				bits = (bits>>2)&BitsMask;
@@ -293,10 +295,9 @@ scanblock(byte *b, uintptr n, byte *ptrmask)
 			// Find the next pair of bits.
 			if(ptrmask == nil) {
 				bits = *ptrbitp;
-				if((((uintptr)b+i)%(PtrSize*wordsPerBitmapByte)) == 0) {
-					ptrbitp--;
-					bits >>= gcBits;
-				}
+				j = ((uintptr)b+i+PtrSize)/PtrSize & 1;
+				ptrbitp -= j;
+				bits >>= gcBits*j;
 				bits = (bits>>2)&BitsMask;
 			} else
 				bits = (ptrmask[((i+PtrSize)/PtrSize)/4]>>((((i+PtrSize)/PtrSize)%4)*BitsPerPointer))&BitsMask;
@@ -328,12 +329,13 @@ scanblock(byte *b, uintptr n, byte *ptrmask)
 			// Check if it points into heap.
 			if(obj == nil)
 				continue;
-			if((uintptr)obj < PhysPageSize) {
-				s = nil;
-				goto badobj;
-			}
-			if(obj < arena_start || obj >= arena_used)
+			if(obj < arena_start || obj >= arena_used) {
+				if((uintptr)obj < PhysPageSize) {
+					s = nil;
+					goto badobj;
+				}
 				continue;
+			}
 			// Mark the object.
 			obj = (byte*)((uintptr)obj & ~(PtrSize-1));
 			off = (uintptr*)obj - (uintptr*)arena_start;
@@ -442,8 +444,7 @@ scanblock(byte *b, uintptr n, byte *ptrmask)
 			PREFETCH(obj);
 			p = scanbuf[scanbufpos];
 			scanbuf[scanbufpos++] = obj;
-			if(scanbufpos == nelem(scanbuf))
-				scanbufpos = 0;
+			scanbufpos %= nelem(scanbuf);
 			if(p == nil)
 				continue;
 
-- 
2.48.1