Article
chart

Fast Delegates for Effective Game Logic in C++

Alex J. Champandard on March 12, 2008

Fast delegates are a C++ version of closures, which are basically functions bound to an execution environment. Delegates, in practice, are used as a lightweight implementation of interfaces, or as an elegant replacement for member function pointers. If you cringe at the thought of writing an interface around simple functionality, or get frustrated with how the C++ standard prevents you from legally casting function pointers, then fast delegates are the solution.

I previously wrote about fast delegates here, focusing more on their performance, since fast delegates help avoid clunky designs that rely overly on interfaces. However, as it turns out, with most delegate implementations it’s very difficult to beat the performance of C++ interfaces. As pointed out in the comments, compilers these days make sure that virtual functions can be optimized better than member function pointers.

This article covers my experience using fast delegates extensively over the past 6+ months, in particular how best to use them for game logic and how to help the compiler optimize them as well as any other (virtual) function. The analysis is also topical, since Insomniac’s recently released Nocturnal library also uses its own C++ delegates extensively for the event system — among others. (Thanks to Arjen Beij for pointing this out.)

Insomniac’s Nocturnal Library

Nocturnal Initiative

Last month, Insomniac Games released some of their framework code to help developers starting out with cross-platform development and prevent them from having to rewrite the basics required to build a new engine. In particular, the code includes delegates for the event system.

  • The code is one of the nicest implementations of a delegate I’ve seen in a traditional C++ style, rather than using modern/generic C++.

  • The implementation itself is written using an interface pattern. There’s a virtual base class that is implemented separately to call member function pointers.

For member function pointers, this implementation basically has the overhead of a double dispatch. However, this goes to show that delegates are useful for C++ game development not for performance reasons, but simply because of their convenience at wrapping arbitrary functions behind a common callable object. As mentioned in the Nocturnal wiki:

“This chunk of code has a long history at Insomniac and has been crucial to engineering our most ambitious applications. This code uses standard C++ to implement the .NET event and delegate functionality. It is type-safe and supports parameters and return value functions (or void functions).”

Here’s a direct link to the archive itself.

Nocturnal Common Package
Download ZIP (37 Kb)

Game::AI++ and Fast Delegates

For the last eight months, I’ve been working sporadically on an experimental game AI library that’s a hybrid between behavior trees and planners — among other things. At the base, I decided to use Don Clugston’s fast delegate library.

In particular, I used fast delegates as the basis for a the low-level tasks, which are managed within a scheduler. Not only that, each task returns another fast delegate (also a task) which indicates to the scheduler which task should be run next time. This is a simple way to implement coroutines using a functional programming style.

Advantages

These fast delegates fix all the annoyances of member function pointers, so it’s easy to add global functions and member functions from any class to the scheduler without requiring the objects to inherit from a common base class or provide an interface.

Disadvantages

Since it’s so easy to use, it’s very easy to go overboard! It also takes some experience to read the template syntax, and having no traditional interface can make it harder to understand the code (they are a good documentation tool). On top of that, debugging these fast delegates is a hassle since their implementation is non-standard custom C++ that gets in the way where a virtual function call wouldn’t.

As for performance, I was a bit disappointed to find out it takes 8 whole bytes to store a member function pointer, since the compiler needs additional information over a standard C function pointer for it to work. That brings fast delegates to 12 bytes each.

Many of the disadvantages can be fixed with good API design and documentation, but that requires a little time to experiment with what works and what doesn’t. After that, you can try to squeeze the last drop of performance by using a slightly different implementation of fast delegates.

Combining Elegance and Efficiency

The fast delegate library mentioned above isn’t standard C++, but it exposes a very elegant interface. Certainly, Game::AI++, in its current form, abuses that a little by defining tasks recursively:

// Definition of a task that returns another task!
struct Task;
struct Task : public FastDelegate<Task ()> {};

// Initialization
MyBehavior behavior;
Task task(&behavior, &MyBehavior::start);

// Execution is done by the scheduler
next = task();

Since these tasks are used extensively within the AI engine for both planning and execution, any gain in performance at such a low-level affects the whole system drastically. This prompted me to experiment with this alternative implementation by Sergey Ryazanov. By using standard C++ template function pointer parameters, it allows the compiler to optimize the delegate call as any normal function.

In practice, this means:

  • This second implementation of fast delegates takes only 8 bytes compared to the 12 for the other, a 33% improvement.

  • The performance of the second implementation, thanks to the compiler, increases by 25% to 50% depending on the case.

It used to be the case that compilers struggled with the function pointer as template parameters, but these days it’s not too much of a problem. However, a real down side is that the syntax is a little more complex to work with. Based on the original description, you can end up with syntax that looks like this:

Task t;
// The function pointer is a template parameter!
t.bind<MyBehavior, &MyBehavior::start>(&behavior);

Using this simple helper function reduces the hassle, but it’s still not as simple as the first implementation. I personally switched the implementation of Game::AI++ to use this second type of fast delegate (hidden behind macros), as the performance and memory gains can’t be ignored. The syntax and compiler support are an acceptable side effect.

Summary

Using some part of the C++ standard cleverly, it’s possible to make sure that fast delegates get optimized as effectively as virtual functions. You can save a lot of memory and reduce the cost of calling any fast delegate if you’re willing to sacrifice compatibility with older compilers.

However, the main benefit of fast delegates is the syntax. They allow you to create much more effective software architectures that avoid the hassle and overhead of a fully blown interface pattern.

Do you have an equivalent of fast delegates in your game or engine? If not, do you think you need them?

Discussion 4 Comments

alexjc on March 13th, 2008

Ian, something like this? [quote]Fast * are a C++ version of *, which are basically * * to an * *. *, in practice, are used as a [U]*[/U][U] * of *[/U], or as an elegant replacement for * * *. If you cringe at the thought of writing an * around simple *, or get frustrated with how the C++ standard prevents you from legally * * *, then * * are the solution.[/quote]Hehe. I'll try again: Fast delegates are like functions that carry around their own memory, and you can use them just as easily as functions. Seriously, if you have any other questions let me know! Alex

zoombapup on March 14th, 2008

I'm using fast delegates to distribute object "message" data around. But finding it a bit less clean and debuggable than I'd like. So its time for a refactor over the easter break. I find I refactor a fair bit right now actually, hopefully my codebase will firm up a bit soon.

alexjc on March 14th, 2008

Thanks for your input, Phil. What annoys me the most about debugging is that I have to step into the delegate's implementation everytime. I haven't figured out a way to stop Eclipse CDT from doing that yet :-) (Yes, I use Linux when I'm not contracting!) That aside, the remainder of my issues are more problems with large "event-driven" behavior trees than the fast delegates themselves. Alex

Ian Morrison on June 19th, 2008

Well, I finally figured these things out, now that I finally needed 'em. Thanks for the resource Alex, it made it way faster to get up to speed on these.

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!