[Issue 15831] IFTI voldemort type exploding bloat

https://issues.dlang.org/show_bug.cgi?id=15831 sigod <sigod.mail@gmail.com> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |sigod.mail@gmail.com --

March 25, 2016

Posted by Anon

Permalink

Anon

Permalink

https://issues.dlang.org/show_bug.cgi?id=15831

--- Comment #1 from Anon <3g5o3v+4kzxpixqyfgsicckylm60badawevzw9upy4e1qrrcmdizcxk734n07il@spam4.me> ---
As I posted on the newsgroup, I would suggest the following changes to the mangling:

1) `LName`s of length 0 (which currently cannot exist) mean to repeat the
previous `LName` of the current symbol.

2) N `Number` is added as a valid `Type`, meaning "Type Back Reference". Basically, all instances of a struct/class/interface/enum type in a symbol's mangling get counted (starting from zero), and subsequent instances of that type can be referred to by N0, N1, N2, etc.

Given:

```
module mod;
struct Foo;
Foo* func(Foo* a, Foo* b);
```

`func` currently mangles as: _D3mod4funcFPS3mod3FooPS3mod3FooZPS3mod3Foo

It would instead mangle as:
_D3mod4funcFPS3mod3FooPN0ZPN0

Nested template declarations would get numbered depth first as follows:

S7!(S2!(S0, S1), S6!(S3, S5!(S4)))

This, on its own, won't eliminate the recursive expansion bloat, but (based on manual experiments I've now done), takes foo's mangled name length almost linear with respect to the number of recursions:

Recursive calls to s() before x.foo :  1 |  2 |   3 |   4 |   5
Current mangle length of foo (bytes): 39 | 90 | 192 | 397 | 807
Same, with proposed mangling changes: 38 | 64 |  90 | 116 | 148

As I said on the newsgroup, I have another idea relating to template string value mangling, but that is only tangentially related to this bug (in that both reducing mangle bloat). I'll post that separately once it is ready.

--

https://issues.dlang.org/show_bug.cgi?id=15831 ZombineDev <petar.p.kirov@gmail.com> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |petar.p.kirov@gmail.com --

https://issues.dlang.org/show_bug.cgi?id=15831 Jonathan M Davis <issues.dlang@jmdavisProg.com> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |issues.dlang@jmdavisProg.co | |m --

https://issues.dlang.org/show_bug.cgi?id=15831 Johan Engelen <jbc.engelen@gmail.com> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |jbc.engelen@gmail.com --- Comment #2 from Johan Engelen <jbc.engelen@gmail.com> --- Hi Anon, I've started implementing your idea. But perhaps you already have a beginning of an implementation? If so, please contact me :) Thanks, Johan --

https://issues.dlang.org/show_bug.cgi?id=15831 Ivan Kazmenko <gassa@mail.ru> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |gassa@mail.ru --

https://issues.dlang.org/show_bug.cgi?id=15831 greensunny12@gmail.com changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |greensunny12@gmail.com --

https://issues.dlang.org/show_bug.cgi?id=15831 Steven Schveighoffer <schveiguy@yahoo.com> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |georgid@outlook.com --- Comment #3 from Steven Schveighoffer <schveiguy@yahoo.com> --- *** Issue 16039 has been marked as a duplicate of this issue. *** --

https://issues.dlang.org/show_bug.cgi?id=15831 Rainer Schuetze <r.sagitario@gmx.de> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |r.sagitario@gmx.de --- Comment #4 from Rainer Schuetze <r.sagitario@gmx.de> --- I tried to untangle the name of the 1.s.s.s.s.s case. Replacing testexpansion with E, I get E.s!(E.s!(E.s!(E.s!(E.s!(int).s(int).Result) .s (E.s!(int).s(int).Result) .Result) .s (E.s!(E.s!(int).s(int).Result) .s (E.s!(int).s(int).Result) .Result) .Result) .s (E.s!(E.s!(E.s!(int).s(int).Result) .s (E.s!(int).s(int).Result) .Result) .s (E.s!(E.s!(int).s(int).Result) .s (E.s!(int).s(int).Result) .Result) .Result) .Result) .s (E.s!(E.s!(E.s!(E.s!(int).s(int).Result) .s (E.s!(int).s(int).Result) .Result) .s (E.s!(E.s!(int).s(int).Result) .s (E.s!(int).s(int).Result) .Result) .Result) .s (E.s!(E.s!(E.s!(int).s(int).Result) .s (E.s!(int).s(int).Result) .Result) .s (E.s!(E.s!(int).s(int).Result) .s (E.s!(int).s(int).Result) .Result) .Result) .Result) .Result.foo() Each step has a mangling of "E.s!(T).s(T).Result" with T being the template argument. The length explosion comes from the type being listed twice. This is not caused by the Voldemort return type, but the eponymous template that is created by the function template. --

https://issues.dlang.org/show_bug.cgi?id=15831 Walter Bright <bugzilla@digitalmars.com> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |bugzilla@digitalmars.com --- Comment #5 from Walter Bright <bugzilla@digitalmars.com> --- The compressor does a good job with this: _D3foo8__T1sTiZ1sFNaNbNiNfiZS3foo8__T1sTiZ1sFiZ6Result _D3foo33__T1sTS€„8€†ŒiZáFá6Result€„NaNbNiNf€›¦€…›€¦Î€›žþ _D3foo84__T1sTS€„33€‹8€†ŒiZáFá6Result€„€›ž€‹¦NaNbNiNf€ÎÙ€†£Ø´€ÎÑþ _D3foo186__T1sTS€„Ž84€‹33€Œš€†ŒiZáFá6Result€„€›ž€¦€ÉÑ€‹®NaNbNiNf‰´¿€…«‹À‰´·þ _D3foo391__T1sTS€„Ž186€‹Ž84€‹33€Œš€†ŒiZáFá6Result€„€›ž€¦€ÉÑ€‘®‰®·€‹¶NaNbNiNf›Œ€†ÞžŒ››„þ Note how the identifier length increases: 8 => 33 => 84 => 186 => 391 but the compressed version doesn't grow nearly so fast. LZW compression is really good at removing redundancy. --

Forums