www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 7767] New: Unstable sort - slow performance cases


           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

--- Comment #0 from Xinok <xinok live.com> 2012-03-24 20:00:28 PDT ---
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;
    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: -------
Mar 24 2012