Need a Faster Compressor

[Timon Gehr via Digitalmars-d]

On 24.05.2016 01:02, Walter Bright wrote:
> On 5/23/2016 2:17 PM, Timon Gehr wrote:
>> 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.
>
> How is that essentially different from running a compression pass?

Speed. The title of this thread is "Need a faster compressor".

> The
> only real problem with the compressor was the compression speed, and the
> LZ4 test shows this is solvable.
> ...

No. Just increase the recursion depth by a small number of levels to 
completely kill the speedups gained by using a faster compression algorithm.

>
>  > (That's similar to how the compiler stores the structure in memory,
> which
>> also avoids the exponential blowup.)
>
> No, it doesn't.
> ...

Yes, it does. The compiler does not use exponential space to store the AST.

>
>> You can't have exponential growth before compression.
>
> The compiler is designed so that the internal names are pretty much
> write-only, uniquely hashed by their address. It's not spending time
> running strlen()'s on them.
> ...

It's _exponential_ growth. We don't even want to spend the time and 
memory required to generate the strings.

>
>> Any scheme that does not prevent running time exponential in template
>> instantiation depth is also
>> inadequate in the long run.
>
> Most algorithms seem to have pathological worst cases, but as long as
> they are rare, it doesn't impede their utility.
>

The reason we have this discussion is that the worst case isn't rare 
enough to make this argument. Why compress in the first place if mangled 
names don't grow large in practice?