7 ms·
> At the very least, relying on quirks of someone else's implementation is a risk that should be understood and accounted for, and no one has any reasonable gro
by gwd 1y ago
> At the very least, relying on quirks of someone else's implementation is a risk that should be understood and accounted for, and no one has any reasonable grounds for complaint if those quirks suddenly change in a new version.
It's almost always unintentional. Someone wrote some code, it works, they ship it, not realizing it only works if the list comes back in a specific order, or with a specific timing. Then a year or two later they do some updates, the list comes back in a different order, or something is faster or slower, and suddenly what worked before doesn't work.
This is why in Golang, for instance, when you iterate over map keys, it purposely does it in a random order -- to make sure that your program doesn't accidentally begin to rely on the internal implementation of the hash function.
ETA: But of course, that's not truly random, just pseudorandom. It's not impossible that someone's code only works because of the particular pseudorandom order they're generating, and that if Golang even changes the pseudorandom number generator they're using to evade Hyrum's Law that someone's code will break.
- RyanCavanaugh 1y agoThere's probably at least one game out there somewhere that uses Go's map iteration order to shuffle a deck of cards, and would thus be broken by Go removing the thing that's supposed to prevent you from depending on implementation details.
- deathanatos 1y agoIntent enters into it when someone complains about something that is obviously out of the specification breaking. Prior that, yeah, that's just a bug. > This is why in Golang, for instance, when you iterate over map keys, it purposely does it in a random order It could be that Go's intentions are different here, but IIRC languages will mix randomization into hashtables as it is otherwise a security issue. (You typically know the hash function, usually, so without randomization you can force hash collisions & turn O(1) lookups into O(n).)
- CobrastanJorji 1y agoA counterexample would be Python, where dictionaries maintain their insertion order.
- deathanatos 1y agoPython does the same hash randomization, but yes, it also maintains the insertion order. This is more expensive, obviously, as additional data has to be tracked.
- porridgeraisin 1y ago> mix randomisation into hash tables. I believe you don't understand. In go, they literally randomly permute the iteration order of the map each time you iterate over it. e.g for x in map { } for x in map { // different order } Now, the fact that they randomize means people use it as a cheap "select random item from map" function :D, which is hyrums law all over again. var randomUser User for userId, user in usersMap { randomUser = user break } Funny isn't it.
- deathanatos 1y agoWell … it seems like you're right. (A playground — https://go.dev/play/p/OHQTIuDWicd https://go.dev/play/p/OHQTIuDWicd — if anyone is curious.) That's … pretty surprising, since that would seem to imply that iteration would require a O(n) sized chunk of memory somewhere to reify the order into. (And probably O(n) time to do the shuffle, or at least, a copy of the ordering; we should shuffle as we go, I suppose, but we'd need to track what we've emitted & what we've not, hence O(n) time & space to populate that scratch…) That seems undesirable.
- porridgeraisin 1y agoThey actually do it without needing a O(n) memory chunk, aiui. 1. choose starting bucket randomly 2. From there iterate through buckets in usual order (wrapping around) 3. Within each bucket, generate permutation of 0..7, and stream it in that order. See func mapiterinit() in runtime/map.go This is just me musing, but you can probably precompute all permutations of 0..7 and store it for ~20KB once for the whole runtime, and just index that each time. Can avoid the fischer yates each time.
- bboreham 1y agoDo note your last example makes a biased, or poorly random, selection.