Bug 10779 – cartesianProduct leads to heavy code bloat
Status
RESOLVED
Resolution
FIXED
Severity
normal
Priority
P2
Component
phobos
Product
D
Version
D2
Platform
All
OS
All
Creation time
2013-08-08T07:53:00Z
Last change time
2014-07-10T21:32:34Z
Keywords
pull
Assigned to
nobody
Creator
tobias
Comments
Comment #0 by tobias — 2013-08-08T07:53:48Z
http://dpaste.dzfl.pl/45240ef6
The program compiled with DMD64 D Compiler v2.063.2 has a size of 37MiB.
It drops to 1,5MiB if you delete the usage of cartesianProduct.
Comment #1 by bearophile_hugs — 2013-08-08T08:13:44Z
(In reply to comment #0)
> http://dpaste.dzfl.pl/45240ef6
>
> The program compiled with DMD64 D Compiler v2.063.2 has a size of 37MiB.
> It drops to 1,5MiB if you delete the usage of cartesianProduct.
The code on dpaste:
import std.conv, std.algorithm, std.range, std.stdio, std.string, std.file, std.csv;
import std.getopt, std.path, std.bitmanip, std.exception;
Parameter[] macParameter;
Parameter[] registerParameter;
Parameter[] immediateParameter;
struct AsmTemplate
{
string template_;
string result;
string arguments;
}
struct Parameter
{
enum Type { Register, Immediate, Mac, None};
Type type;
uint val;
}
struct Test {
string template_;
Parameter[] params;
}
void generateTests(OR)(AsmTemplate ins, ref OR sink)
{
// params is a list of argument ranges with varying length, originally
// optained through a functioncall. We pad it,
// with some empty elements so we can use it in cartProd
auto params = [immediateParameter, registerParameter, macParameter, [], []];
foreach(tup; cartesianProduct(params[0], params[1], params[2], params[3],
params[4]))
{
auto t = Test(ins.template_, [tup[0], tup[1], tup[2], tup[3], tup[4]]);
}
}
void main()
{
auto app = appender!(Test[]);
AsmTemplate asm_;
asm_.generateTests(app);
}
Probably cartesianProduct should be rewritten from scratch, in a lower level way.
Comment #2 by hsteoh — 2013-08-10T09:40:38Z
You are right, cartesianProduct uses a lot of templates internally. It's worse with cartesianProduct of >2 arguments, it uses an exponential number of templates. I'll have to rewrite it from scratch to not use existing range templates. :-( So much for dogfooding...
Comment #3 by hsteoh — 2013-08-10T13:30:04Z
Related: #10693
Comment #4 by hsteoh — 2013-08-10T13:30:42Z
Sigh, let's see if we can get the link: issue #10693