On Thursday, 31 March 2016 at 20:12:34 UTC, Anon wrote:
> Having thought about it a bit more, I am now of the opinion that super-long strings have no business being in template args, so we shouldn't cater to them.

meh, if it is allowed, it is going to happen. Why make it worse when there's so little cost in making it better?

> The main case with longer strings going into template arguments I'm aware of is for when strings will be processed, then fed to `mixin()`.

I often don't actually modify the string at all and by putting the string as a template argument, it enables a kind of compile-time memoization like I talked about here a short while ago: http://stackoverflow.com/a/36251271/1457000

The string may be exceedingly if imported from a file or generated externally and cached:

MyType!(import("definition.txt")) foo;

enum foo = ctfeFunction();

MyType!foo test;


I've never had a huge problem with this in practice, but I've never had a huge problem with big names in practice at all either. I can imagine both though.

(what bothers me more than the mangle actually is the compiler error messages showing all those strings. Gross. I'd like to see XML error messages to make displaying them easier. But that's a separate topic.)

> The original mangling discussion started from the need to either fix a mangling problem or officially discourage Voldemort types.


Yes, indeed, that's probably the bigger problem.

> * Retains current ability to access D symbols from C (in contrast to ideas that would use characters like '$' or '?')

$ is actually a valid identifier character in C (and quite a few other languages). You can use it in the linker as well as in C source code.

On Thursday, 31 March 2016 at 20:40:03 UTC, Adam D. Ruppe wrote:
> meh, if it is allowed, it is going to happen. Why make it worse when there's so little cost in making it better?

Define "little cost". Whatever compression algorithm chosen will need support added to any/all tools that want to demangle D. GDB and LLDB currently link to liblzma (on my system, at least. Configurations may vary). nm and objdump don't link to any compression lib. Good luck convincing binutils to add compression dependencies like that for D when they don't need them any other mangling schemes.

And no, ddemangle isn't a solution here, as then all those projects would need to be able to refer to it, and the best way for them to do that is to bundle it. Since ddemangle is written in D, that would mean binutils would suddenly depend on having a working D compiler. That won't happen in the next decade.

Also, any D code that uses core.demangle for any reason would suddenly depend on that compression library.

I'm not even fully convinced that my bootstring idea is low enough cost, and it's fairly simple, fast, and memory efficient compared to any compression algorithm.

> I often don't actually modify the string at all and by putting the string as a template argument, it enables a kind of compile-time memoization like I talked about here a short while ago: http://stackoverflow.com/a/36251271/1457000
>
> The string may be exceedingly if imported from a file or generated externally and cached:
>
> MyType!(import("definition.txt")) foo;
>
> enum foo = ctfeFunction();
>
> MyType!foo test;

Just assigning to an enum gets you memoization (tested on LDC w/ DFE 2.68.2).
I don't see how the template factors into this.

Now, yes, if you call the function directly multiple times assigning to different enums, it won't memoize those. And it doesn't work lazily how the SO question asked for, but this does:

enum lazily(string name: "foo") = ctfeFunction();

If you don't refer to lazily!"foo", ctfeFunction() never gets called. If you do, it gets called once, regardless of how many times you use lazily!"foo".

That gives you lazy memoization of any CTFEable function without ever needing the function parameters to become template parameters.

I'm not sure what MyType is, but that looks like a prime candidate for my previous post's mixin examples. If not, you could use "definition.txt" as its parameter, and have it import() as an implementation detail.

> $ is actually a valid identifier character in C

Nope. $ as an identifier character is a commonly supported extension, but code that uses it doesn't compile with `clang -std=c11 -Werror -pedantic`.

On Thursday, March 31, 2016 09:10:49 Steven Schveighoffer via Digitalmars-d wrote:
> On 3/30/16 3:19 PM, Liran Zvibel wrote:
> > On Sunday, 27 March 2016 at 17:01:39 UTC, David Nadlinger wrote:
> >> Compression in the usual sense won't help. Sure, it might reduce the object file size, but the full string will again have to be generated first, still requiring absurd amounts time and space. The latter is definitely not negligible for symbol names of several hundreds of kilobytes; it shows up prominently in compiler profiles of affected Weka builds.
> >
> > We love Voldemort types at Weka, and use them a lot in our
> > non-gc-allocating ranges and algorithm libraries. Also, we liberally
> > nest templates inside of other templates.
> > I don't think we can do many of the things we do if we had to define
> > everything at module level. This flexibility is amazing for us and part
> > of the reason we love D.
>
> Voldemort types are what cause the bloat, templates inside templates aren't as much of a problem. It's because the Voldemort type has to include in its symbol name at least twice, and I think 3 times actually (given the return type), the template parameter/function parameter types of the function it resides in. If the template is just a template, it's just included once. This is why moving the type outside the function is effective at mitigation. It's linear growth vs. exponential.

This makes me wonder if there would be a sane way to basically treat the Voldemort type as if it were outside the function it was declared from a mangling standpoint while still treating its accessibility the same way. Maybe that wouldn't work due to potential name clashes, but if the problem is purely because the type is declared inside the function, I would think that it would make sense to try and find a way to treat it more like it was declared outside the function when dealing with the name mangling. Then - in theory - you'd get the benefits of using a Voldemort type while getting the name mangling cost that you get when you declare a private type outside of the function.

- Jonathan M Davis

On Friday, 25 March 2016 at 19:04:46 UTC, Anon wrote:
>
> Two 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.

I have implemented the second part (simplest I thought) to see what it would bring (in LDC). 'Q' seems unused, so I used that instead of 'N'  ;)
I'm not 100% certain of the implementation, as it relies on DMD using the same pointer values for recurring types but it seemed to work with complicated code.
The core.demangle demangler was relatively easy to upgrade for repeated types.

Unfortunately, and perhaps expectedly, it did not give a large size reduction / speed boost. Not very statistically sound results though ;)
The change is relatively easy, I think, so perhaps it is still worthwhile pursuing.

An implementation issue that changes in mangling have to deal with:
One surprising thing was that std.traits uses the mangled name in `ParameterStorageClassTuple`. So std.traits contains its own mini mangling parser, and also calls .mangleof on Types, to skip to the next function argument in the mangled function string. The "type back reference" scheme means that Type.mangleof may not correspond to how the Type embedded in the mangling of a function, and so I had to upgrade std.traits with its own parser (I copied core.demangle.Demangle, and removed all output complications).

For changes in mangling, it'd be good if std.traits.ParameterStorageClassTuple could be rewritten to not use the mangled function name + string processing.

On Friday, 1 April 2016 at 11:00:29 UTC, Johan Engelen wrote:
>
> Unfortunately, and perhaps expectedly, it did not give a large size reduction / speed boost. Not very statistically sound results though ;)

The times I measured are not including linking (!). But I think the small difference in file size does not predict much improved link times.

Meanwhile, I've implemented hashing of function names and other symbols *for the backend*, giving an object file size reduction of ~25% (hashing everything larger than 100 chars) for my current testcase (251MB -> 189MB).
Hashing symbols in the FE is not possible with my testcase because of std.traits.ParameterStorageClassTuple... :/

> For changes in mangling, it'd be good if std.traits.ParameterStorageClassTuple could be rewritten to not use the mangled function name + string processing.

std.traits.ParameterStorageClassTuple is a major obstacle for aggressive mangling changes. Perhaps someone has the time and skills to rewrite it if possible? (My D-fu is not really up to that task)

I'll try and keep you posted with some more measurements, to get a feel for what matters / what doesn't matter too much.

On Friday, 1 April 2016 at 14:46:42 UTC, Johan Engelen wrote:
>
> Meanwhile, I've implemented hashing of function names and other symbols *for the backend*, giving an object file size reduction of ~25% (hashing everything larger than 100 chars) for my current testcase (251MB -> 189MB).
> Hashing symbols in the FE is not possible with my testcase because of std.traits.ParameterStorageClassTuple... :/

See my PR for LDC:
https://github.com/ldc-developers/ldc/pull/1445

"This adds MD5 hashing of symbol names that are larger than threshold set by -hashthres.

What is very unfortunate is that std.traits depends on the mangled name, doing string parsing of the mangled name of symbols to obtain symbol traits. This means that mangling cannot be changed (dramatically, like hashing) at a high level, and the hashing has to be done on a lower level.

Hashed symbols look like this:
_D3one3two5three3L3433_46a82aac733d8a4b3588d7fa8937aad66Result3fooZ
ddemangle gives:
one.two.three.L34._46a82aac733d8a4b3588d7fa8937aad6.Result.foo
Meaning: this symbol is defined in module one.two.three on line 34. The identifier is foo and is contained in the struct or class Result.

Symbols that may be hashed:
- functions
- struct/class initializer
- vtable
- typeinfo (needed surgery inside FE code)

The feature is experimental, and has been tested on Weka.io's codebase. Compilation with -hashthres=1000 results in a binary that is half the size of the original (201MB vs. 461MB). I did not observe a significant difference in total build times. Hash threshold of 8000 gives 229MB, 800 gives 195MB binary size: there is not much gain after a certain hash threshold.
Linking Weka's code fails with a threshold of 500: phobos contains a few large symbols (one larger than 8kb!) and this PR currently does not disable hashing of symbols that are inside phobos, hence "experimental". Future work could try to figure out whether a symbol is inside phobos or not."

On Tuesday, 19 April 2016 at 14:44:12 UTC, Johan Engelen wrote:
> What is very unfortunate is that std.traits depends on the mangled name, doing string parsing of the mangled name of symbols to obtain symbol traits.

I'm surprised that's how it works. I just assumed there was some __traits call for that.

> Compilation with -hashthres=1000 results in a binary that is half the size of the original (201MB vs. 461MB).

Seems promising!

On 4/19/16 10:44 AM, Johan Engelen wrote:

> The feature is experimental, and has been tested on Weka.io's codebase.
> Compilation with -hashthres=1000 results in a binary that is half the
> size of the original (201MB vs. 461MB). I did not observe a significant
> difference in total build times.

I'd be surprised link times did not improve. With my trivial test cases, the linker started getting hung up with very long symbols. The compilation itself was quick though.

Certainly, cutting exe sizes (this is significantly more than half, BTW) is a good thing in itself.

Another thing, however, is memory usage of the compiler. My understanding is that having large symbol names requires more memory. How does that fare?

-Steve

What about using old string compression algorithms on the mangled name? That should effectively get rid of all the repeated words.

-- 
Marco

On 4/19/16 4:50 PM, Marco Leise wrote:
> What about using old string compression algorithms on the
> mangled name? That should effectively get rid of all the
> repeated words.
>

It's somewhat recursive, so I don't know how well string compression will work. It's possible, definitely. But I think a substitution scheme that is tailored to the issue may prove more effective. Just the fact that removing the struct out of the function itself cleans it up shows that there is a path to make this happen.

-Steve