runtime: maps not randomized using range

[gopherbot]

by blake.mizerany:

What steps will reproduce the problem?
If possible, include a link to a program on play.golang.org.

  1. http://play.golang.org/p/O9ZT3iTqJ_

What is the expected output?

  I expect to see different permutations across runs.

  Locally, I see the keys outputted in the same order I insert them, across runs.

Which compiler are you using (5g, 6g, 8g, gccgo)?

  6g

Which operating system are you using?

  OS X 10.8.3

Which version are you using?  (run 'go version')

  go version devel +5e23075b0970 Fri Apr 26 11:42:58 2013 -0700 darwin/amd64

Additional information:

  A colleague running`go version go1.0.3` sees random output across runs.

[ianlancetaylor]

Comment 1:

The Go 1.1 hashmap iteration starts at a random bucket.  However, it stores up to 8
key/value pairs in a bucket.  And within a bucket, hashmap iteration always returns the
values in the same order.  So when you have fewer than 8 key/value pairs, as in your
example, the order of iteration is predictable.
I don't know if this is a problem.

[gopherbot]

Comment 2 by blake.mizerany:

Ah, I see. I don't know if it is a problem either. It is an inconvenience
for me since my map contains only a few keys and I need a random key. I
noticed this "issue" while testing this:
for k, _ := range mySmallMap {
    return k
}
I was predicting the unpredictable.
Instead I could:
i := 0
n := rand.Intn(len(mySmallMap))
for k, _ := range mySmallMap {
    if n = i {
        return k
    }
    i++
}
I'm not sure if this has the performance advantages of a larger map using
only the first key given by a range loop. I'm also not sure I care about
that right now.
Thank you for your help.
-b

[randall77]

Comment 3:

Don't rely on the ordering for ranges over maps.  Relying on it to be random is just as
bad as relying on it to be sorted, or repeatable, or whatever.  Making it random is an
attempt to *prevent* people from relying on the order, not an *invitation* to rely on
the order for randomness.
As you have noticed, the randomness could be improved, but I don't think it's a high
priority.  The randomness costs something, so we use as little of it as possible, just
enough to make the order not consistent (to prevent people from relying on consistent
ordering).  The fact that <=8 size maps return a consistent order bothers me a tiny
bit, but I'm not going to lose sleep over it.

[randall77]

Comment 4:

Labels changed: added priority-someday, removed priority-triage.

[remyoudompheng]

Comment 5:

Shouldn't maps get at least a different hash seed (using fastrand for example), each
time a new one is created?
abusing the randomness to select a random key with a range loop does not work in Go 1
either. Even with extremely trivial examples the result is biased towards a key at 99%.
So there is no regression here.
http://play.golang.org/p/9-UM0V6ww2

[randall77]

Comment 6:

Maps do get a different hash seed using fastrand on each create.  The hash does not
affect the order for maps of size 8 or less.

[randall77]

Comment 7:

Owner changed to @randall77.

Status changed to WontFix.