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

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

(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:
------- You are receiving this mail because: -------

Reply via email to