Comment by deathanatos

1 day 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).)

5 comments

deathanatos

Reply
CobrastanJorji  1 day ago

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

  • deathanatos  1 day 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  1 day 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  1 day 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.

    • porridgeraisin  15 hours ago

      They 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.