[phobos] std.algorithm.sort slow as molasses

[David Simcha]

Here are some benchmarks of std.algorithm.sort vs. GCC 4.1.2's
implementation of STL sort() and the implementation I use in my dstats
library for lots of statistical calculations.

D code:
import std.stdio, std.perf, std.random, std.algorithm, dstats.sort;

void main(string[] args) {
    auto nums = new float[1_000_000];
    foreach(ref num; nums) {
        num = uniform(0.0, 10_000_000.0);
    }

    auto pc = new PerformanceCounter;
    pc.start;

    if(args.length > 1 && args[1] == "--dstats") {
        dstats.sort.qsort(nums);
    } else {
        std.algorithm.sort(nums);
    }

    pc.stop;
    writeln(pc.milliseconds);
}

C++ code:

#include <vector>
#include <ctime>
#include <cstdlib>
#include <algorithm>
#include <iostream>

using namespace std;

// Generates quick and dirty random numbers.
float sloppyRand() {
    unsigned num = 0;
    num += (rand() << 16);
    num += rand();
    return num;
}

int main() {
    vector<float> nums(1000000);
    for(int i = 0; i < nums.size(); i++) {
        nums[i] = sloppyRand();
    }

    double startTime = clock();
    sort(nums.begin(), nums.end());
    double stopTime = clock();

    double clocksPerMillisec = CLOCKS_PER_SEC / 1000.0;
    cout << (stopTime - startTime) / clocksPerMillisec << endl;
}

Compilers:
DMD 2.047 (for D)
GCC 4.1.2  (For C++;  I couldn't get the C++ code to compile on DMC because
of STL issues that I don't feel like solving, even though this would level
the playing field because D and C++ would have the same backend)

Results on Indel Xeon x5472:

Compiler settings:  -O -inline -release (for D), -O3 (for GCC)

D, using std.algorithm.sort:  330 milliseconds
D, using dstats.qsort:  96 milliseconds
C++, using 64-bit compile:  90 milliseconds
C++, using 32-bit compile:  100 milliseconds

I'd say std.algorithm.sort could use some serious optimization.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/phobos/attachments/20100702/1a52f247/attachment.html>