Fast dynamic casting - Bjarne Stroustrup

1 SOFTWARE PRACTICE AND EXPERIENCES oftw. Pract. ;36:139 156 Published online 15 September 2005 in Wiley InterScience ( ). DOI: dynamic castingMichael Gibbs1, , and Bjarne Stroustrup21 Lockheed Martin Aerospace, MZ 6602, Box 748, Fort Worth, TX 76101, of Computer Science, TAMU 3112, Texas A&M University, College Station, TX 77843, describe a scheme for implementing dynamic casts suitable for systems where the performance andpredictability of performance is essential. A dynamic cast from a base class to a derived class in an object-oriented language can be performed quickly by having the linker assign an integer type ID to each simple integer arithmetic operation verifies whether the cast is legal at run time.

2 The type ID schemepresented uses the modulo function to check that one class derives from another. A 64-bit type ID issufficient to handle class hierarchies of large size at least nine levels of derivation deep. We also discussthe pointer adjustments required for a C++ dynamiccast. All examples will be drawn from the C++language. Copyrightc 2005 John Wiley & Sons, WORDS: dynamic casting ; C++; modulo; embedded systems; hard real-timeINTRODUCTIONWhen writing C++, we often convert a pointer to a derived class (subclass) to a pointer to one ofits base classes (superclasses).

3 This is the basis for the object-oriented programming style wherewe use the interface provided by a base class to access the implementation in the derived we want to cast such a pointer to a base class back to a pointer to its derived ++ supports this functionality with thedynamiccasttype conversion operation. ConsiderSource* ptr = new Actual();Target* t = dynamiccast<Targ et *>(ptr);We create an object of typeActual, assign its pointer toptr(whereSourcemustbeabaseofActual),an d attempt to cast pointerptrto a pointer toTa r g e contains a single public baseof classTa r g e t, the offset to the beginning of theTa r g e tobject is computed and a pointer to theTa r g e tobject returned.

4 If the classActualdoes not inherit fromTa r g e t, the cast fails and contains more than a single base of typeTa r g e t(due to multiple non-virtual derivation), Correspondence to: Michael Gibbs, Lockheed Martin Aerospace, MZ 6602, Box 748, Fort Worth, TX 76101, E-mail: 2005 John Wiley & Sons, 22 March 2004 Revised 17 December 2004 Accepted 11 March 2005140M. GIBBS AND B. STROUSTRUPF igure 1. Down- casting and cross- casting in C++.the cast is ambiguous and returns0. The exact specification can be found in section of the ISOC++ standard [1].

5 A more tutorial explanation can be found in section of [2]. A brief discussionof performance and predictability ofdynamiccastcan be found in sections and of [3].Figure1shows the common cases of down- casting and casting is useful in many applications, but current implementations of this functionalityare slow compared with other C++ operations. Current implementations ofdynamiccastrequire extratype information to be kept for eachclass with a virtual function. Whendynamiccastis called, thealgorithm will traverse a data structure representing all ofActual s base classes, searching for a matchfor theTa r g e ttype.

6 If the type is not found or is found more than once,dynamiccast<Ta r g e t *>(ptr) fast , PREDICTABLE ALTERNATIVEU nfortunately, conventional implementations ofdynamiccastrender it unsuitable for real-timeapplications where speed, small memory footprint, and predictable performance are present an alternative implementation strategy designed to meet those constraints. Our solutionis primarily aimed at embedded systems where whole program analysis is typically feasible, but (withsome additional effort) it can be extended to systems with dynamic linking.

7 Please see the sectionentitled Dynamically loaded classes for alternative to walking the inheritance tree is to assign an integer type ID at link time to eachclass, most likely kept in the virtual table. This ID needs to be a static constant associated with theclass. The linker will assign these integers to the classes such that the following property holds: thereis a functionFwhich takes two integer arguments and returns an integer such thatF(derivedtype,basetype) == 0if and only if the class represented by the IDderivedtypeis a derived class of theclass represented by the 2005 John Wiley & Sons, Pract.

8 ;36:139 156 fast dynamic CASTING141 The trick lies in finding a functionFthat satisfies this criterion and in determining the size of theinteger necessary to accommodate realistic softwareprojects. We would prefer 32- or 64-bit integersso that the functionFcould be performed efficiently. If the evaluation of the function takes longer thanwalking the derivation tree, then nothing has been gained except a few bytes of program suggestion for anFfunction is integer modulo. To construct the type ID, a different primenumber is associated with each class.

9 The type ID for that class will be that prime number times theprime number for each of its base classes. Thus, thetype ID for a class will be evenly divisible by thetype ID of any of its base classes, and only by its base classes. This is guaranteed by the uniqueness ofthe factorization of integers into prime factors. Given an arbitrarily large integer type ID, any hierarchycan be represented this way. We wish to determinehow large a hierarchy can be represented using amachine s built-in integer method has the advantage that integer math is very fast for numbers that fit in a machine registerand should be much faster than the usual tree-walking routine.

10 Importantly, the check that one classderives from another is performed in a known, constant time. If the full type of the object being castcontains more than one copy of the target class, the cast will be ambiguous. In this case, the ID for thefull type will be divisible by the square of the prime for the target class. Performing a second divisibilitycheck determines if the cast can be done unambiguously. If the cast can be performed unambiguously,the address of the returned object mustbe computed, as described are a number of heuristic methods for keeping the size of the type ID to a minimum numberof bits.