[phobos] std.algorithm.sort slow as molasses

[Andrei Alexandrescu]

One simple solution would be for you to contribute dstat's sort to 
Phobos. However, I'd be curious what the reason of std's sort slowness 
is. I suspect it might be the fact that I use qsort all the way down 
instead of switching to insertion sort. What is your sort's strategy?

Andrei

David Simcha wrote:
> 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.
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> phobos mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos