• d-bugmail puremagic.com (33/33) Mar 24 2012 http://d.puremagic.com/issues/show_bug.cgi?id=7767

d-bugmail puremagic.com writes:

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

           Summary: Unstable sort - slow performance cases
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Phobos
        AssignedTo: nobody puremagic.com
        ReportedBy: xinok live.com



I've discovered a number of cases in which the unstable sort in std.algorithm
performs very poorly. I'll provide the simplest example I have.

import std.stdio, std.algorithm, std.range, std.datetime;
void main(){
    uint[] arr;
    arr.length = 1024 * 1024;
    foreach(i, ref v; arr) v = i;
    swapRanges(arr[0..$/2], arr[$/2..$]);
    StopWatch sw;
    sw.start();
    sort(arr);
    sw.stop();
    writeln(sw.peek.seconds, " seconds");
}

This case takes 28 seconds on my PC. The problem can be solved by falling back
to a heap sort or shell sort after so many recursions. Slow cases like these
have possible security implications.

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