Michel Fortin Wrote:

> On 2010-05-20 06:34:42 -0400, Steven Schveighoffer <schveiguy@yahoo.com> said:
> 
> > I understand these points, but I'm already using interfaces to copy data between containers.  I don't have to, I could have used generic code, but this way, only one function is instantiated to copy data from all the other containers.  The problem with using generic code is that the compiler will needlessly duplicate functions that are identical.
> 
> One question. Have you calculated the speed difference between using an interface and using generic code? Surely going through all those virtual calls slows things down a lot.
> 
> I do like interfaces in principle, but I fear it'll make things much slower when people implement things in term of interfaces. That's why I'm not sure it's a good idea to offer container interfaces in the standard library.

It's not that much slower.  You get a much higher speedup when things can be inlined than virtual vs. non-virtual.

However, I should probably make all the functions in the concrete implementations final.  I made several of them final, but I should do it across the board.

One thing I just thought of -- in dcollections, similar types can be compared to one another.  For example, you can check to see if a HashSet is equal to a TreeSet.  But that would not be possible without interfaces.

-Steve

On 05/20/2010 03:22 PM, Steven Schveighoffer wrote:
> One thing I just thought of -- in dcollections, similar types can be compared to one another.  For example, you can check to see if a HashSet is equal to a TreeSet.  But that would not be possible without interfaces.
>
> -Steve

I'm sorry, but I think that's a misfeature. In my opinion, a tree is not equal to a hash table, ever.

You could compare the content separately, but that wouldn't require interfaces.

On 2010-05-20 08:30:59 -0400, bearophile <bearophileHUGS@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@michelf.com
http://michelf.com/

On 2010-05-20 09:22:27 -0400, Steven Schveighoffer <schveiguy@yahoo.com> said:

> Michel Fortin Wrote:
> 
>> On 2010-05-20 06:34:42 -0400, Steven Schveighoffer <schveiguy@yahoo.com> said:
>> 
>>> I understand these points, but I'm already using interfaces to copy
>>> data between containers.  I don't have to, I could have used generic
>>> code, but this way, only one function is instantiated to copy data from
>>> all the other containers.  The problem with using generic code is that
>>> the compiler will needlessly duplicate functions that are identical.
>> 
>> One question. Have you calculated the speed difference between using an
>> interface and using generic code? Surely going through all those
>> virtual calls slows things down a lot.
>> 
>> I do like interfaces in principle, but I fear it'll make things much
>> slower when people implement things in term of interfaces. That's why
>> I'm not sure it's a good idea to offer container interfaces in the
>> standard library.
> 
> It's not that much slower.  You get a much higher speedup when things can be inlined than virtual vs. non-virtual.

Yes, but that was part of the equation: a call to a template function can be inlined, not a virtual call (most of the time).

> However, I should probably make all the functions in the concrete implementations final.  I made several of them final, but I should do it across the board.

Yeah, probably.

> One thing I just thought of -- in dcollections, similar types can be compared to one another.  For example, you can check to see if a HashSet is equal to a TreeSet.  But that would not be possible without interfaces.

I'm not sure of what you're saying here. Are you saying it can be done with an interface but not with a template type? Why can't this work:

	class TreeSet {
		bool opEquals(T)(T t) if (IsSet!T) {
			if (t.length != this.length)
				return false;
			foreach (element; this) {
				if (!t.has(element))
					return false;
			}
			return true;
		}
	}

	TreeSet a = new TreeSet;
	HashSet b = new HashSet;
	assert(a == b);

(sorry, I still have to start using the new operator overloading syntax.)

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

Steven Schveighoffer:

>You get a much higher speedup when things can be inlined than virtual vs. non-virtual.<

In current D compilers virtual functions prevent inlining. This can give some performance loss.

Bye,
bearophile

On Thu, 20 May 2010 06:34:42 -0400, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
> Robert Jacques Wrote:
>
>> On Wed, 19 May 2010 21:42:35 -0400, Steven Schveighoffer
>> >
>> > Does that make sense?
>> >
>> > -Steve
>>
>> Yes and No. I understand where your coming from, but I think it's a bad
>> idea. First, I think it needlessly expands the radius of comprehension
>> needed to understand and use the library. (See Tangled up in tools
>> http://www.pragprog.com/magazines/2010-04/tangled-up-in-tools) Second, I
>> think designing a library to be flexible enough to meet some future,
>> anticipated need (e.g. dlls) is a good idea, but actually implementing
>> vaporous future needs is fraught with peril; it's too easy to guess wrong.
>> Third, interface base design is viral; If library X uses interfaces then I
>> have to use interfaces to interface with it. And if another library Y uses
>> classes, then I'm going have to write a (needless) wrapper around one of
>> them.
>
> I understand these points, but I'm already using interfaces to copy data between containers.  I don't have to, I could have used generic code, but this way, only one function is instantiated to copy data from all the other containers.  The problem with using generic code is that the compiler will needlessly duplicate functions that are identical.

This sounds like a failure of design. Why aren't you using ranges to do this?

> Using interfaces is not as viral as you think.  My interfaces can be used in generic code, as long as the generic code uses functions in the interfaces.  If a library returns an interface, the author is saying "I don't want you using any functions outside this interface," so why is that a bad thing?

Well, needlessly duplicated functions for one. :) More importantly, the example I gave was about third party libraries which I have no control over. So this solution explicitly doesn't work. And even if everyone used templates everywhere in order to be compatible with both interfaces and classes, isn't that a viral effect of having both?

> Forcing people to *not* use interfaces has its drawbacks too.  Dcollections gives the most flexible design I could muster, while still being useful.
>
> I'm not saying I'm against removing the interfaces until some later date, but I don't see any convincing arguments yet, especially since I've already seen benefits from having them.
>
> -Steve

On 05/19/2010 07:21 PM, bearophile wrote:
> Andrei Alexandrescu:
>> Destroy me :o).
>
> You ideas are surely interesting, but I don't think there's a simple way to change his code according to your ideas.
> People can use the dcollections in the following weeks and months, and when you have implemented your ideas the people that like them can switch to using your collections.
>
> Bye,
> bearophile

I am sorry, but I've been quite sick since yesterday afternoon. I still can't think straight because of fever, but once it subsides, I'll reply to some of the points made in this thread.

Andrei

Andrei Alexandrescu:

> I am sorry, but I've been quite sick since yesterday afternoon.

Get better and in the meantime don't worry for D.

Bye,
bearophile

Michel Fortin:

>Devirtualization is only possible in certain cases: when the function knows exactly which type it'll get.<

You are wrong, in most cases there are ways to de-virtualize, even when the runtime type isn't exactly known, but sometimes to do it you have to work too much. This is probably why C# dotnet doesn't perform this optimization.

It's a complex topic, I suggest you to read about it, I can't explain here, see polymorpic call points, megamorphic ones, dispatch trees, and so on.

You can read something here too: http://www.digitalmars.com/webnews/newsgroups/newsgroups.php?art_group=digitalmars.D&article_id=105630

LLVM is not able to do this yet well, but once the -O7 optimization level is available it will have the means (if not the capability) to devirtualize as well as HotSpot:
http://linux.die.net/man/1/llvmc
And even if you don't compile your code with -O7 there are ways to improve the situation anyway with static code analysis (but usually this is not as good as type information collected at runtime or during profiling for profile-based optimization).


>Indeed. I'm no expert in linkers, but in my opinion this is one of the most basic optimizations a linker should perform.<

At its basic level it's an easy optimization, but as usual if you want to implement something well, things gets harder :-)
In LDC it's the compiler that is performing this optimization, and only if you manually add the -mergefunc switch, that is not used even in -O3.


>The problem with templates are more the multiple slightly different instanciations.<

This is what I was talking about with things getting "harder". A good implementation of this feature can recognize slightly different functions too, and remove such partial redundancy. This is doable, but LLVM is not able to do this yet. The good thing is that LLVM is improving quickly still.


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

I am not sure what you mean here, but you can be interested in this thread started by me: http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=108136

Bye,
bearophile

On 2010-05-20 15:47:22 -0400, bearophile <bearophileHUGS@lycos.com> said:

> Michel Fortin:
> 
>> Devirtualization is only possible in certain cases: when the function knows exactly which type it'll get.<
> 
> You are wrong, in most cases there are ways to de-virtualize, even when the runtime type isn't exactly known, but sometimes to do it you have to work too much. This is probably why C# dotnet doesn't perform this optimization.
> 
> It's a complex topic, I suggest you to read about it, I can't explain here, see polymorpic call points, megamorphic ones, dispatch trees, and so on.

I know I simplified a bit, and I'll admit you may know more than me about dynamic dispatch optimizations. But if I'm not mistaken other devirtualizing solutions are creating multiple instances of the code path based on either static info or a runtime switch. All this isn't very different from calling a templated function, but it's more complex and less reliable (because those optimizations might not be in the compiler, or might not be applicable to all scenarios).

My point all along was that it's better to stick with templates, where you're "guarantied" to get the "optimal" code path. The downside is that you lose the dynamic dispatch capabilities. But I believe those are rarely needed in most programs. And if you really need it it's quite easy and efficient to layer dynamic dispatch over static calls (much more than the reverse).

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