There's a debate/lesson in here about when implementations should change to actually take up all the space claimed by the spec.
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.
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.
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), 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...), 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_ch...), etc.
(Apple has a totally different viewpoint on this. That’s one reason it never really got into businesses for a long time)
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.
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.
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!
[citation needed]
This is the wrong wording, IE had a decently enough installed/captive user base. It was never particularly stable.
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.