code review 14367043: runtime: fix bug in maps at the intersection of iterato...

runtime: fix bug in maps at the intersection of iterators, growing, and NaN keys

If an iterator is started while a map is in the middle of a grow,
and the map has NaN keys, then those keys might get returned by
the iterator more than once.  This fix makes the evacuation decision
deterministic and repeatable for NaN keys so each one gets returned
only once.

[khr, 2013-10-03 23:37:11]

Hello golang-dev@googlegroups.com,

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

[r, 2013-10-03 23:40:33]

https://codereview.appspot.com/14367043/diff/6001/src/pkg/runtime/map_test.go
File src/pkg/runtime/map_test.go (right):

https://codereview.appspot.com/14367043/diff/6001/src/pkg/runtime/map_test.go...
src/pkg/runtime/map_test.go:389: // Trigger grow
can you verify that it's full? the 13 is a little magical.

[khr1, 2013-10-04 00:11:55]

Yes, 6.5 = 13/2.  I don't think it is worth exposing that constant from
inside of hashmap.c just for this test.



On Thu, Oct 3, 2013 at 4:40 PM, <r@golang.org> wrote:

>
> https://codereview.appspot.**com/14367043/diff/6001/src/**
>
pkg/runtime/map_test.go<https://codereview.appspot.com/14367043/diff/6001/src/pkg/runtime/map_test.go>
> File src/pkg/runtime/map_test.go (right):
>
> https://codereview.appspot.**com/14367043/diff/6001/src/**
>
pkg/runtime/map_test.go#**newcode389<https://codereview.appspot.com/14367043/diff/6001/src/pkg/runtime/map_test.go#newcode389>
> src/pkg/runtime/map_test.go:**389: // Trigger grow
> can you verify that it's full? the 13 is a little magical.
>
>
https://codereview.appspot.**com/14367043/<https://codereview.appspot.com/143...
>

[r, 2013-10-04 00:25:13]

It's trivial: just add a line to export_test.go

-rob

[iant, 2013-10-04 16:20:21]

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

https://codereview.appspot.com/14367043/diff/6001/src/pkg/runtime/hashmap.c#n...
src/pkg/runtime/hashmap.c:886: if(check_bucket >> (it->B - 1) != (b->tophash[i]
& 1)) {
I don't understand why this condition is using check_bucket.  If I'm following
this code, what you want here is a condition that is random and can also be
repeated in evacuate.  But evacuate isn't using check_bucket or anything like
it.  What am I missing?

[khr1, 2013-10-04 20:04:06]

On Fri, Oct 4, 2013 at 9:20 AM, <iant@golang.org> wrote:

>
> https://codereview.appspot.**com/14367043/diff/6001/src/**
>
pkg/runtime/hashmap.c<https://codereview.appspot.com/14367043/diff/6001/src/pkg/runtime/hashmap.c>
> File src/pkg/runtime/hashmap.c (right):
>
> https://codereview.appspot.**com/14367043/diff/6001/src/**
>
pkg/runtime/hashmap.c#**newcode886<https://codereview.appspot.com/14367043/diff/6001/src/pkg/runtime/hashmap.c#newcode886>
> src/pkg/runtime/hashmap.c:886: if(check_bucket >> (it->B - 1) !=
> (b->tophash[i] & 1)) {
> I don't understand why this condition is using check_bucket.  If I'm
> following this code, what you want here is a condition that is random
> and can also be repeated in evacuate.  But evacuate isn't using
> check_bucket or anything like it.  What am I missing?
>

They are working in opposite directions, so it's a bit confusing.  evacuate
is starting from an old bucket and moving to a new bucket.  The relevant
part of hash_iter is starting with a new bucket and figuring out which of
the items in the old bucket will eventually end up there.  check_bucket is
the new bucket ID when we are iterating through the old bucket, but really
it could just be a 1-bit value, as we know the rest of the bits must match
(at least for non-NaNs).

So evacuate is using the low bit of tophash to pick among the two
newbuckets to send an object to.  hash_iter is using the low bit of tophash
to decide whether the the oldbucket item will come to the newbucket or not.
 Make any sense?


>
>
https://codereview.appspot.**com/14367043/<https://codereview.appspot.com/143...
>

[khr1, 2013-10-04 20:06:04]

On Thu, Oct 3, 2013 at 5:24 PM, Rob Pike <r@golang.org> wrote:

> It's trivial: just add a line to export_test.go
>
>
Ok, did that.


> -rob
>
>

[iant, 2013-10-04 20:19:45]

LGTM

[r, 2013-10-04 20:30:42]

LGTM but please remove some capital letters

https://codereview.appspot.com/14367043/diff/20001/src/pkg/runtime/map_test.go
File src/pkg/runtime/map_test.go (right):

https://codereview.appspot.com/14367043/diff/20001/src/pkg/runtime/map_test.g...
src/pkg/runtime/map_test.go:380: const NBUCKETS = 16
this is not usual Go style. how about NBuckets or nBuckets?

https://codereview.appspot.com/14367043/diff/20001/src/pkg/runtime/map_test.g...
src/pkg/runtime/map_test.go:382: NKEYS := int(NBUCKETS * *runtime.HashLoad)
ditto

[khr, 2013-10-04 20:54:06]

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

runtime: fix bug in maps at the intersection of iterators, growing, and NaN keys

If an iterator is started while a map is in the middle of a grow,
and the map has NaN keys, then those keys might get returned by
the iterator more than once.  This fix makes the evacuation decision
deterministic and repeatable for NaN keys so each one gets returned
only once.

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