code review 5279048: runtime: faster and more scalable GC

runtime: faster and more scalable GC
Serial improvements: free memory blocks in batches (sweep), some memory prefetching (mark+sweep).
Parallel improvements: parallel for over root blocks (mark), parallel for over spans (sweep), lock-free stacks of free/full work blocks (mark).
The CL brings unit testing into C runtime.
Below are benchmarking results on 2 machines for test/garbage/parser. usr+sys time basically does grow between procs=2 and procs=4, while gc pause is basically halved and real time is decreased by 2m. For procs=8 usr+sys time starts growing and speedup is very modest. So the CL bumps Gcmaxprocs to 4. Last but not least, there is considerable single-threaded speedup.

on 2 x Intel Xeon E5620 (2 processors x 4 HT cores), 2.4GHz, Linux
procs usr   sys  usr+sys real  pause1 ngc pause
old 1 28.42 0.53 28.95   29.02 0.29   16  4.59
new 1 25.19 0.58 25.77   25.83 0.24   13  3.11
delta old/new    -3.18   -3.19 -.11

old 2 29.90 0.66 30.56   25.31 0.19   14  2.63
new 2 26.90 0.54 27.44   23.71 0.13   14  1.82
delta old/new    -3.12   -1.60 -.06
delta new/new1   +1.67   -2.12 -.09

old 4 30.83 0.82 31.65   22.92 0.10   15  1.44
new 4 27.05 0.62 27.67   21.64 0.07   14  0.96
delta old/new    -3.18   -0.87 -.04
delta new/new1   +1.90   -4.19 -.15

old 8 33.76 2.28 36.04   22.29 0.07   15  1.10
new 8 29.64 1.00 30.64   21.28 0.04   15  0.66
delta old/new    -5.40   -1.01 -.03
delta new/new1   +4.87   -4.55 -.16

on Intel Core2 Penryn (2 cores), 2.1GHz, Darwin
procs usr   sys  usr+sys real  pause1 ngc pause
old 1 37.37 2.03 39.40   40.98 0.39   14  5.01
new 1 35.37 2.02 37.39   38.98 0.29   15  4.43
delta old/new    -2.01   -2.00 -.10

old 2 40.60 2.09 42.69   37.87 0.27   14  3.16
new 2 39.54 2.05 41.59   37.16 0.17   17  2.81
delta old/new    -1.01   -0.70 -.10
delta new/new1   +4.20   -1.82 -.12

[dvyukov, 2011-11-21 17:30:32]

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

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

[rsc, 2011-11-21 21:55:36]

Thanks.

It would certainly have been nice to know this was coming.
This is a very large CL to just drop on us, even if it's great code.
http://golang.org/doc/contribute.html#Design

Some preliminary comments below.  I haven't digested it all.
I do want to figure out what we can do about the 32-bit 
architectures.  We can't just turn our backs on them.

http://codereview.appspot.com/5279048/diff/39130/src/pkg/runtime/arm/asm.s
File src/pkg/runtime/arm/asm.s (right):

http://codereview.appspot.com/5279048/diff/39130/src/pkg/runtime/arm/asm.s#ne...
src/pkg/runtime/arm/asm.s:312: // LDREXD and STREXD were introduced in ARM 11.
What about all the pre-ARM-11 chips?
We can't throw them away.

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

http://codereview.appspot.com/5279048/diff/39130/src/pkg/runtime/mgc0.c#newco...
src/pkg/runtime/mgc0.c:606: collectstackroots(G *gp)
collect is an overloaded word here.
This is just adding the stack roots, so how about addstackroots?

http://codereview.appspot.com/5279048/diff/39130/src/pkg/runtime/mgc0.c#newco...
src/pkg/runtime/mgc0.c:654: collectfinroots(void *v)
s/collect/add

http://codereview.appspot.com/5279048/diff/39130/src/pkg/runtime/mgc0.c#newco...
src/pkg/runtime/mgc0.c:667: collectroots(void)
s/collect/add/

http://codereview.appspot.com/5279048/diff/39130/src/pkg/runtime/mgc0.c#newco...
src/pkg/runtime/mgc0.c:1339: // Amd64 uses 48-bit virtual addresses, 47-th bit
is used as kernel/user flag.
On 32-bit machines (#ifdef _64BIT) it might make more
sense to use 32.

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

http://codereview.appspot.com/5279048/diff/39130/src/pkg/runtime/proc.c#newco...
src/pkg/runtime/proc.c:691: // Figure out how many CPUs GC could possibly use.
I am pretty sure you were the one who suggested that I 
pass the extra flag back so that this computation would
not be duplicated between here and gcprocs.
If these get out of sync then you end up with a thread
leak (because every starttheworld makes a new thread)
or single-threaded gc (because none do).

http://codereview.appspot.com/5279048/diff/39130/src/pkg/runtime/runtime.c
File src/pkg/runtime/runtime.c (right):

http://codereview.appspot.com/5279048/diff/39130/src/pkg/runtime/runtime.c#ne...
src/pkg/runtime/runtime.c:328: uint64 z64 = 42;
Drop initializations.
They don't match the surrounding code and are redundant anyway.

[dvyukov, 2011-11-22 09:12:41]

On 2011/11/21 21:55:36, rsc wrote:
> Thanks.
> 
> It would certainly have been nice to know this was coming.
> This is a very large CL to just drop on us, even if it's great code.
> http://golang.org/doc/contribute.html#Design

Sorry. Initially it was small and innocent... I will keep golang-dev informed of
non-trivial changes.
What should I do now? Testing, benchmarking and result aggregation is time
consuming for such changes, however for the purpose of review and commit I can
split it to several parts (some pieces may make no sense until all pieces code
together).


> Some preliminary comments below.  I haven't digested it all.
> I do want to figure out what we can do about the 32-bit 
> architectures.  We can't just turn our backs on them.

What is the problem with 32-bit architectures?


> http://codereview.appspot.com/5279048/diff/39130/src/pkg/runtime/arm/asm.s
> File src/pkg/runtime/arm/asm.s (right):
> 
>
http://codereview.appspot.com/5279048/diff/39130/src/pkg/runtime/arm/asm.s#ne...
> src/pkg/runtime/arm/asm.s:312: // LDREXD and STREXD were introduced in ARM 11.
> What about all the pre-ARM-11 chips?
> We can't throw them away.

sync/atomic uses them, so I though it is OK... I will think about it.

> http://codereview.appspot.com/5279048/diff/39130/src/pkg/runtime/mgc0.c
> File src/pkg/runtime/mgc0.c (right):
> 
>
http://codereview.appspot.com/5279048/diff/39130/src/pkg/runtime/mgc0.c#newco...
> src/pkg/runtime/mgc0.c:606: collectstackroots(G *gp)
> collect is an overloaded word here.
> This is just adding the stack roots, so how about addstackroots?

Done.

>
http://codereview.appspot.com/5279048/diff/39130/src/pkg/runtime/mgc0.c#newco...
> src/pkg/runtime/mgc0.c:654: collectfinroots(void *v)
> s/collect/add

Done.

>
http://codereview.appspot.com/5279048/diff/39130/src/pkg/runtime/mgc0.c#newco...
> src/pkg/runtime/mgc0.c:667: collectroots(void)
> s/collect/add/

Done.

>
http://codereview.appspot.com/5279048/diff/39130/src/pkg/runtime/mgc0.c#newco...
> src/pkg/runtime/mgc0.c:1339: // Amd64 uses 48-bit virtual addresses, 47-th bit
> is used as kernel/user flag.
> On 32-bit machines (#ifdef _64BIT) it might make more
> sense to use 32.

Done.

> http://codereview.appspot.com/5279048/diff/39130/src/pkg/runtime/proc.c
> File src/pkg/runtime/proc.c (right):
> 
>
http://codereview.appspot.com/5279048/diff/39130/src/pkg/runtime/proc.c#newco...
> src/pkg/runtime/proc.c:691: // Figure out how many CPUs GC could possibly use.
> I am pretty sure you were the one who suggested that I 
> pass the extra flag back so that this computation would
> not be duplicated between here and gcprocs.
> If these get out of sync then you end up with a thread
> leak (because every starttheworld makes a new thread)
> or single-threaded gc (because none do).

I not only suggested that, I implemented that :) But the problem is that now I
need to know number of threads ahead of time. I tried to keep the logic at least
in one place (several functions, though). I am happy to improve/simplify it, if
somebody has any suggestions.


> http://codereview.appspot.com/5279048/diff/39130/src/pkg/runtime/runtime.c
> File src/pkg/runtime/runtime.c (right):
> 
>
http://codereview.appspot.com/5279048/diff/39130/src/pkg/runtime/runtime.c#ne...
> src/pkg/runtime/runtime.c:328: uint64 z64 = 42;
> Drop initializations.
> They don't match the surrounding code and are redundant anyway.

Done.

[dvyukov, 2011-11-22 09:18:40]

test/bench/binary-tree -n=17
procs    old,s     new,s    delta
1        9.29      8.13     -12%
2        9.07      7.15     -21%
4        8.23      6.16     -25%

[rsc, 2011-11-22 13:38:12]

On Tue, Nov 22, 2011 at 04:12,  <dvyukov@google.com> wrote:
> What is the problem with 32-bit architectures?

It's the 64-bit atomics.  If you look at the bottom of 'godoc sync/atomic'
it explains the systems on which the 64-bit ones will not work.
We have to this point just provided those routines for others to use
but not required their use in the standard library.  This would require
their use, which would in particular give up on support for the many
tiny little ARM boards that are available.  There are a lot of people
playing with Go on ARM 5 (no floating point).  I am pretty sure those
chips don't have 64-bit atomics.

Russ

[dvyukov, 2011-11-22 13:48:48]

On Tue, Nov 22, 2011 at 5:38 PM, Russ Cox <rsc@golang.org> wrote:

> On Tue, Nov 22, 2011 at 04:12,  <dvyukov@google.com> wrote:
> > What is the problem with 32-bit architectures?
>
> It's the 64-bit atomics.  If you look at the bottom of 'godoc sync/atomic'
> it explains the systems on which the 64-bit ones will not work.
> We have to this point just provided those routines for others to use
> but not required their use in the standard library.  This would require
> their use, which would in particular give up on support for the many
> tiny little ARM boards that are available.  There are a lot of people
> playing with Go on ARM 5 (no floating point).  I am pretty sure those
> chips don't have 64-bit atomics.
>
>
Portability sucks :)
OK, I think I will be able to solve that one way or another.

[rsc, 2011-11-22 13:57:07]

On the 386 I don't mind requiring the 64-bit atomics.
It is mainly the ARM that needs an alternative.
(On the 386 I would like to require SSE at some point,
and that is even newer.)

Russ

[dvyukov, 2011-11-23 15:30:17]

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

Please take another look.

[dvyukov, 2011-11-23 15:36:44]

On 2011/11/23 15:30:17, dvyukov wrote:
> Hello mailto:rsc@golang.org (cc: mailto:golang-dev@googlegroups.com),
> 
> Please take another look.

I've replaced LDREXD/STREXD with locktable emulation. Not ideal
performance-wise, but should do.
386 arch now requires at least Pentium MMX (1996).

I've addressed your concern regarding gcprocs by adding a unit test that
verifies number of procs created. I've also added isShort parameter to C unit
tests (otherwise some tests are prohibitively slow on ARM emulation).

[dvyukov, 2011-11-23 15:39:19]

On 2011/11/22 09:18:40, dvyukov wrote:
> test/bench/binary-tree -n=17
> procs    old,s     new,s    delta
> 1        9.29      8.13     -12%
> 2        9.07      7.15     -21%
           -.22
> 4        8.23      6.16     -25%

[dvyukov, 2011-11-23 15:41:09]

On 2011/11/22 09:18:40, dvyukov wrote:
> test/bench/binary-tree -n=17
> procs    old,s     new,s    delta
> 1        9.29      8.13     -12%
> 2        9.07      7.15     -21%
           -.22      -.58
> 4        8.23      6.16     -25%
           -.44      -.59

[fw, 2011-11-23 20:27:33]

> I've replaced LDREXD/STREXD with locktable emulation. Not ideal
> performance-wise, but should do.
> 386 arch now requires at least Pentium MMX (1996).

Perhaps you could use FILD/FIST instead?  This is what the JVM does if
SSE2 is not available.

Instead of XADD (i486 and later), plain LOCK ADD would be okay.

[dvyukov, 2011-11-25 11:22:34]

On 2011/11/23 20:27:33, fw_deneb.enyo.de wrote:
> > I've replaced LDREXD/STREXD with locktable emulation. Not ideal
> > performance-wise, but should do.
> > 386 arch now requires at least Pentium MMX (1996).
> 
> Perhaps you could use FILD/FIST instead?  This is what the JVM does if
> SSE2 is not available.
> 
> Instead of XADD (i486 and later), plain LOCK ADD would be okay.

Hi,

LOCK XADD is already used in runtime.xadd(), so it's not a problem.
As for FILD/FIST, I just do not want to do it over again... Russ said that he
want to require SSE in some future anyway and sync/atomic uses MMX.
Well, if you want you may submit a patch with FILD/FIST ;)

[lucio, 2011-11-25 12:35:53]

Deary, deary me!  In the old days these would all be reserved
instructions not available for language designers to mess with.  When
you needed an intelligent locking mechanism, you asked nicely of the
OS to give it to you.

I'm not sure we're gaining anything from having all this weird
technology at user level.  Or having discussions about it, so please
forgive me mouthing off :-)

Lucio.

On 11/25/11, dvyukov@google.com <dvyukov@google.com> wrote:
> On 2011/11/23 20:27:33, fw_deneb.enyo.de wrote:
>> > I've replaced LDREXD/STREXD with locktable emulation. Not ideal
>> > performance-wise, but should do.
>> > 386 arch now requires at least Pentium MMX (1996).
>
>> Perhaps you could use FILD/FIST instead?  This is what the JVM does if
>> SSE2 is not available.
>
>> Instead of XADD (i486 and later), plain LOCK ADD would be okay.
>
> Hi,
>
> LOCK XADD is already used in runtime.xadd(), so it's not a problem.
> As for FILD/FIST, I just do not want to do it over again... Russ said
> that he want to require SSE in some future anyway and sync/atomic uses
> MMX.
> Well, if you want you may submit a patch with FILD/FIST ;)
>
>
>
> http://codereview.appspot.com/5279048/
>

[rsc, 2012-04-04 15:09:43]

Hi.

I would like to move forward with this, but the CL is too big.
As a first couple steps, please:

1) Create a separate CL with just the new atomics.
2) Create a separate CL with the parallel for support in
its own file parfor.c and declarations in runtime.h.

Once those are reviewed and submitted we can come back to this
and figure out what the next steps are.

Thanks.

[dvyukov, 2012-04-04 15:39:34]

On Wed, Apr 4, 2012 at 7:09 PM, <rsc@golang.org> wrote:

> Hi.
>
> I would like to move forward with this, but the CL is too big.
> As a first couple steps, please:
>
> 1) Create a separate CL with just the new atomics.
> 2) Create a separate CL with the parallel for support in
> its own file parfor.c and declarations in runtime.h.
>
> Once those are reviewed and submitted we can come back to this
> and figure out what the next steps are.
>
> Thanks.
>
>
OK. Thanks. I am on it.

[dvyukov, 2012-04-05 04:24:31]

On 2012/04/04 15:09:43, rsc wrote:
> Hi.
> 
> I would like to move forward with this, but the CL is too big.
> As a first couple steps, please:
> 
> 1) Create a separate CL with just the new atomics.
> 2) Create a separate CL with the parallel for support in
> its own file parfor.c and declarations in runtime.h.
> 
> Once those are reviewed and submitted we can come back to this
> and figure out what the next steps are.


Russ,

The CL also contains an infrastructure for unit-testing of C runtime:
http://codereview.appspot.com/5279048/diff/92019/src/pkg/runtime/runtime_test.go
http://codereview.appspot.com/5279048/diff/92019/src/pkg/runtime/export_test.go
It is somewhat debatable and I think must go into a separate CL. So what do you
think in general about unit-testing of C runtime? I found it useful and I think
it may be useful for testing of things like atomics or heap implementation in
timers, etc. What do you think about this particular implementation? In order to
add a new test you need to modify 3 files, I found no shorter way (which is yet
simple and straightforward).
One downside is that tests are compiled into runtime, that is bloat binary size.
If you agree with the general line, then I will prepare a separate CL that
contains the infrastructure and establishes a precedent on a simple test.

[dvyukov, 2012-04-05 04:24:34]

On 2012/04/04 15:09:43, rsc wrote:
> Hi.
> 
> I would like to move forward with this, but the CL is too big.
> As a first couple steps, please:
> 
> 1) Create a separate CL with just the new atomics.
> 2) Create a separate CL with the parallel for support in
> its own file parfor.c and declarations in runtime.h.
> 
> Once those are reviewed and submitted we can come back to this
> and figure out what the next steps are.


Russ,

The CL also contains an infrastructure for unit-testing of C runtime:
http://codereview.appspot.com/5279048/diff/92019/src/pkg/runtime/runtime_test.go
http://codereview.appspot.com/5279048/diff/92019/src/pkg/runtime/export_test.go
It is somewhat debatable and I think must go into a separate CL. So what do you
think in general about unit-testing of C runtime? I found it useful and I think
it may be useful for testing of things like atomics or heap implementation in
timers, etc. What do you think about this particular implementation? In order to
add a new test you need to modify 3 files, I found no shorter way (which is yet
simple and straightforward).
One downside is that tests are compiled into runtime, that is bloat binary size.
If you agree with the general line, then I will prepare a separate CL that
contains the infrastructure and establishes a precedent on a simple test.

[dvyukov, 2012-04-05 14:13:58]

FTR, the atomic part of this CL is moved out to:
http://codereview.appspot.com/5985047

[dvyukov, 2012-04-05 14:21:08]

On 2012/04/05 14:13:58, dvyukov wrote:
> FTR, the atomic part of this CL is moved out to:
> http://codereview.appspot.com/5985047

One more part
http://codereview.appspot.com/5987045/

[dvyukov, 2012-04-05 17:01:38]

On 2012/04/05 04:24:31, dvyukov wrote:
> On 2012/04/04 15:09:43, rsc wrote:
> > Hi.
> > 
> > I would like to move forward with this, but the CL is too big.
> > As a first couple steps, please:
> > 
> > 1) Create a separate CL with just the new atomics.
> > 2) Create a separate CL with the parallel for support in
> > its own file parfor.c and declarations in runtime.h.
> > 
> > Once those are reviewed and submitted we can come back to this
> > and figure out what the next steps are.
> 
> 
> Russ,
> 
> The CL also contains an infrastructure for unit-testing of C runtime:
>
http://codereview.appspot.com/5279048/diff/92019/src/pkg/runtime/runtime_test.go
>
http://codereview.appspot.com/5279048/diff/92019/src/pkg/runtime/export_test.go
> It is somewhat debatable and I think must go into a separate CL. So what do
you
> think in general about unit-testing of C runtime? I found it useful and I
think
> it may be useful for testing of things like atomics or heap implementation in
> timers, etc. What do you think about this particular implementation? In order
to
> add a new test you need to modify 3 files, I found no shorter way (which is
yet
> simple and straightforward).
> One downside is that tests are compiled into runtime, that is bloat binary
size.
> If you agree with the general line, then I will prepare a separate CL that
> contains the infrastructure and establishes a precedent on a simple test.

Russ,

I would like to bring in the C testing infrastructure before submitting parallel
for and lock-free stack.

[rsc, 2012-04-05 17:02:49]

Can you put the C testing stuff in _test.c files?

Russ

[rsc, 2012-04-05 17:03:35]

On Thu, Apr 5, 2012 at 13:02, Russ Cox <rsc@golang.org> wrote:
> Can you put the C testing stuff in _test.c files?

Answering my own question, no, that won't work,
but I would be surprised if the tests end up in the
actual binaries.  They should be dead code, and
the linker should remove dead code.

Russ