[Issue 2966] New: std.algorithm.sort Slower than Selection Sort

[d-bugmail at puremagic.com]

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

           Summary: std.algorithm.sort Slower than Selection Sort
           Product: D
           Version: 2.029
          Platform: PC
        OS/Version: Windows
            Status: NEW
          Keywords: performance
          Severity: regression
          Priority: P2
         Component: Phobos
        AssignedTo: bugzilla at digitalmars.com
        ReportedBy: dsimcha at yahoo.com


I noticed some code I wrote using std.algorithm.sort was really slow, so I
tested it against the builtin sort and a quick and dirty selection sort I
wrote.  (Yes, I used a selection sort just to show how severe this actually
is.)  Here's the test program:

import std.stdio, std.algorithm, std.perf, std.random;

void main() {
    enum N = 100_000;
    uint[] foo = new uint[N];

    // This isn't a corner case bug.  There should be almost no ties here.
    foreach(ref elem; foo) {
        elem = uniform(0U, 4_000_000_000U);
    }

    auto bar = foo.dup;
    scope pc = new PerformanceCounter;
    pc.start;
    std.algorithm.sort(bar);
    pc.stop;
    writeln("std.algorithm:  ", pc.milliseconds);

    bar[] = foo[];
    pc.start;
    selecSort(bar);
    pc.stop;
    writeln("Selection sort:  ", pc.milliseconds);

    bar[] = foo[];
    pc.start;
    bar.sort;  // Builtin.
    pc.stop;
    writeln("Builtin sort:  ", pc.milliseconds);
}

void selecSort(uint[] data) {
    foreach(i; 0..data.length) {
        uint minI = i;
        foreach(j; i + 1..data.length) {
            if(data[j] < data[minI]) {
                minI = j;
            }
        }
        swap(data[i], data[minI]);
    }
}

And the timings:

std.algorithm:  5708
Selection sort:  4029
Builtin sort:  21

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