A case where the usage of ranges (UFCS chains) leads to very bad performance:


import std.stdio: writeln;
import std.algorithm: map, join;

uint count1, count2;

const(int)[] foo1(in int[] data, in int i, in int max) {
    count1++;

    if (i < max) {
        typeof(return) result;
        foreach (immutable n; data)
            result ~= foo1(data, i + 1, max);
        return result;
    } else {
        return data;
    }
}

const(int)[] foo2(in int[] data, in int i, in int max) {
    count2++;

    if (i < max) {
        return data.map!(n => foo2(data, i + 1, max)).join;
    } else {
        return data;
    }
}

void main() {
    const r1 = foo1([1, 2, 3, 4, 5], 1, 7);
    writeln(count1); // 19531
    const r2 = foo2([1, 2, 3, 4, 5], 1, 7);
    writeln(count2); // 1111111
    assert(r1 == r2); // Results are equally correct.
}


Can you tell why? :-)

Bye,
bearophile

On Friday, 19 December 2014 at 10:41:04 UTC, bearophile wrote:
> A case where the usage of ranges (UFCS chains) leads to very bad performance:
>
>
> import std.stdio: writeln;
> import std.algorithm: map, join;
>
> uint count1, count2;
>
> const(int)[] foo1(in int[] data, in int i, in int max) {
>     count1++;
>
>     if (i < max) {
>         typeof(return) result;
>         foreach (immutable n; data)
>             result ~= foo1(data, i + 1, max);
>         return result;
>     } else {
>         return data;
>     }
> }
>
> const(int)[] foo2(in int[] data, in int i, in int max) {
>     count2++;
>
>     if (i < max) {
>         return data.map!(n => foo2(data, i + 1, max)).join;
>     } else {
>         return data;
>     }
> }
>
> void main() {
>     const r1 = foo1([1, 2, 3, 4, 5], 1, 7);
>     writeln(count1); // 19531
>     const r2 = foo2([1, 2, 3, 4, 5], 1, 7);
>     writeln(count2); // 1111111
>     assert(r1 == r2); // Results are equally correct.
> }
>
>
> Can you tell why? :-)
>
> Bye,
> bearophile
Something about the loop in the first case not depending on n and the compiler being able to figure it is out and only drop into recursion once?

On Friday, 19 December 2014 at 10:57:47 UTC, aldanor wrote:
> Something about the loop in the first case not depending on n and the compiler being able to figure it is out and only drop into recursion once?
That's just a wild guess, but does it get transformed into something like this?

typeof(return) result;
typeof(return) tmp = foo1(data, i + 1, max);
foreach (immutable n; data)
    result ~= tmp;

aldanor:

> On Friday, 19 December 2014 at 10:57:47 UTC, aldanor wrote:
>> Something about the loop in the first case not depending on n and the compiler being able to figure it is out and only drop into recursion once?
> That's just a wild guess, but does it get transformed into something like this?
>
> typeof(return) result;
> typeof(return) tmp = foo1(data, i + 1, max);
> foreach (immutable n; data)
>     result ~= tmp;

That's not the cause. You can see it if you add n to the foo functions, to remove that possible optimization:

foo1(data, n, i + 1, max);

(And the compiler is not allowed to perform that optimization because foos aren't strongly pure).

Bye,
bearophile

On Friday, 19 December 2014 at 10:41:04 UTC, bearophile wrote:
> A case where the usage of ranges (UFCS chains) leads to very bad performance:
>
>
> import std.stdio: writeln;
> import std.algorithm: map, join;
>
> uint count1, count2;
>
> const(int)[] foo1(in int[] data, in int i, in int max) {
>     count1++;
>
>     if (i < max) {
>         typeof(return) result;
>         foreach (immutable n; data)
>             result ~= foo1(data, i + 1, max);
>         return result;
>     } else {
>         return data;
>     }
> }
>
> const(int)[] foo2(in int[] data, in int i, in int max) {
>     count2++;
>
>     if (i < max) {
>         return data.map!(n => foo2(data, i + 1, max)).join;
>     } else {
>         return data;
>     }
> }
>
> void main() {
>     const r1 = foo1([1, 2, 3, 4, 5], 1, 7);
>     writeln(count1); // 19531
>     const r2 = foo2([1, 2, 3, 4, 5], 1, 7);
>     writeln(count2); // 1111111
>     assert(r1 == r2); // Results are equally correct.
> }
>
>
> Can you tell why? :-)
>
> Bye,
> bearophile

Changed to
    return data.map!(n => foo2(data, i + 1, max)).cache.joiner.array;
then it produced the same result as array version. `map.cache.join` resulted in 597871.

On Fri, 19 Dec 2014 10:41:03 +0000
bearophile via Digitalmars-d-learn <digitalmars-d-learn@puremagic.com>
wrote:

> Can you tell why? :-)
'cause lazy ranges can't be optimised in compile time? ;-)

anon:

> Changed to
>     return data.map!(n => foo2(data, i + 1, max)).cache.joiner.array;
> then it produced the same result as array version. `map.cache.join` resulted in 597871.

This is close to tell what the cause is :-)

Bye,
bearophile

On Fri, 19 Dec 2014 12:20:34 +0000
bearophile via Digitalmars-d-learn <digitalmars-d-learn@puremagic.com>
wrote:

> anon:
> 
> > Changed to
> >     return data.map!(n => foo2(data, i + 1,
> > max)).cache.joiner.array;
> > then it produced the same result as array version.
> > `map.cache.join` resulted in 597871.
> 
> This is close to tell what the cause is :-)

easy deal indeed: this is due to how `.save` done in lazy mapped range, plus some range properties.

as source range for mapping is forward range (i.e. indicating that it has `.save`), `.join` assumes that `.save` is cheap and goes by the route where it iterates the range twice: first calculating range length and then generating values for preallocated array. but `.save` is not cheap in our case, so `.join` is effectively calculating EVERYTHING TWICE. oops. and as we have no memoization here, the number of calls is exploding.

thank you for the riddle, it took me some time to see what's going on here. ;-)