5 ms·
To prevent these kinds of bugs, the iteration order in a Go map is randomized across each execution.
by evmar 5y ago
To prevent these kinds of bugs, the iteration order in a Go map is randomized across each execution.
- iab 5y agoDoes that prevent, or more expose?
- klodolph 5y agoI think the general idea is "shift left" which you can say exposes bugs earlier, or prevents bugs from reaching production, which is kind of a "six dozen of one, half dozen of the other". Bugs which are exposed early enough do not get committed. "Shift left" just means that you shift the feedback to the developer farther left in the build process, closer (in time and space) to when the mistake was made.
- EE84M3i 5y agoI don't know about go specifically, but many languages randomize their hash tables to avoid Hash Collision DoS attacks. This is a problem for any piece of software putting attacker-controlled data into a hash-table that does not randomize the hashing and where they assume that it will be amortized constant time.
- masklinn 5y agoGo does have that, but it also specifically and explicitly randomises iteration order.
- schoen 5y agoInterestingly, Python deliberately changed it in the other direction. Since Python 3.7, the iteration order is guaranteed to be the same as the insertion order. This was previously a special object (collections.OrderedDict) but is now the default behavior of every dict: https://docs.python.org/3/library/collections.html#ordereddict-objects https://docs.python.org/3/library/collections.html#ordereddi...
- flafla2 5y agoFunny, I just found out about this today. Infuriatingly, this behavior is _not_ preserved for the set type.
- masklinn 5y agoYes that is because sets have their own hashmap implementation and the dev team remains so far unconvinced of the value of “unique lists”, and the primary gains of the new scheme might be nonexistent or of low impact for the set situation (for python the ordering properties were an ancillary change, not the reason for them))
- comex 5y agoI was just bitten by this the other day. In my case, it's not that I cared about any specific order ("unique lists"), but I did need the output to be deterministic for a caching mechanism to work properly. I knew dicts would 'just work' because of the ordering guarantee, but I was surprised to learn sets didn't. In the end the easiest fix was to just reimplement a set type on top of dict.
- raverbashing 5y agoIf you need an ordered set just use the time proven tradition of "poor man's set" in Python: (now ordered) dict keys
- ComodoHacker 5y agoThis is going to be a time bomb, preventing inplementation improvements (or even vulnerability fixes) in the future.
- AYBABTME 5y agoA problem with this is that Go code that uses native maps is non-deterministic, and is very annoying to make deterministic-ish when reproducing results is important.
- gjs278 5y agoit’s not that hard and it makes sure your code isn’t relying on a magic order that can be screwed up by race conditions or some change to the map along the way. it’s a good idea to key it if order matters.
- brundolf 5y agoHmm, seems like it should be a compiler option
- baq 5y agothis is about as against the go philosophy as it gets. if anything, it should be an another type, but this would also be against the go philosophy. ...which is completely fine. it isn't very difficult to work around and keeps the language simple, even if i'd prefer to have the option built-in.
- nicoburns 5y agoRust simply has two types (HashMap and BtreeMap). And you can pick whichever you prefer.
- pjmlp 5y agoIf that is required there are other data structures to pick from. This kind of behaviour should be visible on the application design and not depend on implementation details.
- masklinn 5y ago> If that is required there are other data structures to pick from. Not really since it’s Go (“lol no generics”): there’s no easy way to swap the builtin hashmap for an other associative array with deterministic behaviour and you will lose something (definitely performances, likely either convenience or type-safety, possibly both).
- wyager 5y agoGood luck if you want deterministic state replication across processes!
- evmar 5y agoIf the order matters, it's only as hard as using a (different) data structure that preserves order.
- masklinn 5y ago> it's only as hard as using a (different) data structure that preserves order. Which turns out to be pretty inconvenient in Go. So more likely you’d do something like copy the keys to a slice, sort the slice, then iterate that to get the map values. Incidentally, that’s exactly what the json package does when encoding a map.
- wyager 5y agoNow you’re stuck with the fact that Go doesn’t support generics outside of the stock data structures.
- lilyball 5y agoI doubt that’s why. Modern hash tables typically include a random factor in the hashing to prevent bucketing from being predictable, so attackers can’t craft malicious input that causes every value to be put in the same bucket as a form of DOS attack. The fact that this means iteration order is randomized is a side effect.
- codys 5y agoThe insertion of a random factor in hashing/bucketing that you're describing would change the iteration order per _instance_ of a hash table, not per _iteration_ as the parent comment notes is the case for go maps.
- lilyball 5y agoIt's per _iteration_? That was not clear. Parent comment said "execution", not "iteration". I interpreted that as per execution of the program.
- benesch 5y agoNo, the OP is correct: the Go developers intentionally introduced randomness into map iteration order to shake out bugs. For evidence, see: https://github.com/golang/go/issues/6719 https://github.com/golang/go/issues/6719 https://stackoverflow.com/a/55925880 https://stackoverflow.com/a/55925880 https://codereview.appspot.com/5285042 https://codereview.appspot.com/5285042