Comment 1:

The patch
changeset:   18847:6ea672cbfe43
user:        Josh Bleecher Snyder <josharian@gmail.com>
date:        Tue Jan 14 12:54:05 2014 -0800
summary:     runtime: change map iteration randomization to use intra-bucket offset
changed randomization to cyclically shuffle each bucket, but doesn't start iteration at
a random bucket. As a consequence When a map is very sparse (1 item per bucket),
randomization is ineffective.
Another issue is that a "pop" pattern: deleting an element of the map after first
iteration, will leave the map in a very unbalanced state. Popping all elements will take
a quadratic time instead of something like O(n log n) or maybe a bit more as it is in Go
1.2.

Comment 2:

Status changed to Accepted.

Comment 3:

Is there a real-world style program that this shows up in?
If we want to fix this by randomizing both the offset and the starting bucket (which has
a minor performance cost), there's an implementation of that in Patch Set 5 of CL
47370043.

Comment 4:

Labels changed: added release-go1.4.

Comment 5:

The quadratic pattern happened as a visible performance regression in a real program. It
was possible to work it around by modifying the algorithm.

Comment 6:

We're not shooting for perfect iteration randomness.  We only provide enough randomness
to make sure people aren't depending on iteration order.  We do it to ensure that we can
change the map implementation at some future time and not break people's incorrect code.
Yes, the iteration is not random if the first bucket has <=1 element.  That will only
happen with very sparse maps, which requires inserting and then deleting most elements. 
I'm not particularly worried about that corner case.
The O(n^2) pop problem is more worrying.  Starting at a random bucket as in 1.2 would
help.  Maybe better is to keep track of (a conservative approximation of) the minimum
nonempty bucket.

Comment 7:

I've split out the O(n^2) performance problem into issue #8412.  Let's keep this bug
about the nonrandomness.

Comment 8:

CL https://golang.org/cl/137560044 mentions this issue.

Comment 9:

This issue was closed by revision d6cd230.

Status changed to Fixed.