Comment #0 by bearophile_hugs — 2013-06-09T14:47:09Z
I suggest to:
- Warn against usage of built-in array sort, as soon as possible (possibly in dmd 2.064).
- In the successive dmd release to deprecate the built-in array sort.
- And then, in a successive dmd release, to totally remove it.
The built-in sort is less flexible, slower and more buggy than the Phobos sort functions.
The various layers of a compiler (and its druntime) should be as small as possible, to simplify compiler development, to reduce compiler+druntime source code to work on, and to reduce druntime size.
Generally you want to put in the compiler what's hard/impossible to implement in library code, like tuples and their syntax, and keep in library code the rest, like the sorting.
One advantage of the built-in sort is that it induces less template bloat compared to the Phobos sort. But this advantage is not nearly enough to justify its presence and the problems it causes.
See also Issue 5854 and Issue 7115
Note: this is not an enhancement request because if you use the built-in sort by mistake (you write myarray.sort and you forget to add the trailing ( ) ), you hit bugs and problems. So at the moment I consider the built-in sort a "bug" that should be removed.
Note: this bug report is not about the removal of the built-in array reverse. That's a different issue, to be discussed elsewhere.
Comment #1 by bearophile_hugs — 2013-11-22T02:46:24Z
A comment by yebblies:
> Is the phobos sort good enough to replace it? IIRC there were some problems...
Phobos sort is not perfect, in some pathological cases its unstable algorithm goes in quadratic behavour, and it will need to become something more like the C++ STL introsort (that switches to another O(n ln n) algorithm in those cases).
But still I think the Phobos sort is better than (safer, faster, less buggy, look in Bugzilla for some of the built-in sort bugs) than the built-in sort.
And as programmers are lazy and don't add a () (or sometimes they forget) more and more code is written relying on the built-in sort, and it is not compatible with the Phobos sort (Phobos sort doesn't sort a char[] and it doesn't return the sorted array, you need a ".release"), this will cause growing problems in porting that code. So I think deprecating the built-in sort is becoming urgent.
In some months I will probably increase the importance of this from normal to major.
Comment #3 by bearophile_hugs — 2013-11-22T06:23:10Z
(In reply to comment #2)
> Well, I tried. Issue 5124.
>
> https://github.com/yebblies/dmd/tree/issue10318
> https://github.com/D-Programming-Language/druntime/pull/669
This issue is about the deprecation of just the built-in "sort". It is not about the deprecation of just the built-in "reverse".
The built-in "reverse" can't be yet deprecated, because currently the Phobos "reverse" can't replace all the usages of the built-in "reverse", see Issue 11555
Comment #4 by yebblies — 2013-11-22T07:08:12Z
(In reply to comment #3)
> (In reply to comment #2)
> > Well, I tried. Issue 5124.
> >
> > https://github.com/yebblies/dmd/tree/issue10318
> > https://github.com/D-Programming-Language/druntime/pull/669
>
> This issue is about the deprecation of just the built-in "sort". It is not
> about the deprecation of just the built-in "reverse".
>
> The built-in "reverse" can't be yet deprecated, because currently the Phobos
> "reverse" can't replace all the usages of the built-in "reverse", see Issue
> 11555
And sort doesn't work in pure functions. So what? Besides, this is just a warning, not a full-on deprecation.
Comment #5 by xinok — 2013-12-26T11:50:28Z
(In reply to comment #1)
>
> Phobos sort is not perfect, in some pathological cases its unstable algorithm
> goes in quadratic behavour, and it will need to become something more like the
> C++ STL introsort (that switches to another O(n ln n) algorithm in those
> cases).
>
This issue has been fixed and pushed to the 2.065 branch.
Comment #6 by bearophile_hugs — 2013-12-26T12:16:20Z
(In reply to comment #5)
> This issue has been fixed and pushed to the 2.065 branch.
Good.
You are probably well qualified to answer yebblies question: Is currently the phobos sort good enough to replace the built-in sort? So is it OK to finally warn against the usage of the built-in sort?
Comment #7 by xinok — 2013-12-27T10:49:26Z
(In reply to comment #6)
> (In reply to comment #5)
>
> > This issue has been fixed and pushed to the 2.065 branch.
>
> Good.
> You are probably well qualified to answer yebblies question: Is currently the
> phobos sort good enough to replace the built-in sort? So is it OK to finally
> warn against the usage of the built-in sort?
AFAIK, these two issues remain:
(1) You cannot call Phobos sort from pure functions. I'm not familiar with the subject of purity, but AFAIK, you can't simply mark the function(s) as pure because this would make it impossible to use an impure predicate for sorting. I'm not sure what the solution is as I don't think it's possible to simply infer purity.
(2) This may be a non-issue but Phobos cannot sort char[] arrays whereas the built-in sort can. The issue comes down to the template constraints; char[] isn't classified as a random-access range and neither is wchar[]. However, dchar[] is classified as such and can be sorted by Phobos sort.
At this point, I'm in favor of warning against its usage. The Phobos sort is "free of bugs" (I've found no cases where it sorts incorrectly), runs in O(n log n) time, and is highly optimized (3-4x faster than the built-in sort). However, I think the purity issue needs to be addressed before we move forward with deprecation.
Comment #8 by bearophile_hugs — 2013-12-27T18:04:17Z
(In reply to comment #7)
> I don't think it's possible to simply infer purity.
The D language is able to infer purity for templates. So if sort() is not (wealkly) pure, then there is something that forces it to be not pure. Such parts should be found and fixed.
> (2) This may be a non-issue but Phobos cannot sort char[] arrays
This is by design. On the other hand sorting char[] is a common need for me (I have not yet had to sort a wchar[]).
This works already:
void main() {
import std.algorithm, std.string;
char[] txt = "acb".dup;
txt.representation.sort();
assert(txt == "abc");
}
But that's not enough, as I'd like to use sort() in UFCS chains too.
A simple solution is to add to std.ascii a charsSort() function for this purpose. But then you want charsPartialSort, charsSchwartzSort, etc. And this is a bit too much. So this doesn't seem a very good idea.
Another solution is to introduce a unrepresentation() function, opposite of std.string.representation. With it you can write this long code:
string txt = "acb;
char[] txt2 = txt.dup.representation.sort().release.unrepresentation;
Similar code could be written with partialSort, schwartzSort, multiSort, topN, etc.
Comment #9 by bearophile_hugs — 2014-02-15T03:24:26Z
This should have been removed already, but it's still just a warning.
Can this please be deprecated? This makes it impossible to use std.algorithm's sort with UFCS and should be removed ASAP.
Comment #13 by pro.mathias.lang — 2020-05-18T12:28:42Z