5
\$\begingroup\$

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:

implementation diagram

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:

chunk diagram

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);
            }
        }
    }
}
\$\endgroup\$
2
  • \$\begingroup\$ is there any tests? \$\endgroup\$
    – Sugar
    Oct 9, 2020 at 15:48
  • \$\begingroup\$ @Sugar I have added some unit tests \$\endgroup\$ Oct 9, 2020 at 15:54

2 Answers 2

4
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ Thanks for your excellent feedback, lots to think about. I get the feedback on the Indices being overhead but it allows me to access items by id in o(1), without it I would not be able to couple an entity id to and index in the component array and would getting items by id become o(n). In cases of multiple insert and deletion it would indeed cost cycles so I think I need to check what will be the most common operation, I have failed to see an solution providing optimal performance in both cases. \$\endgroup\$ Oct 12, 2020 at 7:51
  • 1
    \$\begingroup\$ @RickNijhuis Keep in mind that O(1) is only faster than O(N) for "large enough" values of N. On modern CPUs, you can get the first empty position in a 64-bit bitmask with a single instruction. \$\endgroup\$
    – G. Sliepen
    Oct 12, 2020 at 8:18
  • \$\begingroup\$ @G.SIiepen I already know the first empty position though, this because the component arrays are tightly packed(the count of items + 1). In order to keep it like that I can't rely on using an index as entity id because the index of components can change if another component is deleted, this in order to keep the arrays tightly packed. I am not sure if I misunderstood your comment but I don't think I can use a bitmask to link an entity id to the index of components belonging to that entity. \$\endgroup\$ Oct 12, 2020 at 8:44
  • \$\begingroup\$ I do think the struct index array m_indices can be changed to an plain array of integers, this will reduce some of the memory cost per entity. \$\endgroup\$ Oct 12, 2020 at 8:49
  • \$\begingroup\$ @RickNijhuis You could consider making index and entity ID the same. With bitmasks, skipping over unused indices is very fast. If your chunks only contain up to 64 entities, then I think using a bitmask will certainly improve performance, but whether it is worth it depends on the rest of the application. For chunks with much more entities in them, your approach might still be the fastest. But the only way to be sure is to measure both approaches with a realistic workload. \$\endgroup\$
    – G. Sliepen
    Oct 12, 2020 at 9:28
3
\$\begingroup\$

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.

\$\endgroup\$
1
  • 3
    \$\begingroup\$ Trust :-) Just accept your compiler is better than you at its one job (unless you happen to be a compiler engineer, then its your job to make that shit work). ;-) Comming from a compiler background humans are horrible at understanding what is best to "function"-inline (just horrible). You may think you know but you don't (unless you are a compiler engineer and have the handful of extra tools you need to compiler the million other ways and verify). \$\endgroup\$ Oct 9, 2020 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.