11.10 Constant-Time Multimethods: Raw Speed

Maybe you have considered the static dispatcher but found it too coupled, have tried the map-based dispatcher but found it too slow. You cannot settle for less: You need absolute speed and absolute scalability, and you're ready to pay for it.

The price to pay in this case is changing your classes. You are willing to allow the double dispatcher to plant some hooks in your classes so that it leverages them later.

This opportunity gives a fresh perspective to implementing a double-dispatch engine. The support for casts remains the same. The means of storing and retrieving handlers must be changed, however—logarithmic time is not constant time.

To find a better dispatching mechanism, let's ask ourselves again, What is double dispatching? You can see it as finding a handler function (or functor) in a two-dimensional space. On one axis are the types of the left-hand operator. On the other axis are the types of the right-hand operator. At the intersection between two types, you find their respective handler function. Figure 11.5 illustrates double dispatch for two class hierarchies—one of Shapes and one of DrawingDevices. The handlers can be drawing functions that know how to render each concrete Shape object on each concrete DrawingDevice object.

It doesn't take long to figure out that if you need constant-time searches in this two-dimensional space, you must rely on indexed access in a two-dimensional matrix.

The idea takes off swiftly. Each class must bear a unique integral value, which is the index in the dispatcher matrix. That integral value must be accessible for each class in constant time. A virtual function can help here. When you issue a double-dispatch call, the dispatcher fetches the two indices from the two objects, accesses the handler in the matrix, and launches the handler. Cost: two virtual calls, one matrix indexing operation, and a call through a pointer to a function. The cost is constant.

It seems as if the idea should work quite nicely, but some of its details are not easy to get right. For instance, maintaining indices is very likely to be uncomfortable. For each class, you must assign a unique integral ID and hope that you can detect any duplicates at compile time. The integral IDs must start from zero and have no gaps—otherwise, we would waste matrix storage.

A much better solution is to move index management to the dispatcher itself. Each class stores a static integral variable; initially, its value is -1, meaning "unassigned." A virtual function returns a reference to that static variable, allowing the dispatcher to change it at runtime. As you add new handlers to the matrix, the dispatcher accesses the ID and, if it is -1, assigns the next available slot in the matrix to it.

Here's the gist of this implementation—a simple macro that you must plant in each class of your class hierarchy.

#define IMPLEMENT_INDEXABLE_CLASS(SomeClass)


   static int& GetClassIndexStatic()\


   {\


      static int index = -1;\


      return index;\


      }\


      virtual int& GetClassIndex()\


      {\


         assert(typeid(*this) == typeid(SomeClass));\


        return GetClassIndexStatic();\


   }

You must insert this macro in the public portion of each class for which you want to support multiple dispatch.^[6]

^[6] Yes, multiple, not only double, dispatch. You can easily generalize the index-based solution to support multiple dispatch.

The BasicFastDispatcher class template exposes exactly the same functionality as the previously defined BasicDispatcher but uses different storage and retrieval mechanisms.

template


<


   class BaseLhs,


   class BaseRhs = BaseLhs,


   typename ResultType = void,


   typename CallbackType = ResultType (*)(BaseLhs&, BaseRhs&)


>


class BasicFastDispatcher


{


   typedef std::vector<CallbackType> Row;


   typedef std::vector<Row> Matrix;


   Matrix callbacks_;


   int columns_;


public:


   BasicFastDispatcher() : columns_(0) {}


   template <class SomeLhs, SomeRhs>


   void Add(CallbackType pFun)


   {


      int& idxLhs = SomeLhs::GetClassIndexStatic();


      if (idxLhs < 0)


      {


         callbacks_.push_back(Row());


         idxLhs = callbacks_.size() - 1;


      }


      else if (callbacks_.size() <= idxLhs)


      {


         callbacks_.resize(idxLhs + 1);


      }


      Row& thisRow = callbacks_[idxLhs];


      int& idxRhs = SomeRhs::GetClassIndexStatic();


      if (idxRhs < 0)


      {


         thisRow.resize(++columns_);


         idxRhs = thisRow.size() - 1;


      }


      else if (thisRow.size() <= idxRhs)


      {


         thisRow.resize(idxRhs + 1);


      }


      thisRow[idxRhs] = pFun;


   }


};

The callback matrix is implemented as a vector of vectors of MappedType. The BasicFastDispatcher::Add function performs the following sequence of actions:

The columns_ member variable tallies the number of columns added so far. Strictly speaking, columns_ is redundant; a search for the maximum row length in the matrix would yield the same result. However, column_'s convenience justifies its presence.

The BasicFastDispatcher::Go is easy to implement now. The main difference is that Go uses the virtual function GetClassIndex.

template <...>


class BasicFastDispatcher


{


   ... as above ...


   ResultType Go(BaseLhs& lhs, BaseRhs& rhs)


   {


      int& idxLhs = lhs.GetClassIndex();


      int& idxRhs = rhs.GetClassIndex();


      if (idxLhs < 0 || idxRhs < 0 ||


         idxLhs >= callbacks_.size() ||


         idxRhs >= callbacks_[idxLhs].size() ||


         callbacks_[idxLhs][idxRhs] == 0)


      {


         ... error handling goes here ...


      }


      return callbacks_[idxLhs][idxRhs].callback_(lhs, rhs);


   }


};

Let's recap this section. We defined a matrix-based dispatcher that reaches callback objects in constant time by assigning an integral index to each class. In addition, it performs automatic initialization of its support data (the indices corresponding to the classes). Users of BasicFastDispatcher must add a one-macro line, IMPLEMENT_INDEXABLE_CLASS (YourClass), to each class that is to use BasicFastDispatcher.