code review 5992055: runtime: preparation for parallel GC (issue 5992055)

[dvy...@google.com]

Reviewers: golang-dev_googlegroups.com,

Message:
Hello golan...@googlegroups.com,

I'd like you to review this change to
https://go.googlecode.com/hg/


Description:
runtime: preparation for parallel GC
make MHeap.allspans an array instead on a linked-list,
it's required for parallel for

benchmark old ns/op new ns/op delta

garbage.BenchmarkTree 494435529 487962705 -1.31%
garbage.BenchmarkTree-2 499652705 485358000 -2.86%
garbage.BenchmarkTree-4 468482117 454093117 -3.07%
garbage.BenchmarkTree-8 488533235 471872470 -3.41%
garbage.BenchmarkTree-16 507835176 492558470 -3.01%

garbage.BenchmarkTree2 31453900 31404300 -0.16%
garbage.BenchmarkTree2-2 21440600 21477000 +0.17%
garbage.BenchmarkTree2-4 10982000 11117400 +1.23%
garbage.BenchmarkTree2-8 7544700 7456700 -1.17%
garbage.BenchmarkTree2-16 7049500 6805700 -3.46%

garbage.BenchmarkParser 4448988000 4453264000 +0.10%
garbage.BenchmarkParser-2 4086045000 4057948000 -0.69%
garbage.BenchmarkParser-4 3677365000 3661246000 -0.44%
garbage.BenchmarkParser-8 3517253000 3540190000 +0.65%
garbage.BenchmarkParser-16 3506562000 3463478000 -1.23%

garbage.BenchmarkTreePause 20969784 21100238 +0.62%
garbage.BenchmarkTreePause-2 20215875 20139572 -0.38%
garbage.BenchmarkTreePause-4 17240709 16683624 -3.23%
garbage.BenchmarkTreePause-8 18196386 17639306 -3.06%
garbage.BenchmarkTreePause-16 20621158 20215056 -1.97%

garbage.BenchmarkTree2Pause 173992142 173872380 -0.07%
garbage.BenchmarkTree2Pause-2 131281904 131366666 +0.06%
garbage.BenchmarkTree2Pause-4 93484952 95109619 +1.74%
garbage.BenchmarkTree2Pause-8 88950523 86533333 -2.72%
garbage.BenchmarkTree2Pause-16 86071238 84089190 -2.30%

garbage.BenchmarkParserPause 135815000 135255952 -0.41%
garbage.BenchmarkParserPause-2 92691523 91451428 -1.34%
garbage.BenchmarkParserPause-4 53392190 51611904 -3.33%
garbage.BenchmarkParserPause-8 36059523 35116666 -2.61%
garbage.BenchmarkParserPause-16 30174300 27340600 -9.39%

garbage.BenchmarkTreeLastPause 28420000 29142000 +2.54%
garbage.BenchmarkTreeLastPause-2 23514000 26779000 +13.89%
garbage.BenchmarkTreeLastPause-4 21773000 18660000 -14.30%
garbage.BenchmarkTreeLastPause-8 24072000 21276000 -11.62%
garbage.BenchmarkTreeLastPause-16 25149000 28541000 +13.49%

garbage.BenchmarkTree2LastPause 314491000 313982000 -0.16%
garbage.BenchmarkTree2LastPause-2 214363000 214715000 +0.16%
garbage.BenchmarkTree2LastPause-4 109778000 111115000 +1.22%
garbage.BenchmarkTree2LastPause-8 75390000 74522000 -1.15%
garbage.BenchmarkTree2LastPause-16 70333000 67880000 -3.49%

garbage.BenchmarkParserLastPause 327247000 326815000 -0.13%
garbage.BenchmarkParserLastPause-2 217039000 212529000 -2.08%
garbage.BenchmarkParserLastPause-4 119722000 111535000 -6.84%
garbage.BenchmarkParserLastPause-8 70806000 69613000 -1.68%
garbage.BenchmarkParserLastPause-16 62813000 48009000 -23.57%

Please review this at http://codereview.appspot.com/5992055/

Affected files:
M src/pkg/runtime/malloc.h
M src/pkg/runtime/mgc0.c
M src/pkg/runtime/mheap.c


Index: src/pkg/runtime/malloc.h
===================================================================
--- a/src/pkg/runtime/malloc.h
+++ b/src/pkg/runtime/malloc.h
@@ -306,7 +306,6 @@
{
MSpan *next; // in a span linked list
MSpan *prev; // in a span linked list
- MSpan *allnext; // in the list of all spans
PageID start; // starting page number
uintptr npages; // number of pages in span
MLink *freelist; // list of free objects
@@ -351,7 +350,9 @@
Lock;
MSpan free[MaxMHeapList]; // free lists of given length
MSpan large; // free lists length >= MaxMHeapList
- MSpan *allspans;
+ MSpan **allspans;
+ uint32 nspan;
+ uint32 nspancap;

// span lookup
MSpan *map[1<<MHeapMap_Bits];
Index: src/pkg/runtime/mgc0.c
===================================================================
--- a/src/pkg/runtime/mgc0.c
+++ b/src/pkg/runtime/mgc0.c
@@ -123,7 +123,7 @@
Note alldone;
Lock markgate;
Lock sweepgate;
- MSpan *spans;
+ uint32 spanidx;

Lock;
byte *chunk;
@@ -726,16 +726,18 @@
static void
sweep(void)
{
- MSpan *s;
+ MSpan *s, **allspans;
int64 now;
+ uint32 spanidx, nspan;

now = runtime·nanotime();
+ nspan = runtime·mheap.nspan;
+ allspans = runtime·mheap.allspans;
for(;;) {
- s = work.spans;
- if(s == nil)
+ spanidx = runtime·xadd(&work.spanidx, 1) - 1;
+ if(spanidx >= nspan)
break;
- if(!runtime·casp(&work.spans, s, s->allnext))
- continue;
+ s = allspans[spanidx];

// Stamp newly unused spans. The scavenger will use that
// info to potentially give back some pages to the OS.
@@ -967,7 +969,7 @@
mark(debug_scanblock);
t1 = runtime·nanotime();

- work.spans = runtime·mheap.allspans;
+ work.spanidx = 0;
runtime·unlock(&work.sweepgate); // let the helpers in
sweep();
if(work.nproc > 1)
Index: src/pkg/runtime/mheap.c
===================================================================
--- a/src/pkg/runtime/mheap.c
+++ b/src/pkg/runtime/mheap.c
@@ -27,11 +27,24 @@
{
MHeap *h;
MSpan *s;
+ MSpan **all;
+ uint32 cap;

h = vh;
s = (MSpan*)p;
- s->allnext = h->allspans;
- h->allspans = s;
+ if(h->nspan >= h->nspancap) {
+ cap = 64*1024/sizeof(MSpan*);
+ if(cap < h->nspancap*3/2)
+ cap = h->nspancap*3/2;
+ all = (MSpan**)runtime·SysAlloc(cap*sizeof(MSpan*));
+ if(h->allspans) {
+ runtime·memmove(all, h->allspans, h->nspancap*sizeof(MSpan*));
+ runtime·SysFree(h->allspans, h->nspancap*sizeof(MSpan*));
+ }
+ h->allspans = all;
+ h->nspancap = cap;
+ }
+ h->allspans[h->nspan++] = s;
}

// Initialize the heap; fetch memory using alloc.

[r...@golang.org]

LGTM

http://codereview.appspot.com/5992055/diff/6001/src/pkg/runtime/mheap.c
File src/pkg/runtime/mheap.c (right):

http://codereview.appspot.com/5992055/diff/6001/src/pkg/runtime/mheap.c#newcode36
src/pkg/runtime/mheap.c:36: cap = 64*1024/sizeof(MSpan*);
Please use sizeof all[0] instead of sizeof(MSpan*) throughout,
so that I don't have to think about whether that's the right type.

There are 4 here to change.

http://codereview.appspot.com/5992055/

[dvy...@google.com]

Hello r...@golang.org (cc: golan...@googlegroups.com),

Please take another look.

http://codereview.appspot.com/5992055/

[dvy...@google.com]

What does it mean when you say LGTM and write some comments? Does it
mean that I may address the comments and submit w/o one more review? Or
it's better to wait for one more review? Sometimes it's a matter of an
additional day and an additional client.

http://codereview.appspot.com/5992055/

[Rob 'Commander' Pike]

It means: "Looks good to me after these changes. Make the changes and submit". Another round is not necessary unless you disagree with the changes.

-rob

[dvy...@google.com]

*** Submitted as
http://code.google.com/p/go/source/detail?r=512073e3b7f2 ***

R=rsc, r
CC=golang-dev
http://codereview.appspot.com/5992055

http://codereview.appspot.com/5992055/