code review 7722046: runtime: allocate first bucket table lazily

runtime: allocate maps' first bucket table lazily

Motivated by garbage profiling in HTTP benchmarks. This
changes means new empty maps are just one small allocation
(the HMap) instead the HMap + the relatively larger h->buckets
allocation. This helps maps which remain empty throughout
their life.

benchmark               old ns/op    new ns/op    delta
BenchmarkNewEmptyMap          196          107  -45.41%

benchmark              old allocs   new allocs    delta
BenchmarkNewEmptyMap            2            1  -50.00%

benchmark               old bytes    new bytes    delta
BenchmarkNewEmptyMap          195           50  -74.36%

[bradfitz, 2013-03-27 22:46:48]

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

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

[r, 2013-03-27 22:47:33]

why?

[bradfitz, 2013-03-27 22:53:45]

To make empty maps cheaper.

I noticed this during garbage profiling of the HTTP server.  We make new
maps for handlers, and clone them, but they're not always used (e.g. not
setting any particular response headers).

On Wed, Mar 27, 2013 at 3:47 PM, Rob Pike <r@golang.org> wrote:

> why?
>

[khr, 2013-03-27 22:55:52]

LGTM

[bradfitz, 2013-03-27 23:28:56]

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

runtime: allocate maps' first bucket table lazily

Motivated by garbage profiling in HTTP benchmarks. This
changes means new empty maps are just one small allocation
(the HMap) instead the HMap + the relatively larger h->buckets
allocation. This helps maps which remain empty throughout
their life.

benchmark               old ns/op    new ns/op    delta
BenchmarkNewEmptyMap          196          107  -45.41%

benchmark              old allocs   new allocs    delta
BenchmarkNewEmptyMap            2            1  -50.00%

benchmark               old bytes    new bytes    delta
BenchmarkNewEmptyMap          195           50  -74.36%

R=khr, golang-dev, r
CC=golang-dev
https://codereview.appspot.com/7722046

[mtj1, 2013-03-28 14:17:44]

Brad, I have a question about your analysis. Do you have any sense how
commonly Map updates have the general pattern:

if a, present := map[index]; if present { // or !present
    ....

}

It seems that I'm doing this maybe half of the time



On Wed, Mar 27, 2013 at 4:28 PM, <bradfitz@golang.org> wrote:

> *** Submitted as
>
https://code.google.com/p/go/**source/detail?r=6efdf4f2924b<https://code.goog...
>
> runtime: allocate maps' first bucket table lazily
>
> Motivated by garbage profiling in HTTP benchmarks. This
> changes means new empty maps are just one small allocation
> (the HMap) instead the HMap + the relatively larger h->buckets
> allocation. This helps maps which remain empty throughout
> their life.
>
>
> benchmark               old ns/op    new ns/op    delta
> BenchmarkNewEmptyMap          196          107  -45.41%
>
> benchmark              old allocs   new allocs    delta
> BenchmarkNewEmptyMap            2            1  -50.00%
>
> benchmark               old bytes    new bytes    delta
> BenchmarkNewEmptyMap          195           50  -74.36%
>
> R=khr, golang-dev, r
> CC=golang-dev
>
https://codereview.appspot.**com/7722046<https://codereview.appspot.com/7722046>
>
>
>
>
https://codereview.appspot.**com/7722046/<https://codereview.appspot.com/7722...
>
> --
>
> ---You received this message because you are subscribed to the Google
> Groups "golang-dev" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to
golang-dev+unsubscribe@**googlegroups.com<golang-dev%2Bunsubscribe@googlegrou...
> .
> For more options, visit
https://groups.google.com/**groups/opt_out<https://groups.google.com/groups/o...
> .
>
>
>


-- 
Michael T. Jones | Chief Technology Advocate  | mtj@google.com |  +1
650-335-5765

[mtj1, 2013-03-28 14:20:18]

[...grrr...]

if a, present := map[index]; if present { // or !present
    ....
    map[index] = newValue
}

It seems that I'm doing this maybe half of the time and there is the
opportunity to do just one key value computation in such cases. (with an
appropriate way of saying so or caching the result and comparing keys.)

Just wondering of your analysis shows this to be frequent.


On Thu, Mar 28, 2013 at 7:17 AM, Michael Jones <mtj@google.com> wrote:

> Brad, I have a question about your analysis. Do you have any sense how
> commonly Map updates have the general pattern:
>
> if a, present := map[index]; if present { // or !present
>     ....
>
> }
>
> It seems that I'm doing this maybe half of the time
>
>
>
> On Wed, Mar 27, 2013 at 4:28 PM, <bradfitz@golang.org> wrote:
>
>> *** Submitted as
>>
https://code.google.com/p/go/**source/detail?r=6efdf4f2924b<https://code.goog...
>>
>> runtime: allocate maps' first bucket table lazily
>>
>> Motivated by garbage profiling in HTTP benchmarks. This
>> changes means new empty maps are just one small allocation
>> (the HMap) instead the HMap + the relatively larger h->buckets
>> allocation. This helps maps which remain empty throughout
>> their life.
>>
>>
>> benchmark               old ns/op    new ns/op    delta
>> BenchmarkNewEmptyMap          196          107  -45.41%
>>
>> benchmark              old allocs   new allocs    delta
>> BenchmarkNewEmptyMap            2            1  -50.00%
>>
>> benchmark               old bytes    new bytes    delta
>> BenchmarkNewEmptyMap          195           50  -74.36%
>>
>> R=khr, golang-dev, r
>> CC=golang-dev
>>
https://codereview.appspot.**com/7722046<https://codereview.appspot.com/7722046>
>>
>>
>>
>>
https://codereview.appspot.**com/7722046/<https://codereview.appspot.com/7722...
>>
>> --
>>
>> ---You received this message because you are subscribed to the Google
>> Groups "golang-dev" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to
golang-dev+unsubscribe@**googlegroups.com<golang-dev%2Bunsubscribe@googlegrou...
>> .
>> For more options, visit
https://groups.google.com/**groups/opt_out<https://groups.google.com/groups/o...
>> .
>>
>>
>>
>
>
> --
> Michael T. Jones | Chief Technology Advocate  | mtj@google.com |  +1
> 650-335-5765
>



-- 
Michael T. Jones | Chief Technology Advocate  | mtj@google.com |  +1
650-335-5765

[bradfitz, 2013-03-28 15:08:32]

On Thu, Mar 28, 2013 at 7:19 AM, Michael Jones <mtj@google.com> wrote:

>
> if a, present := map[index]; if present { // or !present
>     ....
>     map[index] = newValue
> }
>
> It seems that I'm doing this maybe half of the time and there is the
> opportunity to do just one key value computation in such cases. (with an
> appropriate way of saying so or caching the result and comparing keys.)
>
> Just wondering of your analysis shows this to be frequent.
>

I didn't specifically look for that, but I agree that such a pattern is
common.  I do that all the time as well.

That's an interesting optimization idea (not for Go 1.1).  It would likely
enlarge Hmap, so it would really need to be worth it to justify that,
though.  The cost of caching the last key's hash value in Hmap could be
avoided in most cases since the pattern you describe above is known
statically.  The compiler could pass a hint to the runtime map functions
when the pattern above is detected.  Actually, you probably wouldn't even
need to enlarge and put it in Hmap--- the cached hash value could be saved
in the P.

I've filed https://code.google.com/p/go/issues/detail?id=5147

[mtj1, 2013-03-28 15:23:40]

Cool, thanks. If we had this then such loops might be more than twice as
fast--you'd know the hash value and could know the exact point to do the
insertion (when the bucket was not full). The second map call would largely
be a pointer copy and an index update.


On Thu, Mar 28, 2013 at 8:08 AM, Brad Fitzpatrick <bradfitz@golang.org>wrote:

> On Thu, Mar 28, 2013 at 7:19 AM, Michael Jones <mtj@google.com> wrote:
>
>>
>> if a, present := map[index]; if present { // or !present
>>     ....
>>     map[index] = newValue
>> }
>>
>> It seems that I'm doing this maybe half of the time and there is the
>> opportunity to do just one key value computation in such cases. (with an
>> appropriate way of saying so or caching the result and comparing keys.)
>>
>> Just wondering of your analysis shows this to be frequent.
>>
>
> I didn't specifically look for that, but I agree that such a pattern is
> common.  I do that all the time as well.
>
> That's an interesting optimization idea (not for Go 1.1).  It would likely
> enlarge Hmap, so it would really need to be worth it to justify that,
> though.  The cost of caching the last key's hash value in Hmap could be
> avoided in most cases since the pattern you describe above is known
> statically.  The compiler could pass a hint to the runtime map functions
> when the pattern above is detected.  Actually, you probably wouldn't even
> need to enlarge and put it in Hmap--- the cached hash value could be saved
> in the P.
>
> I've filed https://code.google.com/p/go/issues/detail?id=5147
>



-- 
Michael T. Jones | Chief Technology Advocate  | mtj@google.com |  +1
650-335-5765

[bradfitz, 2013-03-29 17:10:58]

I've prototyped this in https://codereview.appspot.com/8160043 if you want
to play.  The patch isn't very clean yet.  I'm not proposing it for Go 1.1.

On Thu, Mar 28, 2013 at 8:23 AM, Michael Jones <mtj@google.com> wrote:

> Cool, thanks. If we had this then such loops might be more than twice as
> fast--you'd know the hash value and could know the exact point to do the
> insertion (when the bucket was not full). The second map call would largely
> be a pointer copy and an index update.
>
>
> On Thu, Mar 28, 2013 at 8:08 AM, Brad Fitzpatrick <bradfitz@golang.org>wrote:
>
>> On Thu, Mar 28, 2013 at 7:19 AM, Michael Jones <mtj@google.com> wrote:
>>
>>>
>>> if a, present := map[index]; if present { // or !present
>>>     ....
>>>     map[index] = newValue
>>> }
>>>
>>> It seems that I'm doing this maybe half of the time and there is the
>>> opportunity to do just one key value computation in such cases. (with an
>>> appropriate way of saying so or caching the result and comparing keys.)
>>>
>>> Just wondering of your analysis shows this to be frequent.
>>>
>>
>> I didn't specifically look for that, but I agree that such a pattern is
>> common.  I do that all the time as well.
>>
>> That's an interesting optimization idea (not for Go 1.1).  It would
>> likely enlarge Hmap, so it would really need to be worth it to justify
>> that, though.  The cost of caching the last key's hash value in Hmap could
>> be avoided in most cases since the pattern you describe above is known
>> statically.  The compiler could pass a hint to the runtime map functions
>> when the pattern above is detected.  Actually, you probably wouldn't even
>> need to enlarge and put it in Hmap--- the cached hash value could be saved
>> in the P.
>>
>> I've filed https://code.google.com/p/go/issues/detail?id=5147
>>
>
>
>
> --
> Michael T. Jones | Chief Technology Advocate  | mtj@google.com |  +1
> 650-335-5765
>