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
- bearophile (4/9) Dec 19 2014 This is close to tell what the cause is :-)
- ketmar via Digitalmars-d-learn (14/23) Dec 19 2014 On Fri, 19 Dec 2014 12:20:34 +0000
- 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
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?
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
"bearophile" <bearophileHUGS lycos.com> aldanor:On Friday, 19 December 2014 at 10:57:47 UTC, aldanor wrote: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, bearophileSomething 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
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.
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: =20easy 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. ;-)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 :-)
Dec 19 2014
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