Storage container for components of entities (ECS)

Question

Overview
After playing a while with the ECS implementation of the Unity engine and liking it very much I decided to try recreate it as a challenge. As part of this challenge I need a way of storing the components grouped by entity; I solved this by creating a container called a Chunk.

Unity uses archetypes to group components together and stores these components in pre-allocated chunks of fixed size.

I made a simple design of my implementation as clarification:

Here Archetype is a linked list of chunks; the chunks contain arrays of all the components that make the archetype - in this case Comp1, Comp2 and Comp3. Once a chunk is full a new chunk is allocated and can be filled up and so on.

The chunk itself is implemented like this:

With this solution I can store the components grouped by entity while making optimal use of storage and cache because the components are tightly packed in an array. Because of the indirection provided by the array of indices I am able to delete any component and move the rest of the components down to make sure there aren't any holes.

Questions
I have some items I'd like feedback on in order to improve myself

• Is the code clear and concise?
• Are there any obvious performance improvements?
• Because this is my first somewhat deep-dive in templates, are there any STL solutions I could've used that I have missed?

Code

• chunk.h
  Contains the container.

#pragma once

#include "utils.h"
#include "entity.h"

#include <cstdint>
#include <tuple>

template<size_t Capacity, typename ...Components>
class chunk
{

public:
    struct index
    {
        uint16_t id;
        uint16_t index;
        uint16_t next;
    };

    chunk()
        :
        m_enqueue(Capacity - 1),
        m_dequeue(0),
        m_object_count(0)
    {
        static_assert((Capacity & (Capacity - 1)) == 0, "number should be power of 2");

        for (uint16_t i = 0; i < Capacity; i++)
        {
            m_indices[i].id = i;
            m_indices[i].next = i + 1;
        }
    }

    const uint16_t add()
    {
        index& index = m_indices[m_dequeue];
        m_dequeue = index.next;
        index.id += m_new_id;
        index.index = m_object_count++;

        return index.id;
    }

    void remove(uint16_t id)
    {
        index& index = m_indices[id & m_index_mask];
        
        tuple_utils<Components...>::tuple_array<Capacity, Components...>::remove_item(index.index, m_object_count, m_items);

        m_indices[id & m_index_mask].index = index.index;

        index.index = USHRT_MAX;
        m_indices[m_enqueue].next = id & m_index_mask;
        m_enqueue = id & m_index_mask;
    }

    template<typename... ComponentParams>
    constexpr void assign(uint16_t id, ComponentParams&... value)
    {
        static_assert(arg_types<Components...>::contain_args<ComponentParams...>::value, "Component type does not exist on entity");

        index& index = m_indices[id & m_index_mask];
        tuple_utils<Components...>::tuple_array<Capacity, ComponentParams...>::assign_item(index.index, m_object_count, m_items, value...);
    }

    template<typename T>
    constexpr T& get_component_data(uint16_t id)
    {
        static_assert(arg_types<Components...>::contain_type<T>::value, "Component type does not exist on entity");

        index& index = m_indices[id & m_index_mask];
        return std::get<T[Capacity]>(m_items)[index.index];
    }

    inline const bool contains(uint16_t id) const
    {
        const index& index = m_indices[id & m_index_mask];
        return index.id == id && index.index != USHRT_MAX;
    }

    inline const uint32_t get_count() const
    {
        return m_object_count;
    }

    static constexpr uint16_t get_capacity() 
    {
        return Capacity;
    }

private:
    static constexpr uint16_t m_index_mask = Capacity - 1;
    static constexpr uint16_t m_new_id = m_index_mask + 1;

    uint16_t m_enqueue;
    uint16_t m_dequeue;
    uint16_t m_object_count;
    index m_indices[Capacity] = {};
    std::tuple<Components[Capacity]...> m_items;
};

• utils.h
  Contains utility functions for templates used by the chunk class.

// utils.h
#pragma once

#include <tuple>
#include <type_traits>
#include <algorithm>

// get total size of bytes from argumant pack
template<typename First, typename... Rest>
struct args_size
{
    static constexpr size_t value = args_size<First>::value + args_size<Rest...>::value;
};

template <typename T>
struct args_size<T>
{
    static constexpr size_t value = sizeof(T);
};

template<typename... Args>
struct arg_types
{
    //check if variadic template contains types of Args
    template<typename First, typename... Rest>
    struct contain_args
    {
        static constexpr bool value = std::disjunction<std::is_same<First, Args>...>::value ? 
            std::disjunction<std::is_same<First, Args>...>::value : 
            contain_args<Rest...>::value;
    };

    template <typename Last>
    struct contain_args<Last> 
    {
        static constexpr bool value = std::disjunction<std::is_same<Last, Args>...>::value;
    };

    //check if variadic template contains type of T
    template <typename T>
    struct contain_type : std::disjunction<std::is_same<T, Args>...> {};
};

template<typename... Args>
struct tuple_utils
{
    // general operations on arrays inside tuple
    template<size_t Size, typename First, typename... Rest>
    struct tuple_array
    {
        static constexpr void remove_item(size_t index, size_t count, std::tuple<Args[Size]...>& p_tuple)
        {
            First& item = std::get<First[Size]>(p_tuple)[index];
            item = std::get<First[Size]>(p_tuple)[--count];
            tuple_array<Size, Rest...>::remove_item(index, count, p_tuple);
        }

        static constexpr void assign_item(size_t index, size_t count, std::tuple<Args[Size]...>& p_tuple, const First& first, const Rest&... rest)
        {
            std::get<First[Size]>(p_tuple)[index] = first;
            tuple_array<Size, Rest...>::assign_item(index, count, p_tuple, rest...);
        }
    };

    template <size_t Size, typename Last>
    struct tuple_array<Size, Last>
    {
        static constexpr void remove_item(size_t index, size_t count, std::tuple<Args[Size]...>& p_tuple)
        {
            Last& item = std::get<Last[Size]>(p_tuple)[index];
            item = std::get<Last[Size]>(p_tuple)[--count];
        }

        static constexpr void assign_item(size_t index, size_t count, std::tuple<Args[Size]...>& p_tuple, const Last& last)
        {
            std::get<Last[Size]>(p_tuple)[index] = last;
        }
    };
};

Usage

    auto ch = new chunk<2 * 2, TestComponent1, TestComponent2>();
    auto id1 = ch->add();
    auto id2 = ch->add();
    auto contains = ch->contains(id1);

    ch->assign(id1, TestComponent2{ 5 });
    ch->assign(id2, TestComponent1{ 2 });

    ch->remove(id1);

Tests

#include "chunk.h"

#define CATCH_CONFIG_MAIN
#include "catch.h"

struct TestComponent1
{
    int i;
};

struct TestComponent2
{
    int j;
};

struct TestComponent3
{
    char t;
};


SCENARIO("Chunk can be instantiated")
{
    GIVEN("A Capacity of 4 * 4 and 3 component types as template parameters")
    {
        chunk<4 * 4, TestComponent1, TestComponent2, TestComponent3> testChunk;

        THEN("Chunk has Capacity of 4 * 4 and is empty")
        {
            REQUIRE(testChunk.get_capacity() == 4 * 4);
            REQUIRE(testChunk.get_count() == 0);
        }
    }
}

SCENARIO("Items can be added and removed from chunk")
{
    GIVEN("A Capacity of 4 * 4 and 3 component types as template parameters")
    {
        chunk<4 * 4, TestComponent1, TestComponent2, TestComponent3> testChunk;

        auto entityId = 0;

        WHEN("Entity is added to chunk")
        {
            entityId = testChunk.add();

            THEN("Chunk contains entity with id")
            {
                REQUIRE(testChunk.contains(entityId));
                REQUIRE(testChunk.get_count() == 1);
            }           
        }

        WHEN("Entity is removed from chunk")
        {
            testChunk.remove(entityId);

            THEN("Chunk does not contain entity with id")
            {
                REQUIRE(!testChunk.contains(entityId));
                REQUIRE(testChunk.get_count() == 0);
            }
        }
    }
}

SCENARIO("Items can be given a value")
{
    GIVEN("A Capacity of 4 * 4 and 3 component types as template parameters with one entity")
    {
        // prepare
        chunk<4 * 4, TestComponent1, TestComponent2, TestComponent3> testChunk;
        auto entity = testChunk.add();
        auto value = 5;

        WHEN("entity is given a type TestComponent2 with a value of 5")
        {
            testChunk.assign(entity, TestComponent2{ value });

            THEN("entity has component of type TestComponent2 with value of 5")
            {
                auto component = testChunk.get_component_data<TestComponent2>(entity);
                REQUIRE(component.j == value);
            }
        }
    }
}

Answer 1

Answers to your questions

Is the code clear and concise?

That's definitely a yes.

Are there any obvious performance improvements?

That is hard to say. For generic use, I think it will do just fine. However, if the components are very small, the overhead of m_indices might become noticable. A bitmask to mark which elements are in use might be better then. Also, there might be access patterns that could benefit from a different implementation. If you add a lot of entities, then use the entities, then delete all of them and start over, you wasted cycles keeping track of the indices. But again, for generic use it looks fine. Use a profiling tool like Linux's perf tools to measure performance bottlenecks, and if you see you spend a lot of cycles in the member functions of class chunk, you can then decide whether another approach might be better.

Because this is my first somewhat deep-dive in templates, are there any STL solutions I could've used that I have missed?

The list-of-chunks looks a lot like what std::deque does. You could use a std::deque in your class archetype, and not have a class chunk. The only issue is that std::deque hides the chunks it uses internally from you. So you if you go this way, you probably cannot initialize the indices like you did in class chunk, but have to do this in a more dynamic way.

Assert that you don't overflow uint16_t variables

The template parameter Capacity is a size_t, but you use uint16_t indices. Add a static_assert() to ensure you don't overflow the index variables. Note: static_assert()s are declarations, not statements, so you don't have to put them inside a member function.

Add runtime assert()s

Apart from compile-time checks, it might also be useful to add run-time checks to ensure errors are caught early in debug builds. For example, in Chunk::add() you should assert(m_object_count < Capacity).

Consider combining add() and assign()

When reading your code, I was wondering why add() and remove() looked so different. Adding a new entity is apparently a two-step process: first you call add() to reserve an ID, and then you assign() values to the components of that ID. Why not make this a one-step process?

High bits in IDs

You seem to be using the high bits as a kind of generation counter. Is this doing anything useful? If Capacity is set to 65536, then there are no high bits left, so you can't be relying on this. I would avoid this altogether, this way you can remove m_index_mask, m_new_id and all the & m_index_mask operations.

Try to make your class look and act like STL containers

The standard library containers all have a similar interface; you only have to learn it once and you can apply this knowledge on all the containers it provides. It helps if you follow the same conventions, so you don't have to learn and use different terms for your classes. Mostly, it's just renaming a few member functions:

• add() -> insert() (just like std::set)
• remove() -> erase()
• get_component_data() -> get() (just like std::tuple)
• get_count() -> size()
• get_capacity() -> capacity()

You also might want to add some functions commonly found in STL containers, such as empty() and clear(). Most importantly, I assume you want to loop over all entities at some point and call a function on each of them. For this, it helps if you add iterators to this class, so they can be used in range-based for-loops, in STL algorithms, and makes it easy to interact with anything else that supports iterators.

Answer 2

This answer about the use of inline:

https://stackoverflow.com/a/29796839/313768

is very educational; in particular

Another way to mark a function as inline is to define (not just declare) it directly in a class definition. Such a function is inline automatically, even without the inline keyword.

There's no advantage to explicitly declaring inline where you've done it. Trust your compiler.