www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - std.algorithm.sort slower than C++'s std::sort for integer arrays

reply Atila Neves <atila.neves gmail.com> writes:
This I was not expecting:

https://www.reddit.com/r/programming/comments/9v8ouc/an_overview_of_sorting_algorithms_and_a_pretty/e9ajt1o/
Nov 08 2018
next sibling parent Stanislav Blinov <stanislav.blinov gmail.com> writes:
On Thursday, 8 November 2018 at 14:36:45 UTC, Atila Neves wrote:
 This I was not expecting:

 https://www.reddit.com/r/programming/comments/9v8ouc/an_overview_of_sorting_algorithms_and_a_pretty/e9ajt1o/
Could be the DRuntime and libC calls that are made by `swap`, `move*`, etc. Would need to look at the code and generated asm though.
Nov 08 2018
prev sibling next sibling parent reply Andrea Fontana <nospam example.com> writes:
On Thursday, 8 November 2018 at 14:36:45 UTC, Atila Neves wrote:
 This I was not expecting:

 https://www.reddit.com/r/programming/comments/9v8ouc/an_overview_of_sorting_algorithms_and_a_pretty/e9ajt1o/
I wonder if they uses the same algorithm. I mean: qsort could sound like quicksort but is not specified anywhere. I've already said in the past that we probably can improve sort() function tuning it for some cases (f.e. short int or bytes...). Many languages use some hybrid algorithms like timsort & similar. I don't know what D do on phobos... Did you consider this? Andrea
Nov 08 2018
parent reply JN <666total wp.pl> writes:
On Thursday, 8 November 2018 at 15:28:25 UTC, Andrea Fontana 
wrote:
 I've already said in the past that we probably can improve 
 sort() function tuning it for some cases (f.e. short int or 
 bytes...). Many languages use some hybrid algorithms like 
 timsort & similar. I don't know what D do on phobos...

 Did you consider this?

 Andrea
https://dlang.org/phobos/std_algorithm_sorting.html#sort "Algorithms Introsort is used for unstable sorting and Timsort is used for stable sorting."
Nov 08 2018
next sibling parent reply Andrea Fontana <nospam example.com> writes:
On Thursday, 8 November 2018 at 17:43:47 UTC, JN wrote:
 On Thursday, 8 November 2018 at 15:28:25 UTC, Andrea Fontana 
 wrote:
 I've already said in the past that we probably can improve 
 sort() function tuning it for some cases (f.e. short int or 
 bytes...). Many languages use some hybrid algorithms like 
 timsort & similar. I don't know what D do on phobos...

 Did you consider this?

 Andrea
https://dlang.org/phobos/std_algorithm_sorting.html#sort "Algorithms Introsort is used for unstable sorting and Timsort is used for stable sorting."
Right, what about the others language tested?
Nov 08 2018
parent Andrea Fontana <nospam example.com> writes:
On Friday, 9 November 2018 at 07:57:57 UTC, Andrea Fontana wrote:
 On Thursday, 8 November 2018 at 17:43:47 UTC, JN wrote:
 On Thursday, 8 November 2018 at 15:28:25 UTC, Andrea Fontana 
 wrote:
 I've already said in the past that we probably can improve 
 sort() function tuning it for some cases (f.e. short int or 
 bytes...). Many languages use some hybrid algorithms like 
 timsort & similar. I don't know what D do on phobos...

 Did you consider this?

 Andrea
https://dlang.org/phobos/std_algorithm_sorting.html#sort "Algorithms Introsort is used for unstable sorting and Timsort is used for stable sorting."
Right, what about the others language tested?
Wikipedia: "Introsort or introspective sort is a hybrid sorting algorithm that provides both fast average performance and (asymptotically) optimal worst-case performance. It begins with quicksort and switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted." Fast analysis follows. Here it seems qs is used: https://github.com/dlang/phobos/blob/b16687357013eaa952decdc3d1d03d442b9429cd/std/algorithm/sorting.d#L1857 https://github.com/dlang/phobos/blob/b16687357013eaa952decdc3d1d03d442b9429cd/std/algorithm/sorting.d#L1869 But here it seems it is a hybrid algorithm (not using logarithm): https://github.com/dlang/phobos/blob/b16687357013eaa952decdc3d1d03d442b9429cd/std/algorithm/sorting.d#L2059 Calling this in some cases (it doesn't sound like heapsort): https://github.com/dlang/phobos/blob/b16687357013eaa952decdc3d1d03d442b9429cd/std/algorithm/sorting.d#L1622 So I'm not sure documentation is correct. Andrea
Nov 09 2018
prev sibling parent reply Atila Neves <atila.neves gmail.com> writes:
On Thursday, 8 November 2018 at 17:43:47 UTC, JN wrote:
 On Thursday, 8 November 2018 at 15:28:25 UTC, Andrea Fontana 
 wrote:
 I've already said in the past that we probably can improve 
 sort() function tuning it for some cases (f.e. short int or 
 bytes...). Many languages use some hybrid algorithms like 
 timsort & similar. I don't know what D do on phobos...

 Did you consider this?

 Andrea
https://dlang.org/phobos/std_algorithm_sorting.html#sort "Algorithms Introsort is used for unstable sorting and Timsort is used for stable sorting."
That is indeed what the ddoc says. The code, however: ---------------------- static if (ss == SwapStrategy.unstable) quickSortImpl!(lessFun)(r, r.length); else //use Tim Sort for semistable & stable TimSortImpl!(lessFun, Range).sort(r, null); ----------------------
Nov 09 2018
parent Andrea Fontana <nospam example.com> writes:
On Friday, 9 November 2018 at 09:34:10 UTC, Atila Neves wrote:
 On Thursday, 8 November 2018 at 17:43:47 UTC, JN wrote:
 That is indeed what the ddoc says. The code, however:
------------ Check my answer I didn't see yours. It seems a hybrid algorithm, quickSortImpl it's not a pure quick sort implementation actually. Andrea
Nov 09 2018
prev sibling parent reply Jon Degenhardt <jond noreply.com> writes:
On Thursday, 8 November 2018 at 14:36:45 UTC, Atila Neves wrote:
 This I was not expecting:

 https://www.reddit.com/r/programming/comments/9v8ouc/an_overview_of_sorting_algorithms_and_a_pretty/e9ajt1o/
I didn't see a build line. Assuming LDC, one thing that can happen is that code from druntime/phobos may not be optimized as well as code passed in on the build line (ie. manual.d) unless LTO against druntime and phobos is used. Using LTO to include druntime/phobos can be done by including: -flto=<thin|full> -defaultlib=druntime-ldc-lto,phobos2-ldc-lto on the build line. (Personally I'd start with 'thin' LTO and switch to 'full' only if there's an issue.) Using LTO on only D could result in a comparison inequity. However, it is legitimate for comparing std.algorithm.sort to manual.d. --Jon
Nov 08 2018
parent Jon Degenhardt <jond noreply.com> writes:
On Friday, 9 November 2018 at 00:31:32 UTC, Jon Degenhardt wrote:
 On Thursday, 8 November 2018 at 14:36:45 UTC, Atila Neves wrote:
 This I was not expecting:

 https://www.reddit.com/r/programming/comments/9v8ouc/an_overview_of_sorting_algorithms_and_a_pretty/e9ajt1o/
Using LTO on only D could result in a comparison inequity. However, it is legitimate for comparing std.algorithm.sort to manual.d.
I gave LTO a try for this (Mac OS). It did not change anything. Timings I saw were consistent with Atila's report, with and without LTO.
Nov 08 2018