dcollections 1.0 and 2.0a beta released

[Michel Fortin]

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. 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.

-- 
Michel Fortin
michel.fortin at michelf.com
http://michelf.com/