code review 4641082: runtime: parallelize garbage collector mark + sweep

runtime: parallelize garbage collector mark + sweep

Running test/garbage/parser.out.

On a 4-core Lenovo X201s (Linux):
31.12u 0.60s 31.74r 	 1 cpu, no atomics
32.27u 0.58s 32.86r 	 1 cpu, atomic instructions
33.04u 0.83s 27.47r 	 2 cpu

On a 16-core Xeon (Linux):
33.08u 0.65s 33.80r 	 1 cpu, no atomics
34.87u 1.12s 29.60r 	 2 cpu
36.00u 1.87s 28.43r 	 3 cpu
36.46u 2.34s 27.10r 	 4 cpu
38.28u 3.85s 26.92r 	 5 cpu
37.72u 5.25s 26.73r	 6 cpu
39.63u 7.11s 26.95r	 7 cpu
39.67u 8.10s 26.68r	 8 cpu

On a 2-core MacBook Pro Core 2 Duo 2.26 (circa 2009, MacBookPro5,5):
39.43u 1.45s 41.27r 	 1 cpu, no atomics
43.98u 2.95s 38.69r 	 2 cpu

On a 2-core Mac Mini Core 2 Duo 1.83 (circa 2008; Macmini2,1):
48.81u 2.12s 51.76r 	 1 cpu, no atomics
57.15u 4.72s 51.54r 	 2 cpu

The handoff algorithm is really only good for two cores.
Beyond that we will need to so something more sophisticated,
like have each core hand off to the next one, around a circle.
Even so, the code is a good checkpoint; for now we'll limit the
number of gc procs to at most 2.

[rsc, 2011-09-06 18:01:59]

Hello dvyukov (cc: golang-dev@googlegroups.com),

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

[rsc, 2011-09-06 18:02:27]

I would appreciate some advice about the spinning
algorithm.  It's obviously just a giant hack right now.

[dvyukov, 2011-09-07 11:10:50]

http://codereview.appspot.com/4641082/diff/35003/src/pkg/runtime/mgc0.c
File src/pkg/runtime/mgc0.c (right):

http://codereview.appspot.com/4641082/diff/35003/src/pkg/runtime/mgc0.c#newco...
src/pkg/runtime/mgc0.c:54: static uint64 nlookup;
Ultimately we want the statistics to be distributed (M local). However, it may
easily go into a separate CL. Whatever way you prefer.
If you prefer to not do it here, please add a TODO so it don't lost if we don't
do it in a near future.

http://codereview.appspot.com/4641082/diff/35003/src/pkg/runtime/mgc0.c#newco...
src/pkg/runtime/mgc0.c:421: runtime·printf("found unmarked block %p in %p\n",
obj, vp+i);
remove trailing tabs

http://codereview.appspot.com/4641082/diff/35003/src/pkg/runtime/mgc0.c#newco...
src/pkg/runtime/mgc0.c:531: if(runtime·casp(&work.full, b1, b1->next)) {
I think it is a subject to ABA problem.

http://codereview.appspot.com/4641082/diff/35003/src/pkg/runtime/mgc0.c#newco...
src/pkg/runtime/mgc0.c:694: scan(nil, 0);
Why is it placed before markfin? Don't we want it to be after markfin?

http://codereview.appspot.com/4641082/diff/35003/src/pkg/runtime/mgc0.c#newco...
src/pkg/runtime/mgc0.c:772: finq = f;
finq must be protected by a mutex or something.

http://codereview.appspot.com/4641082/diff/35003/src/pkg/runtime/mgc0.c#newco...
src/pkg/runtime/mgc0.c:946: if(work.ndone == work.nproc-1)
I think a better way to do the wait is as follows.
Create a dedicated semaphore. A helper thread that sets ndone==nproc-1 releases
the semaphore. Main thread waits on the semaphore (if nprocs!=1).

http://codereview.appspot.com/4641082/diff/35003/src/pkg/runtime/proc.c
File src/pkg/runtime/proc.c (right):

http://codereview.appspot.com/4641082/diff/35003/src/pkg/runtime/proc.c#newco...
src/pkg/runtime/proc.c:624: while(n+1 < max && (m = mget(nil)) != nil) {
if we set max to 2, after max-- it's 1
n is initially 0
so condition "n+1 < max" seem to be always false

http://codereview.appspot.com/4641082/diff/35003/src/pkg/runtime/proc.c#newco...
src/pkg/runtime/proc.c:625: runtime·sched.mhead = m->schedlink;
What does it mean? mhead is already updated by mget()

http://codereview.appspot.com/4641082/diff/35003/src/pkg/runtime/proc.c#newco...
src/pkg/runtime/proc.c:626: runtime·sched.mwait--;
mwait is also already updated by mget()

http://codereview.appspot.com/4641082/diff/35003/src/pkg/runtime/runtime.h
File src/pkg/runtime/runtime.h (right):

http://codereview.appspot.com/4641082/diff/35003/src/pkg/runtime/runtime.h#ne...
src/pkg/runtime/runtime.h:491: void	runtime·startm(void);
This seems to be unnecessary here.

[dvyukov, 2011-09-07 13:58:23]

http://codereview.appspot.com/4641082/diff/35003/src/pkg/runtime/mgc0.c
File src/pkg/runtime/mgc0.c (right):

http://codereview.appspot.com/4641082/diff/35003/src/pkg/runtime/mgc0.c#newco...
src/pkg/runtime/mgc0.c:242: if(nobj > 0 && (localneed = work.need) != nil &&
runtime·casp(&work.need, localneed, nil)) {
The sufficient condition to fall to slow path is just:
if(work.need != nil)
  handoffwork();
Please, move everything else to a separate function.

http://codereview.appspot.com/4641082/diff/35003/src/pkg/runtime/mgc0.c#newco...
src/pkg/runtime/mgc0.c:245: *localneed = *bp;
I think we need to hand off more work here. One block is a way to small to
"bootstrap" another worker thread. The block can be a 8-byte block w/o any
pointers.

http://codereview.appspot.com/4641082/diff/35003/src/pkg/runtime/mgc0.c#newco...
src/pkg/runtime/mgc0.c:547: for(i=900;; i++) {  // spin loop
What I don't like in the work-requesting scheme is that in includes two
consecutive spin waits, it increases latency and especially untolerant to more
than one helper thread. Moreover, while a thread waits for his work request to
be satisfied, another thread can offload a whole full block to the global work
queue.
I think a better scheme is as follows.
Idle thread increments nwait and then spins on (nwait!=nproc && work.full==0).
If it notices that work.full!=0, it decrements nwait and tries to pop work.full.
On fast path in scanblock threads check nwait!=0, if it's the case and
work.full==nil, split current block and put half to work.full.

[rsc, 2011-09-23 14:35:09]

On Wed, Sep 7, 2011 at 09:58,  <dvyukov@google.com> wrote:
> I think we need to hand off more work here. One block is a way to small
> to "bootstrap" another worker thread. The block can be a 8-byte block
> w/o any pointers.

If it's on the list, it has pointers.

[dvyukov, 2011-09-23 21:00:57]

On 2011/09/23 14:35:09, rsc wrote:
> On Wed, Sep 7, 2011 at 09:58,  <mailto:dvyukov@google.com> wrote:
> > I think we need to hand off more work here. One block is a way to small
> > to "bootstrap" another worker thread. The block can be a 8-byte block
> > w/o any pointers.
> 
> If it's on the list, it has pointers.

Do you mean FlagNoPointers? It is not set for things like struct { x, y, z, int
}.
Anyway, in work-stealing/requesting schedulers you generally want to
steal/request 1/2 (or at least 1/something) of the available work.

[rsc, 2011-09-26 16:46:04]

Hello dvyukov@google.com (cc: golang-dev@googlegroups.com),

Please take another look.

[dvyukov, 2011-09-27 17:57:32]

http://codereview.appspot.com/4641082/diff/59001/src/pkg/runtime/malloc.h
File src/pkg/runtime/malloc.h (right):

http://codereview.appspot.com/4641082/diff/59001/src/pkg/runtime/malloc.h#new...
src/pkg/runtime/malloc.h:129: MaxGcproc = 64,
Don't we want to still limit it to 2/4?

[dvyukov, 2011-09-27 18:17:16]

http://codereview.appspot.com/4641082/diff/59001/src/pkg/runtime/mgc0.c
File src/pkg/runtime/mgc0.c (right):

http://codereview.appspot.com/4641082/diff/59001/src/pkg/runtime/mgc0.c#newco...
src/pkg/runtime/mgc0.c:66: byte **bp;
Why we need the bp pointer at all? It seems to be a LIFO stack, so isn't it
enough to have just nobj?

http://codereview.appspot.com/4641082/diff/59001/src/pkg/runtime/mgc0.c#newco...
src/pkg/runtime/mgc0.c:245: if(nobj > 4 && work.nwait > 0) {
add
&& work.full == nil
I think Ideally we want work.nwait < work.nfull. And now with mutex-protected
queues it's quite easy to implement.

[dvyukov, 2011-09-27 20:32:17]

http://codereview.appspot.com/4641082/diff/59001/src/pkg/runtime/mgc0.c
File src/pkg/runtime/mgc0.c (right):

http://codereview.appspot.com/4641082/diff/59001/src/pkg/runtime/mgc0.c#newco...
src/pkg/runtime/mgc0.c:707: scan(nil, 0);
So, why it is before walkfintab?
As far as I understand, main thread will scan everything else except finalizers
with help of parallel helper threads, and then will scan finalizers alone. I
think scna(nil, 0) must be placed after walkfintab.

http://codereview.appspot.com/4641082/diff/59001/src/pkg/runtime/mgc0.c#newco...
src/pkg/runtime/mgc0.c:785: finq = f;
finq accesses must be thread-safe.
A nice way to do it as follows:
prev = runtime.xchgp(&finq, f);
prev->next = f;
We don't have xchgp yet, though.

http://codereview.appspot.com/4641082/diff/59001/src/pkg/runtime/mgc0.c#newco...
src/pkg/runtime/mgc0.c:956: if(work.ndone == work.nproc-1)
I think a better way to do the wait is as follows.
Create a dedicated semaphore. A helper thread that sets ndone==nproc-1 releases
the semaphore. Main thread waits on the semaphore (if nprocs!=1).

http://codereview.appspot.com/4641082/diff/59001/src/pkg/runtime/proc.c
File src/pkg/runtime/proc.c (right):

http://codereview.appspot.com/4641082/diff/59001/src/pkg/runtime/proc.c#newco...
src/pkg/runtime/proc.c:627: runtime·sched.mwait--;
mget() already updated mwait and mhead

http://codereview.appspot.com/4641082/diff/59001/src/pkg/runtime/runtime.h
File src/pkg/runtime/runtime.h (right):

http://codereview.appspot.com/4641082/diff/59001/src/pkg/runtime/runtime.h#ne...
src/pkg/runtime/runtime.h:500: void	runtime·startm(void);
Remove

[rsc, 2011-09-28 17:57:07]

On Tue, Sep 27, 2011 at 14:17, <dvyukov@google.com> wrote:

> Why we need the bp pointer at all? It seems to be a LIFO stack, so isn't
> it enough to have just nobj?
>

The work stealing steals from the bottom, which is
usually a better way to steal.

Russ

[dvyukov, 2011-09-28 18:45:18]

On 2011/09/28 17:57:07, rsc wrote:
> On Tue, Sep 27, 2011 at 14:17, <mailto:dvyukov@google.com> wrote:
> 
> > Why we need the bp pointer at all? It seems to be a LIFO stack, so isn't
> > it enough to have just nobj?
> >
> 
> The work stealing steals from the bottom, which is
> usually a better way to steal.

Then, I think a better way to do it (simplify all other code) is as follows.
handoff() allocates a new Workbuf and copies second half (last in) of elements
into it.
Then, puts it's *current* buffer into full queue, and continues with the *new*
buffer.
This way we provide FIFO stealing w/o bp pointer.

[rsc, 2011-09-28 23:59:15]

Hello dvyukov@google.com (cc: golang-dev@googlegroups.com),

Please take another look.

[dvyukov, 2011-09-29 21:21:11]

LGTM after the fix

http://codereview.appspot.com/4641082/diff/70001/src/pkg/runtime/proc.c
File src/pkg/runtime/proc.c (right):

http://codereview.appspot.com/4641082/diff/70001/src/pkg/runtime/proc.c#newco...
src/pkg/runtime/proc.c:626: runtime·sched.mhead = m->schedlink;
remove

[rsc, 2011-09-30 13:40:13]

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

runtime: parallelize garbage collector mark + sweep

Running test/garbage/parser.out.

On a 4-core Lenovo X201s (Linux):
31.12u 0.60s 31.74r 	 1 cpu, no atomics
32.27u 0.58s 32.86r 	 1 cpu, atomic instructions
33.04u 0.83s 27.47r 	 2 cpu

On a 16-core Xeon (Linux):
33.08u 0.65s 33.80r 	 1 cpu, no atomics
34.87u 1.12s 29.60r 	 2 cpu
36.00u 1.87s 28.43r 	 3 cpu
36.46u 2.34s 27.10r 	 4 cpu
38.28u 3.85s 26.92r 	 5 cpu
37.72u 5.25s 26.73r	 6 cpu
39.63u 7.11s 26.95r	 7 cpu
39.67u 8.10s 26.68r	 8 cpu

On a 2-core MacBook Pro Core 2 Duo 2.26 (circa 2009, MacBookPro5,5):
39.43u 1.45s 41.27r 	 1 cpu, no atomics
43.98u 2.95s 38.69r 	 2 cpu

On a 2-core Mac Mini Core 2 Duo 1.83 (circa 2008; Macmini2,1):
48.81u 2.12s 51.76r 	 1 cpu, no atomics
57.15u 4.72s 51.54r 	 2 cpu

The handoff algorithm is really only good for two cores.
Beyond that we will need to so something more sophisticated,
like have each core hand off to the next one, around a circle.
Even so, the code is a good checkpoint; for now we'll limit the
number of gc procs to at most 2.

R=dvyukov
CC=golang-dev
http://codereview.appspot.com/4641082