Re: dynamic_cast

From: Jerry Coffin (jcoffin_at_taeus.com)
Date: 01/14/05 

Date: 14 Jan 2005 08:43:30 -0800

> This is pretty slow. I'm sure dynamic_cast is required to be a fast
> operation. Is it O(1)? How might one achieve this?

First of all, dynamic_cast usually _is_ relatively slow (though I've
never done enough testing to figure out whether/to what degree its
speed varies with inheritance depth and such).

As far as making things faster, at least a few things are usually
pretty easy: normally, all objects of a particular class (that has
virtual functions) share a single vtable. As such, finding whether two
objects are of the same class requires only comparing their vtable
pointers rather than retrieving and comparing type_info objects.
Pointers can normally be compared in a single operation, reducing this
to O(1) instead of O(N) on the type_info size.

I doubt anybody does a lot to minimize the time taken to traverse the
inheritance tree -- the typical expectation is that inheritance trees
are fairly shallow, and dynamic_casts are fairly rare. If you're
talking about 4 pointer comparisons happening once an hour, nothing you
do with it is going to make any noticeable difference in speed.

If you honestly had a good reason to do so, I'm pretty sure you could
do this with an expected complexity of O(1). Instead of walking the
list of vtable pointers, you'd create a hash-table indexed by the value
of the vtable pointer of the current class. The value it looked up
would be a boolean indicating whether that class could be converted to
the target type for the dynamic_cast.

If you were doing this in a lot of places, you could make it a
two-dimensional lookup, first looking up the table for a given target
type, then looking up the source pointer in that table to find whether
that particular conversion could take place.

As I said, however, I doubt anybody does this -- it would only make
sense if you expected many dynamic_casts, extremely deep inheritance
trees, or both. In fact, you pretty much expect neither. 

--
Later,
Jerry.
The universe is a figment of its own imagination.

Relevant Pages

  • Re: C programming in 2011
    ... a pointer to ijkl:000h or i000:jklh before comparing pointers. ... counter doesn't have to imply that the *offset* is signed.. ... register and contains a 32-bit value. ...
    (comp.lang.c)
  • Re: map.find doesnt find
    ... Basically the map.findmethod fails to find a match for a key that I ... The method is comparing pointers to determine if the objects are ... In my case the map key is of type const wchar_t* so this is ... Key type is a pointer so mapcompares those pointers, ...
    (microsoft.public.vc.stl)
  • Re: 74HC123 and long pulse
    ... Multiple memory banks, weak instruction ... existing C code because pointers don't work well with multiple memory ... You're comparing a PIC to a real CPU. ... Do you actually need to use C (with pointers, ...
    (sci.electronics.design)
  • Re: C vs. C++
    ... example, unlike C, C++ has a portable mechanism for comparing ... unrelated pointers. ... where to get memory. ...
    (comp.lang.c)