Need a Faster Compressor

[Timon Gehr via Digitalmars-d]

On 23.05.2016 22:34, Walter Bright wrote:
> On 5/23/2016 12:32 PM, Timon Gehr wrote:
>> Instead, compression should be performed while generating the mangled
>> string.
>
> The trouble with that is the mangled string is formed from component
> pieces.

Then don't do that. I.e. re-mangle recursively from scratch for each 
mangled name and allow sharing parts between unrelated components within 
that mangled name. (That's similar to how the compiler stores the 
structure in memory, which also avoids the exponential blowup.)

> Those component pieces may have common substrings with each
> other, which won't be detected until they are merged,
> when you're back to dealing with the string as a whole.
>
>
>> Isn't it enough to create
>> references to previously embedded mangled symbols (i-th symbol already
>> mangled)
>> while generating the mangled string?
>
> That's been covered upthread, and VC++/g++ do that. But as shown, it is
> inadequate. There's a lot more redundancy than just the identifiers.

Yes, but I think that should be covered (up to constants) by what I 
suggested above?

You can't have exponential growth before compression. Any scheme that 
does not prevent running time exponential in template instantiation 
depth is also inadequate in the long run.