Re: 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