Combsort comparison

[bearophile]

Lutger:
> I get about 30% improvement if the inner loop is rewritten to:
> 
> foreach (i; 0 .. total - gap) // total was already computed by walkLength
> {
>     left.popFront;
>     right.popFront;
>     if (binaryFun!less(right.front, left.front)) {
> 	swap(left.front, right.front);
> 	swapped = true;
>     }
> }

This is a version that works (note the popFront at the end of the loop):


// D #4
import std.array: empty, popFront, popFrontN, front;
import std.range: walkLength, isForwardRange, hasSwappableElements;
import std.algorithm: swap, binaryFun;
import std.c.stdlib: malloc;
import std.c.stdio: printf;
debug {
    import std.contracts: enforce;
    import std.algorithm: sort, equal;
    import std.array: array;
}

void combsort(alias less="a < b", Range)(Range data)
  if (isForwardRange!Range && hasSwappableElements!Range) {

    static void combsort_impl(Range data) {
        enum double SHRINK_FACTOR = 1.247330950103979;
        size_t total = walkLength(data);
        size_t gap = total;
        bool swapped = true;

        while (gap > 1 || swapped) {
            if (gap > 1)
                gap /= SHRINK_FACTOR;

            swapped = false;
            auto left = data;
            auto right = data;
            popFrontN(right, gap);

            foreach (_; 0 .. total - gap) {
                if (binaryFun!less(right.front, left.front)) {
                    swap(left.front, right.front);
                    swapped = true;
                }
                left.popFront;
                right.popFront;
            }
        }
    }

    // postcondition verified in debug mode only.
    // This is a workaround, D postconditions don't
    // support the "old" (original input data view) yet.
    debug {
        auto data_copy = array(data);
        sort!(less)(data_copy);
        combsort_impl(data);
        enforce(equal(data, data_copy));
    } else {
        combsort_impl(data);
    }
}

int myrandom() {
    enum uint IM = 139968;
    enum uint IA = 3877;
    enum uint IC = 29573;
    static uint last = 42;
    last = (last * IA + IC) % IM;
    return last;
}

debug {
    bool issorted(int[] items) {
        if (items.length < 2)
            return true;

        foreach (i, el; items[0 .. $-1])
            if (el > items[i+1])
                return false;
        return true;
    }
}

void main() {
    enum int N = 10_000_000;
    int* v = cast(int*)malloc(int.sizeof * N);
    int i;
    for (i = 0; i < N; i++)
        v[i] = myrandom();

    debug {
        for (i = 0; i < N; i++)
            printf("%d ", v[i]);
        printf("\n");
    }

    combsort(v[0 .. N]);

    debug {
        for (i = 0; i < N; i++)
            printf("%d ", v[i]);
        printf("\n");
    }

    printf("%d\n", v[N-1]);

    debug {
        if (!issorted(v[0 .. N]))
            printf("NOT sorted\n");
    }
}

In all the programs I now use a size_t to keep the result of walkLenth and gap.
My timings don't show a 30% improvement:

Timings, seconds, best of 3:
  D3:  5.94
  D4:  5.86
  D2:  3.13
  C++: 3.05
  D1:  2.90
  C:   2.72

Bye,
bearophile