www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Fixed-Length Array Sorting

reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
I have some C++ that does optimal sorting of 3 and 4 elements at

https://github.com/nordlow/justcxx/blob/master/sortn.hpp

Would anybody be interesting in getting this integrated into

std.algorithm.sorting

?
Apr 04 2016
next sibling parent reply Brian Schott <briancschott gmail.com> writes:
On Monday, 4 April 2016 at 09:36:19 UTC, Nordlöw wrote:

 I have some C++ that does optimal sorting of 3 and 4 elements at

 https://github.com/nordlow/justcxx/blob/master/sortn.hpp

 Would anybody be interesting in getting this integrated into

 std.algorithm.sorting

 ?


That's too readable. Try this: 
https://gist.github.com/Hackerpilot/eabb136a840a67b6fb27

Why 0x0607040502030001? I don't remember!
Apr 04 2016
parent reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Monday, 4 April 2016 at 10:53:51 UTC, Brian Schott wrote:

 That's too readable.


?
Apr 04 2016
parent Marco Leise <Marco.Leise gmx.de> writes:
Am Mon, 04 Apr 2016 12:11:20 +0000
schrieb Nordl=C3=B6w <per.nordlow gmail.com>:


 On Monday, 4 April 2016 at 10:53:51 UTC, Brian Schott wrote:

 That's too readable. =20


=20
 ?


=20
When you talk about optimizing there is always a "how far will
you go". Your code is still plain D and barely digestible.
Hackerpilot presents a different solution that is outright
cryptic and platform dependent, but supposedly even faster.

The humor lies in the continued obfuscation of the higher
level sort operation to the point of becoming an obfuscated
code challenge and the controversy it starts in our minds when
we demand both fast and maintainable library code.

--=20
Marco
Apr 04 2016
prev sibling next sibling parent Andrea Fontana <nospam example.com> writes:
On Monday, 4 April 2016 at 09:36:19 UTC, Nordlöw wrote:

 I have some C++ that does optimal sorting of 3 and 4 elements at

 https://github.com/nordlow/justcxx/blob/master/sortn.hpp

 Would anybody be interesting in getting this integrated into

 std.algorithm.sorting

 ?


But it sorts array only in a predefined way. You can't define a 
sort functions.
If we need to sort bytes in an ascending/descending order I think 
we should consider something like this too (it works well with 
large arrays, of course):

// Sort bytes array
auto byteSort(in ubyte[] src)
{
    size_t[256] buckets;
    src.each!(x => buckets[x]++);
    return buckets[].enumerate.map!(x => 
x.index.repeat(x.value)).join;
}
Apr 04 2016
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 04/04/2016 05:36 AM, Nordlöw wrote:

 I have some C++ that does optimal sorting of 3 and 4 elements at

 https://github.com/nordlow/justcxx/blob/master/sortn.hpp

 Would anybody be interesting in getting this integrated into

 std.algorithm.sorting

 ?


This is a good start but we'd need a more principled attack on the 
problem. There are optimal sorting networks for a number of small sizes; 
a good start is Knuth's TAoCP Volume 3 but there's newer research as 
well, which needs to be investigated. A sorting network in D can be 
nicely done with variadic template parameters, e.g. this:

r.conditionalSwap!(less, 0, 2, 1, 3);

expands to:

if (less(r[0], r[1])) r.swapAt(0, 2);
if (less(r[1], r[3])) r.swapAt(1, 3);

so then building a sorting network boils down to writing the right 
sequence of indexes.

We'd need to figure at which point the size of the generated code 
overwhelms any gains made from the specialized routines.

All of the above should be packaged in a routine:

auto sortUpTo(uint n, alias less = "a < b", Range)(Range r);

which asserts that r.length <= n, or maybe two because this is also useful:

auto sortExactly(uint n, alias less = "a < b", Range)(Range r);

which asserts that r.length == n. The documentation specifies the 
largest available n.


Andrei
Apr 07 2016
next sibling parent reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Thursday, 7 April 2016 at 13:09:22 UTC, Andrei Alexandrescu 
wrote:

 This is a good start but we'd need a more principled attack on 
 the problem. There are optimal sorting networks for a number of 
 small sizes; a good start is Knuth's TAoCP Volume 3 but there's 
 newer research as well, which needs to be investigated. A 
 sorting network in D can be nicely done with variadic template 
 parameters, e.g. this:


Could these fixed-length overloads be reused in the deepest 
recursions of existing Phobos algorithms, such as 
std.algorithm.sorting.sort() provided that the 
comparison-predicate matches.
Apr 07 2016
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 04/07/2016 09:28 AM, Nordlöw wrote:

 On Thursday, 7 April 2016 at 13:09:22 UTC, Andrei Alexandrescu wrote:

 This is a good start but we'd need a more principled attack on the
 problem. There are optimal sorting networks for a number of small
 sizes; a good start is Knuth's TAoCP Volume 3 but there's newer
 research as well, which needs to be investigated. A sorting network in
 D can be nicely done with variadic template parameters, e.g. this:


 Could these fixed-length overloads be reused in the deepest recursions
 of existing Phobos algorithms, such as std.algorithm.sorting.sort()


Could and should.


 provided that the comparison-predicate matches.


How do you mean that?


Andrei
Apr 07 2016
parent =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Thursday, 7 April 2016 at 16:03:00 UTC, Andrei Alexandrescu 
wrote:

 provided that the comparison-predicate matches.


 How do you mean that?


Ahh, isn't needed here.

I was referring to the extra checking that is needed when we want 
to specialize sorting to use integer sorting algorithms.
Apr 08 2016
prev sibling next sibling parent reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Thursday, 7 April 2016 at 13:09:22 UTC, Andrei Alexandrescu 
wrote:

 if (less(r[0], r[1])) r.swapAt(0, 2);
 if (less(r[1], r[3])) r.swapAt(1, 3);


Shouldn't it be

if (less(r[0], r[2])) r.swapAt(0, 2);
if (less(r[1], r[3])) r.swapAt(1, 3);

? Could you elaborate a bit on how this is used to express 
sorting? AFAICT, to become a full sorting network we need

if (less(r[0], r[2])) r.swapAt(0, 2);
if (less(r[1], r[3])) r.swapAt(1, 3);
if (less(r[0], r[1])) r.swapAt(0, 1);
if (less(r[2], r[3])) r.swapAt(2, 3);

right?
Apr 08 2016
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 4/8/16 3:18 AM, Nordlöw wrote:

 On Thursday, 7 April 2016 at 13:09:22 UTC, Andrei Alexandrescu wrote:

 if (less(r[0], r[1])) r.swapAt(0, 2);
 if (less(r[1], r[3])) r.swapAt(1, 3);


 Shouldn't it be

 if (less(r[0], r[2])) r.swapAt(0, 2);
 if (less(r[1], r[3])) r.swapAt(1, 3);

 ?


Yah, sorry for the mistake.


 Could you elaborate a bit on how this is used to express sorting?
 AFAICT, to become a full sorting network we need

 if (less(r[0], r[2])) r.swapAt(0, 2);
 if (less(r[1], r[3])) r.swapAt(1, 3);
 if (less(r[0], r[1])) r.swapAt(0, 1);
 if (less(r[2], r[3])) r.swapAt(2, 3);

 right?


Right, was just giving a quick example involving two arbitrary pairs of 
indexes.


Andrei
Apr 08 2016
prev sibling parent =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Friday, 8 April 2016 at 07:18:58 UTC, Nordlöw wrote:

 if (less(r[0], r[2])) r.swapAt(0, 2);
 if (less(r[1], r[3])) r.swapAt(1, 3);
 if (less(r[0], r[1])) r.swapAt(0, 1);
 if (less(r[2], r[3])) r.swapAt(2, 3);

 right?


Actually, needs a fifth stage

     if (less(r[1], r[2])) r.swapAt(1, 2);

to complete.
Apr 12 2016
prev sibling parent reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Thursday, 7 April 2016 at 13:09:22 UTC, Andrei Alexandrescu 
wrote:

 This is a good start but we'd need a more principled attack on 
 the problem.


Ok, Andrei! Here's a start.

https://github.com/nordlow/phobos-next/blob/master/src/sortn.d

Currently uses Phobos' permutations for complete verification. 
Its complexity will of course not work for larger values such as 
16.

Supports sorting networks currently up to length 6.

More to come :)

Could you please take a look at how to handle stability of 
"equal" elements?
Apr 12 2016
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 04/12/2016 06:49 AM, Nordlöw wrote:

 On Thursday, 7 April 2016 at 13:09:22 UTC, Andrei Alexandrescu wrote:

 This is a good start but we'd need a more principled attack on the
 problem.


 Ok, Andrei! Here's a start.

 https://github.com/nordlow/phobos-next/blob/master/src/sortn.d

 Currently uses Phobos' permutations for complete verification. Its
 complexity will of course not work for larger values such as 16.

 Supports sorting networks currently up to length 6.

 More to come :)


This is great. A few notes:

* Spacing around operators is inconsistent, for Phobos please use the 
prevalent style.

* There's a bit too much foreplay, e.g. why introduce names for 
everything even when used once (e.g. "alias comp = binaryFun!less;").

* There should be a notion of at what point the networks become too 
bulky to be fast - 6-16 may be the limit.

* The arguments in conditionalSwap are a bit awkward, how about:

template conditionalSwap(indexes...)
{
   void conditionalSwap(less = "a < b", Range)(Range r) { ... }
}

That way the caller doesn't need to specify less and Range.

* There is a nice peephole optimization you could make. Consider:

r.conditionalSwap!("a < b", less, 0, 1, 1, 2)(r);

which needs to do

if (r[1] < r[0]) r.swapAt(0, 1);
if (r[2] < r[1]) r.swapAt(1, 2);

For types with no elaborate copy/assignment, it's more efficient to use 
a "hole"-based approach - assign the first element to a temporary and 
then consider it a hole that you fill, then leaving another hole:

if (r[1] < r[0])
   if (r[2] < r[0]) r.swapAt(0, 1, 2);
   else r.swapAt(0, 1);
else
   if (r[2] < r[1]) r.swapAt(1, 2);

with swapAt with three argument having this definition: auto t = r[a]; 
r[a] = r[b]; r[b] = r[c]; r[c] = t;

i.e. create a temporary (which creates a "hole" in the array) then fill 
it leaving another hole etc., until the last hole is filled with the 
temporary.

* I found no use for hybridSort, only for sortExactly. Then hybridSort 
is a two-liner the user may write.


 Could you please take a look at how to handle stability of "equal"
 elements?


I'm not sure. Does it suffice to always swap when the lhs index is less 
than the rhs index?


Andrei
Apr 12 2016
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 04/12/2016 10:53 AM, Andrei Alexandrescu wrote:

 There is a nice peephole optimization


Should be fine to leave that to 2.0. -- Andrei
Apr 12 2016
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Also to avoid cache line thrashing, sort parallel swaps by leftmost 
index. E.g. this line:

18,19, 20,21, 2,4, 1,3, 0,5, 6,8, 7,9, 10,12, 11,13,

becomes:

0,5, 1,3, 2,4, 6,8, 7,9, 10,12, 11,13, 18,19, 20,21,


Andrei
Apr 12 2016
parent reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Tuesday, 12 April 2016 at 14:56:00 UTC, Andrei Alexandrescu 
wrote:

 Also to avoid cache line thrashing, sort parallel swaps by 
 leftmost index. E.g. this line:

 18,19, 20,21, 2,4, 1,3, 0,5, 6,8, 7,9, 10,12, 11,13,

 becomes:

 0,5, 1,3, 2,4, 6,8, 7,9, 10,12, 11,13, 18,19, 20,21,


 Andrei


Done.
Apr 13 2016
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 04/13/2016 12:07 PM, Nordlöw wrote:

 On Tuesday, 12 April 2016 at 14:56:00 UTC, Andrei Alexandrescu wrote:

 Also to avoid cache line thrashing, sort parallel swaps by leftmost
 index. E.g. this line:

 18,19, 20,21, 2,4, 1,3, 0,5, 6,8, 7,9, 10,12, 11,13,

 becomes:

 0,5, 1,3, 2,4, 6,8, 7,9, 10,12, 11,13, 18,19, 20,21,


 Andrei


 Done.


No time but couple more remarks:\

* Cut and paste error at 
https://github.com/nordlow/phobos-next/blob/master/src/sortn.d#L90

* I see some sizes are not supported, we should not have holes.

* Sometimes the sort routine gets too bulky. Suggestion: also define 
networks for medianOfUpTo and medianExactly, then use them in a 
quicksort manner - first compute the median to segregate values in 
below/over the median, then make two calls to sortExactly!(n / 2). That 
way you get to sort n values with median of n values (smaller and 
simpler) and two sorts of n / 2 values.

I think this is great work in the making. We should be able at some 
point to plug this into std.sort.


Andrei
Apr 13 2016
parent reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Wednesday, 13 April 2016 at 19:58:49 UTC, Andrei Alexandrescu 
wrote:

 * Cut and paste error at 
 https://github.com/nordlow/phobos-next/blob/master/src/sortn.d#L90


Fixed.


 * I see some sizes are not supported, we should not have holes.

 * Sometimes the sort routine gets too bulky. Suggestion: also 
 define networks for medianOfUpTo and medianExactly, then use 
 them in a quicksort manner - first compute the median to 
 segregate values in below/over the median, then make two calls 
 to sortExactly!(n / 2). That way you get to sort n values with 
 median of n values (smaller and simpler) and two sorts of n / 2 
 values.


Added as TODOs for now.

Thanks!
Apr 13 2016
parent reply Temtaime <temtaime gmail.com> writes:
On Wednesday, 13 April 2016 at 22:02:19 UTC, Nordlöw wrote:

 On Wednesday, 13 April 2016 at 19:58:49 UTC, Andrei 
 Alexandrescu wrote:

 * Cut and paste error at 
 https://github.com/nordlow/phobos-next/blob/master/src/sortn.d#L90


 Fixed.


 * I see some sizes are not supported, we should not have holes.

 * Sometimes the sort routine gets too bulky. Suggestion: also 
 define networks for medianOfUpTo and medianExactly, then use 
 them in a quicksort manner - first compute the median to 
 segregate values in below/over the median, then make two calls 
 to sortExactly!(n / 2). That way you get to sort n values with 
 median of n values (smaller and simpler) and two sorts of n / 
 2 values.


 Added as TODOs for now.

 Thanks!


If you want help std algorithm sorting, a better start is to fix 
bugs : a lot of functions can't work with swapstrategy stable and 
so on.
Me for example suffers from that.
Apr 13 2016
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 4/13/16 7:20 PM, Temtaime wrote:

 If you want help std algorithm sorting, a better start is to fix bugs :
 a lot of functions can't work with swapstrategy stable and so on.


Are these in bugzilla? -- Andrei
Apr 13 2016
parent Temtaime <temtaime gmail.com> writes:
On Thursday, 14 April 2016 at 01:13:55 UTC, Andrei Alexandrescu 
wrote:

 On 4/13/16 7:20 PM, Temtaime wrote:

 If you want help std algorithm sorting, a better start is to 
 fix bugs :
 a lot of functions can't work with swapstrategy stable and so 
 on.


 Are these in bugzilla? -- Andrei


Yes, once i had reported it. Also there're quotes from docs for 
example:

« Bugs:
Stable topN has not been implemented yet. »
Apr 14 2016
prev sibling parent =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Monday, 4 April 2016 at 09:36:19 UTC, Nordlöw wrote:

 I have some C++ that does optimal sorting of 3 and 4 elements at


Here's a nice presention on the topic "Sorting Networks":

http://hoytech.github.io/sorting-networks/
Apr 12 2016