Type-based dispatching

Today’s useful C++ technique is type-based dispatching. This can be used whenever you want to call different functions based on properties of a certain class, without paying unnecessary performance penalties.

Consider the following code which does two distinct things based on a property of a given class:

class Dispatch
{
public:
  template <class T>
  void Do(void)
  {
    if (T::IS_THIS)
    {
      // do something this way
    }
    else
    {
      // do something that way
    }
  }
};

In order to use this code, our class T must exhibit a boolean property named IS_THIS. Whether we use type traits for this kind of property or just a static bool inside our classes doesn’t matter for the example we’re about to discuss.

So let’s say we’ve got the following two classes lying around:

struct That
{
  static const bool IS_THIS = false;
};

struct This
{
  static const bool IS_THIS = true;
};

And we use the above code like this:

Dispatch dispatch;
dispatch.Do<This>();
dispatch.Do<That>();

Upon compiling this code in MSVC, the compiler will warn about ‘warning C4127: conditional expression is constant’, and rightly so. Of course, which branch we need to take can be determined at compile-time, but still, sometimes the compiler is (or rather can’t) be smart enough to figure this out on his own. Additionally, in some optimized code we don’t want branches like this if the code is really performance-critical.

So, how can we do the same thing, but make sure that there’s no branches, and no compiler warnings?

One solution might be to use different overloads for different types of classes, but there’s some problems with that approach:

  • We used a template in the original example because we want the function to work for any type – this cannot be done with overloads (think user-defined types)
  • Overloads only work as long as we pass parameters to the function, otherwise there’s nothing to “overload”

The second bullet point already renders this solution unusable, because we don’t take any parameters. Still, function overloads is the way to go, if only we could introduce new types based on the IS_THIS property of the given class T…

In fact, we can exactly do that, by using a very small but nifty helper template class:

template <size_t N>
struct IntToType
{
};

Think about this a minute. Ready? Read on.

This little template does nothing more than declare a different type for each different value we feed it, e.g. IntToType<0> is different from IntToType<1>, which is different from IntToType<2>, and so on. So by using IntToType<T::IS_THIS>, we can turn the class’ property into distinct types. And now we are able to introduce overloads based on those types. Behold:

class Dispatch
{
public:
  template <class T>
  void Do(void)
  {
    Do(IntToType<T::IS_THIS>());
  }

  void Do(IntToType<0>)
  {
    // do something that way
  }

  void Do(IntToType<1>)
  {
    // do something this way
  }
};

The code does exactly the same it did before, the calling code is the same, but function dispatching is now really decided at compile-time. No more compiler-warnings, no if/else-branches.

Used under the right circumstances, this technique really shines whenever you want to squeeze out the last drops of performance, and want to reduce some (compile-time deducable) branches in performance-critical code.

The idiom used here is known as the IntToType-Idiom, and you can read more about it here. And while you’re at it, make sure to read Andrei Alexandrescu’s excellent book Modern C++ Design.

Advertisements

2 thoughts on “Type-based dispatching

  1. Pingback: Memory system – Part 2 | Molecular Musings

  2. Pingback: Implementing a semi-automatic structure-of-arrays data container | Molecular Musings

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s