dynamic_cast

Discussion in 'C++' started by Mark, Jan 13, 2005.

  1. Mark

    Mark Guest

    can someone explain, purely for my information, how
    dynamic_cast is implemented using only C++ language
    facilities.

    I don't mean how to use it, rather what is going on under the
    hood.

    Thanks

    Mark
     
    Mark, Jan 13, 2005
    #1
    1. Advertising

  2. Mark

    Mike Wahler Guest

    "Mark" <> wrote in message
    news:cs6vel$4jm$...
    > can someone explain, purely for my information, how
    > dynamic_cast is implemented using only C++ language
    > facilities.


    It's not.

    >
    > I don't mean how to use it, rather what is going on under the
    > hood.


    That's an implementation detail that can and does vary
    among implementations. Since here we only discuss the
    language itself, you'll need to ask about this where
    your particular compiler is discussed (or perhaps
    its vendor's web site).

    -Mike
     
    Mike Wahler, Jan 13, 2005
    #2
    1. Advertising

  3. Mark

    Siemel Naran Guest

    "Mark" <> wrote in message

    > can someone explain, purely for my information, how
    > dynamic_cast is implemented using only C++ language
    > facilities.


    I think one way to implement it is this: The virtual pointer of a class
    points to the virtual table, in the virtual table is a pointer to a
    std::type_info object that represents the type info for class, and there is
    also a pointer to the virtual table of the parent class.

    Suppose you have

    Something * s = new MoreDerivedSomething();

    Now when you say dynamic_cast<DerivedSomething*>(s), that system gets the
    virtual pointer of 's', namely something like s.__vptr. Then check if the
    type_info object pointed to in DerivedSomething is the same as the type_info
    object pointed to by MoreDerivedSomething. They're not equal. So then
    traverse to the virtual table of the parent class, which is the virtual
    table of class DerivedSomething and repeat the test. If there is no parent
    class then dynamic_cast returns NULL.

    This algorithm is O(N) where N is the depth of the hierarchy. Furthermore,
    comparing two type_info objects for equality may be O(M) where M is the
    length of the class name including namespaces, because there may be multiple
    copies of std::type_info objcets for a single class or even multiple copies
    of the virtual table, so std::type_info::eek:perator== would have to compare
    class names.

    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?
     
    Siemel Naran, Jan 14, 2005
    #3
  4. Mark

    Siemel Naran Guest

    "Mike Wahler" <> wrote in message news:8nDFd.6054

    > > I don't mean how to use it, rather what is going on under the
    > > hood.

    >
    > That's an implementation detail that can and does vary
    > among implementations. Since here we only discuss the
    > language itself, you'll need to ask about this where
    > your particular compiler is discussed (or perhaps
    > its vendor's web site).


    General topics about implementation are valid as it might shed light on the
    performance hit of using a certain feature, and provide insight for better
    future implementations. So one often asks about the cost of iostreams over
    printf, vector over array, exceptions over returning ints, and dynamic_cast
    over other designs.
     
    Siemel Naran, Jan 14, 2005
    #4
  5. Mark

    Jerry Coffin Guest

    > 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.
     
    Jerry Coffin, Jan 14, 2005
    #5
  6. Mark wrote:

    > can someone explain, purely for my information, how
    > dynamic_cast is implemented using only C++ language
    > facilities.
    >
    > I don't mean how to use it, rather what is going on under the
    > hood.



    Usually it is *not* implemented with C++ facilities. However all newer
    C++ casts keep a templatised syntax, showing the way on how you can
    write your own casts (brute force conversions).


    Once I had written a cast converting from whatever pointer to another
    pointer type, which always points at the beginning of an object, even in
    multiple inheritance.


    It was in the style:


    #include <iostream>


    template <class BasePointer, class CurrentPointer>
    inline BasePointer base_cast(CurrentPointer cp)
    {
    return reinterpret_cast<BasePointer>(static_cast<void *>(cp));
    }

    class A
    {};

    int main()
    {
    A a;

    unsigned char *p= base_cast<unsigned char *>(&a);
    }




    --
    Ioannis Vranos

    http://www23.brinkster.com/noicys
     
    Ioannis Vranos, Jan 15, 2005
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. alg

    dynamic_cast<>

    alg, Jul 14, 2003, in forum: C++
    Replies:
    3
    Views:
    485
    Rolf Magnus
    Jul 14, 2003
  2. Dan Noland

    dynamic_cast and references

    Dan Noland, Jul 29, 2003, in forum: C++
    Replies:
    0
    Views:
    500
    Dan Noland
    Jul 29, 2003
  3. Yuming Ma
    Replies:
    1
    Views:
    707
    Jeff Schwab
    Dec 17, 2003
  4. Andreas Sch.

    typeid and dynamic_cast, gcc 3.3

    Andreas Sch., Jan 23, 2004, in forum: C++
    Replies:
    18
    Views:
    1,894
    Janusz Szpilewski
    Jan 29, 2004
  5. Jamie Burns
    Replies:
    11
    Views:
    9,012
    Nick Hounsome
    Jan 29, 2004
Loading...

Share This Page