[Issue 6192] std.algorithm.sort performance

[via Digitalmars-d-bugs]

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

[via Digitalmars-d-bugs]

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

[via Digitalmars-d-bugs]

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

greenify  changed:

   What|Removed |Added

 CC||greeen...@gmail.com

--

[Issue 6192] std.algorithm.sort performance

[via Digitalmars-d-bugs]

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

[via Digitalmars-d-bugs]

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

[d-bugmail]

https://d.puremagic.com/issues/show_bug.cgi?id=6192


Andrei Alexandrescu and...@erdani.com changed:

   What|Removed |Added

 CC||and...@erdani.com


--- Comment #5 from Andrei Alexandrescu and...@erdani.com 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

[d-bugmail]

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

[d-bugmail]

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

[d-bugmail]

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: ---