www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Eh, bit faster sort

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
https://github.com/dlang/phobos/pull/4816

Destroy!

Andrei
Sep 24 2016
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 09/24/2016 11:13 AM, Andrei Alexandrescu wrote:

 https://github.com/dlang/phobos/pull/4816


Autotester fails with:

std/algorithm/sorting.d(1314): Error: undefined identifier '__dollar'
std/algorithm/sorting.d(1314): Error: undefined identifier '__dollar'
std/algorithm/sorting.d(1715): Error: template instance 
std.algorithm.sorting.shortSort!(binaryFun, RefRange!(int[])) error 
instantiating
std/algorithm/sorting.d(1502):        instantiated from here: 
quickSortImpl!(binaryFun, RefRange!(int[]))
std/range/package.d(9438):        instantiated from here: sort!("a < b", 
cast(SwapStrategy)0, RefRange!(int[]))

It seems RefRange does define length but not opDollar. Could somebody 
fix that?

Also I saw this:

          property auto length()
         {
             return (*_range).length;
         }

         static if (is(typeof((*cast(const R*)_range).length))) 
 property auto length() const
         {
             return (*_range).length;
         }

What's the deal with that? Surely there are easier ways! Fixes much 
appreciated, thanks!


Andrei
Sep 24 2016
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 09/24/2016 11:38 AM, Andrei Alexandrescu wrote:

 On 09/24/2016 11:13 AM, Andrei Alexandrescu wrote:

 https://github.com/dlang/phobos/pull/4816


 Autotester fails with:

 std/algorithm/sorting.d(1314): Error: undefined identifier '__dollar'
 std/algorithm/sorting.d(1314): Error: undefined identifier '__dollar'
 std/algorithm/sorting.d(1715): Error: template instance
 std.algorithm.sorting.shortSort!(binaryFun, RefRange!(int[])) error
 instantiating
 std/algorithm/sorting.d(1502):        instantiated from here:
 quickSortImpl!(binaryFun, RefRange!(int[]))
 std/range/package.d(9438):        instantiated from here: sort!("a < b",
 cast(SwapStrategy)0, RefRange!(int[]))

 It seems RefRange does define length but not opDollar. Could somebody
 fix that?

 Also I saw this:

          property auto length()
         {
             return (*_range).length;
         }

         static if (is(typeof((*cast(const R*)_range).length)))  property
 auto length() const
         {
             return (*_range).length;
         }

 What's the deal with that? Surely there are easier ways! Fixes much
 appreciated, thanks!


https://issues.dlang.org/show_bug.cgi?id=16534

Andrei
Sep 24 2016
parent ZombineDev <petar.p.kirov gmail.com> writes:
On Saturday, 24 September 2016 at 15:45:56 UTC, Andrei 
Alexandrescu wrote:

 On 09/24/2016 11:38 AM, Andrei Alexandrescu wrote:

 [...]


 https://issues.dlang.org/show_bug.cgi?id=16534

 Andrei


https://github.com/dlang/phobos/pull/4817
Sep 24 2016
prev sibling parent reply deadalnix <deadalnix gmail.com> writes:
On Saturday, 24 September 2016 at 15:13:47 UTC, Andrei 
Alexandrescu wrote:

 https://github.com/dlang/phobos/pull/4816

 Destroy!

 Andrei


Adding sorting network for small cases ?
Sep 24 2016
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 9/24/16 5:02 PM, deadalnix wrote:

 On Saturday, 24 September 2016 at 15:13:47 UTC, Andrei Alexandrescu wrote:

 https://github.com/dlang/phobos/pull/4816

 Destroy!

 Andrei


 Adding sorting network for small cases ?


That's kind of what's happening. -- Andrei
Sep 24 2016
parent Era Scarecrow <rtcvb32 yahoo.com> writes:
On Saturday, 24 September 2016 at 22:11:19 UTC, Andrei 
Alexandrescu wrote:

 On 9/24/16 5:02 PM, deadalnix wrote:

 On Saturday, 24 September 2016 at 15:13:47 UTC, Andrei 
 Alexandrescu wrote:

 https://github.com/dlang/phobos/pull/4816

 Destroy!


 Adding sorting network for small cases ?


 That's kind of what's happening. -- Andrei


  From the glancing at it, the short cases are inlined or very 
short cases of code that hopefully reduce excessive frame 
setup/teardown when fully optimized.

  I recall us going over some of the optimal 
combinations/breakdowns, but the complexity in code vs the speed 
improvement, not sure. With exceptions to embedded/limited 
memory/drive space, making code faster will probably be the 
priority.
Sep 25 2016
prev sibling parent =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Saturday, 24 September 2016 at 21:02:31 UTC, deadalnix wrote:

 Adding sorting network for small cases ?


Feel free to integrate these:

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

:)

Lengths 7 and 17 are missing. If you think this is a problem I 
can add them.

If Andrei gives me instructions on how to do the integration I 
can help out.
Sep 26 2016