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

           Summary: std.algorithm.sort performance
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Keywords: performance
          Severity: enhancement
          Priority: P2
         Component: Phobos
        AssignedTo: nobody@puremagic.com
        ReportedBy: bearophile_hugs@eml.cc


--- Comment #0 from bearophile_hugs@eml.cc 2011-06-21 15:51:37 PDT ---
Created an attachment (id=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

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

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


Dmitry Olshansky <dmitry.olsh@gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dmitry.olsh@gmail.com


--- Comment #1 from Dmitry Olshansky <dmitry.olsh@gmail.com> 2011-06-26 08:35:32 PDT ---
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

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

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



--- Comment #2 from bearophile_hugs@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=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.

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

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


kennytm@gmail.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |kennytm@gmail.com


--- Comment #3 from kennytm@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=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

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

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



--- Comment #4 from bearophile_hugs@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: -------