## 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
"bearophile" <bearophileHUGS lycos.com> writes:
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
"aldanor" <i.s.smirnov gmail.com> writes:
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
"aldanor" <i.s.smirnov gmail.com> writes:
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
"bearophile" <bearophileHUGS lycos.com> writes:
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
"anon" <anonymous mail.invalid> writes:
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
"bearophile" <bearophileHUGS lycos.com> writes:
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
ketmar via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> writes:
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