How is dynamic_cast typically implemented?

Question

Is the type check a mere integer comparison? Or would it make sense to have a GetTypeId virtual function to distinguishing which would make it an integer comparison?

(Just don't want things to be a string comparison on the class names)

EDIT: What I mean is, if I'm often expecting the wrong type, would it make sense to use something like:

struct Token
{
    enum {
        AND,
        OR,
        IF
    };
    virtual std::size_t GetTokenId() = 0;
};

struct AndToken : public Token
{
    std::size_t GetTokenId() { return AND; }
};

And use the GetTokenId member instead of relying on dynamic_cast.

you might want to take a look at http://stackoverflow.com/questions/2253168/dynamic-cast-in-c — YeenFei, Jul 23 '10 at 02:24
@YeenFei: I know what Dynamic_Cast actually does, I'm just curious (for various reasons) if I should rely on it rather than providing my own type codes for tokens. — Billy ONeal, Jul 23 '10 at 02:31
if RTTI is an overhead for your application, consider using type traits. I've posted some example on http://stackoverflow.com/questions/2377636/any-suggestion-for-doing-an-arbitrary-operation-using-given-arguments-of-arbitrar/2377991#2377991 — YeenFei, Jul 23 '10 at 03:07
It's weird that no one has mentioned, `virtual` base classes is a whole other can of worms that isn't discussed here... — user541686, Jul 29 '13 at 07:25
Probably because we run from virtual bases like the plague :) — Billy ONeal, Jul 29 '13 at 15:23

score 6 · Accepted Answer · answered Jul 23 '10 at 02:30

6

The functionality of the dynamic_cast goes far beyond a simple type check. If it was just a type check, it would be very easy to implement (something like what you have in your original post).

In addition to type checking, dynamic_cast can perform casts to void * and hierarchical cross-casts. These kinds of casts conceptually require some ability to traverse class hierarchy in both directions (up and down). The data structures needed to support such casts are more complicated than a mere scalar type id. The information the dynamic_cast is using is a part of RTTI.

Trying to describe it here would be counterproductive. I used to have a good link that described one possible implementation of RTTI... will try to find it.

answered Jul 23 '10 at 02:30

AnT stands with Russia

312,472
42
525
765

So, in my case, where a scalar type id is sufficient, should I use such a scalar? – Billy ONeal Jul 23 '10 at 02:32
2

@Billy ONeal: Well, yes... if your really need it. Except I don't understand why you decided to use `size_t` for the return type. `size_t` has nothing to do with all this. – AnT stands with Russia Jul 23 '10 at 04:14
I use `size_t` as sort of a default unsigned integer type. – Billy ONeal Jul 23 '10 at 12:37
Cast to `void*` is arguably the simplest case: it's a simple runtime offset, like implicitly converting to a virtual base class. – curiousguy Sep 10 '16 at 16:14
@AnT Any chance you will find the promised link from your answer ? ;-) – clickMe Mar 15 '17 at 18:07

score 1 · Answer 2 · answered Aug 27 '12 at 15:03

I don't know the exact implementation, but here is an idea how I would do it:

Casting from Derived* to Base* can be done in compile time. Casting between two unrelated polimorphic types can be done in compile time too (just return NULL).

Casting from Base* to Derived* needs to be done in run-time, because multiple derived classes possible. The identification of dynamic type can be done using the virtual method table bound to the object (that's why it requires polymorphic classes).

This VMT probably contains extra information about the base classes and their data offsets. These data offsets are relevant when multiple inheritance is involved and is added to the source pointer to make it point to the right location.

If the desired type was not found among the base classes, dynamic_cast would return null.

score 1 · Answer 3 · edited Jun 20 '20 at 09:12

1

In some of the original compilers you are correct they used string comparison.

As a result dynamic_cast<> was very slow (relatively speaking) as the class hierarchy was traversed each step up/down the hierarchy chain required a string compare against the class name.

This leads to a lot of people developing their own casting techniques. This was nearly always ultimately futile as it required each class to be annotated correctly and when things went wrong it was nearly impossible to trace the error.

But that is also ancient history.

I am not sure how it is done now but it definitely does not involve string comparison. Doing it yourself is also a bad idea (never do work that the compiler is already doing). Any attempt you make will not be as fast or as accurate as the compiler, remember that years of development have gone into making the compiler code as quick as possible (and it will always be correct).

edited Jun 20 '20 at 09:12

Community

1
1

answered Jul 23 '10 at 04:15

Martin York

257,169
86
333
562

I suspect that now it's done by comparing vtbl pointers, which are likely linked with superclass (parent) pointers. If you know the class of the object being casted, and the desired class (the template parameter), it's simple enough to get the vtbl pointers from each of those classes and march up the inheritance tree until you come to (or not) a common base class. – Drew Hall Jul 23 '10 at 04:33
@Drew Hall. Yes that was also a technique (or somthing very similar to your description) was used. But it is a couple of years since I looked at the source of gcc so I don't actually know. But I seem to remember reading a paper on a more effecient mechanism, but it is a long time since I was active in the compiler field. – Martin York Jul 23 '10 at 06:18
2

"I am not sure how it is done now but it definately does not involve string comparison". I would not be so sure, today I saw that 'strcmp' was showing in my profiler. After setting a breakpoint in 'strcmp' assembly, I saw that it was called by 'dynamic_cast'... I'm currently sad to use Microsoft Visual Studio 2005 and can hope that things have improved since ! – rotoglup Sep 16 '10 at 12:09
1

I'm not sure a string comparison (or something equivalent) can be avoided, with multiple DLLs and `dynamic_cast` from an object created in one DLL. A successful `dynamic_cast` might be able to be done without any string comparison, but if there is a successful `dynamic_cast` that requires string comparison to validate, every failed `dynamic_cast` needs to do a string comparison to show that it isn't covered... – Yakk - Adam Nevraumont Jul 31 '13 at 14:12
@Yakk: Compilers stopped using strings a decade ago. – Martin York Jul 31 '13 at 17:05
1

Strings, or string-equivalents? I'd like to see some evidence: even an idea how they do it instead. If you have a pure header file class `A` used in two different DLLs, and a derived class `B1` in one DLL and `B2` in the other, how is `dynamic_cast` supposed to work between DLLs without essentially the fully qualified name of `A` encoded in the type and compared? I suppose a global type registry in the runtime that pushes the string comparison to DLL loading might work, or hashes to make the string comparison faster, but string equivalents must be compared. – Yakk - Adam Nevraumont Jul 31 '13 at 17:13
@Yakk: No I can **not** prove it (because I have neither the time nor inclination to do so). But equally you have not proven your statement either. Now it is true that the RTTI system did use string comparisons to do this but I also remember this was a significant bottleneck (and people spent a lot of time working around it). But this is in the days before exceptions were a part of the standard. – Martin York Jul 31 '13 at 18:23
@Yakk: I also remember when g++ removed the bottleneck (about a decade ago) and MSVC (or the compiler cl) quickly followed in the using the new technique that removed the bottleneck. Exactly how they did it I forget and I no longer actively contribute to g++ so it has probably been significant changed since my time. – Martin York Jul 31 '13 at 18:24
@Yakk: I suspect (I have no real idea this is a pure guess). That involves work in both the linker and the runtime loader. – Martin York Jul 31 '13 at 18:27
@LokiAstari AFAIK, MSVC still has to do string comparisons. – Navin Feb 25 '14 at 19:02
@Navin: Very it sure it does not. Do you have a reference. – Martin York Feb 26 '14 at 01:29
I just saw strcmp dominating a dynamic_cast hotspot in gcc 4.8.2. – experquisite Nov 25 '15 at 17:50
@experquisite: I believe that `stcmp()` is still used as a last resort when the main techniques fails (but it has been many years since I have looked at anything that low level in the compiler). This is an indication that you are not organizing your source files in a traditional way and the runtime has to fall back to this technique. – Martin York Nov 25 '15 at 18:08

score 0 · Answer 4 · answered Jul 23 '10 at 06:09

0

The compiler cannot divine additional information you may have and stick it in dynamic_cast. If you know certain invariants about your code and you can show that your manual casting mechanism is faster, do it yourself. It doesn't really matter how dynamic_cast is implemented in that case.

answered Jul 23 '10 at 06:09

MSN

53,214
7
75
105

1

Unfortunately, I don't have oodles of code written yet, but it would be a nontrivial operation to convert from one to the other. There's a large amount of code that goes "Is this token an AND?" ... "Is this token an OR?" ... The actual cast itself isn't really required other than to determine whether I have the correct type. – Billy ONeal Jul 23 '10 at 12:39

How is dynamic_cast typically implemented?

4 Answers4

But that is also ancient history.

Linked

Related