[Issue 5077] New: std.algorithm.schwartzSort is slow

[d-bugmail at puremagic.com]

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

           Summary: std.algorithm.schwartzSort is slow
           Product: D
           Version: D2
          Platform: x86
        OS/Version: Windows
            Status: NEW
          Keywords: performance
          Severity: enhancement
          Priority: P2
         Component: Phobos
        AssignedTo: nobody at puremagic.com
        ReportedBy: bearophile_hugs at eml.cc


--- Comment #0 from bearophile_hugs at eml.cc 2010-10-18 19:08:43 PDT ---
Here are few benchmarks that show that schwartzSort() is much slower than
sort().

(While in Python the usage of the 'key' argumement, analogous to a Schwartz
sort, usually leads to faster code. But Python and D have very different
compilation structure, so comparisons are hazardous at best.)


Timings 2.1 GHz CPU, , DATA_LEN=1_000_000, best of 4, seconds:
  none:      0.3
  sort:      4.1
  sort:      3.4 (alternative)
  schwartz: 17.9


I have no idea why the "alternative" sort is faster than the normal sort, I was
expecting the opposite.

-----------------------------------------

import std.stdio: writeln;
import std.algorithm: schwartzSort, sort;
import std.random: Random, uniform;
import std.typecons: Tuple;

enum SortType { none, sort, schwartz }

enum DATA_LEN = 1_000_000;
enum sort_type = SortType.sort;


alias Tuple!(double, "x", double, "y") P;

void main() {
    auto data = new P[DATA_LEN];
    auto rnd = Random(1);
    foreach (ref el; data) {
        double x = uniform(0.0, 1.0, rnd);
        double y = uniform(0.0, 1.0, rnd);
        el = P(x, y);
    }

    if (data.length < 50) writeln(data);

    static if (sort_type == SortType.schwartz) {
        schwartzSort!((p) { return p.y; })(data);
        schwartzSort!((p) { return p.x; })(data);
        schwartzSort!((p) { return p.y; })(data);
    }

    static if (sort_type == SortType.sort) {
        sort!q{ a.y < b.y }(data);
        sort!q{ a.x < b.x }(data);
        sort!q{ a.y < b.y }(data);
        /*
        // alternative
        sort!((P a, P b) { return a.y < b.y; })(data);
        sort!((P a, P b) { return a.x < b.x; })(data);
        sort!((P a, P b) { return a.y < b.y; })(data);
        */
    }

    if (data.length < 50) writeln(data);
}

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