Performance penalty for using ranges

[bearophile]

Paul Jurczak:

> I wrote a few versions of a palindrome testing function and 
> noticed that versions using ranges 
> (isPalindrome1..isPalindrome3) are 3 times slower than array 
> indexing one (isPalindrome0). Is there a more efficient way of 
> using ranges?

I have modified and improved and fixed your code a little:


import std.stdio, std.datetime, std.array, std.typetuple,
        std.range, std.algorithm;

bool isPalindrome0(T)(in T[] s) pure nothrow {
     size_t i = 0;
     for (; i < s.length / 2 && s[i] == s[$ - i - 1]; ++i) {}
     return i == s.length / 2;
}

bool isPalindrome1(T)(T[] s) pure nothrow {
     while (s.length > 1 && s.front == s.back) {
         s.popBack;
         s.popFront;
     }

     return s.length <= 1;
}

bool isPalindrome2(T)(T[] s) pure nothrow {
     for (;
          s.length > 1 && s.front == s.back;
          s.popBack, s.popFront) {}
     return s.length <= 1;
}

bool isPalindrome3(T)(in T[] s) pure nothrow {
     foreach (immutable i; 0 .. s.length / 2)
         if (s[i] != s[$ - i - 1])
             return false;
     return true;
}

/// A high-level version.
bool isPalindrome4(T)(in T[] s) /*pure nothrow*/ {
     return s.retro.equal(s);
}

int test(alias F)(in int nLoops) /*pure nothrow*/ {
     int[10] a;
     typeof(return) n = 0;

     foreach (immutable _; 0 .. nLoops) {
         a[4] = !a[4];
         n += F(a);
     }

     return n;
}

void main() {
     enum size_t nLoops = 60_000_000;
     StopWatch sw;

     foreach (alg; TypeTuple!(isPalindrome0, isPalindrome1,
                              isPalindrome2, isPalindrome3,
                              isPalindrome4)) {
         sw.reset;
         sw.start;
         immutable n = test!alg(nLoops);
         sw.stop;
         writeln(n, " ", sw.peek.msecs);
     }
}


Using a compiler with a better optimizing back-end (especially 
with a better inlining), the timings show that the faster 
versions are the second and third, but all of them have a very 
similar performance (the last one reads the whole array twice, so 
it's a little slower, as expected):


...>ldmd2 -O -release -inline -noboundscheck -run test2.d
30000000 1150
30000000 1073
30000000 1038
30000000 1215
30000000 1621


Someday a function like isPalindrome4 will be pure & nothrow.

Bye,
bearophile