Need a Faster Compressor

[Guillaume Boucher via Digitalmars-d]

On Monday, 23 May 2016 at 20:34:19 UTC, Walter Bright wrote:
> On 5/23/2016 12:32 PM, Timon Gehr wrote:
>> 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, not all redundancy is covered.  However, I think all 
non-pathologic blow-ups are avoided.

Let's look at the properties of the Itanium C++ ABI mangling:

1. Guaranteed linear size name for recursive types that have 
exponential size names.
2. Compression speed can be linear to the size of the compressed 
name (i.e. no need to create an exponential garbage name just to 
compress it).
3. Decompression easy, possible without tools and speed linear to 
size of the compressed name.
4. Name retains some redundancy (in itself and when compared to 
other mangled names), well suited for a follow-up compression.

Compare this to apply some arbitrary compression algorithm to a 
name of exponential size:

1. Exponential size names remain exponential size.  Yes, up until 
the view size, some compression algorithms guarantee that, but 
they can not guarantee it in the general case.
2. Compression needs the whole name first.
3. Decompression only possible with tools.
4. Multiple mangled names can not be compressed well.