Update : Walter Brown has come up with a much much more elegant way to do this. You can find the updated technique at the bottom of this post, or read more about it on cppreference.
A little while ago, I watched Jason Turner’s great cppcon talk, where he uses C++17 to write a commodore game. At that point, I decided it was quite time I confirm my (now proven false) beliefs on templates. If you ever want to convince a game programmer that templates are fine, show him that talk, and some assembly ;)
Today, I will share one of my template experiments. The generated assembly is beautiful, when compiled in release mode, and it opens the door to some very decoupled programming patterns. But first, what is duck typing?
Duck Typing
If it quacks like a duck […], it must be a duck. Duck Typing is a pattern by which you accept any kind of object for a certain task, but only call certain methods, or do certain operations, if the object has the required member functions/member variables. Usually, one would use runtime reflection to check if an object contains the desired characteristics. We performance fanatics cannot condone runtime reflection, so we’ll find another way while we wait for the static reflection proposal.
Lets take a simple game example to explain the idea. There is an explosion in my game. I use a sphere cast to gather all objects in a certain radius from the explosion. Now, I would like to damage all objects close to the explosion. Of course tiles, the level itself, static decoration objects and miscellaneous objects shouldn’t be hurt.
One way to solve this problem is using interfaces. Everybody that should get hurt implements an interface hurt(float damage) and we are done with it. For many cases this is enough, but we will have to deal with base pointers everywhere, which your compiler doesn’t like. More on your compiler later.
Instead, you could use reflection to check every object. If they implement a public hurt(float damage) member function, then we hurt them. This is duck typing.
It is a very relaxed, extremely flexible way to deal with logic on heterogenous types of objects. It has it’s flaws, but when used adequately, it can improve your code base tremendously.
On Compilers and Performance
When I started benchmarking various patterns and code, I quickly came to the conclusion that using base pointers was slower than not. I assumed the slowdowns were caused by cache-misses due to our objects’ vtables. Though this is true, it is not the biggest reason for slowdowns. The main reason working with base pointers is slower than using objects directly is your compilers capacity to devirtualize your code.
I am not talking about down casting here. The term is used by compiler writers (clang at least) to denote when the compiler can reason about your code. All the amazing inlining, variables magically disappearing, hundreds of lines of code collapsing to virtually nothing. All of that is possible due to devirtualization, amongst other things. When you benchmark pointers vs objects, and you go look at the assembly, you will quickly see the main speedups are often the result of your compiler doing “compiler magic”.
I like compiler magic. I want my compiler to do magic. Thus, I explored ways to use objects as-is, without interfaces, polymorphism or such paradigms.
Making Managers Quack
In this example, I will be creating component managers. These will have an awake() and an update(float dt) “event” or if you prefer, an optional member function. Since some of these managers could come from your users, we will be using duck typing to call the events rather than enforcing inheritance from a ComponentBase.
You will need :
tuplestype_traitsstd::enable_if*SFINAEVariadic templatesMACROS - shouldn't be required when we get reflection
Before we start, I would like to issue a warning. As I’ve mentioned previously, I haven’t been writing type_trait code for years upon years. As such, there may be kinks here and there. Note that I rather the code be readable and understandable than comprehensive and production ready.
This is C++14, but could be easily converted to C++11 with a few tweaks (index_sequence in particular). It was compiled using AppleClang.
Preliminaries
First lets create 3 objects, they will implement a variety of desired events. We will add them to a std::tuple and get everything ready.
#include <cstdio>
#include <type_traits>
#include <tuple>
struct Transform {
void awake() {
printf("transform awake\n");
}
void update(float dt) {
printf("transform update : %f\n", dt);
}
};
struct Collider {
void update(float dt) {
printf("collider update : %f\n", dt);
}
};
struct Physics {
void awake() {
printf("physics awake\n");
}
};
Transform transform;
Collider coll;
Physics phys;
auto component_managers = std::make_tuple(transform, phys, coll);
/* ... */
int main (int, char**) {
/* ... */
return 0;
}We also need the C++14 equivalent of std::apply. This calls a given member function, and passes an expanded tuple as it’s arguments. Our “events” would be quite useless if we couldn’t use arguments.
/**
* C++14 std::apply. Will be superceded by C++17.
*/
template<typename Function, typename Object, typename Tuple, size_t ... I>
auto _call(Function f, Object& obj, Tuple t, std::index_sequence<I ...>) {
return (obj.*f)(std::get<I>(t) ...);
}
template<typename Function, typename Object, typename Tuple>
auto _call(Function f, Object& obj, Tuple t) {
static constexpr auto size = std::tuple_size<Tuple>::value;
return _call(f, obj, t, std::make_index_sequence<size>{});
}SFINAE Hackery
We will use a now ubiquitous technique to detect whether or not a given type contains a member function. For now, lets focus on the update method. We will generalize the process with macros later on.
template <typename T>
class has_update_method {
template <typename C> static char test(decltype(&C::update));
template <typename C> static long test(...);
public:
static constexpr bool value = sizeof(test<T>(0)) == sizeof(char);
};
template<typename T>
constexpr bool has_update_method_v = has_update_method<T>::value;We are creating a class that will detect whether a given type T implements T::update. To do this, we need some SFINAE trickery. We define 2 member functions, one that accepts a method pointer as a parameter, one that accepts anything. Overload resolution will choose the first method if the provided type C has an update method, or the other if it doesn’t.
Using some trickery, we can figure out at compile-time whether or not a type has the ::update method by using the sizeof operator. If test< T >(0) returns a char, the type has an update member function and ::value is true. If not, the sizes will not match and value will be false.
has_update_method_v is a helper to make things look a little less convoluted later on. You can test the previous code with some static_asserts.
int main (int, char**) {
static_assert(has_update_method_v<Transform> == true, "");
static_assert(has_update_method_v<Physics> == true, "");
return 0;
}At this point, we “simply” have to provide 2 wrappers, one that calls update, one that will gracefully fail (do nothing) if our object doesn’t implement a certain member function.
To Call or not to Call
First, we will provide 2 versions of a _do_update_if_has_method function. The first will do nothing (gracefully fail), the second will call update with the user provided parameters. It uses the previously created _call template method.
template <typename T, typename... Args>
inline typename std::enable_if_t<!has_update_method_v<T>, void>
_do_update_if_has_method(T& t, Args... args)
{}
template <typename T, typename... Args>
inline typename std::enable_if_t<has_update_method_v<T>, void>
_do_update_if_has_method(T& t, Args... args)
{
_call(&T::update, t, std::make_tuple(args...));
}Using our method checker, has_update_method_v< T >, we can tell at compile-time whether or not a type has our desired method. std::enable_if does just what it says, it will enable one of our functions according to has_update_method.
The function accepts an object on which to call the update method and a varying number of arguments. We will pack these arguments into a tuple, and pass them on to _call.
Lets test this whole thing.
int main (int, char**) {
_do_update_if_has_method<Transform>(transform, 42.f);
_do_update_if_has_method<Collider>(coll, 42.f);
_do_update_if_has_method<Physics>(phys, 42.f);
return 0;
}Which should output.
transform update : 42.000000 collider update : 42.000000
Not bad at all.
We now need to apply this idea to all of our objects in the component_managers tuple. To do so, we will recursively process our tuple elements, incrementing an index until we have processed the whole tuple. We will stop at an empty version of our function. C++17 makes this a little nicer with if constexpr, but 2 functions will have to do for now.
We use std::enable_if again, but this time we check our index against the size of our tuple. If we have reached the end, our recursion stops.
template<size_t N = 0, typename... Ts, typename... Args>
inline typename std::enable_if_t<N == sizeof...(Ts), void>
update_managers(std::tuple<Ts...>& t, Args... args)
{}
template<size_t N = 0, typename... Ts, typename... Args>
inline typename std::enable_if_t<N < sizeof...(Ts), void>
update_managers(std::tuple<Ts...>& t, Args... args)
{
_do_update_if_has_method(std::get<N>(t), args...);
update_managers<N + 1, Ts...>(t, args...);
}This is what a compile time tuple foreach looks like. Beautiful…
And a quick test.
int main (int, char**) {
update_managers(component_managers, 42.f);
return 0;
}Outputs.
transform update : 42.000000 collider update : 42.000000
Very nice! If this doesn’t get you excited about C++ meta programming, I don’t know what will.
Generalizing
So everything is working as intended, but we need to generalize our process. We want to quickly and simply add events. If it all possible, we really do not want to type all of this again. The solution is to use a macro. I wish there was another way, but I haven’t found one.
Our macro will generate yourfunc_managers event call, which accepts at minimum a tuple of objects.
/**
* Declares yourfunc_managers(std::tuple<...>, ...)
* Calls member function on tuple objects, if it exists.
*/
#define MANAGERS_DUCK_TYPE(func) \
template <typename T> \
class has_##func##_method { \
typedef char one; typedef long two; \
template <typename C> static one test(decltype(&C::func)); \
template <typename C> static two test(...); \
public: \
static constexpr bool value = sizeof(test<T>(0)) == sizeof(char); \
}; \
\
template<typename T> \
constexpr bool has_##func##_method_v = has_##func##_method<T>::value; \
\
template <typename T, typename... Args> \
inline typename std::enable_if_t<!has_##func##_method_v<T>, void> \
_do_##func##_if_has_method(T& t, Args... args) {} \
template <typename T, typename... Args> \
inline typename std::enable_if_t<has_##func##_method_v<T>, void> \
_do_##func##_if_has_method(T& t, Args... args) { \
_call(&T::func, t, std::make_tuple(args...)); \
} \
\
template<size_t N = 0, typename... Ts, typename... Args> \
inline typename std::enable_if_t<N == sizeof...(Ts), void> \
func##_managers(std::tuple<Ts...>& t, Args... args) {} \
template<size_t N = 0, typename... Ts, typename... Args> \
inline typename std::enable_if_t<N < sizeof...(Ts), void> \
func##_managers(std::tuple<Ts...>& t, Args... args) { \
_do_##func##_if_has_method(std::get<N>(t), args...); \
func##_managers<N + 1, Ts...>(t, args...); \
}
/**
* Here we create events. Quick and easy.
*/
MANAGERS_DUCK_TYPE(awake);
MANAGERS_DUCK_TYPE(update);
int main (int, char**) {
awake_managers(component_managers);
// while (true) {
update_managers(component_managers, 42.f);
// }
return 0;
}All this is doing, is replacing “func” with your provided event name. You can now add new member function support quickly and it will be completely decoupled from your user code.
More over, your users can choose whether or not to implement a given function when writing their classes. Some of you may have recognized this pattern, it is exactly how the Unity 3D engine functions; minus the wicked static duck typing.
And the results.
transform awake physics awake transform update : 42.000000 collider update : 42.000000
gg wp ;)
Conclusion
If you are struggling with template meta-programming, I hope this post has helped you grasp some of the fundamentals of type traits and even a little SFINAE. For seasoned veterans, hopefully you now have another example of “cool things you can do with type traits”. Or you are simply triggered by my use of printf.
The provided example is not the be all end all of this pattern, far from it. Using something like a multi-vector (a container of multiple heterogenous types), you wouldn’t need to impose a single object limitation to your users. You could use this for more traditional event systems (sockets?) and probably many things I haven’t thought about.
This post wouldn’t have been possible without the endless discussions and late-night hackerywith my friend Alex. Merci pour l’aide!
Full Example
#include <cstdio>
#include <type_traits>
#include <tuple>
struct Transform {
void awake() {
printf("transform awake\n");
}
void update(float dt) {
printf("transform update : %f\n", dt);
}
};
struct Collider {
void update(float dt) {
printf("collider update : %f\n", dt);
}
};
struct Physics {
void awake() {
printf("physics awake\n");
}
};
Transform transform;
Collider coll;
Physics phys;
auto component_managers = std::make_tuple(transform, phys, coll);
/**
* C++14 std::apply. Will be superceded by C++17.
*/
template<typename Function, typename Object, typename Tuple, size_t ... I>
auto _call(Function f, Object& obj, Tuple t, std::index_sequence<I ...>) {
return (obj.*f)(std::get<I>(t) ...);
}
template<typename Function, typename Object, typename Tuple>
auto _call(Function f, Object& obj, Tuple t) {
static constexpr auto size = std::tuple_size<Tuple>::value;
return _call(f, obj, t, std::make_index_sequence<size>{});
}
/**
* Declares yourfunc_managers(std::tuple<...>, ...)
* Calls member function on tuple objects, if it exists.
*/
#define MANAGERS_DUCK_TYPE(func) \
template <typename T> \
class has_##func##_method { \
typedef char one; typedef long two; \
template <typename C> static one test(decltype(&C::func)); \
template <typename C> static two test(...); \
public: \
static constexpr bool value = sizeof(test<T>(0)) == sizeof(char); \
}; \
\
template<typename T> \
constexpr bool has_##func##_method_v = has_##func##_method<T>::value; \
\
template <typename T, typename... Args> \
inline typename std::enable_if_t<!has_##func##_method_v<T>, void> \
_do_##func##_if_has_method(T& t, Args... args) {} \
template <typename T, typename... Args> \
inline typename std::enable_if_t<has_##func##_method_v<T>, void> \
_do_##func##_if_has_method(T& t, Args... args) { \
_call(&T::func, t, std::make_tuple(args...)); \
} \
\
template<size_t N = 0, typename... Ts, typename... Args> \
inline typename std::enable_if_t<N == sizeof...(Ts), void> \
func##_managers(std::tuple<Ts...>& t, Args... args) {} \
template<size_t N = 0, typename... Ts, typename... Args> \
inline typename std::enable_if_t<N < sizeof...(Ts), void> \
func##_managers(std::tuple<Ts...>& t, Args... args) { \
_do_##func##_if_has_method(std::get<N>(t), args...); \
func##_managers<N + 1, Ts...>(t, args...); \
}
MANAGERS_DUCK_TYPE(awake);
MANAGERS_DUCK_TYPE(update);
int main (int, char**) {
awake_managers(component_managers);
// while (true) {
update_managers(component_managers, 42.f);
// }
return 0;
}Cheers
Update : is_detected
The demonstrated technique is great to understand the concept of compile time duck-typing in C++. There is, however, a new and less convoluted way to achieve the same results. Combined with c++17’s if constexpr, it makes for much more readable code.
First, you’ll want to create a “detector”. You do so by creating a templated alias that will check a given type for your desired function.
template <class T>
using has_awake = decltype(std::declval<T>().awake());This delays compilation of the check and allows us to trigger the compile error inside a template declaration (which is allowed due to SFINAE). To check for a function with arguments, one would use the following.
template <class T>
using has_update = decltype(std::declval<T>().update(std::declval<float>()));You do need to create one of these for each “event” you will be testing for, but at least it isn’t some insane macro.
To check whether a given type has a function, you pass the type and detector to a is_detected trait. This is how you use it in c++17.
if constexpr(is_detected_v<has_awake, T>) {
obj.awake();
}
if constexpr(is_detected_v<has_update, T>) {
obj.update(42.f);
}And finally, here is a simple is_detected implementation.
template <template <class> class Op, class T, class = void>
struct is_detected : std::false_type {};
template <template <class> class Op, class T>
struct is_detected<Op, T, std::void_t<Op<T>>> : std::true_type {};
template <template <class> class Op, class T>
inline constexpr bool is_detected_v = is_detected<Op, T>::value;Without going into too much details, this struct delays checking whether the type T has our event until the right moment. It does the check inside void_t, which takes any template expression and returns void. If T has the given function, the expression compiles and that specialization is chosen since it is more specialized. If Op
And that’s it for this little update, pretty sweet if you ask me!