www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - builtin sort

reply "Stephan Schiffels" <stephan_schiffels mac.com> writes:
Hi,

I know it has been discussed previously to deprecate the builtin 
sort. I don't know the status of this, but I observed the 
following problem.

With dmd, druntime and phobos all on 2.063, this program runs 
successfully on a mac:

#!/usr/bin/env rdmd

import std.stdio;

void main() {

   int[] a = [5, 4, 3, 2, 1];

   a.sort;
   writeln(a);

}

But it fails on linux, with the line:


/nfs/users/nfs_s/ss27/Software/dlang/phobos/generated/linux/release/64/libphobos2
a(qsort_4c4_2cc.o): 
In function `_adSort':
src/rt/qsort.d:(.text._adSort+0x47): undefined reference to 
`qsort_r'
collect2: ld returned 1 exit status
--- errorlevel 1


When I change "a.sort" -> "a.sort()" and add import std.algorithm 
everything works fine.
Does this mean that the builtin sort on Linux is broken with 
2.063?

Stephan
Jun 08 2013
next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Saturday, June 08, 2013 10:30:52 Stephan Schiffels wrote:
 Hi,
 
 I know it has been discussed previously to deprecate the builtin
 sort. I don't know the status of this, but I observed the
 following problem.
 
 With dmd, druntime and phobos all on 2.063, this program runs
 successfully on a mac:
 
 #!/usr/bin/env rdmd
 
 import std.stdio;
 
 void main() {
 
    int[] a = [5, 4, 3, 2, 1];
 
    a.sort;
    writeln(a);
 
 }
 
 But it fails on linux, with the line:
 
 
 /nfs/users/nfs_s/ss27/Software/dlang/phobos/generated/linux/release/64/libph
 obos2.a(qsort_4c4_2cc.o): In function `_adSort':
 src/rt/qsort.d:(.text._adSort+0x47): undefined reference to
 `qsort_r'
 collect2: ld returned 1 exit status
 --- errorlevel 1
 
 
 When I change "a.sort" -> "a.sort()" and add import std.algorithm
 everything works fine.
 Does this mean that the builtin sort on Linux is broken with
 2.063?

Hmm, it works just fine on my system (64-bit Linux), so I don't know why you're seeing the problem that you're seeing. However, we really, really need to deprecate the built-in sort - especially when a pair of parens can make the difference between whether you call the built-in sort or std.algorithm's sort - and it's particularly broken with regards to Unicode. - Jonathan M Davis
Jun 08 2013
prev sibling next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Saturday, 8 June 2013 at 08:52:22 UTC, Jonathan M Davis wrote:
 However, we really, really need to deprecate the built-in sort 
 - especially
 when a pair of parens can make the difference between whether 
 you call the
 built-in sort or std.algorithm's sort - and it's particularly 
 broken with
 regards to Unicode.

 - Jonathan M Davis

Or anything that uses non-POD comparison (opCmp) for that matter: //---- import std.stdio; import std.algorithm; struct S { int i; int opCmp(S o) { return (i < o.i) - (i > o.i); //inverse order } } void main() { auto a = [S(1), S(2), S(3)]; writeln(a); //[S(1), S(2), S(3)] a.sort; writeln(a); //[S(1), S(2), S(3)] a.sort(); writeln(a); //[S(3), S(2), S(1)] } //---- I had pretty much forgotten ".sort" even existed (it really never even crossed my mind that it could be built-in), and given the push for optional parenthesis in general (especially in UFCS call chains), I can say I am surprised by this behavior.
Jun 08 2013
prev sibling next sibling parent "Stephan Schiffels" <stephan_schiffels mac.com> writes:
On Saturday, 8 June 2013 at 08:52:22 UTC, Jonathan M Davis wrote:

 Hmm, it works just fine on my system (64-bit Linux), so I don't 
 know why you're
 seeing the problem that you're seeing.

Hmm, that's bizarre, but I guess there's no need to understand this further since things work fine with std.algorithm.sort.
 However, we really, really need to deprecate the built-in sort 
 - especially
 when a pair of parens can make the difference between whether 
 you call the
 built-in sort or std.algorithm's sort - and it's particularly 
 broken with
 regards to Unicode.

Yes, I completely agree! Stephan
Jun 08 2013
prev sibling next sibling parent "Stephan Schiffels" <stephan_schiffels mac.com> writes:
On Saturday, 8 June 2013 at 09:16:23 UTC, monarch_dodra wrote:
 On Saturday, 8 June 2013 at 08:52:22 UTC, Jonathan M Davis 
 wrote:
 However, we really, really need to deprecate the built-in sort 
 - especially
 when a pair of parens can make the difference between whether 
 you call the
 built-in sort or std.algorithm's sort - and it's particularly 
 broken with
 regards to Unicode.

 - Jonathan M Davis

Or anything that uses non-POD comparison (opCmp) for that matter: //---- import std.stdio; import std.algorithm; struct S { int i; int opCmp(S o) { return (i < o.i) - (i > o.i); //inverse order } } void main() { auto a = [S(1), S(2), S(3)]; writeln(a); //[S(1), S(2), S(3)] a.sort; writeln(a); //[S(1), S(2), S(3)] a.sort(); writeln(a); //[S(3), S(2), S(1)] } //---- I had pretty much forgotten ".sort" even existed (it really never even crossed my mind that it could be built-in), and given the push for optional parenthesis in general (especially in UFCS call chains), I can say I am surprised by this behavior.

Wow, that's much worse than in my example... indeed very unexpected behaviour.
Jun 08 2013
prev sibling next sibling parent reply Peter Williams <pwil3058 bigpond.net.au> writes:
On 08/06/13 18:51, Jonathan M Davis wrote:
 On Saturday, June 08, 2013 10:30:52 Stephan Schiffels wrote:
 Hi,

 I know it has been discussed previously to deprecate the builtin
 sort. I don't know the status of this, but I observed the
 following problem.

 With dmd, druntime and phobos all on 2.063, this program runs
 successfully on a mac:

 #!/usr/bin/env rdmd

 import std.stdio;

 void main() {

     int[] a = [5, 4, 3, 2, 1];

     a.sort;
     writeln(a);

 }

 But it fails on linux, with the line:


 /nfs/users/nfs_s/ss27/Software/dlang/phobos/generated/linux/release/64/libph
 obos2.a(qsort_4c4_2cc.o): In function `_adSort':
 src/rt/qsort.d:(.text._adSort+0x47): undefined reference to
 `qsort_r'
 collect2: ld returned 1 exit status
 --- errorlevel 1


 When I change "a.sort" -> "a.sort()" and add import std.algorithm
 everything works fine.
 Does this mean that the builtin sort on Linux is broken with
 2.063?

Hmm, it works just fine on my system (64-bit Linux), so I don't know why you're seeing the problem that you're seeing. However, we really, really need to deprecate the built-in sort - especially when a pair of parens can make the difference between whether you call the built-in sort or std.algorithm's sort - and it's particularly broken with regards to Unicode. - Jonathan M Davis

Rather than deprecate it why not fix it? Shouldn't have to import std.algorithm just to sort an array. Peter
Jun 08 2013
parent reply Jacob Carlborg <doob me.com> writes:
On 2013-06-10 11:03, Stephan Schiffels wrote:

 I agree. Do people have the same opinion on the builtin reverse? I don't
 remember whether there was a discussion about this. I suggest to kill
 that as well. sort and reverse are perfectly well implemented in the
 standard library rather than builtin.

"reverse" is implemented with the stupid name "retro".
 Is anyone actually on this? I could try to dig into it, I guess I could
 start looking for spurious places in phobos and druntime where these
 builtin functions are used and replace them with the library ones. If we
 deprecate it in the end we don't want to see it being used anywhere in
 the standard implementations.

Perhaps start with modifying the compiler to indicate the "sort" and "reverse" functions are deprecated. Then it will be easier to find in Phobos and druntime. Also, if used in druntime they need to be reimplemented there. -- /Jacob Carlborg
Jun 10 2013
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/10/13 7:10 AM, Jacob Carlborg wrote:
 On 2013-06-10 11:03, Stephan Schiffels wrote:

 I agree. Do people have the same opinion on the builtin reverse? I don't
 remember whether there was a discussion about this. I suggest to kill
 that as well. sort and reverse are perfectly well implemented in the
 standard library rather than builtin.

"reverse" is implemented with the stupid name "retro".

std.algorithm.reverse reverses a range in place: http://dlang.org/phobos/std_algorithm.html#reverse std.range.retro iterates a range in retrograde order without modifying it: http://dlang.org/phobos/std_range.html#.retro Andrei
Jun 10 2013
parent Jacob Carlborg <doob me.com> writes:
On 2013-06-10 17:15, Andrei Alexandrescu wrote:

 std.algorithm.reverse reverses a range in place:
 http://dlang.org/phobos/std_algorithm.html#reverse

 std.range.retro iterates a range in retrograde order without modifying
 it: http://dlang.org/phobos/std_range.html#.retro

Right, my bad. -- /Jacob Carlborg
Jun 10 2013
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Peter Williams:

 Rather than deprecate it why not fix it?  Shouldn't have to 
 import std.algorithm just to sort an array.

Generally you want to keep the compiler (all its layers) as simpler as possible, to make it simpler to compile, debug and develop. A sort is implementable very well in library code. Other things, like tuples with a good syntax maybe can't be implemented well in library code, so they should be in the compiler :) I suggest to kill the built-in sort ASAP. Bye, bearophile
Jun 08 2013
prev sibling next sibling parent "David Nadlinger" <code klickverbot.at> writes:
On Saturday, 8 June 2013 at 22:25:14 UTC, Peter Williams wrote:
 Shouldn't have to import std.algorithm just to sort an array.

Why not? David
Jun 08 2013
prev sibling next sibling parent Peter Williams <pwil3058 bigpond.net.au> writes:
On 09/06/13 08:54, David Nadlinger wrote:
 On Saturday, 8 June 2013 at 22:25:14 UTC, Peter Williams wrote:
 Shouldn't have to import std.algorithm just to sort an array.

Why not?

Because it's large with a lot of stuff unrelated to sorting. Peter PS A few weeks ago I would have said "large and ugly" but now I have a better feel for component programming it's not so ugly :-) but it's still large.
Jun 08 2013
prev sibling next sibling parent "David Nadlinger" <code klickverbot.at> writes:
On Sunday, 9 June 2013 at 00:03:04 UTC, Peter Williams wrote:
 On 09/06/13 08:54, David Nadlinger wrote:
 On Saturday, 8 June 2013 at 22:25:14 UTC, Peter Williams wrote:
 Shouldn't have to import std.algorithm just to sort an array.

Why not?

Because it's large with a lot of stuff unrelated to sorting.

import std.algorithm : sort; David
Jun 08 2013
prev sibling next sibling parent "Idan Arye" <GenericNPC gmail.com> writes:
On Sunday, 9 June 2013 at 00:03:04 UTC, Peter Williams wrote:
 On 09/06/13 08:54, David Nadlinger wrote:
 On Saturday, 8 June 2013 at 22:25:14 UTC, Peter Williams wrote:
 Shouldn't have to import std.algorithm just to sort an array.

Why not?

Because it's large with a lot of stuff unrelated to sorting.

http://forum.dlang.org/thread/kooe7p$255m$1 digitalmars.com
Jun 08 2013
prev sibling next sibling parent "Stephan Schiffels" <stephan_schiffels mac.com> writes:
On Saturday, 8 June 2013 at 22:51:06 UTC, bearophile wrote:
 Peter Williams:

 Rather than deprecate it why not fix it?  Shouldn't have to 
 import std.algorithm just to sort an array.

Generally you want to keep the compiler (all its layers) as simpler as possible, to make it simpler to compile, debug and develop. A sort is implementable very well in library code. Other things, like tuples with a good syntax maybe can't be implemented well in library code, so they should be in the compiler :) I suggest to kill the built-in sort ASAP. Bye, bearophile

I agree. Do people have the same opinion on the builtin reverse? I don't remember whether there was a discussion about this. I suggest to kill that as well. sort and reverse are perfectly well implemented in the standard library rather than builtin. Is anyone actually on this? I could try to dig into it, I guess I could start looking for spurious places in phobos and druntime where these builtin functions are used and replace them with the library ones. If we deprecate it in the end we don't want to see it being used anywhere in the standard implementations. Stephan
Jun 10 2013
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
I have opened this issue:

http://d.puremagic.com/issues/show_bug.cgi?id=10318

Bye,
bearophile
Jun 10 2013
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Jacob Carlborg:

 "reverse" is implemented with the stupid name "retro".

Nope. "retro" is a lazy range that yields in reverse direction. The Phobos in-place reverse for arrays is named "reverse". But unlike the built-in reverse returns void.
 Perhaps start with modifying the compiler to indicate the 
 "sort" and "reverse" functions are deprecated.

The first step for Issue 10318 is indeed a warning for usage of the built-in sort. Bye, bearophile
Jun 10 2013
prev sibling next sibling parent "Stephan Schiffels" <stephan_schiffels mac.com> writes:
On Monday, 10 June 2013 at 11:10:06 UTC, Jacob Carlborg wrote:
 On 2013-06-10 11:03, Stephan Schiffels wrote:

 I agree. Do people have the same opinion on the builtin 
 reverse? I don't
 remember whether there was a discussion about this. I suggest 
 to kill
 that as well. sort and reverse are perfectly well implemented 
 in the
 standard library rather than builtin.

"reverse" is implemented with the stupid name "retro".

That's not correct, it's called "reverse" and is a builtin property of dynamic arrays, see bearophiles answer... "retro" is lazy!
 Is anyone actually on this? I could try to dig into it, I 
 guess I could
 start looking for spurious places in phobos and druntime where 
 these
 builtin functions are used and replace them with the library 
 ones. If we
 deprecate it in the end we don't want to see it being used 
 anywhere in
 the standard implementations.

Perhaps start with modifying the compiler to indicate the "sort" and "reverse" functions are deprecated. Then it will be easier to find in Phobos and druntime. Also, if used in druntime they need to be reimplemented there.

Right, I thought so, too. Indeed, bearophiles issue addresses this in this order. I will try this on a local branch first and possibly open a pull request to start a more concrete discussion on this... Stephan
Jun 10 2013
prev sibling parent "nazriel" <spam dzfl.pl> writes:
On Saturday, 8 June 2013 at 08:30:54 UTC, Stephan Schiffels wrote:
 Hi,

 I know it has been discussed previously to deprecate the 
 builtin sort. I don't know the status of this, but I observed 
 the following problem.

 With dmd, druntime and phobos all on 2.063, this program runs 
 successfully on a mac:

 #!/usr/bin/env rdmd

 import std.stdio;

 void main() {

   int[] a = [5, 4, 3, 2, 1];

   a.sort;
   writeln(a);

 }

 But it fails on linux, with the line:


 /nfs/users/nfs_s/ss27/Software/dlang/phobos/generated/linux/release/64/libphobos2
a(qsort_4c4_2cc.o): 
 In function `_adSort':
 src/rt/qsort.d:(.text._adSort+0x47): undefined reference to 
 `qsort_r'
 collect2: ld returned 1 exit status
 --- errorlevel 1


 When I change "a.sort" -> "a.sort()" and add import 
 std.algorithm everything works fine.
 Does this mean that the builtin sort on Linux is broken with 
 2.063?

 Stephan

Maybe it is related to https://github.com/D-Programming-Language/druntime/pull/427
Jun 10 2013