code review 8852047: runtime: do hashmap grow work during reads.

runtime: do hashmap grow work during reads.

Before this change, grow work was done only
during map writes to ensure multithreaded safety.
This can lead to maps remaining in a partially
grown state for a long time, potentially forever.
This change allows grow work to happen during reads,
which will lead to grow work finishing sooner, making
the resulting map smaller and faster.

Grow work is not done in parallel.  Reads can
happen in parallel while grow work is happening.

[khr, 2013-05-23 22:17:54]

Hello golang-dev@googlegroups.com,

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

[dvyukov, 2013-05-24 08:22:33]

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

https://codereview.appspot.com/8852047/diff/19003/src/pkg/runtime/hashmap.c#n...
src/pkg/runtime/hashmap.c:447: h->nevacuate = n + 1;
please use atomicstorep() to release the lock

https://codereview.appspot.com/8852047/diff/19003/src/pkg/runtime/hashmap.c#n...
src/pkg/runtime/hashmap.c:448: if(n + 1 == noldbuckets) {
h->B can not change while we are here, right?
otherwise here would be a subtle race if checked against wrong (smaller) h->B

[khr1, 2013-05-24 13:28:14]

On Fri, May 24, 2013 at 1:22 AM, <dvyukov@google.com> wrote:

>
> https://codereview.appspot.**com/8852047/diff/19003/src/**
>
pkg/runtime/hashmap.c<https://codereview.appspot.com/8852047/diff/19003/src/pkg/runtime/hashmap.c>
> File src/pkg/runtime/hashmap.c (right):
>
> https://codereview.appspot.**com/8852047/diff/19003/src/**
>
pkg/runtime/hashmap.c#**newcode447<https://codereview.appspot.com/8852047/diff/19003/src/pkg/runtime/hashmap.c#newcode447>
> src/pkg/runtime/hashmap.c:447: h->nevacuate = n + 1;
> please use atomicstorep() to release the lock
>

Done

>
> https://codereview.appspot.**com/8852047/diff/19003/src/**
>
pkg/runtime/hashmap.c#**newcode448<https://codereview.appspot.com/8852047/diff/19003/src/pkg/runtime/hashmap.c#newcode448>
> src/pkg/runtime/hashmap.c:448: if(n + 1 == noldbuckets) {
> h->B can not change while we are here, right?
> otherwise here would be a subtle race if checked against wrong (smaller)
> h->B
>

Right, while we're inside grow_work_read, we're guaranteed that no one is
writing the hashtable, so no one is calling hash_grow, which is the only
thing that changes B.


>
>
https://codereview.appspot.**com/8852047/<https://codereview.appspot.com/8852...
>
> --
>
> ---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...
> .
>
>
>

[dvyukov, 2013-05-31 04:15:47]

On 2013/05/24 13:28:14, khr1 wrote:
> On Fri, May 24, 2013 at 1:22 AM, <mailto:dvyukov@google.com> wrote:
> 
> >
> > https://codereview.appspot.**com/8852047/diff/19003/src/**
> >
>
pkg/runtime/hashmap.c<https://codereview.appspot.com/8852047/diff/19003/src/pkg/runtime/hashmap.c>
> > File src/pkg/runtime/hashmap.c (right):
> >
> > https://codereview.appspot.**com/8852047/diff/19003/src/**
> >
>
pkg/runtime/hashmap.c#**newcode447<https://codereview.appspot.com/8852047/diff/19003/src/pkg/runtime/hashmap.c#newcode447>
> > src/pkg/runtime/hashmap.c:447: h->nevacuate = n + 1;
> > please use atomicstorep() to release the lock
> >
> 
> Done


You seem to forget to upload the new version.

[khr1, 2013-05-31 04:27:45]

Sorry about that, it's up now.


On Thu, May 30, 2013 at 9:15 PM, <dvyukov@google.com> wrote:

> On 2013/05/24 13:28:14, khr1 wrote:
>
>> On Fri, May 24, 2013 at 1:22 AM, <mailto:dvyukov@google.com> wrote:
>>
>
>  >
>> > https://codereview.appspot.****com/8852047/diff/19003/src/**
>> >
>>
>
> pkg/runtime/hashmap.c<https://**codereview.appspot.com/**
>
8852047/diff/19003/src/pkg/**runtime/hashmap.c<https://codereview.appspot.com/8852047/diff/19003/src/pkg/runtime/hashmap.c>
> >
>
>> > File src/pkg/runtime/hashmap.c (right):
>> >
>> > https://codereview.appspot.****com/8852047/diff/19003/src/**
>> >
>>
>
> pkg/runtime/hashmap.c#****newcode447<https://codereview.**
>
appspot.com/8852047/diff/**19003/src/pkg/runtime/hashmap.**c#newcode447<https://codereview.appspot.com/8852047/diff/19003/src/pkg/runtime/hashmap.c#newcode447>
> >
>
>  > src/pkg/runtime/hashmap.c:447: h->nevacuate = n + 1;
>> > please use atomicstorep() to release the lock
>> >
>>
>
>  Done
>>
>
>
> You seem to forget to upload the new version.
>
>
https://codereview.appspot.**com/8852047/<https://codereview.appspot.com/8852...
>

[dvyukov, 2013-05-31 05:31:08]

LGTM
I never looked at hashmap code closely before, so I am not skilled to review
this in all details. But I understand what you are doing.
If you are sure in this and all.bash passes, I think you can submit. Or
otherwise wait for another review.

[iant, 2013-06-01 00:05:41]

LGTM

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

https://codereview.appspot.com/8852047/diff/27001/src/pkg/runtime/hashmap.c#n...
src/pkg/runtime/hashmap.c:120: CanFreeBucket = 16, // ok to free buckets
As far as I can tell the CanFreeBucket flag is no longer used.  It seems that
the code never free buckets and always relies on the GC.  Which is fine.

https://codereview.appspot.com/8852047/diff/27001/src/pkg/runtime/hashmap.c#n...
src/pkg/runtime/hashmap.c:407: // Ensure that bucket has been evacuated from
oldbucket so that we can modify it.
s/oldbucket/oldbuckets/ ?

[khr1, 2013-06-01 03:55:41]

On Fri, May 31, 2013 at 5:05 PM, <iant@golang.org> wrote:

> LGTM
>
>
> https://codereview.appspot.**com/8852047/diff/27001/src/**
>
pkg/runtime/hashmap.c<https://codereview.appspot.com/8852047/diff/27001/src/pkg/runtime/hashmap.c>
> File src/pkg/runtime/hashmap.c (right):
>
> https://codereview.appspot.**com/8852047/diff/27001/src/**
>
pkg/runtime/hashmap.c#**newcode120<https://codereview.appspot.com/8852047/diff/27001/src/pkg/runtime/hashmap.c#newcode120>
> src/pkg/runtime/hashmap.c:120: CanFreeBucket = 16, // ok to free buckets
> As far as I can tell the CanFreeBucket flag is no longer used.  It seems
> that the code never free buckets and always relies on the GC.  Which is
> fine.
>
>
Yes, I added a TODO to clean this up.


> https://codereview.appspot.**com/8852047/diff/27001/src/**
>
pkg/runtime/hashmap.c#**newcode407<https://codereview.appspot.com/8852047/diff/27001/src/pkg/runtime/hashmap.c#newcode407>
> src/pkg/runtime/hashmap.c:407: // Ensure that bucket has been evacuated
> from oldbucket so that we can modify it.
> s/oldbucket/oldbuckets/ ?
>
>
Done.


>
https://codereview.appspot.**com/8852047/<https://codereview.appspot.com/8852...
>

[khr, 2013-06-01 03:58:34]

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

runtime: do hashmap grow work during reads.

Before this change, grow work was done only
during map writes to ensure multithreaded safety.
This can lead to maps remaining in a partially
grown state for a long time, potentially forever.
This change allows grow work to happen during reads,
which will lead to grow work finishing sooner, making
the resulting map smaller and faster.

Grow work is not done in parallel.  Reads can
happen in parallel while grow work is happening.

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