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. The type ID schemepresented uses the modulo function to check that one class derives from another.

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

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

4 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]. 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.

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

6 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. ;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.

7 To construct the type ID, a different primenumber is associated with each class. 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. Importantly, the check that one classderives from another is performed in a known, constant time.

8 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. To prevent the type IDs from being any larger than necessary, the classes are sorted accordingto priority. The priority for a class is the maximum number of ancestors that any of its descendants priority reflects the number of prime factors that are multiplied together to form a class type with the highest priority are assigned the smallest prime we had to assign each class a unique prime number, the type IDs would quickly get very , this is not strictly necessary.

9 While all classes at the root level (those having no base classes)must be assigned globally unique prime numbers, independent hierarchies can use the same primes fornon-root classes without conflict. Two classes with a common descendant then cannot have the sameprime and none of their children may have the same prime. This also implies that no two children ofa class may have the same prime. In all other cases, the primes can be duplicated across a level ofthe hierarchy. For example, in a tree structure two classes on the same level of the tree never have acommon descendant, so they may have identical sub-trees beneath them without a CLASSESF igure2shows an error that an overly simple assignment of prime multipliers could proposed scheme avoids this problem.

10 Note that the type ID for classD, 10, divides the typeID for classE, 210, even though classEdoes not derive from classD. This has happened because weassigned the same prime multiplier, 2, to classesCandD, thinking they were independent. They arenot independent because classesAandBshare a common descendant, classE. In our terminology,classes which share a common descendant are said to be in the classBarein the same group. This motivates the rule for assigning primes: if any parent of classFis in the samegroup as any parent of classG,thenclassFand classGmust be assigned different prime rule is probably too strict, but we do not see any obvious way to loosen 2005 John Wiley & Sons, Pract. ;36:139 156142M. gibbs AND B. STROUSTRUPF igure 2. Justification for the conflict classes can be divided into levels and each level assigned a distinct set of prime level of a class must be greater than the level of any of its base classes and a class with nobase classes ( a root class) has a level of 0.