On 05/20/2010 09:41 AM, Michel Fortin wrote:
> 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.

(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

On 05/20/2010 02:47 PM, bearophile wrote:
> 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.

If we get deeper into this branch, we'll forget where we started from (are interfaces sensible for this design?) and we'll reframe the interfaces vs. no interfaces decision into a speed loss vs. no speed loss decision. There are other arguments to look at besides performance.


Andrei

Andrei Alexandrescu wrote:
> I wrote a solution to the problem in native D. It goes like this:
> 
> alias Container!(int, addable | purgeable) Messerschmidt;
> 
> void messWith(Messerschmidt i) {
>     ... use i's capabilities to add and purge ...
> }

I agree with Michael Fortin that the | is questionable. I'd like to suggest instead that it should instead be a variadic list of names, like:

    alias Container!(int, addable, purgeable) Msserschmidt;

Perhaps the names should follow a naming convention,


    alias Container!(int, ContainerAddable, ContainerPurgeable) Msserschmidt;

The problem with using scoped names, like Container.Addable, is scoped names cannot be added to.

On 05/21/2010 01:34 PM, Walter Bright wrote:
> Andrei Alexandrescu wrote:
>> I wrote a solution to the problem in native D. It goes like this:
>>
>> alias Container!(int, addable | purgeable) Messerschmidt;
>>
>> void messWith(Messerschmidt i) {
>> ... use i's capabilities to add and purge ...
>> }
>
> I agree with Michael Fortin that the | is questionable. I'd like to
> suggest instead that it should instead be a variadic list of names, like:
>
> alias Container!(int, addable, purgeable) Msserschmidt;
>
> Perhaps the names should follow a naming convention,
>
>
> alias Container!(int, ContainerAddable, ContainerPurgeable) Msserschmidt;
>
> The problem with using scoped names, like Container.Addable, is scoped
> names cannot be added to.

Well the problem stays: compound interfaces grow combinatorially with the number of components, because an interface X!(A, B, C) inherits at the same time X!(A, B), X!(A, C), and X!(B, C).

Check the epic inheritance diagram here:

http://www.artima.com/cppsource/codefeatures2.html

and the equally epic table here:

http://www.artima.com/cppsource/codefeatures3.html


Andrei

Andrei Alexandrescu wrote:
>>> 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.

Unfortunately, it's an agonizingly slow process. It also does nothing for Linux or OSX.

Steven Schveighoffer wrote:
> 
> I myself don't really use the interface aspect of the classes, it is mostly a carryover from the Java/Tango inspirations.  But I can see one good reason to keep them -- binary interoperability.  For example, it might be the case some day when D has good support with dynamic libraries that a library exposes some piece of itself as a Map or List interface.
> 

Hi, Steven.
You made a good point on interoperability.
Strict, precise, readable, interfaces, that's what I would like in the really good standard library for D.
But, is D mature enough to this kind of possibilities, considering, at least, known bugs involving interfaces?
I don't even feel myself free to use interfaces in my code because of undefined behavior it may cause.
Shared libraries...
Is this going to happen on Linux?
When?

-- 
Alex Makhotin,
the founder of BITPROX,
http://bitprox.com

Andrei Alexandrescu wrote:
> On 05/19/2010 09:59 PM, Robert Jacques wrote:
>> 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)
> 
> For the record, I strongly agree with this.

I do too, but that's the easy part. Living up to those ideals is extremely hard, usually because most designers think they have designed simple interfaces when everyone else thinks they didn't.

In this whole container discussion, I'd like to point out something Andrei pointed out to me. The one extremely successful example of pluggable components is the unix filter model. Essentially, one program pipes its output to the next, which pipes its output to the next, etc. The unix console is designed around that paradigm.

If we can get anywhere close to that level of success with ranges and containers, we should all be well pleased.

Walter Bright wrote:
> If we can get anywhere close to that level of success with ranges and containers, we should all be well pleased.

Mike Taylor has a phrase for that I think is well-coined: "impedance matching",
defined as the work necessary to get one library module to work with another
library module.

One example of bad impedance matching is C++ iostreams' attempt to make a memory
buffer look like a file. Phobos propagated that mistake in its own streams.

On Thu, 20 May 2010 04:42:35 +0300, Steven Schveighoffer <schveiguy@yahoo.com> wrote:

> interfaces

Does that imply that the most important methods are virtual?

If so, say good-bye to inlining, and hello to an additional level of dereferencing.

Without meaning any disrespect to all the work you did, allow me to say that I won't use a library that could be faster (without making usage too clumsy), but isn't. (I prefer my D programs to be as fast as reasonably possible - if I didn't care about speed, I'd use another language.) For the same reasons, I'd be disappointed if the library was admitted as-is into Phobos, since it doesn't live up to my personal ideal of what D should be.

-- 
Best regards,
 Vladimir                            mailto:vladimir@thecybershadow.net

Hello superdan,


> dun tell me it dun work. i dun explain shit again. it works coz a
> struct cant be null. but a struct can be a ref if it only haz one
> pointer inside. methinks the builtin hash iz dat way.
> 

> void foo(container!shit poo)
> {
> if(!poo) poo = new container!shit; // fuck dat shit
> poo.addElement(Shit(diarrhea));
> }
> dat sucks bull ballz.

That code is broken, if poo is of a class type, that just new's a container, adds an element, and then drops the reference to get GC'ed. To many it do anything generally useful, it would need to have another level of indirection.

-- 
... <IXOYE><