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.

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();
}