5 ms·

so the behavior is going to change: sorting becomes unstable, i.e. it doesn't preserve the relative order of equal elements. I'm pretty sure this will affect us

by buryat 5y ago

so the behavior is going to change: sorting becomes unstable, i.e. it doesn't preserve the relative order of equal elements. I'm pretty sure this will affect users

sanxiyn 5y ago
Go's sort was already unstable.
- buryat 5y ago
  oh, that's pretty cool
- deleted 5y ago
  [deleted]
ayanamist 5y ago
If you want a stable sort, you should always use https://pkg.go.dev/sort#SliceStable https://pkg.go.dev/sort#SliceStable This PR only modifies Slice method which is declared as "is not guaranteed to be stable"
- Asraelite 5y ago
  Go already randomizes the order of keys in map iterations to discourage relying on undefined behavior. It would be funny if they randomized the order of equal elements in what would otherwise be a stable algorithm for the same reason.
skunkworker 5y ago
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 5y 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 5y 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 5y 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 5y 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!
comonoid 5y ago
https://polkadot.network/blog/a-polkadot-postmortem-24-05-2021/ https://polkadot.network/blog/a-polkadot-postmortem-24-05-20... comes to mind. And Hyrum's law in general: https://www.hyrumslaw.com/ https://www.hyrumslaw.com/
turing_complete 5y ago
Nothing changes. If you read the diff, you will see that they used Quicksort before. And vanilla quicksort is unstable as well.
benibela 5y ago
I wanted a stable sort in one of my projects, so I implemented merge sort Then I had a larger input (like 100k elements) and wondered, why does it take a few minutes to print the output, when it calculated the output in a second? Well, it was the merge sort being called after the calculation completed to print it sorted. A double fail, because the calculation already produced sorted output in this case. Now I sort a list of indices with quick sort
tptacek 5y ago
Those users deserve what they get; not only does Sort() explicitly not guarantee a stable sort, but the library provides --- directly next to Sort() in the package --- a Stable().

by buryat 5y ago

so the behavior is going to change: sorting becomes unstable, i.e. it doesn't preserve the relative order of equal elements. I'm pretty sure this will affect users

sanxiyn 5y ago

Go's sort was already unstable.

buryat 5y ago
oh, that's pretty cool
deleted 5y ago
[deleted]

ayanamist 5y ago

If you want a stable sort, you should always use https://pkg.go.dev/sort#SliceStable https://pkg.go.dev/sort#SliceStable This PR only modifies Slice method which is declared as "is not guaranteed to be stable"

Asraelite 5y ago
Go already randomizes the order of keys in map iterations to discourage relying on undefined behavior. It would be funny if they randomized the order of equal elements in what would otherwise be a stable algorithm for the same reason.

skunkworker 5y ago

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 5y 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 5y 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 5y 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 5y 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!

comonoid 5y ago

https://polkadot.network/blog/a-polkadot-postmortem-24-05-2021/ https://polkadot.network/blog/a-polkadot-postmortem-24-05-20... comes to mind. And Hyrum's law in general: https://www.hyrumslaw.com/ https://www.hyrumslaw.com/

turing_complete 5y ago

Nothing changes. If you read the diff, you will see that they used Quicksort before. And vanilla quicksort is unstable as well.

benibela 5y ago

I wanted a stable sort in one of my projects, so I implemented merge sort Then I had a larger input (like 100k elements) and wondered, why does it take a few minutes to print the output, when it calculated the output in a second? Well, it was the merge sort being called after the calculation completed to print it sorted. A double fail, because the calculation already produced sorted output in this case. Now I sort a list of indices with quick sort

tptacek 5y ago

Those users deserve what they get; not only does Sort() explicitly not guarantee a stable sort, but the library provides --- directly next to Sort() in the package --- a Stable().