code review 141270043: runtime: on bigger maps, start iterator at a random bucket.

runtime: on bigger maps, start iterator at a random bucket.

This change brings the iter/delete pattern down to O(n lgn) from O(n^2).

Fixes issue 8412.

before:
BenchmarkMapPop100	   50000	     32498 ns/op
BenchmarkMapPop1000	     500	   3244851 ns/op
BenchmarkMapPop10000	       5	 270276855 ns/op

after:
BenchmarkMapPop100	  100000	     16169 ns/op
BenchmarkMapPop1000	    5000	    300416 ns/op
BenchmarkMapPop10000	     300	   5990814 ns/op

[khr, 2014-09-08 20:33:07]

Hello golang-codereviews@googlegroups.com,

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

[iant, 2014-09-08 23:00:29]

https://codereview.appspot.com/141270043/diff/80001/src/runtime/hashmap.go
File src/runtime/hashmap.go (right):

https://codereview.appspot.com/141270043/diff/80001/src/runtime/hashmap.go#ne...
src/runtime/hashmap.go:128: // If you modify hiter, also change cmd/gc/reflect.c
to indicate
This comment says you need to change cmd/gc/reflect.c, but there is no such
change in this CL.  Either that file should change or this comment should
change.

[khr1, 2014-09-08 23:07:37]

On Mon, Sep 8, 2014 at 4:00 PM, <iant@golang.org> wrote:

>
> https://codereview.appspot.com/141270043/diff/80001/src/runtime/hashmap.go
> File src/runtime/hashmap.go (right):
>
> https://codereview.appspot.com/141270043/diff/80001/src/
> runtime/hashmap.go#newcode128
> src/runtime/hashmap.go:128: // If you modify hiter, also change
> cmd/gc/reflect.c to indicate
> This comment says you need to change cmd/gc/reflect.c, but there is no
> such change in this CL.  Either that file should change or this comment
> should change.
>
>
I've carefully edited hiter so that there is no compiler change.  In
particular, the first 6 words are pointers, the rest aren't, and the total
size is unchanged.


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

[iant, 2014-09-09 00:00:04]

LGTM

[khr, 2014-09-09 00:42:24]

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

runtime: on bigger maps, start iterator at a random bucket.

This change brings the iter/delete pattern down to O(n lgn) from O(n^2).

Fixes issue 8412.

before:
BenchmarkMapPop100	   50000	     32498 ns/op
BenchmarkMapPop1000	     500	   3244851 ns/op
BenchmarkMapPop10000	       5	 270276855 ns/op

after:
BenchmarkMapPop100	  100000	     16169 ns/op
BenchmarkMapPop1000	    5000	    300416 ns/op
BenchmarkMapPop10000	     300	   5990814 ns/op

LGTM=iant
R=golang-codereviews, iant, khr
CC=golang-codereviews
https://codereview.appspot.com/141270043

[rsc, 2014-09-09 00:49:52]

Please add a proper test, perhaps along the lines of test/maplinear.go. 
The benchmark is good but it won't keep us from breaking this again
the next time we rewrite maps.