Re: Fixed-Length Array Sorting

[Temtaime via Digitalmars-d]

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. »

Re: Fixed-Length Array Sorting

[Andrei Alexandrescu via Digitalmars-d]

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

Re: Fixed-Length Array Sorting

[Temtaime via Digitalmars-d]

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.

Re: Fixed-Length Array Sorting

[Nordlöw via Digitalmars-d]

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!

Re: Fixed-Length Array Sorting

[Andrei Alexandrescu via Digitalmars-d]

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

Re: Fixed-Length Array Sorting

[Nordlöw via Digitalmars-d]

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.

Re: Fixed-Length Array Sorting

[Andrei Alexandrescu via Digitalmars-d]

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

Re: Fixed-Length Array Sorting

[Andrei Alexandrescu via Digitalmars-d]

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

Re: Fixed-Length Array Sorting

[Andrei Alexandrescu via Digitalmars-d]

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

Re: Fixed-Length Array Sorting

[Nordlöw via Digitalmars-d]

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?

Re: Fixed-Length Array Sorting

[Nordlöw via Digitalmars-d]

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.

Re: Fixed-Length Array Sorting

[Nordlöw via Digitalmars-d]

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/

Re: Fixed-Length Array Sorting

[Andrei Alexandrescu via Digitalmars-d]

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

Re: Fixed-Length Array Sorting

[Nordlöw via Digitalmars-d]

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?

Re: Fixed-Length Array Sorting

[Nordlöw via Digitalmars-d]

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.

Re: Fixed-Length Array Sorting

[Andrei Alexandrescu via Digitalmars-d]

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

Re: Fixed-Length Array Sorting

[Nordlöw via Digitalmars-d]

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.

Re: Fixed-Length Array Sorting

[Andrei Alexandrescu via Digitalmars-d]

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

Re: Fixed-Length Array Sorting

[Andrea Fontana via Digitalmars-d]

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;

}

Re: Fixed-Length Array Sorting

[Marco Leise via Digitalmars-d]

Am Mon, 04 Apr 2016 12:11:20 +
schrieb Nordlöw :

> On Monday, 4 April 2016 at 10:53:51 UTC, Brian Schott wrote:
> > That's too readable.  
> 
> ?
 
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.

-- 
Marco

Re: Fixed-Length Array Sorting

[Nordlöw via Digitalmars-d]

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

That's too readable.


?

Re: Fixed-Length Array Sorting

[Brian Schott via Digitalmars-d]

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!