code review 135660043: runtime: map iterators: always use intrabucket randomess

runtime: map iterators: always use intrabucket randomess

Fixes issue 8688

[khr, 2014-09-09 21:01:38]

Hello golang-codereviews@googlegroups.com,

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

[bradfitz, 2014-09-09 21:06:38]

Can we modify that test to run 1024 times on its own too?


On Tue, Sep 9, 2014 at 2:01 PM, <khr@golang.org> wrote:

> Reviewers: golang-codereviews,
>
> Message:
> Hello golang-codereviews@googlegroups.com,
>
> I'd like you to review this change to
> https://khr%40golang.org@code.google.com/p/go/
>
>
> Description:
> runtime: map iterators: always use intrabucket randomess
>
> Fixes issue 8688
>
> Please review this at https://codereview.appspot.com/135660043/
>
> Affected files (+8, -12 lines):
>   M src/runtime/hashmap.go
>
>
> Index: src/runtime/hashmap.go
> ===================================================================
> --- a/src/runtime/hashmap.go
> +++ b/src/runtime/hashmap.go
> @@ -59,7 +59,8 @@
>
>  const (
>         // Maximum number of key/value pairs a bucket can hold.
> -       bucketCnt = 8
> +       bucketCntBits = 3
> +       bucketCnt     = 1 << bucketCntBits
>
>         // Maximum average load of a bucket that triggers growth.
>         loadFactor = 6.5
> @@ -138,7 +139,7 @@
>         offset      uint8          // intra-bucket offset to start from
> during iteration (should be big enough to hold bucketCnt-1)
>         wrapped     bool           // already wrapped around from end of
> bucket array to beginning
>         B           uint8
> -       i           uint8
> +       i           uint8
>         bucket      uintptr
>         checkBucket uintptr
>  }
> @@ -562,17 +563,12 @@
>         it.buckets = h.buckets
>
>         // decide where to start
> -       switch {
> -       case h.B == 0:
> -               it.startBucket = 0
> -               it.offset = uint8(fastrand1()) & (bucketCnt - 1)
> -       case h.B <= 31:
> -               it.startBucket = uintptr(fastrand1()) & (uintptr(1)<<h.B-1)
> -               it.offset = 0
> -       default:
> -               it.startBucket = (uintptr(fastrand1()) +
> uintptr(fastrand1())<<31) & (uintptr(1)<<h.B-1)
> -               it.offset = 0
> +       r := uintptr(fastrand1())
> +       if h.B > 31-bucketCntBits {
> +               r += uintptr(fastrand1()) << 31
>         }
> +       it.startBucket = r & (uintptr(1)<<h.B - 1)
> +       it.offset = uint8(r >> h.B & (bucketCnt - 1))
>
>         // iterator state
>         it.bucket = it.startBucket
>
>
> --
> 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/d/optout.
>

[rsc, 2014-09-09 21:19:21]

LGTM

[khr1, 2014-09-09 21:19:43]

Updated with repeated test.

Even at 1000 iterations, it is only ~60msec.


On Tue, Sep 9, 2014 at 2:06 PM, Brad Fitzpatrick <bradfitz@golang.org>
wrote:

> Can we modify that test to run 1024 times on its own too?
>
>
> On Tue, Sep 9, 2014 at 2:01 PM, <khr@golang.org> wrote:
>
>> Reviewers: golang-codereviews,
>>
>> Message:
>> Hello golang-codereviews@googlegroups.com,
>>
>> I'd like you to review this change to
>> https://khr%40golang.org@code.google.com/p/go/
>>
>>
>> Description:
>> runtime: map iterators: always use intrabucket randomess
>>
>> Fixes issue 8688
>>
>> Please review this at https://codereview.appspot.com/135660043/
>>
>> Affected files (+8, -12 lines):
>>   M src/runtime/hashmap.go
>>
>>
>> Index: src/runtime/hashmap.go
>> ===================================================================
>> --- a/src/runtime/hashmap.go
>> +++ b/src/runtime/hashmap.go
>> @@ -59,7 +59,8 @@
>>
>>  const (
>>         // Maximum number of key/value pairs a bucket can hold.
>> -       bucketCnt = 8
>> +       bucketCntBits = 3
>> +       bucketCnt     = 1 << bucketCntBits
>>
>>         // Maximum average load of a bucket that triggers growth.
>>         loadFactor = 6.5
>> @@ -138,7 +139,7 @@
>>         offset      uint8          // intra-bucket offset to start from
>> during iteration (should be big enough to hold bucketCnt-1)
>>         wrapped     bool           // already wrapped around from end of
>> bucket array to beginning
>>         B           uint8
>> -       i           uint8
>> +       i           uint8
>>         bucket      uintptr
>>         checkBucket uintptr
>>  }
>> @@ -562,17 +563,12 @@
>>         it.buckets = h.buckets
>>
>>         // decide where to start
>> -       switch {
>> -       case h.B == 0:
>> -               it.startBucket = 0
>> -               it.offset = uint8(fastrand1()) & (bucketCnt - 1)
>> -       case h.B <= 31:
>> -               it.startBucket = uintptr(fastrand1()) &
>> (uintptr(1)<<h.B-1)
>> -               it.offset = 0
>> -       default:
>> -               it.startBucket = (uintptr(fastrand1()) +
>> uintptr(fastrand1())<<31) & (uintptr(1)<<h.B-1)
>> -               it.offset = 0
>> +       r := uintptr(fastrand1())
>> +       if h.B > 31-bucketCntBits {
>> +               r += uintptr(fastrand1()) << 31
>>         }
>> +       it.startBucket = r & (uintptr(1)<<h.B - 1)
>> +       it.offset = uint8(r >> h.B & (bucketCnt - 1))
>>
>>         // iterator state
>>         it.bucket = it.startBucket
>>
>>
>>
>> --
>> 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/d/optout.
>>
>
>

[khr, 2014-09-09 21:23:01]

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

runtime: map iterators: always use intrabucket randomess

Fixes issue 8688

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

[gobot, 2014-09-10 00:06:22]

This CL appears to have broken the windows-amd64-perf builder.
See http://build.golang.org/log/4aabe2fa36ab73fe0b942e520b1a41e02d735e81