5 ms·

Currently sort is not guaranteed to be stable. https://github.com/golang/go/blob/master/src/sort/sort.go#L41 https://github.com/golang/go/blob/master/src/sort/

Currently sort is not guaranteed to be stable. https://github.com/golang/go/blob/master/src/sort/sort.go#L41 https://github.com/golang/go/blob/master/src/sort/sort.go#L4...

dehrmann 4y ago
Is it stable, but not guaranteed to be stable, or is it unstable? If it just happens to be stable, code somewhere will eventually depend on that behavior.
- edflsafoiewq 4y ago
  Happened in JS land. IE was stable and sites depended on it. FF switched to match IE. Chrome switched to match IE and FF. And then finally they put it into the spec.
  - ElectricalUnion 4y ago
    > IE was stable [citation needed] This is the wrong wording, IE had a decently enough installed/captive user base. It was never particularly stable.
- setr 4y ago
  If you ignore the stated guarantees of the API and depend on implementation details instead, then it’s on you? I might understand if it were unstated, but it explicitly states it’s not. Otherwise the only way to have a non-stable sort function that currently happens-to-be stable would have to include a randomized shuffle afterwards to ensure no one goes around depending on it… It would be equivalent to assuming the golang ABI was stable because it survived unmodified for a couple versions, despite it being explicitly not. And then freezing the ABI to maintain a guarantee it explicitly didn’t want to maintain.
  - remus 4y ago
    While I totally agree with the sentiment it is nice when language developers go out of their way to not break stuff, even when they don't have to. For example the golang team have made efforts not to break certain usages of the unsafe package in the past, despite the package offering no guarantees about stability. On a similar note, Im sure there was a suggestion to artificially make the previous golang sort function unstable so that users wouldn't come to rely on stable behaviour where it wasn't guaranteed. I quite like the idea, start the fight against hyrum's law!
  - Someone 4y ago
    > if you ignore the stated guarantees of the API and depend on implementation details instead, then it’s on you? In theory, yes. In practice, if a OS or library update uncovers bugs in many programs, that update won’t get favorable reviews. That’s the reason behind Linux’s “we do not break userspace!” rule (https://linuxreviews.org/WE_DO_NOT_BREAK_USERSPACE https://linuxreviews.org/WE_DO_NOT_BREAK_USERSPACE), and also why Microsoft Windows has layer upon layer of APIs, a copy of the Windows 95 memory manager (https://mcpmag.com/articles/2010/07/27/trip-down-memory-lane-with-emulateheap.aspx?m=2 https://mcpmag.com/articles/2010/07/27/trip-down-memory-lane...), why large databases support character sets that probably haven’t been used anywhere since before many HN readers were born (https://docs.oracle.com/goldengate/1212/gg-winux/GWUAD/wu_charsets.htm#GWUAD1013 https://docs.oracle.com/goldengate/1212/gg-winux/GWUAD/wu_ch...), etc. (Apple has a totally different viewpoint on this. That’s one reason it never really got into businesses for a long time)
    - samus 4y ago
      Linus' rule also has disadvantages as it blocks real innovation in the Linux ecosystem. Granted, Desktop Linux doesn't need another Python 2 -> 3 or X.org -> Wayland deathmarch...
      - ElectricalUnion 4y ago
        > Linus' rule also has disadvantages as it blocks real innovation in the Linux ecosystem. Block real innovation like what? > Granted, Desktop Linux doesn't need another Python 2 -> 3 or X.org -> Wayland deathmarch... That's all userspace? Userspace doesn't care it breaks. That's why userspace sucks. You need to keep compatibility if you want to have a stable base to build something. That's why we have (sometimes silly) standards like SUS or POSIX. "we do not break userspace" at least garantees that you need to fix only the userspace, and not the whole thing all the time.
        samus 4y ago
        Breakages of userspace are almost always unintended consequences. I don't have examples to the contrary, but I believe that intentional breakages and redesigns are almost unthinkable because of Linus's rule. Significant changes in the kernel already often need years to land because of the multitude of configurations and interfaces that have to be supported. And even longer to deprecate and remove. Not necessarily a bad thing, just the price of success. Large-scale breakages like the Wayland transition affect the whole Desktop Linux ecosystem, and are just an example of what mayhem fundamental changes can cause.
- tgv 4y ago
  Good question. I checked the 1.18.1 code, and Sort() and Stable() call different functions. The former calls quick sort, the latter something else (groups of 20 items with insertion sort, then symmerge?). Quick sort's traditional implementation isn't stable, so I'd be surprised if Sort() would actually be.
- infogulch 4y ago
  Go has moved in this direction before, when they made map iteration order actually random to match the spec that said that you can't depend on iteration order. IIRC the impl is actually pretty light and only randomizes the starting index, and only generates the random offset once at startup, but it's enough to prevent people from accidentally depending on the order e.g. in their test suite. There might be a bit of disruption, but I expect it will be reasonably well received by most Go users. There's a debate/lesson in here about when implementations should change to actually take up all the space claimed by the spec.
  - Cthulhu_ 4y ago
    I kinda like that, because a lot of people will not read the spec but just try something first. If their map iteration is the same as e.g. insertion order, they will shrug and assume it's correct and move on.
    - tialaramex 4y ago
      Go's decision here also defeats the next lazy thing people do, which is they run it once, and then they copy-paste whatever the results are as "correct" into their test case. With the randomisation their next run is also randomised and this "correct" answer will now be wrong so their tests fail again. As a result most people will go "Oh, I guess I should actually test the outcome I care about" (good) or "Oh, testing is hard, I'll skip it" (bad, but at least not a problem for the team maintaining the standard library). Very few will say to themselves "I bet I can defeat the randomisation somehow with a different incorrect test design" because humans are lazy.
- dspillett 4y ago
  The former. The spec just says the result will be sorted, it just happens that the current implementations use a method that results in stable positioning of items with equal sort value. There aren't a lot of places where stability matters, where it does the programmer should hopefully know and not have relied on an undefined behaviour… The most likely impact, I think, will be in UIs where the difference won't really matter but could be quite noticeable. Do note though that "unstable" can mean two different things. A single threaded sort will produce the same result for the same input, and many parallels sorts have this property too due to the way they coordinate the threads and collate their results, so the output order of equal items is arbitrary but not random. Some parallel sorts do order items with the same sort key more randomly though due to being sensitive to timing differences caused by uncontrolled factors (the OS's scheduler and other things it is dealing with, differing IO delays if the sort is not in-memory, different numbers of threads if comparing run results with those done on other processor architectures, …). IIRC pdqsort is the former if those two types of unstable.
petesergeant 4y ago
Perl's move to actively randomize hash/dict ordering, where previously it'd been sort of stable but not guaranteed, affected a lot of codebases that had incorrectly relied on that stability. I'm just noting that users are necessarily flawed, and moving from "stable but not guaranteed to be" to "actually unstable" will be a breaking change for some real world codebases.
- masklinn 4y ago
  This exact issue is why go actively randomises dict iteration too. Seems really odd that the same team would have used a stable sort and just documented as “not guaranteed to be stable”.
  - Someone 4y ago
    That’s not the reason. Library developers aren’t changing code to annoy or educate their users. 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) And that’s a real problem. https://lwn.net/Articles/474912/ https://lwn.net/Articles/474912/ says: “That's where web frameworks come into play. Those frameworks helpfully collect up all of the POST form data that gets sent to a particular web page into a dictionary that gets handed off to the application for processing. The amount of data that the frameworks will allow is typically rather large (e.g. 1MB), so an attacker can create tens of thousands of form entries in a single HTTP request. Because they all collide, those entries can take tens of seconds to a few minutes to process on an i7 core according to the advisory [PDF] released by Wälde and Klink.” If you manage to insert 10,000 keys with identical hashes, that’s about 10,000²/2 key comparisons.
    - masklinn 4y ago
      > 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. For some reason they dropped this explicit mention when https://go.dev/blog/go-maps-in-action https://go.dev/blog/go-maps-in-action was moved over to https://go.dev/blog/maps 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 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#L844-L850 https://github.com/golang/go/blob/master/src/runtime/map.go#...

Currently sort is not guaranteed to be stable. https://github.com/golang/go/blob/master/src/sort/sort.go#L41 https://github.com/golang/go/blob/master/src/sort/sort.go#L4...

dehrmann 4y ago

Is it stable, but not guaranteed to be stable, or is it unstable? If it just happens to be stable, code somewhere will eventually depend on that behavior.

edflsafoiewq 4y ago
Happened in JS land. IE was stable and sites depended on it. FF switched to match IE. Chrome switched to match IE and FF. And then finally they put it into the spec.
- ElectricalUnion 4y ago
  > IE was stable [citation needed] This is the wrong wording, IE had a decently enough installed/captive user base. It was never particularly stable.
setr 4y ago
If you ignore the stated guarantees of the API and depend on implementation details instead, then it’s on you? I might understand if it were unstated, but it explicitly states it’s not. Otherwise the only way to have a non-stable sort function that currently happens-to-be stable would have to include a randomized shuffle afterwards to ensure no one goes around depending on it… It would be equivalent to assuming the golang ABI was stable because it survived unmodified for a couple versions, despite it being explicitly not. And then freezing the ABI to maintain a guarantee it explicitly didn’t want to maintain.
- remus 4y ago
  While I totally agree with the sentiment it is nice when language developers go out of their way to not break stuff, even when they don't have to. For example the golang team have made efforts not to break certain usages of the unsafe package in the past, despite the package offering no guarantees about stability. On a similar note, Im sure there was a suggestion to artificially make the previous golang sort function unstable so that users wouldn't come to rely on stable behaviour where it wasn't guaranteed. I quite like the idea, start the fight against hyrum's law!
- Someone 4y ago
  > if you ignore the stated guarantees of the API and depend on implementation details instead, then it’s on you? In theory, yes. In practice, if a OS or library update uncovers bugs in many programs, that update won’t get favorable reviews. That’s the reason behind Linux’s “we do not break userspace!” rule (https://linuxreviews.org/WE_DO_NOT_BREAK_USERSPACE https://linuxreviews.org/WE_DO_NOT_BREAK_USERSPACE), and also why Microsoft Windows has layer upon layer of APIs, a copy of the Windows 95 memory manager (https://mcpmag.com/articles/2010/07/27/trip-down-memory-lane-with-emulateheap.aspx?m=2 https://mcpmag.com/articles/2010/07/27/trip-down-memory-lane...), why large databases support character sets that probably haven’t been used anywhere since before many HN readers were born (https://docs.oracle.com/goldengate/1212/gg-winux/GWUAD/wu_charsets.htm#GWUAD1013 https://docs.oracle.com/goldengate/1212/gg-winux/GWUAD/wu_ch...), etc. (Apple has a totally different viewpoint on this. That’s one reason it never really got into businesses for a long time)
  - samus 4y ago
    Linus' rule also has disadvantages as it blocks real innovation in the Linux ecosystem. Granted, Desktop Linux doesn't need another Python 2 -> 3 or X.org -> Wayland deathmarch...
    - ElectricalUnion 4y ago
      > Linus' rule also has disadvantages as it blocks real innovation in the Linux ecosystem. Block real innovation like what? > Granted, Desktop Linux doesn't need another Python 2 -> 3 or X.org -> Wayland deathmarch... That's all userspace? Userspace doesn't care it breaks. That's why userspace sucks. You need to keep compatibility if you want to have a stable base to build something. That's why we have (sometimes silly) standards like SUS or POSIX. "we do not break userspace" at least garantees that you need to fix only the userspace, and not the whole thing all the time.
      - samus 4y ago
        Breakages of userspace are almost always unintended consequences. I don't have examples to the contrary, but I believe that intentional breakages and redesigns are almost unthinkable because of Linus's rule. Significant changes in the kernel already often need years to land because of the multitude of configurations and interfaces that have to be supported. And even longer to deprecate and remove. Not necessarily a bad thing, just the price of success. Large-scale breakages like the Wayland transition affect the whole Desktop Linux ecosystem, and are just an example of what mayhem fundamental changes can cause.
tgv 4y ago
Good question. I checked the 1.18.1 code, and Sort() and Stable() call different functions. The former calls quick sort, the latter something else (groups of 20 items with insertion sort, then symmerge?). Quick sort's traditional implementation isn't stable, so I'd be surprised if Sort() would actually be.
infogulch 4y ago
Go has moved in this direction before, when they made map iteration order actually random to match the spec that said that you can't depend on iteration order. IIRC the impl is actually pretty light and only randomizes the starting index, and only generates the random offset once at startup, but it's enough to prevent people from accidentally depending on the order e.g. in their test suite. There might be a bit of disruption, but I expect it will be reasonably well received by most Go users. There's a debate/lesson in here about when implementations should change to actually take up all the space claimed by the spec.
- Cthulhu_ 4y ago
  I kinda like that, because a lot of people will not read the spec but just try something first. If their map iteration is the same as e.g. insertion order, they will shrug and assume it's correct and move on.
  - tialaramex 4y ago
    Go's decision here also defeats the next lazy thing people do, which is they run it once, and then they copy-paste whatever the results are as "correct" into their test case. With the randomisation their next run is also randomised and this "correct" answer will now be wrong so their tests fail again. As a result most people will go "Oh, I guess I should actually test the outcome I care about" (good) or "Oh, testing is hard, I'll skip it" (bad, but at least not a problem for the team maintaining the standard library). Very few will say to themselves "I bet I can defeat the randomisation somehow with a different incorrect test design" because humans are lazy.
dspillett 4y ago
The former. The spec just says the result will be sorted, it just happens that the current implementations use a method that results in stable positioning of items with equal sort value. There aren't a lot of places where stability matters, where it does the programmer should hopefully know and not have relied on an undefined behaviour… The most likely impact, I think, will be in UIs where the difference won't really matter but could be quite noticeable. Do note though that "unstable" can mean two different things. A single threaded sort will produce the same result for the same input, and many parallels sorts have this property too due to the way they coordinate the threads and collate their results, so the output order of equal items is arbitrary but not random. Some parallel sorts do order items with the same sort key more randomly though due to being sensitive to timing differences caused by uncontrolled factors (the OS's scheduler and other things it is dealing with, differing IO delays if the sort is not in-memory, different numbers of threads if comparing run results with those done on other processor architectures, …). IIRC pdqsort is the former if those two types of unstable.

petesergeant 4y ago

Perl's move to actively randomize hash/dict ordering, where previously it'd been sort of stable but not guaranteed, affected a lot of codebases that had incorrectly relied on that stability. I'm just noting that users are necessarily flawed, and moving from "stable but not guaranteed to be" to "actually unstable" will be a breaking change for some real world codebases.

masklinn 4y ago
This exact issue is why go actively randomises dict iteration too. Seems really odd that the same team would have used a stable sort and just documented as “not guaranteed to be stable”.
- Someone 4y ago
  That’s not the reason. Library developers aren’t changing code to annoy or educate their users. 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) And that’s a real problem. https://lwn.net/Articles/474912/ https://lwn.net/Articles/474912/ says: “That's where web frameworks come into play. Those frameworks helpfully collect up all of the POST form data that gets sent to a particular web page into a dictionary that gets handed off to the application for processing. The amount of data that the frameworks will allow is typically rather large (e.g. 1MB), so an attacker can create tens of thousands of form entries in a single HTTP request. Because they all collide, those entries can take tens of seconds to a few minutes to process on an i7 core according to the advisory [PDF] released by Wälde and Klink.” If you manage to insert 10,000 keys with identical hashes, that’s about 10,000²/2 key comparisons.
  - masklinn 4y ago
    > 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. For some reason they dropped this explicit mention when https://go.dev/blog/go-maps-in-action https://go.dev/blog/go-maps-in-action was moved over to https://go.dev/blog/maps 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 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#L844-L850 https://github.com/golang/go/blob/master/src/runtime/map.go#...