Article

Fast Delegates for Efficient AI

Alex J. Champandard on June 11, 2007

This post about the efficiency of fast delegates has been superseded by this article. It’s hard to make a fast delegate as efficient as an equivalent virtual interface (though it’s possible). The main benefit of fast delegates is their effectiveness at keeping software architectures simple, which indirectly can improve efficiency.

From the perspective of maintainable software, having a class for low-level tasks and individual observers is very useful. However, this particular implementation of object oriented behaviors can have its costs. All behaviors must be exposed as tasks when they are added to the scheduler, which requires many small memory allocations. On top of that, all the function calls are virtual — which adds a non-negligible overhead on most platforms.

In plain C, having tasks as function pointers would resolve these performance problems, but it would exclude most object oriented designs that are common in C++. Having unique tasks for certain NPC for example would be much harder to achieve.

Conceptually, closures are the solution to this problem. A closure is a function that has its own execution environment. In the case of AI logic, a task is such a closure with its own code and memory. Most languages support some kind of closures, but C++ has always had trouble with this. Anyone who has worked with function pointers knows how hard it is to deal with different types of functions (even if they have the same prototype).

Fast delegates are the answer to this C++ conundrum. Delegates are just like interfaces, but they have much lower overhead. They store only a function pointer and the associated “this” object. As such, it’s possible to implement closures with them very efficiently. Fast delegates, on most platforms, take barely 8 bytes of memory and compile down to two instructions in assembler. (Edit: Sadly, since compilers must compile C++ member function pointers with the worst case scenario in mind, the general fast delegate ends up taking up more memory and instructions than the best case C function pointer.)

The fast delegate library makes it very easy to create such closures from any type of function:

using namespace fastdelegate;
typedef FastDelegate()> Task;

Status MyTaskFunction()
{
    return Running;
}

struct MyHolder
{
    Status MyTaskMember()
    {
        return Completed;
    }
};

This is how the tasks are initialized and called:

// Initialize the delegates.
Task t1(&MyTaskFunction);

MyHolder holder;
Task t2(&holder, &MyHolder::MyTaskMember);

// Run them.
Status s1 = t1();
Status s2 = t2();

This particular library isn’t 100% C++ standards compliant under the hood, but all modern compilers are fully supported. The interface, however, is type-safe so it’s generally not much of a problem. On the other hand, this alternative implementation is standards compliant, but not supported on as many platforms.

Once you get comfortable with these delegates, you’ll find yourself using them everywhere. They allow you to use object oriented C++ designs, and still get the most performance out of the system — as if you were implementing it in plain C!

Discussion 2 Comments

alexjc on July 6th, 2007

Thanks Emmanuel. That's good to know. But one thing that makes fast delegates so useful regardless of speed is the syntax. Function pointers in C++ are just terrible compared to most other languages, and the FastDelegate library makes it easy to treat any function in the same way. So it's a great pattern as well as an optimization trick. Alex

alexjc on March 12th, 2008

[quote]This post about the efficiency of fast delegates has been superseded by this article. It's hard to make a fast delegate as efficient as an equivalent virtual interface (though it's possible). The main benefit of fast delegates is their effectiven[/quote] Read the [url=http://aigamedev.com/programming-tips/fast-delegate]full article[/url] on the blog.

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!