Just about any software you write needs some way to store and parse data, game engines being no exception. The most common (and easiest) use of containers comes from the C++ Standard Template Library (
STL) which provides easy access to containers such as vectors, lists, queues, maps, etc. However, game engines rarely rely on the containers in this library for multiple reasons:
- You lose direct control over the container's performance
- Game engines are performance-critical and anytime you lose the ability to optimize something it could make an impact on how high your framerate can be. Oftentimes the containers in STL are fairly generalized whereas the equivalent container in a game engine can be written for a more specific use-case, tuned for better performance.
- How memory is allocated
- By default, STL containers will use the operating system's memory allocator to allocate/deallocate memory. While you can supply custom allocators, they're a hassle to work with, are unable to carry state information, and force your code to have template creep. Game engines often need to have very specific control over how memory is used, sometimes even forbidding deallocations by game code altogether. This need for control usually rules out any use of the STL memory allocators.
- Underlying container algorithms
- From a compiler implementation viewpoint, STL is just an API. How it's implemented underneath is totally up to the specific compiler you're using (GCC, CLANG, Visual Studio, etc.). Therefore, on one platform an std::map may be a red-black tree and on another it may not. Even if it is a red-black tree, that doesn't necessarily mean it's a good idea for your use case. Maybe your data is fairly small (< 100 elements). In that case, a red-black tree can be pretty overkill for storing your data as the overhead of processing it can be more expensive than just searching some linear list. There are of course other searchable STL containers (such as std::set) but the point is, you can't control the underlying implementation algorithm to be specific for your needs.
- Cache locality
- Properly exploiting cache locality can be a huge win for a game engine's performance. Certain algorithmic complexity requirements of STL operations may force the underlying implementations to store data in a way that can ruin cache locality (for example, constant-time deletion in an std::map). This kind of storage can be a nice win for lots of insertions/deletions into a container but oftentimes in a game there's more querying of the containers than there is container modifications.
- Serialization
- In a future post we'll get into the intricacies of serializing game objects. The things to keep in mind here is that any data stored in a game engine's containers can get automatically serialized for the user without them having to do anything. This can be much simpler than a user having to manually serialize data located in an STL container.
- Container naming
- This point may seem a little contrived, but oftentimes things like vector or map in a game engine would refer to a mathematical vector or a map designating some region of a game level (or a texture map). This kind of naming can be confusing for any programmers not familiar with STL. However, having containers named obvious container names (such as array instead of vector) may go a long way in removing any confusion.
These are just a few points to use in arguing against the use of STL in any performance-critical code. I'm not saying that STL isn't great or that you shouldn't use it, just that these kinds of things should be considered before using it all over a game engine. Personally I'm a large fan of how easy STL is to use, especially because many programmers understand it and can fairly easily pickup code where it's in use.
Now that we've gotten through all of the reasons Qi doesn't use STL, let's get into the custom containers currently in the engine
