Re:Go will use pdqsort in next release
by masklinn on Thursday April 21, 2022 @01:35PM
(#31112606)
> That’s not the reason. Library developers aren’t changing code to annoy or educate their users.
They absolutely are.
> The reason is that a hash table with a fixed hash function may be used for denial of service attacks. If an attacker knows how a hash map maps keys and can control the keys being inserted, they can insert thousands of keys that all map to the same hash, effectively turning the hash map into a list or vector that has to be searched linearly (on both lookups and insertions)
That has nothing to do with what I'm talking about.
Independent from hash randomisation, Go will randomise the iteration of hashmaps, such that iterating the same hashmap twice, within the same process, without having modified it in any way, will yield different results. Currently this is done by offsetting the starting point of the iteration by a random amount.
> Since the release of Go 1.0, the runtime has randomized map iteration order. Programmers had begun to rely on the stable iteration order of early versions of Go, which varied between implementations, leading to portability bugs.
You can trivially observe this behaviour by just iterating the same map multiple times. With mere hash randomisation, even if hash randomisation was done on a per-map basis by iterating the same map you'd observe the same order, but in Go you don't: https://go.dev/play/p/3HZBv2WHKcT
As you can see the items are always in the same relative order, but the starting point of the iteration varies.
They absolutely are.
> The reason is that a hash table with a fixed hash function may be used for denial of service attacks. If an attacker knows how a hash map maps keys and can control the keys being inserted, they can insert thousands of keys that all map to the same hash, effectively turning the hash map into a list or vector that has to be searched linearly (on both lookups and insertions)
That has nothing to do with what I'm talking about.
Independent from hash randomisation, Go will randomise the iteration of hashmaps, such that iterating the same hashmap twice, within the same process, without having modified it in any way, will yield different results. Currently this is done by offsetting the starting point of the iteration by a random amount.
For some reason they dropped this explicit mention when https://go.dev/blog/go-maps-in-action was moved over to https://go.dev/blog/maps, but it used to be there:
> Since the release of Go 1.0, the runtime has randomized map iteration order. Programmers had begun to rely on the stable iteration order of early versions of Go, which varied between implementations, leading to portability bugs.
You can trivially observe this behaviour by just iterating the same map multiple times. With mere hash randomisation, even if hash randomisation was done on a per-map basis by iterating the same map you'd observe the same order, but in Go you don't: https://go.dev/play/p/3HZBv2WHKcT
As you can see the items are always in the same relative order, but the starting point of the iteration varies.
You can also see this in the initialisation of the map iterator, it's even labelled with a nice little comment: https://github.com/golang/go/blob/master/src/runtime/map.go#...