dcollections 1.0 and 2.0a beta released

[Andrei Alexandrescu]

On 05/20/2010 09:41 AM, Michel Fortin wrote:
> On 2010-05-20 08:30:59 -0400, bearophile <bearophileHUGS at lycos.com> said:
>
>> Michel Fortin:
>>
>>> Surely going through all those virtual calls slows things down a lot.<
>>
>> Right. But the purpose of a good compiler is to kill those,
>> devirtualizing. LLVM devs are working on this too. See:
>> http://llvm.org/bugs/show_bug.cgi?id=6054
>> http://llvm.org/bugs/show_bug.cgi?id=3100
>
> Devirtualization is only possible in certain cases: when the function
> knows exactly which type it'll get. But downcasting to a more generic
> type and passing it around function calls strips it of this precise
> information required for devirtualization.

(I assume you meant upcasting.) Even then, it's possible to accelerate 
calls by doing method casing, type casing, class hierarchy analysis...

> The only way to propagate the
> exact type is to either instanciate a new version of the function you
> call for that specific type (which is what a template does) or inline it
> (because it also creates a new instance of the function, inline inside
> the caller).
>
> For instance:
>
> void test1(List list) {
> list.clear(); // can't devirtualize since we do now know which kind of
> list we'll get
> }
>
> void test2() {
> List list = new ArrayList;
> list.clear(); // now the compiler can see we'll always have an
> ArrayList, can devritualize
> }
>
> void test3(L)(L list) {
> list.clear(); // parent's type is propagated, can devirtualize if parent
> can.
> }
>
>
>> Steven Schveighoffer:
>>
>>> The problem with using generic code is that the compiler will
>>> needlessly duplicate functions that are identical.<
>>
>> See the -mergefunc compiler switch of LDC, to merge identical
>> functions (like ones produced by template instantiations). This
>> feature is not very powerful yet, but it's present and I have seen it
>> works.
>
> Indeed. I'm no expert in linkers, but in my opinion this is one of the
> most basic optimizations a linker should perform. And C++ has pushed
> linkers to do that for years now so I'd expect most linkers to do that
> already...
>
> The problem with templates are more the multiple slightly different
> instanciations. In general this is good for performance, but it's only
> needed for the code paths that need to be fast. I think generic
> containers should be fast.

There's been talk that Walter's slow porting of the linker to C and then 
D will put him in the position to introduce such an optimization.


Andrei