Re: Inheritance - why so slow?

[Paul Pluzhnikov]

"Krzysztof Duleba" <krzysan@skrzynka.pl> writes:

> Tell me if I'm wrong, but there are only N classes, right? 

Argh, I guess I only looked at your second example.

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

Now the tree contains 2^N-1 nodes.

> I'd expect O(N^2) slow-down and Visual C++ seems to work his fast. Why
> should g++ be that much slower?

FWIW, IBM xlC is also very fast on this test, but Sun CC and EDG
front-end are also very slow.

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.

Cheers,
-- 
In order to understand recursion you must first understand recursion.
Remove /-nsp/ for email.