Combsort comparison

[Lutger]

> // D #3 version
> 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;
>         int gap = walkLength(data);
>         bool swapped = true;
> 
>         while (gap > 1 || swapped) {
>             if (gap > 1)
>                 gap /= SHRINK_FACTOR;
> 
>             swapped = false;
>             auto right = data;
>             popFrontN(right, gap);
> 
>             for (auto left = data; !right.empty; left.popFront,
>             right.popFront) {
>                 if (binaryFun!less(right.front, left.front)) {
>                     swap(left.front, right.front);
>                     swapped = true;
>                 }
>             }
>         }
>     }

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;
    }
}

Quite surprising. i don't understand asm well enough to analyse this further.