code review 38750047: runtime: combine small NoScan allocations

runtime: combine small NoScan allocations
Combine NoScan allocations < 16 bytes into a single memory block.
Reduces number of allocations on json/garbage benchmarks by 10+%.

json-1
allocated                 8039872      7949194      -1.13%
allocs                     105774        93776     -11.34%
cputime                 156200000    100700000     -35.53%
gc-pause-one              4908873      3814853     -22.29%
gc-pause-total            2748969      2899288      +5.47%
rss                      52674560     43560960     -17.30%
sys-gc                    3796976      3256304     -14.24%
sys-heap                 43843584     35192832     -19.73%
sys-other                 5589312      5310784      -4.98%
sys-stack                  393216       393216      +0.00%
sys-total                53623088     44153136     -17.66%
time                    156193436    100886714     -35.41%
virtual-mem             256548864    256540672      -0.00%

garbage-1
allocated                 2996885      2932982      -2.13%
allocs                      62904        55200     -12.25%
cputime                  17470000     17400000      -0.40%
gc-pause-one            932757485    925806143      -0.75%
gc-pause-total            4663787      4629030      -0.75%
rss                    1151074304   1133670400      -1.51%
sys-gc                   66068352     65085312      -1.49%
sys-heap               1039728640   1024065536      -1.51%
sys-other                38038208     37485248      -1.45%
sys-stack                 8650752      8781824      +1.52%
sys-total              1152485952   1135417920      -1.48%
time                     17478088     17418005      -0.34%
virtual-mem            1343709184   1324204032      -1.45%

[dvyukov, 2013-12-31 11:35:08]

Hello golang-codereviews@googlegroups.com,

I'd like you to review this change to
https://dvyukov%40google.com@code.google.com/p/go/

[dave_cheney.net, 2013-12-31 11:47:28]

> On 31 Dec 2013, at 22:35, dvyukov@google.com wrote:
> 
> Reviewers: golang-codereviews,
> 
> Message:
> Hello golang-codereviews@googlegroups.com,
> 
> I'd like you to review this change to
> https://dvyukov%40google.com@code.google.com/p/go/
> 
> 
> Description:
> runtime: combine small NoScan allocations
> Combine NoScan allocations < 16 bytes into a single memory block.
> Reduces number of allocations on json/garbage benchmarks by 10+%.
> 
> json-1
> allocated                 8039872      7949194      -1.13%
> allocs                     105774        93776     -11.34%
> cputime                 156200000    100700000     -35.53%
> gc-pause-one              4908873      3814853     -22.29%
> gc-pause-total            2748969      2899288      +5.47%

Why did this value go up? Was there more work done in total, thus more gc
activity ?
> rss                      52674560     43560960     -17.30%
> sys-gc                    3796976      3256304     -14.24%
> sys-heap                 43843584     35192832     -19.73%
> sys-other                 5589312      5310784      -4.98%
> sys-stack                  393216       393216      +0.00%
> sys-total                53623088     44153136     -17.66%
> time                    156193436    100886714     -35.41%
> virtual-mem             256548864    256540672      -0.00%
> 
> garbage-1
> allocated                 2996885      2932982      -2.13%
> allocs                      62904        55200     -12.25%
> cputime                  17470000     17400000      -0.40%
> gc-pause-one            932757485    925806143      -0.75%
> gc-pause-total            4663787      4629030      -0.75%
> rss                    1151074304   1133670400      -1.51%
> sys-gc                   66068352     65085312      -1.49%
> sys-heap               1039728640   1024065536      -1.51%
> sys-other                38038208     37485248      -1.45%
> sys-stack                 8650752      8781824      +1.52%
> sys-total              1152485952   1135417920      -1.48%
> time                     17478088     17418005      -0.34%
> virtual-mem            1343709184   1324204032      -1.45%
> 
> Please review this at https://codereview.appspot.com/38750047/
> 
> Affected files (+64, -7 lines):
>  M src/pkg/runtime/malloc.goc
>  M src/pkg/runtime/mgc0.c
>  M src/pkg/runtime/runtime.h
> 
> 
> Index: src/pkg/runtime/malloc.goc
> ===================================================================
> --- a/src/pkg/runtime/malloc.goc
> +++ b/src/pkg/runtime/malloc.goc
> @@ -26,6 +26,12 @@
> 
> extern volatile intgo runtime·MemProfileRate;
> 
> +enum
> +{
> +    TinySize = 16,
> +    TinySizeClass = 2,
> +};
> +
> // Allocate an object of at least size bytes.
> // Small objects are allocated from the per-thread cache's free lists.
> // Large objects (> 32 kB) are allocated straight from the heap.
> @@ -59,6 +65,46 @@
> 
>    c = m->mcache;
>    if(!runtime·debug.efence && size <= MaxSmallSize) {
> +        if((flag&(FlagNoScan|FlagNoGC)) == FlagNoScan && size <= TinySize/2)
{
> +            byte *tiny;
> +            uintptr tinysize;
> +            P *p;
> +
> +            p = m->p;
> +            tinysize = p->tinysize;
> +            if(size <= tinysize) {
> +                tiny = p->tiny;
> +                if((size&7) == 0)
> +                    tiny = (byte*)ROUND((uintptr)tiny, 8);
> +                else if((size&3) == 0)
> +                    tiny = (byte*)ROUND((uintptr)tiny, 4);
> +                else if((size&1) == 0)
> +                    tiny = (byte*)ROUND((uintptr)tiny, 2);
> +                size = size + (tiny - p->tiny);
> +                if(size <= tinysize) {
> +                    v = (MLink*)tiny;
> +                    p->tiny += size;
> +                    p->tinysize -= size;
> +                    m->mallocing = 0;
> +                    m->locks--;
> +                    if(m->locks == 0 && g->preempt)  // restore the
preemption request in case we've cleared it in newstack
> +                        g->stackguard0 = StackPreempt;
> +                    return v;
> +                }
> +            }
> +            l = &c->list[TinySizeClass];
> +            if(l->list == nil)
> +                runtime·MCache_Refill(c, TinySizeClass);
> +            v = l->list;
> +            l->list = v->next;
> +            l->nlist--;
> +            ((uint64*)v)[0] = 0;
> +            ((uint64*)v)[1] = 0;
> +            p->tiny = (byte*)v + size;
> +            p->tinysize = TinySize - size;
> +            size = TinySize;
> +            goto done;
> +        }
>        // Allocate from mcache free lists.
>        // Inlined version of SizeToClass().
>        if(size <= 1024-8)
> @@ -78,6 +124,7 @@
>            if(size > sizeof(uintptr) && ((uintptr*)v)[1] != 0)
>                runtime·memclr((byte*)v, size);
>        }
> +    done:
>        c->local_cachealloc += size;
>    } else {
>        // TODO(rsc): Report tracebacks for very large allocations.
> Index: src/pkg/runtime/mgc0.c
> ===================================================================
> --- a/src/pkg/runtime/mgc0.c
> +++ b/src/pkg/runtime/mgc0.c
> @@ -60,16 +60,22 @@
> static void
> clearpools(void)
> {
> -    void **p, **next;
> +    P *p, **pp;
> +    void **pool, **next;
> 
> -    for(p = pools.head; p != nil; p = next) {
> -        next = p[0];
> -        p[0] = nil; // next
> -        p[1] = nil; // slice
> -        p[2] = nil;
> -        p[3] = nil;
> +    for(pool = pools.head; pool != nil; pool = next) {
> +        next = pool[0];
> +        pool[0] = nil; // next
> +        pool[1] = nil; // slice
> +        pool[2] = nil;
> +        pool[3] = nil;
>    }
>    pools.head = nil;
> +
> +    for(pp=runtime·allp; p=*pp; pp++) {
> +        p->tiny = nil;
> +        p->tinysize = 0;
> +    }
> }
> 
> // Bits in per-word bitmap.
> Index: src/pkg/runtime/runtime.h
> ===================================================================
> --- a/src/pkg/runtime/runtime.h
> +++ b/src/pkg/runtime/runtime.h
> @@ -371,6 +371,10 @@
>    M*    m;        // back-link to associated M (nil if idle)
>    MCache*    mcache;
> 
> +    // Allocator cache for tiny objects w/o pointers.
> +    byte*    tiny;
> +    uintptr    tinysize;
> +
>    // Queue of runnable goroutines.
>    G**    runq;
>    int32    runqhead;
> 
> 
> -- 
> You received this message because you are subscribed to the Google Groups
"golang-codereviews" group.
> To unsubscribe from this group and stop receiving emails from it, send an
email to golang-codereviews+unsubscribe@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.

[dvyukov, 2013-12-31 11:52:26]

On Tue, Dec 31, 2013 at 3:47 PM, Dave Cheney <dave@cheney.net> wrote:
>
>
>
>
>> On 31 Dec 2013, at 22:35, dvyukov@google.com wrote:
>>
>> Reviewers: golang-codereviews,
>>
>> Message:
>> Hello golang-codereviews@googlegroups.com,
>>
>> I'd like you to review this change to
>> https://dvyukov%40google.com@code.google.com/p/go/
>>
>>
>> Description:
>> runtime: combine small NoScan allocations
>> Combine NoScan allocations < 16 bytes into a single memory block.
>> Reduces number of allocations on json/garbage benchmarks by 10+%.
>>
>> json-1
>> allocated                 8039872      7949194      -1.13%
>> allocs                     105774        93776     -11.34%
>> cputime                 156200000    100700000     -35.53%
>> gc-pause-one              4908873      3814853     -22.29%
>> gc-pause-total            2748969      2899288      +5.47%
>
> Why did this value go up? Was there more work done in total, thus more gc
activity ?


When heap size decreases gc-pause-one goes down, but gc-pause-total
goes up because frequency of GCs increases.
If you have spare RAM, you can offset this by increasing GOGC. Then
you will have less frequent GCs of the same duration.

[dave_cheney.net, 2013-12-31 11:54:54]

Ahh right. Thank you for the explanation


On Tue, Dec 31, 2013 at 10:52 PM, Dmitry Vyukov <dvyukov@google.com> wrote:

> On Tue, Dec 31, 2013 at 3:47 PM, Dave Cheney <dave@cheney.net> wrote:
> >
> >
> >
> >
> >> On 31 Dec 2013, at 22:35, dvyukov@google.com wrote:
> >>
> >> Reviewers: golang-codereviews,
> >>
> >> Message:
> >> Hello golang-codereviews@googlegroups.com,
> >>
> >> I'd like you to review this change to
> >> https://dvyukov%40google.com@code.google.com/p/go/
> >>
> >>
> >> Description:
> >> runtime: combine small NoScan allocations
> >> Combine NoScan allocations < 16 bytes into a single memory block.
> >> Reduces number of allocations on json/garbage benchmarks by 10+%.
> >>
> >> json-1
> >> allocated                 8039872      7949194      -1.13%
> >> allocs                     105774        93776     -11.34%
> >> cputime                 156200000    100700000     -35.53%
> >> gc-pause-one              4908873      3814853     -22.29%
> >> gc-pause-total            2748969      2899288      +5.47%
> >
> > Why did this value go up? Was there more work done in total, thus more
> gc activity ?
>
>
> When heap size decreases gc-pause-one goes down, but gc-pause-total
> goes up because frequency of GCs increases.
> If you have spare RAM, you can offset this by increasing GOGC. Then
> you will have less frequent GCs of the same duration.
>

[dvyukov, 2013-12-31 12:33:53]

If this is generally LGTM, then we also need finalizer support for such combined
allocations. I will wait for Keith' finalizer/special refactoring, and then it
must be trivial to do.

[dvyukov, 2014-01-22 13:02:06]

On 2013/12/31 12:33:53, dvyukov wrote:
> If this is generally LGTM, then we also need finalizer support for such
combined
> allocations. I will wait for Keith' finalizer/special refactoring, and then it
> must be trivial to do.


I've updated the patch to utilize new finalizers/specials. Now all.bash passes.

Please take a look.

[iant, 2014-01-22 16:26:12]

The code looks OK but I think you need a test with a finalizer on a tiny
allocated object.

[dvyukov, 2014-01-22 17:22:49]

On 2014/01/22 16:26:12, iant wrote:
> The code looks OK but I think you need a test with a finalizer on a tiny
> allocated object.

Done
see test/tinyfin.go

[iant, 2014-01-22 18:59:28]

LGTM

[rsc, 2014-01-22 19:18:13]

https://codereview.appspot.com/38750047/diff/160001/src/pkg/runtime/malloc.goc
File src/pkg/runtime/malloc.goc (right):

https://codereview.appspot.com/38750047/diff/160001/src/pkg/runtime/malloc.go...
src/pkg/runtime/malloc.goc:29: enum
please add a nice overview comment here about what is going on.

https://codereview.appspot.com/38750047/diff/160001/src/pkg/runtime/malloc.go...
src/pkg/runtime/malloc.goc:70: uintptr tinysize, size1;
declare variables at top of function please

[bradfitz, 2014-01-23 00:03:24]

https://codereview.appspot.com/38750047/diff/160001/src/pkg/runtime/env_posix.c
File src/pkg/runtime/env_posix.c (right):

https://codereview.appspot.com/38750047/diff/160001/src/pkg/runtime/env_posix...
src/pkg/runtime/env_posix.c:55: if(len < 16)
this is kinda gross, having this constant (and knowledge) duplicated here.  why
not a flag to malloc, like FlagNoTiny?

https://codereview.appspot.com/38750047/diff/160001/src/pkg/runtime/malloc.goc
File src/pkg/runtime/malloc.goc (right):

https://codereview.appspot.com/38750047/diff/160001/src/pkg/runtime/malloc.go...
src/pkg/runtime/malloc.goc:522: runtime·free(runtime·malloc(16));
TinySize?

[dvyukov, 2014-01-23 16:44:12]

PTAL

https://codereview.appspot.com/38750047/diff/160001/src/pkg/runtime/env_posix.c
File src/pkg/runtime/env_posix.c (right):

https://codereview.appspot.com/38750047/diff/160001/src/pkg/runtime/env_posix...
src/pkg/runtime/env_posix.c:55: if(len < 16)
On 2014/01/23 00:03:24, bradfitz wrote:
> this is kinda gross, having this constant (and knowledge) duplicated here. 
why
> not a flag to malloc, like FlagNoTiny?

Done.

https://codereview.appspot.com/38750047/diff/160001/src/pkg/runtime/malloc.goc
File src/pkg/runtime/malloc.goc (right):

https://codereview.appspot.com/38750047/diff/160001/src/pkg/runtime/malloc.go...
src/pkg/runtime/malloc.goc:29: enum
On 2014/01/22 19:18:14, rsc wrote:
> please add a nice overview comment here about what is going on.

Done
I've added it to mallocgc() because the constants have moved to malloc.h

https://codereview.appspot.com/38750047/diff/160001/src/pkg/runtime/malloc.go...
src/pkg/runtime/malloc.goc:70: uintptr tinysize, size1;
On 2014/01/22 19:18:14, rsc wrote:
> declare variables at top of function please

Done.

https://codereview.appspot.com/38750047/diff/160001/src/pkg/runtime/malloc.go...
src/pkg/runtime/malloc.goc:522: runtime·free(runtime·malloc(16));
On 2014/01/23 00:03:24, bradfitz wrote:
> TinySize?

Done.

[bradfitz, 2014-01-23 23:22:34]

LGTM for *.go and env_posix.c

[dvyukov, 2014-01-24 18:35:58]

*** Submitted as https://code.google.com/p/go/source/detail?r=54a5513d9d6a ***

runtime: combine small NoScan allocations
Combine NoScan allocations < 16 bytes into a single memory block.
Reduces number of allocations on json/garbage benchmarks by 10+%.

json-1
allocated                 8039872      7949194      -1.13%
allocs                     105774        93776     -11.34%
cputime                 156200000    100700000     -35.53%
gc-pause-one              4908873      3814853     -22.29%
gc-pause-total            2748969      2899288      +5.47%
rss                      52674560     43560960     -17.30%
sys-gc                    3796976      3256304     -14.24%
sys-heap                 43843584     35192832     -19.73%
sys-other                 5589312      5310784      -4.98%
sys-stack                  393216       393216      +0.00%
sys-total                53623088     44153136     -17.66%
time                    156193436    100886714     -35.41%
virtual-mem             256548864    256540672      -0.00%

garbage-1
allocated                 2996885      2932982      -2.13%
allocs                      62904        55200     -12.25%
cputime                  17470000     17400000      -0.40%
gc-pause-one            932757485    925806143      -0.75%
gc-pause-total            4663787      4629030      -0.75%
rss                    1151074304   1133670400      -1.51%
sys-gc                   66068352     65085312      -1.49%
sys-heap               1039728640   1024065536      -1.51%
sys-other                38038208     37485248      -1.45%
sys-stack                 8650752      8781824      +1.52%
sys-total              1152485952   1135417920      -1.48%
time                     17478088     17418005      -0.34%
virtual-mem            1343709184   1324204032      -1.45%

LGTM=iant, bradfitz
R=golang-codereviews, dave, iant, rsc, bradfitz
CC=golang-codereviews, khr
https://codereview.appspot.com/38750047

[gobot, 2014-01-24 18:55:15]

This CL appears to have broken the windows-amd64 builder.