A modest proposal: eliminate template code bloat

[Dmitry Olshansky]

On 08.04.2012 18:18, H. S. Teoh wrote:
[snip]
>>
>> 1. Every time a function is generated (or pretty much any symbol)
>> not only a size calculated but also a checksum* of it's data.
>> (If we go for link-time optimization we should find a place to stick
>> it to in the object file)
>
> We'd have to make sure the checksum doesn't end up in the final
> executable though, otherwise the bloat may negate any gains we've made.

Easy the symbol size is in object file (obviously) but it surely not 
present in the executable. If I worth anything legacy formats have a 
plenty of slack space reserved for future. Nwo is the future :)
[snip]
>> 3. After any function was generated compiler checks an entry in the
>> duplicate table that matches size, followed by matching checksum and
>> only then (if required) doing a straight memcmp. If it happens that
>> there is a match compiler just throws generated code away and
>> _aliases_ it's symbol to that of a matched entry.
>> (so there has to be an alias table if there isn't one already)
>
> I think you don't even need an alias table; IIRC the OS dynamic linker
> can easily handle symbols that have the same value (i.e. that point to
> the same place). All you have to do is to change the value of the
> duplicated symbols so that they all point to the same address.
>

Nice to know.
>
> [...]
>> Applicability:
>> It's not only const-immutable bloat, it can be alleviated with
>> inout. Yet there are plenty of places the exact same code is being
>> generated: e.g. sealed containers of int vs uint, std.find on
>> dchar[] vs uint[]/int[] an so on.
>> In general, the coarse grained parametrization is the root of all
>> evil and it is inevitable since we are just humans after all.
>
> I'm not sure I understand the last sentence there, but duplicate code
> elimination is definitely a big plus. It will also mean that we can use
> templates more freely without having to worry about template bloat.
>

It's easy - define a template on type T. Code it up.
Now how many times you did consider that e.g. you can parametrize on the 
size of the type instead of the type itself? I'm making a point that 
it's almost always the case with sealed containers of PODs for instance.
(now multiply the argument for total number of parameters)

>
>> Notes:
>> 1. If we do checksum calculation on the fly during codegen it gets
>> at virtually no cost as the data is in CPU data cache. Preliminary
>> version can avoid hacking this part of backend though.
>>
>> 2. By _alias_ I mean the ability of compiler to emit references to a
>> given symbol as if it was some other symbol (should be really
>> straight forward).
>
> Like I said, I think this isn't even necessary, if the compiler can just
> generate the same value for the duplicated symbols.

OK, I'm not much into how *exactly* linker works these days. I know the 
basics though.


>
>> 4. Ironically the same exact thing works with any kind of immutable
>> data structures. It looks like string pooling is superseded by this
>> proposal.
> [...]
>
> Not really... string pooling can take advantage of overlapping
> (sub)strings, but I don't think you can do that with code. But I think
> your idea has a lot of merit. I'm for making linkers smarter than they
> currently are.
>

Sorry, it's just me running ahead of train somewhat. Basically once this 
initial version is in place I have one cool refinement for it in mind. 
For now we just need to keep the hash function transitive and 
associative for the gods sake. 128/64bit checksum please ;)

-- 
Dmitry Olshansky