digitalmars.D - std.algorithm.sort slower than C++'s std::sort for integer arrays
- Atila Neves (2/2) Nov 08 2018 This I was not expecting:
- Stanislav Blinov (4/6) Nov 08 2018 Could be the DRuntime and libC calls that are made by `swap`,
- Andrea Fontana (10/12) Nov 08 2018 I wonder if they uses the same algorithm.
- JN (6/12) Nov 08 2018 https://dlang.org/phobos/std_algorithm_sorting.html#sort
- Andrea Fontana (2/16) Nov 08 2018 Right, what about the others language tested?
- Andrea Fontana (17/35) Nov 09 2018 Wikipedia:
- Atila Neves (8/22) Nov 09 2018 That is indeed what the ddoc says. The code, however:
- Andrea Fontana (5/7) Nov 09 2018 ------------
- Jon Degenhardt (13/15) Nov 08 2018 I didn't see a build line. Assuming LDC, one thing that can
- Jon Degenhardt (4/11) Nov 08 2018 I gave LTO a try for this (Mac OS). It did not change anything.
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
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
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
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? Andreahttps://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
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:Right, what about the others language tested?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? Andreahttps://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
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: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. AndreaOn Thursday, 8 November 2018 at 15:28:25 UTC, Andrea Fontana wrote:Right, what about the others language tested?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? Andreahttps://dlang.org/phobos/std_algorithm_sorting.html#sort "Algorithms Introsort is used for unstable sorting and Timsort is used for stable sorting."
Nov 09 2018
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: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); ----------------------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? Andreahttps://dlang.org/phobos/std_algorithm_sorting.html#sort "Algorithms Introsort is used for unstable sorting and Timsort is used for stable sorting."
Nov 09 2018
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
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
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: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.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.
Nov 08 2018