code review 14794043: runtime: pass key/value to map accessors by reference, ...

runtime: pass key/value to map accessors by reference, not by value.

This change is part of the plan to get rid of all vararg C calls
which are a pain for getting exact stack scanning.

We allocate a chunk of zero memory to return a pointer to when a
map access doesn't find the key.  This is simpler than returning nil
and fixing things up in the caller.  Linker magic allocates a single
zero memory area that is shared by all (non-reflect-generated) map
types.

Passing things by reference gets rid of some copies, so it speeds
up code with big keys/values.

benchmark             old ns/op    new ns/op    delta
BenchmarkBigKeyMap           34           31   -8.48%
BenchmarkBigValMap           37           30  -18.62%
BenchmarkSmallKeyMap         26           23  -11.28%

[khr, 2013-11-13 00:43:25]

Hello golang-dev@googlegroups.com,

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

[dvyukov, 2013-11-14 05:52:43]

https://codereview.appspot.com/14794043/diff/206001/src/pkg/runtime/hashmap.c
File src/pkg/runtime/hashmap.c (right):

https://codereview.appspot.com/14794043/diff/206001/src/pkg/runtime/hashmap.c...
src/pkg/runtime/hashmap.c:741: uint8* value; // Must be in second position.
please add a reference to code/function that requires this

https://codereview.appspot.com/14794043/diff/206001/src/pkg/runtime/hashmap.c...
src/pkg/runtime/hashmap.c:989: // hold onto it for very long.
is it whole map? or only the bucket?
once we've removed all GC magic for hashmaps, I would expect that it holds only
the bucket

[khr1, 2013-11-14 06:19:19]

On Wed, Nov 13, 2013 at 9:52 PM, <dvyukov@google.com> wrote:

>
> https://codereview.appspot.com/14794043/diff/206001/src/
> pkg/runtime/hashmap.c
> File src/pkg/runtime/hashmap.c (right):
>
> https://codereview.appspot.com/14794043/diff/206001/src/
> pkg/runtime/hashmap.c#newcode741
> src/pkg/runtime/hashmap.c:741: uint8* value; // Must be in second
> position.
> please add a reference to code/function that requires this
>
> Done.


> https://codereview.appspot.com/14794043/diff/206001/src/
> pkg/runtime/hashmap.c#newcode989
> src/pkg/runtime/hashmap.c:989: // hold onto it for very long.
> is it whole map? or only the bucket?
> once we've removed all GC magic for hashmaps, I would expect that it
> holds only the bucket
>
>
It will likely point to the main bucket array, which practically means it
would keep the whole map (except the header) alive.  If you're lucky it
would point to an overflow bucket and then it would keep just that bucket
alive.
It is not a big worry.  The compiler immediately dereferences the returned
value, so that pointer won't last.


> https://codereview.appspot.com/14794043/
>

[dvyukov, 2013-11-14 06:37:20]

On 2013/11/14 06:19:19, khr1 wrote:
> On Wed, Nov 13, 2013 at 9:52 PM, <mailto:dvyukov@google.com> wrote:
> 
> >
> > https://codereview.appspot.com/14794043/diff/206001/src/
> > pkg/runtime/hashmap.c
> > File src/pkg/runtime/hashmap.c (right):
> >
> > https://codereview.appspot.com/14794043/diff/206001/src/
> > pkg/runtime/hashmap.c#newcode741
> > src/pkg/runtime/hashmap.c:741: uint8* value; // Must be in second
> > position.
> > please add a reference to code/function that requires this
> >
> > Done.
> 
> 
> > https://codereview.appspot.com/14794043/diff/206001/src/
> > pkg/runtime/hashmap.c#newcode989
> > src/pkg/runtime/hashmap.c:989: // hold onto it for very long.
> > is it whole map? or only the bucket?
> > once we've removed all GC magic for hashmaps, I would expect that it
> > holds only the bucket
> >
> >
> It will likely point to the main bucket array, which practically means it
> would keep the whole map (except the header) alive.  If you're lucky it
> would point to an overflow bucket and then it would keep just that bucket
> alive.
> It is not a big worry.  The compiler immediately dereferences the returned
> value, so that pointer won't last.


Ah, OK, there is a single bucket array.

[dvyukov, 2013-11-14 06:57:39]

https://codereview.appspot.com/14794043/diff/226001/src/cmd/gc/range.c
File src/cmd/gc/range.c (right):

https://codereview.appspot.com/14794043/diff/226001/src/cmd/gc/range.c#newcode13
src/cmd/gc/range.c:13: Type *hiter(Type* t);
move to go.h, there is a section for reflect.c

https://codereview.appspot.com/14794043/diff/226001/src/cmd/gc/reflect.c
File src/cmd/gc/reflect.c (right):

https://codereview.appspot.com/14794043/diff/226001/src/cmd/gc/reflect.c#newc...
src/cmd/gc/reflect.c:236: Type *hiter(Type *t) {
{ on next line

https://codereview.appspot.com/14794043/diff/226001/src/pkg/runtime/hashmap.c
File src/pkg/runtime/hashmap.c (left):

https://codereview.appspot.com/14794043/diff/226001/src/pkg/runtime/hashmap.c...
src/pkg/runtime/hashmap.c:518: static uint8 empty_value[MAXVALUESIZE];
why do you remove this?

[khr1, 2013-11-18 21:07:32]

On Wed, Nov 13, 2013 at 10:57 PM, <dvyukov@google.com> wrote:

>
> https://codereview.appspot.com/14794043/diff/226001/src/cmd/gc/range.c
> File src/cmd/gc/range.c (right):
>
> https://codereview.appspot.com/14794043/diff/226001/src/
> cmd/gc/range.c#newcode13
> src/cmd/gc/range.c:13: Type *hiter(Type* t);
> move to go.h, there is a section for reflect.c
>
> Fixed.


> https://codereview.appspot.com/14794043/diff/226001/src/cmd/gc/reflect.c
> File src/cmd/gc/reflect.c (right):
>
> https://codereview.appspot.com/14794043/diff/226001/src/
> cmd/gc/reflect.c#newcode236
> src/cmd/gc/reflect.c:236: Type *hiter(Type *t) {
> { on next line
>

Fixed/


>
> https://codereview.appspot.com/14794043/diff/226001/src/
> pkg/runtime/hashmap.c
> File src/pkg/runtime/hashmap.c (left):
>
> https://codereview.appspot.com/14794043/diff/226001/src/
> pkg/runtime/hashmap.c#oldcode518
> src/pkg/runtime/hashmap.c:518: static uint8 empty_value[MAXVALUESIZE];
> why do you remove this?
>

Now that we have the per-type zero value, we don't need that one.  We could
still use it; it would be fine either way.


>
> https://codereview.appspot.com/14794043/
>

[rsc, 2013-11-18 21:43:48]

Please arrange for the type to have a name (maybe map.iter), similar to what I
did for map buckets in https://codereview.appspot.com/15110044.
I am a little worried about the unbounded zero type in the bss, but we can run
with it and see what happens.

Russ

[dvyukov, 2013-11-19 05:03:45]

LGTM

[rsc, 2013-11-19 14:28:04]

https://codereview.appspot.com/14794043/diff/246001/src/pkg/runtime/type.h
File src/pkg/runtime/type.h (right):

https://codereview.appspot.com/14794043/diff/246001/src/pkg/runtime/type.h#ne...
src/pkg/runtime/type.h:34: byte *zero;  // ptr to the zero value for this type
can we move this into the MapType?
then if someone is using code like

p := (*[1<<30]byte)(unsafe.Pointer(&q))[:n]

(with no map in sight) we don't try to arrange for 1<<30 zeros in the bss.

[rsc, 2013-11-19 14:28:28]

That is, the zero would be attached to the MapType and be a zero the size of the
map's value type.

[khr1, 2013-11-19 16:54:15]

I'd like to leave it there because I'm also going to be using the zero
value for other things, like assertI2T2.

Note that we only allocate space for the zero value if we actually need it.
 That is, we won't allocate 2^30 bytes for

p := (*[1<<30]byte)(unsafe.Pointer(&q))[:n]

only for something like

var m map[int][1<<30]byte
x := m[5]


On Tue, Nov 19, 2013 at 6:28 AM, <rsc@golang.org> wrote:

> That is, the zero would be attached to the MapType and be a zero the
> size of the map's value type.
>
>
> https://codereview.appspot.com/14794043/
>

[rsc, 2013-11-21 14:53:03]

On Tue, Nov 19, 2013 at 11:54 AM, Keith Randall <khr@google.com> wrote:

> I'd like to leave it there because I'm also going to be using the zero
> value for other things, like assertI2T2.
>

sounds good. please make the naming change though (map.iter types).

[khr1, 2013-11-21 17:07:42]

Ok, PTAL.


On Thu, Nov 21, 2013 at 6:53 AM, Russ Cox <rsc@golang.org> wrote:

> On Tue, Nov 19, 2013 at 11:54 AM, Keith Randall <khr@google.com> wrote:
>
>> I'd like to leave it there because I'm also going to be using the zero
>> value for other things, like assertI2T2.
>>
>
> sounds good. please make the naming change though (map.iter types).
>
>

[rsc, 2013-11-21 18:16:20]

LGTM

[khr, 2013-12-02 21:05:07]

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

runtime: pass key/value to map accessors by reference, not by value.

This change is part of the plan to get rid of all vararg C calls
which are a pain for getting exact stack scanning.

We allocate a chunk of zero memory to return a pointer to when a
map access doesn't find the key.  This is simpler than returning nil
and fixing things up in the caller.  Linker magic allocates a single
zero memory area that is shared by all (non-reflect-generated) map
types.

Passing things by reference gets rid of some copies, so it speeds
up code with big keys/values.

benchmark             old ns/op    new ns/op    delta
BenchmarkBigKeyMap           34           31   -8.48%
BenchmarkBigValMap           37           30  -18.62%
BenchmarkSmallKeyMap         26           23  -11.28%

R=golang-dev, dvyukov, khr, rsc
CC=golang-dev
https://codereview.appspot.com/14794043

[dave_cheney.net, 2013-12-02 23:19:25]

On 2013/12/02 21:05:07, khr wrote:
> *** Submitted as https://code.google.com/p/go/source/detail?r=6e50725ac753 ***
> 
> runtime: pass key/value to map accessors by reference, not by value.
> 
> This change is part of the plan to get rid of all vararg C calls
> which are a pain for getting exact stack scanning.
> 
> We allocate a chunk of zero memory to return a pointer to when a
> map access doesn't find the key.  This is simpler than returning nil
> and fixing things up in the caller.  Linker magic allocates a single
> zero memory area that is shared by all (non-reflect-generated) map
> types.
> 
> Passing things by reference gets rid of some copies, so it speeds
> up code with big keys/values.
> 
> benchmark             old ns/op    new ns/op    delta
> BenchmarkBigKeyMap           34           31   -8.48%
> BenchmarkBigValMap           37           30  -18.62%
> BenchmarkSmallKeyMap         26           23  -11.28%
> 
> R=golang-dev, dvyukov, khr, rsc
> CC=golang-dev
> https://codereview.appspot.com/14794043

This commit generated two build failures. Do you want bugs created for them, or
are you already on it ?

[khr1, 2013-12-02 23:30:44]

Bugs would be good.


On Mon, Dec 2, 2013 at 3:19 PM, <dave@cheney.net> wrote:

> On 2013/12/02 21:05:07, khr wrote:
>
>> *** Submitted as
>>
> https://code.google.com/p/go/source/detail?r=6e50725ac753 ***
>
>  runtime: pass key/value to map accessors by reference, not by value.
>>
>
>  This change is part of the plan to get rid of all vararg C calls
>> which are a pain for getting exact stack scanning.
>>
>
>  We allocate a chunk of zero memory to return a pointer to when a
>> map access doesn't find the key.  This is simpler than returning nil
>> and fixing things up in the caller.  Linker magic allocates a single
>> zero memory area that is shared by all (non-reflect-generated) map
>> types.
>>
>
>  Passing things by reference gets rid of some copies, so it speeds
>> up code with big keys/values.
>>
>
>  benchmark             old ns/op    new ns/op    delta
>> BenchmarkBigKeyMap           34           31   -8.48%
>> BenchmarkBigValMap           37           30  -18.62%
>> BenchmarkSmallKeyMap         26           23  -11.28%
>>
>
>  R=golang-dev, dvyukov, khr, rsc
>> CC=golang-dev
>> https://codereview.appspot.com/14794043
>>
>
> This commit generated two build failures. Do you want bugs created for
> them, or are you already on it ?
>
> https://codereview.appspot.com/14794043/
>