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:



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 reply 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:
 

 
 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
next sibling parent reply "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
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 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 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:



 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
next sibling parent reply "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
next sibling parent reply "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
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
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 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 



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



Right, my bad.

-- 
/Jacob Carlborg
Jun 10 2013
prev 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 parent reply "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
parent reply 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
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 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 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:



 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