4 ms·

The Go runtime explicitly randomizes the iteration of map, because the language designers noticed 'Programmers had begun to rely on the stable iteration order'[

The Go runtime explicitly randomizes the iteration of map, because the language designers noticed 'Programmers had begun to rely on the stable iteration order'[0]. Most languages, as far as I can tell, tell you that the iteration order is undefined but frequently have some stable iteration order that's consistent for the compiler or the system architecture, and don't take the extra step of randomization. [0]https://blog.golang.org/go-maps-in-action https://blog.golang.org/go-maps-in-action - Header: Iteration Order

krylon 8y ago
Thanks for the clarification! When I first learned about hash tables (in Perl), the book I used said that the iteration order over a hash should never ever be relied upon, and that it could change arbitrarily from one release to the next. If the order mattered, one should use a different approach (get the keys and sort them by whatever criteria), plain and simple. I guess that has sunk in pretty deeply with me. ;-) The .Net framework provides an OrderedDictionary and a SortedDictionary, both of which make some kind of promise regarding iteration order, but I have never used them myself.
wwweston 8y ago
Having done the work of observing langugage users apparently want an ordered map, were there any steps taken to add such a facility, or did efforts stop at letting developers know they were they were wrong by taking away a de facto feature?
- likpok 8y ago
  Ordered maps require other tradeoffs. For example, c++ has both: std::map and std::unordered_map. std::map is a treemap, and so has logn access/insertion times. It also does a ton of small allocations, and scatters your data across memory, leading to poor cache performance at scale. But it has ordered output, and doesn't invalidate iterators on insertion (hashmaps might, because they sometimes need to rehash). Generally, the suggestion that I've heard is to avoid using std::map unless you really really what it specifically provides, because it's expensive and it's hard to know if you can safely relax those constraints.
  - masklinn 8y ago
    > Ordered maps require other tradeoffs. Ordered maps don't require trees, and don't have that high a tradeoff: https://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html https://morepypy.blogspot.com/2015/01/faster-more-memory-eff... https://github.com/rust-lang/rust/pull/45282#issuecomment-336700260 https://github.com/rust-lang/rust/pull/45282#issuecomment-33...
    - fanf2 8y ago
      C++ ordered maps are in sorted order whereas php-style hashes are in insertion order (recent versions of Ruby and Python have adopted the php semantics; in JS maps are php style but JS objects are unordered)
      - demurgos 8y ago
        Small note, the JS objects are in fact ordered. The lack of determinism caused issues between browsers so the spec now defines the following order: 1. Integer indexes (string keys) in ascending numeric order 2. Other string keys (non-integer indexes) in insertion order 3. Symbols in insertion order https://www.ecma-international.org/ecma-262/#sec-ordinary-object-internal-methods-and-internal-slots-ownpropertykeys https://www.ecma-international.org/ecma-262/#sec-ordinary-ob...
  - int_19h 8y ago
    The biggest advantage of trees is deterministic complexity. There's a bunch of DoS attacks that exploit hashtables, because they can be O(n) in the worst case - and if you control the input, you can deliberately make it worst case. Most "secure C++" guidelines recommend defaulting to std::set and std::map for this reason alone.
- fishywang 8y ago
  If you really need an ordered map, implement one in Go isn't too difficult (but the usual no-generic caveat applies). You can just define a struct that wraps a map and a slice (or some other data structure) to record the order of the keys.
  - lemoncucumber 8y ago
    If you want it to be performant, a linked list is better than a slice. Then in your map you store structs that have both the stores value and a pointer to the corresponding node in the linked list. That way random deletions are constant time since they don’t require copying the slice.
bitwize 8y ago
Some language implementors deliberately introduce gotchas to bite you in the ass should you rely on implementation-specific, rather than standardized, behavior. Take this example from Scheme: R5RS specified two procedures, integer->char and char->integer, to bijectively map characters to integer character codes, but it said nothing about a specific encoding. Most Scheme implementations happily mapped characters to their ASCII codes or Unicode codepoints. Not so Scheme48, which mapped each character to its ASCII code number plus a magic constant (believe it was 1000). Scheme48 provided library functions ascii->char and char->ascii, that did what most people actually wanted and its maintainers insisted that people use those. Had significant code appeared in the wild that, say, simply subtracted the magic constant from the value returned by char->integer and re-added it again before calling integer->char, the maintainers probably would have either changed the magic constant, or changed the mapping entirely, in a future version.
dmoy 8y ago
One motivation for this is the herculean effort it took to move from an older to newer version of java. The stable order that exists turns into another footgun when people start to hardcode that into tests, and it breaks out from under them when the compiler changes slightly.
Someone 8y ago
Many (probably most) popular languages nowadays change the hash function and, with it, iteration order between runs to make it much harder to do a denial of service attack using hash collisions (https://www.securityweek.com/hash-table-collision-attacks-could-trigger-ddos-massive-scale https://www.securityweek.com/hash-table-collision-attacks-co...) Reading your [0], I couldn’t say whether go changes iteration order between iterations in the same run. I would guess it doesn’t.
DannyBee 8y ago
It's not that uncommon, actually: For the same reason (too many people depending on non-stable orders) - LLVM now deliberately shuffles things when you use non-stable sorts to provoke different results.
staticassertion 8y ago
Those other languages are very arguably making a mistake. I dislike Go for a billion reasons but I appreciate when they "break" APIs that explicitly never made those guarantees.
millstone 8y ago
It's easy to print a map in arbitrary order. All you have to do is create an array, iterate the map append to the array, create a new type, define the Len() and Swap() and Less() functions for that type, cast your array to that type, and finally call Sort on it. It's literally less than 20 lines of code.
paulddraper 8y ago
I believe that Google randomized the iteration order of the versions of Java and Python that they use too.

krylon 8y ago

Thanks for the clarification! When I first learned about hash tables (in Perl), the book I used said that the iteration order over a hash should never ever be relied upon, and that it could change arbitrarily from one release to the next. If the order mattered, one should use a different approach (get the keys and sort them by whatever criteria), plain and simple. I guess that has sunk in pretty deeply with me. ;-) The .Net framework provides an OrderedDictionary and a SortedDictionary, both of which make some kind of promise regarding iteration order, but I have never used them myself.

wwweston 8y ago

Having done the work of observing langugage users apparently want an ordered map, were there any steps taken to add such a facility, or did efforts stop at letting developers know they were they were wrong by taking away a de facto feature?

likpok 8y ago
Ordered maps require other tradeoffs. For example, c++ has both: std::map and std::unordered_map. std::map is a treemap, and so has logn access/insertion times. It also does a ton of small allocations, and scatters your data across memory, leading to poor cache performance at scale. But it has ordered output, and doesn't invalidate iterators on insertion (hashmaps might, because they sometimes need to rehash). Generally, the suggestion that I've heard is to avoid using std::map unless you really really what it specifically provides, because it's expensive and it's hard to know if you can safely relax those constraints.
- masklinn 8y ago
  > Ordered maps require other tradeoffs. Ordered maps don't require trees, and don't have that high a tradeoff: https://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html https://morepypy.blogspot.com/2015/01/faster-more-memory-eff... https://github.com/rust-lang/rust/pull/45282#issuecomment-336700260 https://github.com/rust-lang/rust/pull/45282#issuecomment-33...
  - fanf2 8y ago
    C++ ordered maps are in sorted order whereas php-style hashes are in insertion order (recent versions of Ruby and Python have adopted the php semantics; in JS maps are php style but JS objects are unordered)
    - demurgos 8y ago
      Small note, the JS objects are in fact ordered. The lack of determinism caused issues between browsers so the spec now defines the following order: 1. Integer indexes (string keys) in ascending numeric order 2. Other string keys (non-integer indexes) in insertion order 3. Symbols in insertion order https://www.ecma-international.org/ecma-262/#sec-ordinary-object-internal-methods-and-internal-slots-ownpropertykeys https://www.ecma-international.org/ecma-262/#sec-ordinary-ob...
- int_19h 8y ago
  The biggest advantage of trees is deterministic complexity. There's a bunch of DoS attacks that exploit hashtables, because they can be O(n) in the worst case - and if you control the input, you can deliberately make it worst case. Most "secure C++" guidelines recommend defaulting to std::set and std::map for this reason alone.
fishywang 8y ago
If you really need an ordered map, implement one in Go isn't too difficult (but the usual no-generic caveat applies). You can just define a struct that wraps a map and a slice (or some other data structure) to record the order of the keys.
- lemoncucumber 8y ago
  If you want it to be performant, a linked list is better than a slice. Then in your map you store structs that have both the stores value and a pointer to the corresponding node in the linked list. That way random deletions are constant time since they don’t require copying the slice.

bitwize 8y ago

Some language implementors deliberately introduce gotchas to bite you in the ass should you rely on implementation-specific, rather than standardized, behavior. Take this example from Scheme: R5RS specified two procedures, integer->char and char->integer, to bijectively map characters to integer character codes, but it said nothing about a specific encoding. Most Scheme implementations happily mapped characters to their ASCII codes or Unicode codepoints. Not so Scheme48, which mapped each character to its ASCII code number plus a magic constant (believe it was 1000). Scheme48 provided library functions ascii->char and char->ascii, that did what most people actually wanted and its maintainers insisted that people use those. Had significant code appeared in the wild that, say, simply subtracted the magic constant from the value returned by char->integer and re-added it again before calling integer->char, the maintainers probably would have either changed the magic constant, or changed the mapping entirely, in a future version.

dmoy 8y ago

One motivation for this is the herculean effort it took to move from an older to newer version of java. The stable order that exists turns into another footgun when people start to hardcode that into tests, and it breaks out from under them when the compiler changes slightly.

Someone 8y ago

Many (probably most) popular languages nowadays change the hash function and, with it, iteration order between runs to make it much harder to do a denial of service attack using hash collisions (https://www.securityweek.com/hash-table-collision-attacks-could-trigger-ddos-massive-scale https://www.securityweek.com/hash-table-collision-attacks-co...) Reading your [0], I couldn’t say whether go changes iteration order between iterations in the same run. I would guess it doesn’t.

DannyBee 8y ago

It's not that uncommon, actually: For the same reason (too many people depending on non-stable orders) - LLVM now deliberately shuffles things when you use non-stable sorts to provoke different results.

staticassertion 8y ago

Those other languages are very arguably making a mistake. I dislike Go for a billion reasons but I appreciate when they "break" APIs that explicitly never made those guarantees.

millstone 8y ago

It's easy to print a map in arbitrary order. All you have to do is create an array, iterate the map append to the array, create a new type, define the Len() and Swap() and Less() functions for that type, cast your array to that type, and finally call Sort on it. It's literally less than 20 lines of code.

paulddraper 8y ago

I believe that Google randomized the iteration order of the versions of Java and Python that they use too.