Game Data Structures

Another linked article, this one about a set of foundation libraries released by bitsquid under the MIT license, the Bitsquid Foundation Library

Some observations…

Memory management and avoiding C++ STL

Memory is often as critical a resource as execution time. Bad memory management can result in lots of little fragments of unusable free memory and a game that crashes when trying to load the next level. In addition, many standard memory allocators serialize the memory allocation in order to be thread safe when running on multiple CPU cores. With lots of memory allocations, this can turn into a performance bottleneck. The C++ Standard Template Libraries are handy, but mostly consider memory allocation and deallocation as free operations, and are waaay more willing to do them than most game developers would prefer. Consequently, you’ll find a profusion of different memory allocators and data structures that most people think of as being part of standard C++. This is one such library.

Header organization and compile time

Compile time is a big issue for major game projects. Some use Visual Studio precompiled headers. They are good for relatively unchanging headers, but any change to any file in the precompiled header will result is a sloooow rebuild of the entire project.

Some try to reduce the dependencies between header files to only include what you absolutely need, and (in C++ at least) declare by name the classes you just need for pointers or references. This reduces the number of files that will need be recompiled for a header change. I first read about this technique in Large Scale C++ Software Design, by John Lakos. That book also advocates the pimpl approach, where rather than declaring private members in the public include file, the class will just contain a pointer to an implementation class. The implementation class is declared and defined with all of the implementation code, so does not need to be part of the class include file, and implementation changes do not cause recompilation for anyone using the class. Most games that I’ve seen do not use the pimpl method, because each class (even if created on the stack) results in an extra memory allocation, and each member function has an extra pointer dereference into the implementation class.

Bitsquid uses another technique, where the public class only contains data declarations. Rather than use member functions, you use regular functions to operate on the class. The idea is that most of the header interdependencies that increase compile time are just member-to-member dependencies which only need to know the data layout. Source implementation code may need to know about the functions too, but that’s still fewer dependencies (and faster compilation).

I have not done much coding in this style, but the key takeaway here is that game developers spend a lot of time compiling, and anything that makes compilation slower is potentially hours per day of lost work.