## digitalmars.D.learn - Loops versus ranges

• bearophile (34/34) Dec 19 2014 A case where the usage of ranges (UFCS chains) leads to very bad
• aldanor (4/38) Dec 19 2014 Something about the loop in the first case not depending on n and
• aldanor (7/10) Dec 19 2014 That's just a wild guess, but does it get transformed into
• bearophile (8/18) Dec 19 2014 That's not the cause. You can see it if you add n to the foo
• anon (6/40) Dec 19 2014 Changed to
• ketmar via Digitalmars-d-learn (4/5) Dec 19 2014 On Fri, 19 Dec 2014 10:41:03 +0000
```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
```
Dec 19 2014
```On Friday, 19 December 2014 at 10:41:04 UTC, bearophile wrote:
A case where the usage of ranges (UFCS chains) leads to very

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?
```
Dec 19 2014
```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;
```
Dec 19 2014
```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
```
Dec 19 2014
```On Friday, 19 December 2014 at 10:41:04 UTC, bearophile wrote:
A case where the usage of ranges (UFCS chains) leads to very

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.
```
Dec 19 2014
```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
```
Dec 19 2014
```On Fri, 19 Dec 2014 12:20:34 +0000
bearophile via Digitalmars-d-learn <digitalmars-d-learn puremagic.com>
wrote:

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

=20
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. ;-)
```
Dec 19 2014    ketmar via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> writes:
```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? ;-)
```
Dec 19 2014