June 28, 2011 3:58 pm
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:
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.
Posted by Stefan Reinalter
Categories: C++
Tags: C++, compile time, idiom, int to type
Mobile Site | Full Site
Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.
[…] can be achieved via type-based dispatching in conjunction with template type-traits, but the explanation and implementation have to wait until […]
By Memory system – Part 2 | Molecular Musings on July 7, 2011 at 4:32 pm
[…] allowed on function templates, so that doesn’t work either. There is a third option, however: type-based dispatching. By introducing two overloads of the ForEach function template, we can choose the correct one by […]
By Implementing a semi-automatic structure-of-arrays data container | Molecular Musings on October 22, 2013 at 4:28 pm