[Issue 15831] New: IFTI voldemort type exploding bloat
via Digitalmars-d-bugs
digitalmars-d-bugs at puremagic.com
Fri Mar 25 11:18:25 PDT 2016
https://issues.dlang.org/show_bug.cgi?id=15831
Issue ID: 15831
Summary: IFTI voldemort type exploding bloat
Product: D
Version: D2
Hardware: All
OS: All
Status: NEW
Severity: enhancement
Priority: P1
Component: dmd
Assignee: nobody at puremagic.com
Reporter: schveiguy at yahoo.com
The current name mangling rules for template expansion lead to excessive bloat
when voldemort types are returned and used in subsequent chained calls.
This pattern is used in some places in Phobos for instance to allow wrapped
ranges. An example is std.range.chain.
If this pattern is used recursively, the resulting template mangling expands at
an exponential rate, because the template parameter is used multiple times in
the expansion (once for the type name for the template, and once for the type
name of the parameter). Because the return type depends on the function name
mangling, the cycle continues as you expand the chain.
A simple example:
(Please read through the whole bug report, as I have comments in between a lot
of output)
struct S(T)
{
void foo(){ throw new Exception("1");}
}
auto s(T)(T t)
{
version(bad)
{
struct Result
{
void foo(){ throw new Exception("2");}
}
return Result();
}
else
return S!T();
}
void main(string[] args)
{
auto x = 1.s.s.s.s.s;
x.foo;
}
If I compile this without -version=bad, I get this:
Stevens-MacBook-Pro:testd steves$ time dmd testexpansion.d
real 0m0.058s
user 0m0.040s
sys 0m0.014s
Stevens-MacBook-Pro:testd steves$ ls -l testexpansion*
-rwxr-xr-x+ 1 steves staff 409948 Mar 25 11:59 testexpansion
-rw-r--r--+ 1 steves staff 324 Mar 25 11:59 testexpansion.d
-rw-r--r--+ 1 steves staff 7104 Mar 25 11:59 testexpansion.o
Stevens-MacBook-Pro:testd steves$ ./testexpansion
object.Exception at testexpansion.d(3): 1
----------------
4 testexpansion 0x00000001050edc14 pure @safe void
testexpansion.S!(testexpansion.S!(testexpansion.S!(testexpansion.S!(testexpansion.S!(int).S).S).S).S).S.foo()
+ 144
5 testexpansion 0x00000001050ed837 _Dmain + 119
6 ... # etc.
Now, let's compile with the -bad version:
Stevens-MacBook-Pro:testd steves$ time dmd -version=bad testexpansion.d
real 0m0.058s
user 0m0.041s
sys 0m0.014s
Stevens-MacBook-Pro:testd steves$ ls -l testexpansion*
-rwxr-xr-x+ 1 steves staff 429412 Mar 25 12:00 testexpansion
-rw-r--r--+ 1 steves staff 324 Mar 25 11:59 testexpansion.d
-rw-r--r--+ 1 steves staff 15312 Mar 25 12:00 testexpansion.o
Stevens-MacBook-Pro:testd steves$ ./testexpansion
object.Exception at testexpansion.d(12): 2
----------------
4 testexpansion 0x000000010f639c0c pure @safe void
testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).Result).Result.foo()
+ 144
5 testexpansion 0x000000010f639807 _Dmain + 119
6 ... # etc.
Note the extreme increase in object size. Also note the much larger symbol name
when the exception is thrown.
Let's expand the number of s calls to 10:
auto x = 1.s.s.s.s.s.s.s.s.s.s;
New results:
Stevens-MacBook-Pro:testd steves$ time dmd testexpansion.d
real 0m0.074s
user 0m0.043s
sys 0m0.018s
Stevens-MacBook-Pro:testd steves$ ls -l testexpansion*
-rwxr-xr-x+ 1 steves staff 431716 Mar 25 14:01 testexpansion
-rw-r--r--+ 1 steves staff 334 Mar 25 14:01 testexpansion.d
-rw-r--r--+ 1 steves staff 16528 Mar 25 14:01 testexpansion.o
OK, so the size of the object doubled for doubling the number of calls/types.
Not unexpected.
Stevens-MacBook-Pro:testd steves$ ./testexpansion
object.Exception at testexpansion.d(3): 1
----------------
4 testexpansion 0x0000000104816bec pure @safe void
testexpansion.S!(testexpansion.S!(testexpansion.S!(testexpansion.S!(testexpansion.S!(testexpansion.S!(testexpansion.S!(testexpansion.S!(testexpansion.S!(testexpansion.S!(int).S).S).S).S).S).S).S).S).S).S.foo()
+ 144
5 testexpansion 0x00000001048164c6 _Dmain + 214
6 ... # etc.
A reasonable expanding of the symbol name.
Let's try the bad version:
Stevens-MacBook-Pro:testd steves$ time dmd -version=bad testexpansion.d
real 0m0.164s
user 0m0.145s
sys 0m0.016s
Comparing to original compilation time of testexpansion with bad version
(0.058s), this is a significant slowdown. My tests show me that the major
slowdown is calling the linker.
Stevens-MacBook-Pro:testd steves$ ls -l testexpansion*
-rwxr-xr-x+ 1 steves staff 1308740 Mar 25 14:01 testexpansion
-rw-r--r--+ 1 steves staff 334 Mar 25 14:01 testexpansion.d
-rw-r--r--+ 1 steves staff 382168 Mar 25 14:01 testexpansion.o
Here the object has drastically blown up from 15k to 382k.
I'm timing the execution, because this is significant as well:
Stevens-MacBook-Pro:testd steves$ time ./testexpansion
object.Exception at testexpansion.d(12): 2
----------------
4 testexpansion 0x0000000109b83bec pure @safe void
testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).Result).s(testexpansion.s!(testexpansion.s!(testexpansion.s!(int).s(int).Result).s(testexpansion.s!(int).s(int).Result).Result).s(testexpansion.s!(testexpansion.s!(int).s(i
5 testexpansion 0x0000000109b83476 _Dmain + 214
6 ... # etc.
real 0m2.801s
user 0m2.790s
sys 0m0.004s
That's right, it takes 2.8 seconds to decide to print not quite the entire
symbol name, before giving up. So this affects runtime issues as well.
I tried adding 5 more calls to .s, and the object file climbed to 12MB, along
with the compilation taking at least 1.5 minutes before I killed it.
This is not a real-world example, but I have encountered real world examples
with my iopipe library. Originally I made all the wrapping types voldemort
types. Compiling a test program was at about 10MB and showed similar slowdowns
when an exception was thrown. Moving the voldemort types outside the functions
reduced the size to <1MB, and fixed the exception problems.
I think if Phobos used more voldemort types and less external structs (there
actually aren't that many voldemort ones as early range/algorithm code didn't
have the luxury), I think we would have run into this sooner.
We need some way to elide all the repeated type names, either via compression
or substitution, or something. If we can factor out the multiplier for the
symbol mangling, we can fix the problem.
--
More information about the Digitalmars-d-bugs
mailing list