code review 45770044: runtime: increase page size to 8K

runtime: increase page size to 8K
Tcmalloc uses 8K, 32K and 64K pages, and in custom setups 256K pages.
Only Chromium uses 4K pages today (in "slow but small" configuration).
The general tendency is to increase page size, because it reduces
metadata size and DTLB pressure.
This change reduces GC pause by ~10% and slightly improves other metrics.

json-1
allocated                 8037492      8038689      +0.01%
allocs                     105762       105573      -0.18%
cputime                 158400000    155800000      -1.64%
gc-pause-one              4412234      4135702      -6.27%
gc-pause-total            2647340      2398707      -9.39%
rss                      54923264     54525952      -0.72%
sys-gc                    3952624      3928048      -0.62%
sys-heap                 46399488     46006272      -0.85%
sys-other                 5597504      5290304      -5.49%
sys-stack                  393216       393216      +0.00%
sys-total                56342832     55617840      -1.29%
time                    158478890    156046916      -1.53%
virtual-mem             256548864    256593920      +0.02%

garbage-1
allocated                 2991113      2986259      -0.16%
allocs                      62844        62652      -0.31%
cputime                  16330000     15860000      -2.88%
gc-pause-one            789108229    725555211      -8.05%
gc-pause-total            3945541      3627776      -8.05%
rss                    1143660544   1132253184      -1.00%
sys-gc                   65609600     65806208      +0.30%
sys-heap               1032388608   1035599872      +0.31%
sys-other                37501632     22777664     -39.26%
sys-stack                 8650752      8781824      +1.52%
sys-total              1144150592   1132965568      -0.98%
time                     16364602     15891994      -2.89%
virtual-mem            1327296512   1313746944      -1.02%

[dvyukov, 2013-12-31 09:47:58]

Hello golang-codereviews@googlegroups.com,

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

[dvyukov, 2013-12-31 09:48:42]

Any better ideas on what to do with MemStats?

[dave_cheney.net, 2014-01-06 23:38:06]

On 2013/12/31 09:48:42, dvyukov wrote:
> Any better ideas on what to do with MemStats?

Why stop at 8k, what are the disadvantages of something like 64k or 1mb ?

[dvyukov, 2014-01-09 10:39:44]

On 2014/01/06 23:38:06, dfc wrote:
> On 2013/12/31 09:48:42, dvyukov wrote:
> > Any better ideas on what to do with MemStats?
> 
> Why stop at 8k, what are the disadvantages of something like 64k or 1mb ?

There are several drawbacks of larger spans/pages:
- probability that a span will become completely freed is much lower, so fewer
spans can be reused for different size classes
- currently we transfer whole span from central cache to thread-local cache, we
don't want this granularity to be very large because then threads can have lots
of unused memory
- with concurrent sweeping span size determines granularity of lazy work a
thread suddenly needs to do, we don't want it to be large as well
And there may be other aspects that I don't remember now.
Let's do it gradually. If we deploy 8K pages in 1.3 and it shows no issues, then
we can consider 16K pages.

[dave_cheney.net, 2014-01-09 10:43:21]

Sounds reasonable to me. 

> On 9 Jan 2014, at 21:39, dvyukov@google.com wrote:
> 
>> On 2014/01/06 23:38:06, dfc wrote:
>> On 2013/12/31 09:48:42, dvyukov wrote:
>> > Any better ideas on what to do with MemStats?
> 
>> Why stop at 8k, what are the disadvantages of something like 64k or
> 1mb ?
> 
> There are several drawbacks of larger spans/pages:
> - probability that a span will become completely freed is much lower, so
> fewer spans can be reused for different size classes
> - currently we transfer whole span from central cache to thread-local
> cache, we don't want this granularity to be very large because then
> threads can have lots of unused memory
> - with concurrent sweeping span size determines granularity of lazy work
> a thread suddenly needs to do, we don't want it to be large as well
> And there may be other aspects that I don't remember now.
> Let's do it gradually. If we deploy 8K pages in 1.3 and it shows no
> issues, then we can consider 16K pages.
> 
> 
> 
> https://codereview.appspot.com/45770044/

[dvyukov, 2014-01-18 15:41:28]

ping

[khr, 2014-01-21 22:00:08]

On 2014/01/18 15:41:28, dvyukov wrote:
> ping

I'm happy with the code proper.

Who was the genius who hardcoded 61 size classes?  Ugh.

Do you have a feel for how much additional memory is wasted by partially-used
pages?

[rsc, 2014-01-21 22:10:43]

On 2014/01/21 22:00:08, khr wrote:
> Who was the genius who hardcoded 61 size classes?  Ugh.

Even if it had been a named constant we still couldn't change it. Probably it
was a mistake to expose the BySize array in the struct at all.

> Do you have a feel for how much additional memory is wasted by partially-used
> pages?

This is the key question. What is the cost of the newly wasted space in real
programs as opposed to microbenchmarks?

The fact that other tcmalloc implementations have switched away from 4k pages is
the best evidence I've seen, but I'd still like to understand whether there is a
hidden cost here.

[khr1, 2014-01-21 22:13:05]

On Tue, Jan 21, 2014 at 2:10 PM, <rsc@golang.org> wrote:

> On 2014/01/21 22:00:08, khr wrote:
>
>> Who was the genius who hardcoded 61 size classes?  Ugh.
>>
>
> Even if it had been a named constant we still couldn't change it.
> Probably it was a mistake to expose the BySize array in the struct at
> all.
>
>
It should have been a slice, then we could change its length without
breaking the API.


>
>  Do you have a feel for how much additional memory is wasted by
>>
> partially-used
>
>> pages?
>>
>
> This is the key question. What is the cost of the newly wasted space in
> real programs as opposed to microbenchmarks?
>
> The fact that other tcmalloc implementations have switched away from 4k
> pages is the best evidence I've seen, but I'd still like to understand
> whether there is a hidden cost here.
>
>
>
>
> https://codereview.appspot.com/45770044/
>

[rsc, 2014-01-21 22:14:08]

On Tue, Jan 21, 2014 at 5:13 PM, Keith Randall <khr@google.com> wrote:

> On Tue, Jan 21, 2014 at 2:10 PM, <rsc@golang.org> wrote:
>
>> On 2014/01/21 22:00:08, khr wrote:
>>
>>> Who was the genius who hardcoded 61 size classes?  Ugh.
>>>
>>
>> Even if it had been a named constant we still couldn't change it.
>> Probably it was a mistake to expose the BySize array in the struct at
>> all.
>>
>>
> It should have been a slice, then we could change its length without
> breaking the API.
>

Then it would require allocating.

[khr1, 2014-01-21 22:38:32]

On Tue, Jan 21, 2014 at 2:14 PM, Russ Cox <rsc@golang.org> wrote:

> On Tue, Jan 21, 2014 at 5:13 PM, Keith Randall <khr@google.com> wrote:
>
>> On Tue, Jan 21, 2014 at 2:10 PM, <rsc@golang.org> wrote:
>>
>>> On 2014/01/21 22:00:08, khr wrote:
>>>
>>>> Who was the genius who hardcoded 61 size classes?  Ugh.
>>>>
>>>
>>> Even if it had been a named constant we still couldn't change it.
>>> Probably it was a mistake to expose the BySize array in the struct at
>>> all.
>>>
>>>
>> It should have been a slice, then we could change its length without
>> breaking the API.
>>
>
> Then it would require allocating.
>
> Sure, but you could have a

   func MakeMemStats() *MemStats

People who care could preallocate it so that no allocation would be
required at read time.

[dvyukov, 2014-01-22 09:28:39]

On 2014/01/21 22:10:43, rsc wrote:
> On 2014/01/21 22:00:08, khr wrote:

> > Do you have a feel for how much additional memory is wasted by
partially-used
> > pages?
> 
> This is the key question. What is the cost of the newly wasted space in real
> programs as opposed to microbenchmarks?
> 
> The fact that other tcmalloc implementations have switched away from 4k pages
is
> the best evidence I've seen, but I'd still like to understand whether there is
a
> hidden cost here.


Here is a program that prints size class characteristics for the 2 page sizes:
http://play.golang.org/p/V5Z6M3_mF_

The strict upper limit on wasted memory can be calculated as SUM(spanSize -
objSize) (as if each thread allocates 1 object from each size class and wastes
the rest).
For 4K pages it's 427K per GOMAXPROC.
For 8K pages it's 1006K (+579K) per GOMAXPROC.
Note that if a thread allocates 1 object, after a GC another thread can allocate
from the same span (we flush all caches during GC). So the worst case requires
that all threads allocate at the same time w/o GCs.
I've also calculated it only for size classes >512 and not powers of 2 (assuming
that small objects and powers of 2 are actively used).
For 4K pages it's 332K per GOMAXPROC.
For 8K pages it's 789K (+457K) per GOMAXPROC.

I think that ~500K worst case is a reasonable price. I doubt that it ever will
be realized in real programs.

[dvyukov, 2014-01-22 10:21:05]

On 2014/01/22 09:28:39, dvyukov wrote:
> On 2014/01/21 22:10:43, rsc wrote:
> > On 2014/01/21 22:00:08, khr wrote:
> 
> > > Do you have a feel for how much additional memory is wasted by
> partially-used
> > > pages?
> > 
> > This is the key question. What is the cost of the newly wasted space in real
> > programs as opposed to microbenchmarks?
> > 
> > The fact that other tcmalloc implementations have switched away from 4k
pages
> is
> > the best evidence I've seen, but I'd still like to understand whether there
is
> a
> > hidden cost here.
> 
> 
> Here is a program that prints size class characteristics for the 2 page sizes:
> http://play.golang.org/p/V5Z6M3_mF_
> 
> The strict upper limit on wasted memory can be calculated as SUM(spanSize -
> objSize) (as if each thread allocates 1 object from each size class and wastes
> the rest).
> For 4K pages it's 427K per GOMAXPROC.
> For 8K pages it's 1006K (+579K) per GOMAXPROC.
> Note that if a thread allocates 1 object, after a GC another thread can
allocate
> from the same span (we flush all caches during GC). So the worst case requires
> that all threads allocate at the same time w/o GCs.
> I've also calculated it only for size classes >512 and not powers of 2
(assuming
> that small objects and powers of 2 are actively used).
> For 4K pages it's 332K per GOMAXPROC.
> For 8K pages it's 789K (+457K) per GOMAXPROC.
> 
> I think that ~500K worst case is a reasonable price. I doubt that it ever will
> be realized in real programs.



Here is more raw data collected with GOMAXPROCS=8.


json-8
allocated                 8009094      8015036      +0.07%
allocs                     105583       105475      -0.10%
cputime                 123840000    122860000      -0.79%
gc-pause-one              3828784      3442078     -10.10%
gc-pause-total             911250       826098      -9.34%
rss                     171376640    156143616      -8.89%
sys-gc                   10649600      9732096      -8.62%
sys-heap                153550848    138936320      -9.52%
sys-other                 7199040      5904704     -17.98%
sys-stack                 4063232      4325376      +6.45%
sys-total               175462720    158898496      -9.44%
time                     15665362     15573089      -0.59%
virtual-mem             499736576    537743360      +7.61%

garbage-8
allocated                 3011557      3014005      +0.08%
allocs                      63554        63369      -0.29%
cputime                  21834000     20418000      -6.49%
gc-pause-one            147937442    130424885     -11.84%
gc-pause-total             828449       730379     -11.84%
rss                    1201635328   1186242560      -1.28%
sys-gc                   68804608     68788224      -0.02%
sys-heap               1084030976   1083834368      -0.02%
sys-other                40221376     23613248     -41.29%
sys-stack                11927552     11796480      -1.10%
sys-total              1204984512   1188032320      -1.41%
time                      2816131      2616303      -7.10%
virtual-mem            1442783232   1432731648      -0.70%

rpc-8
allocated                     723          718      -0.69%
allocs                         23           23      +0.00%
cputime                     27004        26232      -2.86%
gc-pause-one              2018780      1673236     -17.12%
gc-pause-total                102           84     -17.65%
latency-50                1783222      1749187      -1.91%
latency-95                4224952      4026695      -4.69%
latency-99                5869683      5611114      -4.41%
rss                      49758208     49569792      -0.38%
sys-gc                    3407872      3416064      +0.24%
sys-heap                 37683200     37879808      +0.52%
sys-other                 5577024      5282112      -5.29%
sys-stack                 8257536      8257536      +0.00%
sys-total                54925632     54835520      -0.16%
time                         3427         3329      -2.86%
virtual-mem             372510720    447655936     +20.17%

widefinder-8
allocated                     781          778      -0.38%
allocs                          4            4      +0.00%
cputime                      4644         4533      -2.39%
gc-pause-one              1577097      1413723     -10.36%
gc-pause-total                 73           65     -10.96%
rss                      52678656     52592640      -0.16%
sys-gc                    3866624      3874816      +0.21%
sys-heap                 45023232     45219840      +0.44%
sys-other                 5593408      5290304      -5.42%
sys-stack                 3407872      3801088     +11.54%
sys-total                57891136     58186048      +0.51%
time                          604          589      -2.48%
virtual-mem             449667072    483696640      +7.57%

[rsc, 2014-01-22 19:06:43]

LGTM

Okay, let's try it and see.

[dvyukov, 2014-01-23 15:00:08]

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

runtime: increase page size to 8K
Tcmalloc uses 8K, 32K and 64K pages, and in custom setups 256K pages.
Only Chromium uses 4K pages today (in "slow but small" configuration).
The general tendency is to increase page size, because it reduces
metadata size and DTLB pressure.
This change reduces GC pause by ~10% and slightly improves other metrics.

json-1
allocated                 8037492      8038689      +0.01%
allocs                     105762       105573      -0.18%
cputime                 158400000    155800000      -1.64%
gc-pause-one              4412234      4135702      -6.27%
gc-pause-total            2647340      2398707      -9.39%
rss                      54923264     54525952      -0.72%
sys-gc                    3952624      3928048      -0.62%
sys-heap                 46399488     46006272      -0.85%
sys-other                 5597504      5290304      -5.49%
sys-stack                  393216       393216      +0.00%
sys-total                56342832     55617840      -1.29%
time                    158478890    156046916      -1.53%
virtual-mem             256548864    256593920      +0.02%

garbage-1
allocated                 2991113      2986259      -0.16%
allocs                      62844        62652      -0.31%
cputime                  16330000     15860000      -2.88%
gc-pause-one            789108229    725555211      -8.05%
gc-pause-total            3945541      3627776      -8.05%
rss                    1143660544   1132253184      -1.00%
sys-gc                   65609600     65806208      +0.30%
sys-heap               1032388608   1035599872      +0.31%
sys-other                37501632     22777664     -39.26%
sys-stack                 8650752      8781824      +1.52%
sys-total              1144150592   1132965568      -0.98%
time                     16364602     15891994      -2.89%
virtual-mem            1327296512   1313746944      -1.02%

R=golang-codereviews, dave, khr, rsc, khr
CC=golang-codereviews
https://codereview.appspot.com/45770044