code review 47370043: runtime: make map iteration start at a random offset wi...

runtime: change map iteration randomization to use intra-bucket offset

Map iteration previously started from a random bucket, but walked each
bucket from the beginning. Now, iteration always starts from the first
bucket and walks each bucket starting at a random offset. For
performance, the random offset is selected at the start of iteration
and reused for each bucket.

Iteration over a map with 8 or fewer elements--a single bucket--will
now be non-deterministic. There will now be only 8 different possible
map iterations.

Significant benchmark changes, on my OS X laptop (rough but consistent):

benchmark                              old ns/op     new ns/op     delta
BenchmarkMapIter                       128           121           -5.47%
BenchmarkMapIterEmpty                  4.26          4.45          +4.46%
BenchmarkNewEmptyMap                   114           111           -2.63%

Fixes issue 6719.

[khr, 2014-01-06 06:11:28]

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

https://codereview.appspot.com/47370043/diff/40001/src/pkg/runtime/hashmap.c#...
src/pkg/runtime/hashmap.c:787: it->bucket = it->endbucket = (rand >>
BUCKETSIZE_BITS) & (((uintptr)1 << h->B) - 1);
I don't think you need BUCKETSIZE_BITS.  Just do "/ BUCKETSIZE" instead of ">>
BUCKETSIZE_BITS" and you'll get the right behavior.

[josharian, 2014-01-06 13:30:26]

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

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

[josharian, 2014-01-06 13:30:50]

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

https://codereview.appspot.com/47370043/diff/40001/src/pkg/runtime/hashmap.c#...
src/pkg/runtime/hashmap.c:787: it->bucket = it->endbucket = (rand >>
BUCKETSIZE_BITS) & (((uintptr)1 << h->B) - 1);
On 2014/01/06 06:11:29, khr wrote:
> I don't think you need BUCKETSIZE_BITS.  Just do "/ BUCKETSIZE" instead of ">>
> BUCKETSIZE_BITS" and you'll get the right behavior.

Done, thanks.

[josharian, 2014-01-13 02:53:57]

PTAL

New:

* No longer randomize starting bucket (cf discussion in CL 48340043 and CL
47330043).
* Update description and benchmarks.

I have a nagging feeling there ought to be more simplification possible, but I
don't see it.

-josh

[khr, 2014-01-14 05:00:12]

On 2014/01/13 02:53:57, josharian wrote:
> PTAL
> 
> New:
> 
> * No longer randomize starting bucket (cf discussion in CL 48340043 and CL
> 47330043).
> * Update description and benchmarks.
> 
> I have a nagging feeling there ought to be more simplification possible, but I
> don't see it.
> 
> -josh

LGTM.

[bradfitz, 2014-01-14 17:39:57]

Keith,

You want to submit this for Josh?



On Mon, Jan 13, 2014 at 9:00 PM, <khr@golang.org> wrote:

> On 2014/01/13 02:53:57, josharian wrote:
>
>> PTAL
>>
>
>  New:
>>
>
>  * No longer randomize starting bucket (cf discussion in CL 48340043
>>
> and CL
>
>> 47330043).
>> * Update description and benchmarks.
>>
>
>  I have a nagging feeling there ought to be more simplification
>>
> possible, but I
>
>> don't see it.
>>
>
>  -josh
>>
>
> LGTM.
>
>
>
> https://codereview.appspot.com/47370043/
>
> --
> You received this message because you are subscribed to the Google Groups
> "golang-codereviews" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to golang-codereviews+unsubscribe@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>

[khr, 2014-01-14 20:54:08]

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

runtime: change map iteration randomization to use intra-bucket offset

Map iteration previously started from a random bucket, but walked each
bucket from the beginning. Now, iteration always starts from the first
bucket and walks each bucket starting at a random offset. For
performance, the random offset is selected at the start of iteration
and reused for each bucket.

Iteration over a map with 8 or fewer elements--a single bucket--will
now be non-deterministic. There will now be only 8 different possible
map iterations.

Significant benchmark changes, on my OS X laptop (rough but consistent):

benchmark                              old ns/op     new ns/op     delta
BenchmarkMapIter                       128           121           -5.47%
BenchmarkMapIterEmpty                  4.26          4.45          +4.46%
BenchmarkNewEmptyMap                   114           111           -2.63%

Fixes issue 6719.

R=khr, bradfitz
CC=golang-codereviews
https://codereview.appspot.com/47370043

Committer: Keith Randall <khr@golang.org>