← Back to context

Comment by gwd

20 hours 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.

7 comments

gwd

Reply
RyanCavanaugh  19 hours ago

There'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  19 hours ago

Intent 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  17 hours ago

    A counterexample would be Python, where dictionaries maintain their insertion order.

    • deathanatos  15 hours ago

      Python 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  15 hours 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  15 hours ago

      Well … it seems like you're right. (A playground — 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.

      1 reply →