Re: Inheritance - why so slow?

[Krzysztof Duleba]

Paul Pluzhnikov wrote:
>
> > Tell me if I'm wrong, but there are only N classes, right?
> Argh, I guess I only looked at your second example.

OK, I was talking about it.

> > So the graph has only O(N) veticles and O(N^2) edges.
>
> In the first example you do have N nodes, and g++ does exhibit
> slightly worse than O(N^2) slowdown.
>
> > Where can you see a tree of exponential size?
>
> In your second example, there are also N classes, but A2 inheritance
> tree looks like this:
>
>      A2     inherits from
>    /   \
>   A1    A0
>   |
>   A0
>
> for a total of 3 classes (and A2 actually contains 2 separate
> instances of A0).

Really? I don't like what you say. I thought that a class can contain only
one inscance of another class. It seems that I've been wrong about it for
quite a long time. Thanks for clearing it out.

> Now the tree contains 2^N-1 nodes.

I see it now.

> Anyway, deep inheritance like the one you are simulating just doesn't
> happen in any real code I've seen (except for the IUnknown/OLE), and
> optimizing for it seem pointless.

Well, right, at least to some point. But it's nice to say that a compiler
is smart enough to handle such case, instead of failing to compile a code
which has only about 1kB.

Regards
Krzysztof Duleba