Creating a cache-friendly component system

Question

I am fairly new to c++ and am attempting to write a simple 2D game engine. I am currently working on my object model: a pure component system, similar to that described in the Data Locality chapter in Game Programming Patterns, whereby the components are fixed types, each stored in a separate array in the game world class. My current code looks a bit like this:

#include <iostream>
#define SID(str) HashString(str)
typedef unsigned long long StringID;
// Simple FNV string hash.
StringID HashString(const char* str) {
 const unsigned int fnv_prime = 0x811C9DC5;
 unsigned int hash = 0;
 unsigned int i = 0;
 unsigned int len = strlen(str);
 for (i = 0; i < len; i++) {
 hash *= fnv_prime;
 hash ^= (str[i]);
 }
 return hash;
}
// Component base class
class Component
{
public:
 static const int MAX_COMPONENTS = 10;
 Component() {};
 virtual ~Component() {};
 virtual void Update() = 0;
 StringID mID;
};
// Basic 2D vector.
struct Vec2 {
 float x;
 float y;
};
// Component for storing world position.
class TransformComponent : public Component
{
public:
 TransformComponent() {}
 TransformComponent(float x, float y) {
 Vec2 mPosition = { x, y };
 }
 virtual ~TransformComponent() {};
 virtual void Update() { /* No need to update- only to store data */ };
private:
 Vec2 mPosition;
};
// A struct for storing components in a contiguous way.
struct Components
{
 int CurrentTransformComponents = 0;
 TransformComponent* TransformComponents = new TransformComponent[Component::MAX_COMPONENTS];
};
// Variarg function to add all listed components
template <typename T>
inline void AddComponents(StringID gameObjectID, T component) {
 Application* app = Application::GetApplication();
 std::cout << "Adding component..." << std::endl;
 // Ugly placement of componet in array :)
 if (typeid(T) == typeid(TransformComponent)) {
 component.mID = gameObjectID;
 // Add component to the correct place in the array;
 app->mComponents.TransformComponents[app->mComponents.CurrentTransformComponents] = component;
 ++app->mComponents.CurrentTransformComponents;
 }
}
template <typename Arg, typename ... Args>
inline void AddComponents(StringID gameObjectID, Arg first, Args ... args) {
 AddComponents(gameObjectID, first);
 AddComponents(gameObjectID, args...);
}
// Adds componets AND returns ID.
template <typename ... Args>
inline StringID CreateGameObject(const char* name, Args ... args) {
 std::cout << "Creating GameObject " << name << " ";
 StringID id = SID((char*)name);
 std::cout << "Hash ID is " << id << std::endl;
 AddComponents(id, args...);
 return id;
}
// A base app class. 
// This is a singleton :(
class Application
{
 template <typename T>
 friend void AddComponents(StringID gameObjectID, T component);
public:
 Application() : mComponents() {
 if (mApplication != nullptr) {
 std::cout << "Application already exists. You can only create 1 Application" << std::endl;
 }
 mApplication = this;
 }
 virtual ~Application() {}
 static Application* GetApplication() { return mApplication; }
 // Debug run to check components have been added correctly.
 void Run() {
 StringID testObject1ID = CreateGameObject("testObject1", TransformComponent(0, 0));
 StringID testObject2ID = CreateGameObject("testObject2", TransformComponent(0, 0), TransformComponent(10, 10));
 std::cin.get();
 }
private:
 Components mComponents;
 static Application* mApplication;
};
Application* Application::mApplication = nullptr;
class TestGame : public Application {
};
int main() {
 TestGame* testGame = new TestGame();
 testGame->Run();
 delete testGame;
 return 0;
}

Pros:

• It is cache-friendly
• It is relatively flexible

Cons:

• Template functions are slow
• The repeated typeid is very bad :)

I don't know if using variarg templates is the best option, because it means i have to use all of those typeids. Also, I feel like the variarg template functions aren't the best either, however the only alternatives I can think of are functions for each component, eg.

void AddTransformComponent(StringID gameObjectID, TransformComponent component);

or overloaded functions, such as

void AddComponent(StringID gameObjectID, TransformComponent component);

If there is any code which you need which is missing, please say.

Thanks for the help, and i would appreciate any advice.

• t3chb0t: Oh, there is code that is missing... what happened to //Data... or /* Data args... */? Can't I read c++ or have you removed anything? On Code Review you need to post complete code.
• user8780062: Thank you for the feedback. I have now edited the code and it compiles correctly on Visual Studio 2017.
• t3chb0t: Great! I now voted to reopen it. Could you tell us one more thing, which c++ version this is targetting?
• user8780062: I am currently targeting C++17. Hope that helps :)
• Cris Luengo: I don’t have time to write a full answer, but what is the point of the Application class? This construct looks like a way to try to legitimize global variables. Why not put the code in Run in main or at least a free function?

Answer 1

Note: I first looked at modernizing your code, after that, I've resolved your questions in the assumption you applied my suggestions.

Looking at your code, I'm a bit worried that you are trying to reeinvent some weels. First of all: SID and HashString.

I'm really worried about this, as it ain't as readable, predictable and performant as it could be.

Let's start with readable: Why would you redefine HashString to SID? This introduces an extra indirection that doesn't add any value. I can see some arguments of making an alias, however, as you are using C++17, just make it an inline function.

Secondly: Predictable. HashString returns a StringId. All std::hash return std::size_t. I suspect it's the same type, however, all your calculations use unsigned int instead of StringId. So any hash you create will have several zeros.

Finally: Performance. Your function accepts const char *. Why don't you use std::string_view instead? If you would have a std::string, it already knows the size, so you shouldn't recalculate it. It can still be called with a zero-terminated char*, in which case strlen will be called in the Ctor of the view.

As already said, it looks like a reimplementation of std::hash<std::string_view>. However, I see an argument in having your own hash function.

Still looking at the same function: fnv_prime is a constant. Why don't you use constexpr for it instead of const?

I also see a for-loop. Whenever, I see for (i = 0, I immediately worry about the scope of the variable, do we need it after the loop? Having to check this increases the complexity for me. How about for (unsigned int i = 0; i < len; ++i)? However, as you will be using std::string_view, it can become: for (auto c : str), even easier to read/understand;

Moving on: the Component class. Again, you have a constant that could be constexpr. However, I'm worried much more about mID. This ID is free to access for everyone and free to update. Make it private and provide a getter/setter for it.

Your constructor/dtor are implemented as {}, while this could be = default; and the move/copy ctor/assignment are missing. Best to check on the rule of 5.

Going forward: TransformComponent. Are you compiling with compiler warnings (-Weverything -Werror in Clang, /WX /W4 in MSVC)? You have a nice example of what is called shadowing. The member mPosition will never be initialized as you create a variable with the same name in a different scope. One could even wonder why you pass x and y separately, I would expect a single argument of type Vec2.

The struct Components creeps me out. Looking at it, its a really bad implementation of std::vector. Get rid of it! (And prereserve the vector if relevant).

AddComponents also looks pre-C++17. An alternative:

template <typename Arg, typename ... Args>
inline void AddComponents(StringID gameObjectID, Arg first, Args ... args) {
 // Do the work
 if constexpr (sizeof...(args))
 AddComponents(gameObjectID, args...);
}

Moving to CreateGameObject why do a c-style cast to char* when not needed?

Up to the Application class. This looks like an attempt for a singleton pattern. I would at least use std::cerr instead of std::cout for reporting failures. However, I'd even recommend assert. Your destructor also never resets the static to nullptr.

And a final remark for main: Why would you even allocate memory here. Try writing it as:

TestGame testGame{};
testGame.Run();
return 0;

Looking at your questions:

Templates ain't slow, please compile with optimizations: -O3 in clang, /O2 in MSVC. It might hurt you for compile time, however, it hurts less as having to write everything manually.

I agree, typeid is bad. You don't need it. Having the overload will work good enough without the runtime overhead. However, I wouldn't overload AddComponents on the type. I would have an overloaded function that returns you the correct std::vector. Much less code to duplicate, much easier to reuse at other places.

template<typename T>
auto &getStorage()
{
 if constexpr (std::is_same_v<T, TransformComponent>)
 return TransformComponents;
 else if constexpr (std::is_same_v<T, OtherComponent>)
 return OtherComponents;
}
template<typename T>
const auto &getStorage() const
{
 return const_cast<ThisType &>(*this).getStorage();
}

• user8780062: Thanks for the advice! Just one quick question. How would the overloaded function returning the vector be implemented? What would its declaration look like?
• JVApen: I've added a possible implementation. Another could be by having a templated function and specialized functions that return the right vector. As your example only contains a single type, its a bit hard to know how you are currently intending to store it.
• Cris Luengo: It took me a while to figure this out: "iso" = "instead of". Your answer would benefit if you wrote that out.