ranges

[bearophile]

Ellery Newcomer:

> I'm muddling over the following code, which compares an array/take 
> composition with the analogous imperative code. For medium-large values 
> of n, I'm seeing a fivefold degradation in performance, which blows up 
> to 30 times worse at n=50000000.

Some of the code written by Andrei can be bad. I have modified your code like this:

import std.range: front, popFront, array, take;
import std.date: getUTCtime;
import std.random: rndGen;
import std.stdio: writeln;

void main() {
    for (int n = 500; n <= 500_000_000; n *= 10) {
        writeln(n, ":");
        auto rnd = rndGen();

        auto t0 = getUTCtime();
        auto rnd_arr1 = new int[n];
        foreach (ref el; rnd_arr1) {
            el = rnd.front();
            rnd.popFront();
        }

        auto t1 = getUTCtime();
        auto rnd_arr2 = new int[n];
        int i;
        foreach (r; take(rnd, n))
            rnd_arr2[i++] = r;

        auto t2 = getUTCtime();
        auto rnd_arr3 = array(take(rnd, n));

        auto t3 = getUTCtime();

        writeln("  arr:   ", t1 - t0);
        writeln("  take:  ", t2 - t1);
        writeln("  range: ", t3 - t2);
    }
}


It shows that most of the time is spent by array().
After some experiments I have found that the Appender() is very slow. But the direct cause of this problem, beside the slowness of Appender() is that the hasLength is buggy and doesn't find the length of the take, using the Appender.

If you replace the hasLenght with the equivalent from my dlibs1:

template hasLength(R) {
    enum bool hasLength = is(typeof(R.length)) || is(typeof(R.init.length))
                          && !isNarrowString!R;
}

The problem essentially vanishes. The root of the problem is that Phobos has not enough unittests and it not battle-tested yet.
I will probably write a bug report.

Bye,
bearophile