[Issue 6192] std.algorithm.sort performance

[d-bugmail at puremagic.com]

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



--- Comment #4 from bearophile_hugs at 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=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).

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------