Bug 12957 – std.algorithm.cartesianProduct is sometimes very slow to compile
Status
RESOLVED
Resolution
FIXED
Severity
enhancement
Priority
P1
Component
phobos
Product
D
Version
D2
Platform
x86
OS
Windows
Creation time
2014-06-20T11:37:00Z
Last change time
2014-07-10T21:39:01Z
Keywords
pull
Assigned to
nobody
Creator
bearophile_hugs
Comments
Comment #0 by bearophile_hugs — 2014-06-20T11:37:00Z
This program:
void main() {
import std.algorithm: cartesianProduct;
auto r3 = [0, 1, 2];
foreach (x; cartesianProduct(r3, r3, r3, r3, r3, r3)) {}
}
On my PC gets compiled in about 9.4 seconds, using dmd 2.066alpha. In my opinion this is an excessive compilation time.
Comment #1 by hsteoh — 2014-06-26T15:05:49Z
Yeah, we need to rethink the implementation of cartesianProduct; currently, it produces an exponential number of template instantiations with the number of arguments, which is not scalable at all. :-(
Comment #2 by bearophile_hugs — 2014-06-26T17:29:26Z
(In reply to hsteoh from comment #1)
> Yeah, we need to rethink the implementation of cartesianProduct; currently,
> it produces an exponential number of template instantiations with the number
> of arguments, which is not scalable at all. :-(
We have also to change the order of the output, and probably more. So I think it will need to be rewritten.