[Issue 6192] std.algorithm.sort performance
https://issues.dlang.org/show_bug.cgi?id=6192 Andrei Alexandrescu changed: What|Removed |Added Status|NEW |RESOLVED Resolution|--- |FIXED --- Comment #10 from Andrei Alexandrescu --- Fixed by https://github.com/dlang/phobos/pull/4826 --
[Issue 6192] std.algorithm.sort performance
https://issues.dlang.org/show_bug.cgi?id=6192 --- Comment #9 from Andrei Alexandrescu --- https://github.com/dlang/phobos/pull/4826 --
[Issue 6192] std.algorithm.sort performance
https://issues.dlang.org/show_bug.cgi?id=6192 greenify changed: What|Removed |Added CC||greeen...@gmail.com --
[Issue 6192] std.algorithm.sort performance
https://issues.dlang.org/show_bug.cgi?id=6192 --- Comment #8 from Andrei Alexandrescu --- After a few more tweaks: dmd -O -inline -release -run sort-benchmark.d 600 sort-sort2 benchmarks (milliseconds), N=600: 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 --
[Issue 6192] std.algorithm.sort performance
https://issues.dlang.org/show_bug.cgi?id=6192 --- Comment #7 from Andrei Alexandrescu --- (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 600 the output is: sort-sort2 benchmarks (milliseconds), N=600: 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 --
[Issue 6192] std.algorithm.sort performance
https://issues.dlang.org/show_bug.cgi?id=6192 --- Comment #6 from Andrei Alexandrescu --- https://github.com/D-Programming-Language/phobos/pull/3922 --
[Issue 6192] std.algorithm.sort performance
https://d.puremagic.com/issues/show_bug.cgi?id=6192 Andrei Alexandrescu changed: What|Removed |Added CC||and...@erdani.com --- Comment #5 from Andrei Alexandrescu 2014-02-17 15:01:46 PST --- 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/ -- Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 6192] std.algorithm.sort performance
http://d.puremagic.com/issues/show_bug.cgi?id=6192 --- Comment #4 from bearophile_h...@eml.cc 2011-07-11 04:58:06 PDT --- Thank you for your work. The new timings (after pull 74): sort-sort2 benchmarks (milliseconds), N=600: 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). -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 6192] std.algorithm.sort performance
http://d.puremagic.com/issues/show_bug.cgi?id=6192 kenn...@gmail.com changed: What|Removed |Added CC||kenn...@gmail.com --- Comment #3 from kenn...@gmail.com 2011-07-06 11:00:55 PDT --- (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=600: > 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 -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 6192] std.algorithm.sort performance
http://d.puremagic.com/issues/show_bug.cgi?id=6192 --- Comment #2 from bearophile_h...@eml.cc 2011-07-06 10:42:20 PDT --- 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=600: 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. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 6192] std.algorithm.sort performance
http://d.puremagic.com/issues/show_bug.cgi?id=6192 Dmitry Olshansky changed: What|Removed |Added CC||dmitry.o...@gmail.com --- Comment #1 from Dmitry Olshansky 2011-06-26 08:35:32 PDT --- Results for me on upcomming 2.054 Phobos: sort-sort2 benchmarks (milliseconds), N=600: 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 -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
