Bug 6192 – std.algorithm.sort performance

Created attachment 1004 sort bench The small benchmark program shows the performance of std.algorithm.sort compared to a different one (it doesn't accept a key sort function, etc). One output example: sort-sort2 benchmarks (milliseconds), N=6000000: Random distribution: sort: 4131 sort2: 2635 Already sorted arrays: sort: 1979 sort2: 787 Inverted order arrays: sort: 2105 sort2: 1374 Few random doubles appended to the sorted arrays: sort: 2890 sort2: 1551 See also bug 5077

Results for me on upcomming 2.054 Phobos: sort-sort2 benchmarks (milliseconds), N=6000000: Random distribution: sort: 1040 sort2: 1012 Already sorted arrays: sort: 357 sort2: 312 Inverted order arrays: sort: 361 sort2: 576 Few random doubles appended to the sorted arrays: sort: 3657 sort2: 482 compiled with: dmd -O -inline -release sort_bench.d

Was this update in the sort code caused by this enhancement request, or are they unrelated? Timings with DMD 2.054beta, a different CPU: sort-sort2 benchmarks (milliseconds), N=6000000: Random distribution: sort: 1892 sort2: 1131 Already sorted arrays: sort: 748 sort2: 376 Inverted order arrays: sort: 1048 sort2: 656 Few random doubles appended to the sorted arrays: sort: 3085 sort2: 734 It seems the random case is improved a lot, the already sorted case is improved, the inverted order is about the same, and the few random values added case is slower than before.

(In reply to comment #2) > Was this update in the sort code caused by this enhancement request, or are > they unrelated? > > Timings with DMD 2.054beta, a different CPU: > > > sort-sort2 benchmarks (milliseconds), N=6000000: > Random distribution: > sort: 1892 > sort2: 1131 > Already sorted arrays: > sort: 748 > sort2: 376 > Inverted order arrays: > sort: 1048 > sort2: 656 > Few random doubles appended to the sorted arrays: > sort: 3085 > sort2: 734 > > > It seems the random case is improved a lot, the already sorted case is > improved, the inverted order is about the same, and the few random values added > case is slower than before. https://github.com/D-Programming-Language/phobos/pull/74

Thank you for your work. The new timings (after pull 74): sort-sort2 benchmarks (milliseconds), N=6000000: Random distribution: sort: 1261 sort2: 1201 Already sorted arrays: sort: 300 sort2: 441 Inverted order arrays: sort: 315 sort2: 729 Few random doubles appended to the sorted arrays: sort: 9962 sort2: 632 The last case is a common use case in Python code. Python programmers sometimes append unsorted items to a sorted list, and once in a while they sort it. Because the Timsort used in Python (and Java) is able to face this case very well, this is an efficient strategy to keep a rarely updated list sorted in Python. I don't know how much common this pattern is in real D code (but experience shows that often real-world data is already partially sorted).

Just pasting this for future reference: dual-pivot quicksort http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf Seems to be used in Java 8's sort for primitive types according to http://vkostyukov.ru/posts/dual-pivot-binary-search/

(In reply to Andrei Alexandrescu from comment #6) > https://github.com/D-Programming-Language/phobos/pull/3922 With this PR and the command line: dmd -O -inline -release -run sort-benchmark.d 6000000 the output is: sort-sort2 benchmarks (milliseconds), N=6000000: Random distribution: sort: 696 sort2: 680 Already sorted arrays: sort: 122 sort2: 113 Inverted order arrays: sort: 132 sort2: 224 Few random doubles appended to the sorted arrays: sort: 244 sort2: 234

After a few more tweaks: dmd -O -inline -release -run sort-benchmark.d 6000000 sort-sort2 benchmarks (milliseconds), N=6000000: Random distribution: sort: 702 sort2: 689 Already sorted arrays: sort: 108 sort2: 115 Inverted order arrays: sort: 154 sort2: 215 Few random doubles appended to the sorted arrays: sort: 247 sort2: 251

Fixed by https://github.com/dlang/phobos/pull/4826