Tuesday, September 11, 2007

Alternative ways to implement downcasts

To perform a downcast is to cast a pointer to a class into a pointer to a subclass. The three standard ways of doing it are:
  1. Using dynamic_cast
  2. Using a virtual function
  3. Using a type tags and static_cast
In the remaining section, we will use source class to denote the class being cast from and target class to denote the class that we are casting to.

Using dynamic_cast

Of the three methods, using a dynamic_cast is the simplest one. Unfortunately, on the systems measured, it is also the slowest way of performing a downcast. To use dynamic cast, the compiler has to generate code for RTTI and the class has to contain at least one virtual function. If you are going to inherit from a class, you should make the destructor virtual, so that is automatically solved. The code to perform the downcast is:
if (Derived* d = dynamic_cast<Derived*>(b)) {
  ...
}
Advantages:
  • The class does not have to be designed in any special way.
Disadvantages:
  • Requires RTTI to be compiled in

Using virtual function

To use a virtual function to perform the downcast, we require each the base class to define a virtual function for the target class of the downcast, and then the target class overrides this function and returns itself. The following code illustrates how to do this:
class Derived;         // Forward declaration

class Base {
public:
  virtual Derived* IsDerived() { return 0; }
};

class Derived : public Base {
public:
  virtual Derived* IsDerived() { return this; }
};
To perform a downcast using this method, we can then use the following code:
Base* b = ...;
  .
  .
  .
if (Derived* d = b->IsDerived()) {
  ...
}
Advantages:
  • Does not require RTTI
  • Easy to get right
Disadvantages:
  • Requires defining virtual functions for every subclass that can be the target of a downcast.

Using type tags and static_cast

The fastest of the methods for performing a downcast is by handling the type tags yourself by using an enum and a static_cast. It is also the method that is the least flexible and which requires the most from the programmer. The following code illustrates how to implement this method:
class Base {
public:
  enum Type { BASE, DERIVED };
  Type type() const { return mType; }

  Base() : mType(BASE) { }

  enum { TAG = BASE };       // For the down_cast function below

protected:
  // Protected since it's only intended for subclasses
  Base(Type t) : mType(t) { }

private:
  Type mType;
};

class Derived : public Base {
public:
  Derived() : Base(Base::DERIVED) { }

  enum { TAG = DERIVED };    // For the down_cast function below
};
The method can then be used in the following manner:
Base* b = ...;
  .
  .
  .
Derived* d = b->type() == DERIVED ? static_cast<Derived*>(b) : 0;
To simplify the usage, we can introduce the following template function to do the job:
template <class Target, class Source>
Target* down_cast(Source* s) {
  return s->type() == Target::TAG ? static_cast<Target*>(s) : 0;
}
Then we can use it in almost the same way that you use the other casts:
if (Derived* d = down_cast<Derived>(b)) {
 ...
}
It is possible to make it look exactly like the other casts, but that requires some more work with templates. See the afternote below for the source code for that.
Advantages:
  • Does not require RTTI
Disadvantages:
  • Requires extending an enum with a new type tag for each class that can be the target of a downcast.
  • Hard to maintain for large number of subclasses

Measurements

All measurements done are on an Intel(R) Pentium(R) M processor 1.60GHz using GCC with -O3 optimization level (mainly to get function inlining).
Downcasting (execution time)
Down-cast method Factor
Length dynamic_cast virtual call static_cast DC/VC VC/SC DC/SC
20000.160.020.016.622.6717.67
40000.320.050.026.532.7217.78
60000.480.070.036.502.6417.18
80000.630.100.046.482.5816.71
100000.800.120.056.392.7217.37
120000.970.150.066.582.5816.96
140001.110.170.076.562.5816.89
160001.280.200.086.482.6116.88
180001.430.220.086.502.5916.84
200001.610.250.106.512.5716.74

Summary

Of the three methods to perform a down cast, using a type tag and a static cast is by far the most efficient way: about 17 times faster than using dynamic_cast and almost 3 times as efficient as using a virtual function. There is an added advantage that only non-virtual functions are used to perform the cast, which potentially affects the surrounding code since it allows the compiler to take advantage of the fact that the function is inlined and the internals available to the optimizer.

Afternote: implementation of down_cast

In order to make the down_cast above appear as a normal cast, we have to use different code depending on whether we are casting to a pointer or to a reference. Casting to a value is not meaningful for this use, so we elect to only implement casting a pointer and a reference downwards in a class hierarchy. To handle that, we introduce a helper class down_caster, and then use a template function to let the compiler figure out the proper type to use for the values.

template <class, class> struct down_caster;

template <class To, class From>
struct down_caster<To*, From*> {
  static To* cast(From* from) {
    return from->type() == To::TAG ? static_cast<To*>(from) : 0;
  }
};

template <class To, class From>
struct down_caster<To&, From>
{
  static To& cast(From& from) {
    if (from.type() == To::TAG)
      return static_cast<To&>(from);
    else
      throw std::bad_cast();
  }
};

template <class To, class From>
struct down_caster<const To*, From*> {
  static const To* cast(From* from) {
    return from->type() == To::TAG ? static_cast<const To*>(from) : 0;
  }
};

template <class To, class From>
struct down_caster<const To&, From>
{
  static const To& cast(From& from) {
    if (from.type() == To::TAG)
      return static_cast<const To&>(from);
    else
      throw std::bad_cast();
  }
};
Especially note the From when casting to a reference type. The reason for this can best be explained through an example. Consider this code:
Derived& foo(Base *pbase) {
  return down_cast<Derived&>(*pbase);
}
The code is legal and will resolve the second template parameter of down_cast to be Base. If we used the template parameter From&, it would not match Base and generate a compile error, even though the code above is reasonable and shall compile (compare it with how dynamic_cast would behave).

No comments: