15 ms·

The Go designers went the other way (as they often do): > When iterating over a map with a range loop, the iteration order is not specified and is not guarante

by rob74 7y ago

The Go designers went the other way (as they often do): > When iterating over a map with a range loop, the iteration order is not specified and is not guaranteed to be the same from one iteration to the next. Actually it is not only "not guaranteed to be the same", the runtime actively makes sure that the iteration order is actually different so you don't even start to rely on it...

tele_ski 7y ago
That seems like it would be a performance hit to actively make it different? That seems like a very weird and strange design decision if true
- TheNorthman 7y ago
  It actually doesn't make that much of a difference. See this commit for actual benchmarks about the impact: https://github.com/golang/go/commit/3be4d95731a17073afb1f69bde264eecbdfa32bb https://github.com/golang/go/commit/3be4d95731a17073afb1f69b...
- dallbee 7y ago
  It is a performance hit and I initially had the same reservations. Importantly, the implementation imposes a small overhead on the access time of iteration over a map, but not in a way which changes the scaling behavior. Other map operations are not implicated. I think the decision was wise - it prevents user code from relying on ordered iteration behavior, which allows the go team to switch to different map implementations without fear of breaking user code. If the order had been unspecified, but iteration was still ordered in practice, there'd undoubtedly be (incorrect) user code that relied on that behavior. Amusingly, I now run into engineers who are under the misconception that map iteration is random, and proceed to use maps as an RNG. That's an unfortunate mistake because Go's map iteration is quite non-uniform - it's shuffled just enough to appear random to the untrained eye, while be performant.
- adev_ 7y ago
  > That seems like it would be a performance hit to actively make it different Not really. I don't know the go implementation but you can get this behaviour by adding an arbitrary "startup defined" seed to your hash function and that does the trick. It also gives the benefit of making hash table attacks harder.
- jerf 7y ago
  It's a very small performance hit because it doesn't do the work to be uniformly random, just "not always the same". If you think about how you have to iterate through a hash table or similar data structure anyhow, it's either O(1) or O(log n) paid once per "range" on the data structure, which is dwarfed by the actual act of ranging on the data structure. Go's philosophy is also definitely willing to pay that price to avoid a large class of known bugs that has hit all kinds of code bases. It is not about being the fastest language. As compiled languages go, it's solidly middle-tier, and not likely to go up much from there. (Among the C-style compiled languages, it's low-tier on performance, at around half the speed of C in general. However there's enough compiled languages like Haskell that are still generally relatively slow so that Go is mid-tier for compiled languages over all.)
3fe9a03ccd14ca5 7y ago
It’s kind of annoying, but does catch an easily missed novice mistake.
mpfundstein 7y ago
Ah i love go. While its mega cumbersome sometimes and lacks generics (WHY????) , i found that i write pretty stable code in it that still looks good after years (^^)
ivanfon 7y ago
In case anyone else is curious: https://github.com/golang/go/issues/6719 https://github.com/golang/go/issues/6719
Someone 7y ago
That’s fairly common, as it is protection against denial-of-service attacks that use hash collisions to make code perform poorly (https://events.ccc.de/2011/12/28/crypto-talk-at-28c3-effective-denial-of-service-attacks-against-web-application-platforms-day-2-1400-saal-1/ https://events.ccc.de/2011/12/28/crypto-talk-at-28c3-effecti...) If I read https://lwn.net/Articles/474912/ https://lwn.net/Articles/474912/ correctly, Perl fixed that in 2003. C#, Java and Swift do it, too. As does (or, reading this, did?) Python (https://bugs.python.org/issue13703 https://bugs.python.org/issue13703)
- jnwatson 7y ago
  The hash value order and insertion order are unrelated.
- to11mtm 7y ago
  > C#, Java and Swift do it, too. Welllllllll In the case of C# it is/was more a matter of picking the -correct- Dictionary. 'OrderedDictionary' has been around since Net 2.0 (2005 or so,) as has 'SortedDictionary<TKey, TValue>' But for some ungodly reason, there is no 'OrderedDictionary<TKey,TValue>' included in the framework that you can use. All you get normally is the non-generic one (where you have to type-check everything...) There are internal implementations used by the framework, but you'd have to do some hacky things to even get it to work. However, in my 12 years of C# programming, I've only run into the need for this _once_, and it was to assist interfacing with a VB6 monstrosity.
masklinn 7y ago
Python kinda sorta did the same from Python 3.3 to 3.5: iteration order was not actively randomised but the hash was "seeded" (for DDOS resistance) so iteration order would only be coherent within a run, which in effect made it unreliable. Python 3.6 changed the underlying implementation to one which incidentally made iteration order not rely on the hash function, and as that seemed like a useful property and one which risked causing compatibility issues with alternate implementation (developers would come to rely on cpython's iteration order and code would break on jython or whatever) they decided to make it part of the spec for 3.7.

by rob74 7y ago

tele_ski 7y ago

That seems like it would be a performance hit to actively make it different? That seems like a very weird and strange design decision if true

TheNorthman 7y ago
It actually doesn't make that much of a difference. See this commit for actual benchmarks about the impact: https://github.com/golang/go/commit/3be4d95731a17073afb1f69bde264eecbdfa32bb https://github.com/golang/go/commit/3be4d95731a17073afb1f69b...
dallbee 7y ago
It is a performance hit and I initially had the same reservations. Importantly, the implementation imposes a small overhead on the access time of iteration over a map, but not in a way which changes the scaling behavior. Other map operations are not implicated. I think the decision was wise - it prevents user code from relying on ordered iteration behavior, which allows the go team to switch to different map implementations without fear of breaking user code. If the order had been unspecified, but iteration was still ordered in practice, there'd undoubtedly be (incorrect) user code that relied on that behavior. Amusingly, I now run into engineers who are under the misconception that map iteration is random, and proceed to use maps as an RNG. That's an unfortunate mistake because Go's map iteration is quite non-uniform - it's shuffled just enough to appear random to the untrained eye, while be performant.
adev_ 7y ago
> That seems like it would be a performance hit to actively make it different Not really. I don't know the go implementation but you can get this behaviour by adding an arbitrary "startup defined" seed to your hash function and that does the trick. It also gives the benefit of making hash table attacks harder.
jerf 7y ago
It's a very small performance hit because it doesn't do the work to be uniformly random, just "not always the same". If you think about how you have to iterate through a hash table or similar data structure anyhow, it's either O(1) or O(log n) paid once per "range" on the data structure, which is dwarfed by the actual act of ranging on the data structure. Go's philosophy is also definitely willing to pay that price to avoid a large class of known bugs that has hit all kinds of code bases. It is not about being the fastest language. As compiled languages go, it's solidly middle-tier, and not likely to go up much from there. (Among the C-style compiled languages, it's low-tier on performance, at around half the speed of C in general. However there's enough compiled languages like Haskell that are still generally relatively slow so that Go is mid-tier for compiled languages over all.)

3fe9a03ccd14ca5 7y ago

It’s kind of annoying, but does catch an easily missed novice mistake.

mpfundstein 7y ago

Ah i love go. While its mega cumbersome sometimes and lacks generics (WHY????) , i found that i write pretty stable code in it that still looks good after years (^^)

ivanfon 7y ago

In case anyone else is curious: https://github.com/golang/go/issues/6719 https://github.com/golang/go/issues/6719

Someone 7y ago

That’s fairly common, as it is protection against denial-of-service attacks that use hash collisions to make code perform poorly (https://events.ccc.de/2011/12/28/crypto-talk-at-28c3-effective-denial-of-service-attacks-against-web-application-platforms-day-2-1400-saal-1/ https://events.ccc.de/2011/12/28/crypto-talk-at-28c3-effecti...) If I read https://lwn.net/Articles/474912/ https://lwn.net/Articles/474912/ correctly, Perl fixed that in 2003. C#, Java and Swift do it, too. As does (or, reading this, did?) Python (https://bugs.python.org/issue13703 https://bugs.python.org/issue13703)

jnwatson 7y ago
The hash value order and insertion order are unrelated.
to11mtm 7y ago
> C#, Java and Swift do it, too. Welllllllll In the case of C# it is/was more a matter of picking the -correct- Dictionary. 'OrderedDictionary' has been around since Net 2.0 (2005 or so,) as has 'SortedDictionary<TKey, TValue>' But for some ungodly reason, there is no 'OrderedDictionary<TKey,TValue>' included in the framework that you can use. All you get normally is the non-generic one (where you have to type-check everything...) There are internal implementations used by the framework, but you'd have to do some hacky things to even get it to work. However, in my 12 years of C# programming, I've only run into the need for this _once_, and it was to assist interfacing with a VB6 monstrosity.

masklinn 7y ago

Python kinda sorta did the same from Python 3.3 to 3.5: iteration order was not actively randomised but the hash was "seeded" (for DDOS resistance) so iteration order would only be coherent within a run, which in effect made it unreliable. Python 3.6 changed the underlying implementation to one which incidentally made iteration order not rely on the hash function, and as that seemed like a useful property and one which risked causing compatibility issues with alternate implementation (developers would come to rely on cpython's iteration order and code would break on jython or whatever) they decided to make it part of the spec for 3.7.