data_locality.cpp

#include <iostream>
#include <vector>
#include <array>
#include <chrono>

class AIComponent
{
public:
    void update()
    {
        x++;
        y++;
    }

private:
    int x = 0;
    int y = 0;
    int target = 0;
};

class PhysicsComponent
{
public:
    void update()
    {
        velocity += gravity;
    }

private:
    int gravity = 10;
    int velocity = 0;
    int mass = 1;
};

class RenderComponent
{
public:
    void update()
    {
        mesh++;
        texture++;
        shader++;
    }

private:
    int mesh = 0;
    int texture = 0;
    int shader = 0;
};

class Entity
{
public:
    Entity(AIComponent *ai, PhysicsComponent *physics, RenderComponent *render)
        : ai(ai), physics(physics), render(render)
    {
    }

    AIComponent *ai;
    PhysicsComponent *physics;
    RenderComponent *render;
};

int main()
{
    constexpr int numEntities = 10000;
    constexpr int numFrames = 10000;

    // ----- This is BAD -----
    std::vector<Entity *> entities(numEntities);
    for (int i = 0; i < numEntities; i++)
    {
        entities[i] = new Entity(new AIComponent(),
                                 new PhysicsComponent(),
                                 new RenderComponent());
    }

    auto start = std::chrono::system_clock::now();
    for (int frame = 0; frame < numFrames; frame++)
    {
        for (int i = 0; i < numEntities; i++)
        {
            entities[i]->ai->update();
        }

        for (int i = 0; i < numEntities; i++)
        {
            entities[i]->physics->update();
        }

        for (int i = 0; i < numEntities; i++)
        {
            entities[i]->render->update();
        }
    }
    auto end = std::chrono::system_clock::now();
    double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    std::cout << "elapsed: " << elapsed << " ms" << std::endl;

    // ----- This is GOOD -----
    std::vector<AIComponent> aiComponents(numEntities);
    std::vector<PhysicsComponent> physicsComponents(numEntities);
    std::vector<RenderComponent> renderComponents(numEntities);

    start = std::chrono::system_clock::now();
    for (int frame = 0; frame < numFrames; frame++)
    {
        for (int i = 0; i < numEntities; i++)
        {
            aiComponents[i].update();
        }

        for (int i = 0; i < numEntities; i++)
        {
            physicsComponents[i].update();
        }

        for (int i = 0; i < numEntities; i++)
        {
            renderComponents[i].update();
        }
    }
    end = std::chrono::system_clock::now();
    elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    std::cout << "elapsed: " << elapsed << " ms" << std::endl;
}

Game Programming Patterns, Chapter 17 Data Locality

• 連続したメモリにアクセスする方が速い
• ポインタの配列を使うとメモリが散らばるので遅い

$ g++ data_locality.cpp -O3; ./a.out
elapsed: 859 ms
elapsed: 134 ms