EnTTを使って大量のオブジェクトを扱う

この記事は[C++ Advent Calendar 2023](https://qiita.com/advent-calendar/2023/cxx)の10日目の記事です。

# はじめに
この記事はECS (Entity Component System)の説明と、
C++でECSの機能を提供する[EnTT](https://github.com/skypjack/entt)というライブラリの紹介です。

https://github.com/skypjack/entt?tab=readme-ov-file#code-example

DXライブラリを使ってポリゴンがいっぱい動いているウケの良い絵を作りたかったのですが、
別の部分で問題が発生して描画できなかったので、コンソールで確認できるコードになっています。

# 環境
Windowsで、Visual Studio2022、C++20を使用しています。
(C++17以上で動作します)

# ECS (Entity Component System)について

ECSについて、[Wikipedia](https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%B3%E3%83%86%E3%82%A3%E3%83%86%E3%82%A3%E3%83%BB%E3%82%B3%E3%83%B3%E3%83%9D%E3%83%BC%E3%83%8D%E3%83%B3%E3%83%88%E3%83%BB%E3%82%B7%E3%82%B9%E3%83%86%E3%83%A0)では以下のように説明されています。
>エンティティ・コンポーネント・システム（英語: Entity component system、ECS）とは、主にゲーム開発で使用されているソフトウェアアーキテクチャパターンである。ECSは継承よりコンポジションの原則に従うことで、より柔軟にエンティティを定義することを可能にする。エンティティとは、ゲームのシーンの中のすべての実体であるオブジェクトのことである（例えば、敵、銃弾、乗り物など）。すべてのエンティティは、付加的な振る舞いや機能を追加するものである１つ以上のコンポーネントから構成される。したがって、エンティティの振る舞いは、実行時にコンポーネントを追加あるいは削除することで変更可能である。これは、深く幅広い継承階層を除去し、その理解・保守・拡張が難しくなりあいまいになるという問題を取り除く。ECSの一般的なアプローチはデータ指向設計の手法と高い互換性を持ち、よく組み合わせられる。

なにやら難しそうなことを書いていますね。
まとめてみると
 - ECSとは設計の名前 (Unityだけで使われる機能名とかではない)
 - 継承を使いたくない
 - エンティティにコンポーネントを追加して、動き(振る舞い)を表現したい
 - データ指向設計に向いてる設計(ECS≠データ指向設計)
   
データ指向設計についての詳しい説明は割愛しますが、すごく簡単に説明すると
CPUが取り出しやすいようにメモリにデータを置くことを意識した設計で、
他にも拡張性、複雑さを減らせるなどのメリットがあります。

# コードを比較してみる

「コンポーネント」は、GameObjectクラスを使用したコンポーネントベースの設計でも登場します。
```main.cpp
#include <iostream>
#include <vector>
#include <memory>
#include <string>

class Component {
public:
    virtual void update() = 0;
    virtual ~Component() {}
};

class TransformComponent : public Component {
public:
    float _x, _y, _z;

    TransformComponent(float x = 0, float y = 0, float z = 0) : _x(x), _y(y), _z(z) {}

    void update() override {
        std::cout << "Transform: " << _x << ", " << _y << ", " << _z << std::endl;
    }
};

class GameObject {
private:
    std::vector<std::shared_ptr<Component>> _components;
    std::string _name;

public:
    GameObject(const std::string& name) : _name(name) {}

    template<typename T, typename... Args>
    void addComponent(Args&&... args) {
        _components.push_back(std::make_shared<T>(std::forward<Args>(args)...));
    }

    void update() {
        for (auto& component : _components) {
            component->update();
        }
    }
};

int main() {
    GameObject gameObject("Object1");

    gameObject.addComponent<TransformComponent>(1.0f, 2.0f, 3.0f);
    gameObject.update();

    return 0;
}
```
※このコードはECSではありません

詳しい説明を１行ずつしていく前に、先にEnTTを使用してこのコードをECSで書き換えて見ましょう。

EnTTにはこれをincludeするだけですぐ使える！という便利なものが
[https://github.com/skypjack/entt/blob/master/single_include/entt/entt.hpp](https://github.com/skypjack/entt/blob/master/single_include/entt/entt.hpp)
single_includeというところに用意されています。
「シングルヘッダ」とか「シングルファイル」とか呼ばれています。

これをダウンロードしてプロジェクトに追加します。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/852552/0da760a1-70c2-cc38-2089-4bd6755c305e.png)
画像ではvendorというフォルダを用意してそこに追加していますが、includeできればどこでも良いです。

EnTTではC++17以上でないと動かないので、プロジェクト -> [プロジェクト名]のプロパティから
C++17以上にします。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/852552/10c4f59c-0c11-f74f-6308-3062a2639c81.png)

コードはこんな感じになります
```main.cpp
#include "vendor/entt.hpp"
#include <iostream>

struct TransformComponent {
    float _x, _y, _z;

    TransformComponent(float x = 0, float y = 0, float z = 0) : _x(x), _y(y), _z(z) {}
};

int main() {
    entt::registry registry;

    entt::entity entity = registry.create();

    registry.emplace<TransformComponent>(entity, 1.0f, 2.0f, 3.0f);

    for (auto [entity, transform] : registry.view<TransformComponent>().each()) {
		std::cout << "Transform: " << transform._x << ", " << transform._y << ", " << transform._z << std::endl;
	}

    return 0;
}
```

GameObjectクラスの部分がEnTTの提供するEntityに置き換わり
かなり短くなりました。
補足
 - 分かりやすいようにentt:entity entityと書きましたが、autoでも良いです。
 - registry.view<TransformComponent>().each()はラムダを入れられるようになっていますが、
   私の環境ではIntelliSenseがうまく効かなかったのでこの形にしています。

## 解説

違いを挙げてみると
 - TransformComponentに振る舞いが入っていないし、structになっている
 - インターフェースであった親クラス(Componentクラス)が無い
 - GameObjectにくっついているコンポーネントをforで回しているのではなく
   コンポーネントがくっついているEntityをforで回している
 - registryというのが登場している
 - entity.addComponentになっていない

などがあります

### classとstructの違い
もしかしたら普段Unity/C#を使われる方がこの記事を読んでいるかもしれませんが、

C++におけるclassとstructの違いは
デフォルトのアクセス修飾子がclassはprivate、structはpublic
継承のデフォルトアクセス修飾子もclassはprivate、structはpublic
しか違いがありません。
用途的に、データの集合を表す場合structを使用するケースが多いです。

(C#の場合は機能的に多くの違いがあります)

### EntityとRegistry

Entityは実はただのIDで、型を辿るとuint32_tなので
```main.cpp
    for (auto [entity, transform] : registry.view<TransformComponent>().each()) {
        std::cout << (uint32_t)entity << std::endl;

		std::cout << "Transform: " << transform._x << ", " << transform._y << ", " << transform._z << std::endl;
	}
```
このようにキャストすると出力できます。
※ここがGameObjectとEntityの違いになります。

１つだと分かりづらいので、10個くらいEntityを生成してみましょう。
```main.cpp
#include "vendor/entt.hpp"
#include <iostream>

struct TransformComponent {
    float _x, _y, _z;

    TransformComponent(float x = 0, float y = 0, float z = 0) : _x(x), _y(y), _z(z) {}
};

int main() {
    entt::registry registry;

    for (size_t i = 0; i < 10; i++)
    {
        entt::entity entity = registry.create();
        registry.emplace<TransformComponent>(entity, 1.0f, 2.0f, 3.0f);
    }

    for (auto [entity, transform] : registry.view<TransformComponent>().each()) {
        std::cout << "entity: " << (uint32_t)entity << std::endl;

		std::cout << "Transform: " << transform._x << ", " << transform._y << ", " << transform._z << std::endl;
	}

    return 0;
}
```
結果は
```
entity: 9
Transform: 1, 2, 3
entity: 8
Transform: 1, 2, 3
entity: 7
Transform: 1, 2, 3
entity: 6
Transform: 1, 2, 3
entity: 5
Transform: 1, 2, 3
entity: 4
Transform: 1, 2, 3
entity: 3
Transform: 1, 2, 3
entity: 2
Transform: 1, 2, 3
entity: 1
Transform: 1, 2, 3
entity: 0
Transform: 1, 2, 3
```

registry.create()は被らないようにIDを発行してくれていることが分かります。
あとは何となくでも読めるかもしれませんが
```
registry.emplace<TransformComponent>(entity, 1.0f, 2.0f, 3.0f);
```
で、このentityにTransformComponentを紐づけます。
entityは前述のとおりただのIDなので、entity.addComponentとはできません。

```
for (auto [entity, transform] : registry.view<TransformComponent>().each()) {
```
で、TransformComponentがくっついているEntityをループで回しています。
このようにregistryはentityの管理をしてくれています。

entityをラップして、entity(自前のクラス).addComponent<Component>(args)とすることはできますが、
複数registryがあるとentity(ID)が被ってしまう可能性があること、
registry.viewを使用せずにforを使うと、オブジェクト指向設計の恩恵であるパフォーマンスが損なわれる可能性があることに注意してください。

# 設計的な嬉しさ
例えばGameObjectの例で
_dx, _dy, _dzを持つVelocityComponentを作成して
TransformComponentは_x, _y, _zに_dx, _dy, _dzを足すという動作を書こうとすると

TransformComponentはどこかでVelocityComponentを取得しなくてはいけなくなり、
コンポーネント間で依存関係ができてしまいます。
もしGameObjectにVelocityComponentが付いたり、付かなかったりすると、
nullptrチェックも入ってさらに複雑になります。
(この場合TransformComponentに持たせようみたいな結論になりそうですが)

EnTTを使用した場合
```main.cpp
#include "vendor/entt.hpp"
#include <iostream>

struct TransformComponent {
    float _x, _y, _z;

    TransformComponent(float x = 0, float y = 0, float z = 0) : _x(x), _y(y), _z(z) {}
};

struct VelocityComponent {
    float _dx, _dy, _dz;

    VelocityComponent(float dx = 0, float dy = 0, float dz = 0) : _dx(dx), _dy(dy), _dz(dz) {}
};

int main() {
    entt::registry registry;

    for (size_t i = 0; i < 10; i++)
    {
        entt::entity entity = registry.create();
        registry.emplace<TransformComponent>(entity, 1.0f, 2.0f, 3.0f);
        registry.emplace<VelocityComponent>(entity, 1.0f, 1.0f, 1.0f);
    }

    for (auto [entity, transform, velocity] : registry.view<TransformComponent, VelocityComponent>().each()) {
        transform._x += velocity._dx;
        transform._y += velocity._dy;
        transform._z += velocity._dz;
    }

    return 0;
}
```
このように、複数のコンポーネントに紐づくEntityを抽出できるので、コンポーネント間の依存関係を減らすことができます。

実際には
TransformComponent, MeshComponent, MaterialComponentがくっついていたら3D描画
TransformComponent, StripeComponentがくっついていたら2D描画
のようにviewを作って処理するという風に使っています。

# で、速いのか

なるべく条件を合わせて、GameObjectとEnTTを使ってECSで比較してみました
x64, debugで実行
GameObject版
```main.cpp
#include <iostream>
#include <vector>
#include <memory>
#include <string>
#include <chrono>

class Component {
public:
    virtual void update() = 0;
    virtual ~Component() {}
};

class TransformComponent : public Component {
public:
    float _x, _y, _z;

    TransformComponent(float x = 0, float y = 0, float z = 0) : _x(x), _y(y), _z(z) {}

    void update() override {
        _x += 1.0f;
		_y += 1.0f;
		_z += 1.0f;
    }
};

class GameObject {
private:
    std::vector<std::shared_ptr<Component>> _components;

public:
    GameObject(){}

    template<typename T, typename... Args>
    void addComponent(Args&&... args) {
        _components.push_back(std::make_shared<T>(std::forward<Args>(args)...));
    }

    void update() {
        for (auto& component : _components) {
            component->update();
        }
    }
};

int main() {
    auto start_creation = std::chrono::high_resolution_clock::now();

    std::vector<GameObject> gameObjects;
    // gameObject(1000000)とするのはフェアじゃなさそうなので1つずつpush_backしてます。
    for (size_t i = 0; i < 1000000; i++)
    {
        GameObject gameObject;
        gameObject.addComponent<TransformComponent>(1.0f, 2.0f, 3.0f);
        gameObjects.push_back(gameObject);
    }
    auto stop_creation = std::chrono::high_resolution_clock::now();
    auto duration_creation = std::chrono::duration_cast<std::chrono::milliseconds>(stop_creation - start_creation);
    std::cout << "GameObjectの作成とコンポーネントの追加: " << duration_creation.count() << " ミリ秒\n";

    auto start_modification = std::chrono::high_resolution_clock::now();

    for (auto& gameObject : gameObjects) {
        gameObject.update();
    }
    auto stop_modification = std::chrono::high_resolution_clock::now();
    auto duration_modification = std::chrono::duration_cast<std::chrono::milliseconds>(stop_modification - start_modification);
    std::cout << "コンポーネントの変更にかかった時間: " << duration_modification.count() << " ミリ秒\n";

    return 0;
}
```
GameObject版 実行結果

```
GameObjectの作成とコンポーネントの追加: 4454 ミリ秒
コンポーネントの変更にかかった時間: 106 ミリ秒
```

次にEnTTを使ったECS版
```main.cpp
#include "vendor/entt.hpp"
#include <iostream>
#include <chrono>

struct TransformComponent {
    float _x, _y, _z;

    TransformComponent(float x = 0, float y = 0, float z = 0) : _x(x), _y(y), _z(z) {}
};

int main() {
    entt::registry registry;
    auto start_creation = std::chrono::high_resolution_clock::now();

    for (size_t i = 0; i < 1000000; i++)
    {
        entt::entity entity = registry.create();
        registry.emplace<TransformComponent>(entity, 1.0f, 2.0f, 3.0f);
    }

    auto stop_creation = std::chrono::high_resolution_clock::now();
    auto duration_creation = std::chrono::duration_cast<std::chrono::milliseconds>(stop_creation - start_creation);
    std::cout << "エンティティの作成とコンポーネントの追加: " << duration_creation.count() << " ミリ秒\n";

    auto start_modification = std::chrono::high_resolution_clock::now();

    for (auto [entity, transform] : registry.view<TransformComponent>().each()) {
        transform._x += 1.0f;
        transform._y += 1.0f;
        transform._z += 1.0f;
	}

    auto stop_modification = std::chrono::high_resolution_clock::now();
    auto duration_modification = std::chrono::duration_cast<std::chrono::milliseconds>(stop_modification - start_modification);
    std::cout << "コンポーネントの変更にかかった時間: " << duration_modification.count() << " ミリ秒\n";

    return 0;
}
```

ECS版 実行結果

```
エンティティの作成とコンポーネントの追加: 4431 ミリ秒
コンポーネントの変更にかかった時間: 206 ミリ秒
```

作成にかかる時間は同じくらい。
変更は。。。あれ。。。
**EnTTを使った方が遅い！！！なんで！！！**

debugだったので、releaseに変更して実行してみる


GameObject版 実行結果

```
GameObjectの作成とコンポーネントの追加: 206 ミリ秒
コンポーネントの変更にかかった時間: 14 ミリ秒
```

ECS版 実行結果
```
エンティティの作成とコンポーネントの追加: 42 ミリ秒
コンポーネントの変更にかかった時間: 1 ミリ秒
```

**なんかすごい速い！！！逆になんで！！！**
0の数はちゃんと合っていました。

## 考えられる要因
データ指向設計が速いと言われている理由は、キャッシュヒット率にあります。

CPUはメインメモリから読み出したデータをCPU内のキャッシュメモリというところに置きます。
キャッシュメモリはメインメモリからデータを読むよりずっと高速です。

キャッシュヒット率は、メインメモリを見に行く前にキャッシュメモリを見て、
欲しいデータが存在する割合を指します。

「forを一周させるだけならキャッシュメモリは使われないんじゃない？？」と思われますが、
CPUには「次この辺読まれそうだな」と予測して先にキャッシュメモリに入れておく
**プリフェッチ**(ハードウェアプリフェッチ)という機能があります。

データ指向設計は、データをキレイにメモリに並べることと、ランダムアクセスを減らす事でキャッシュヒット率を上げています。

debugでECS版が遅かったのは
 - 最適化されていない状態ではキャッシュヒット率が低下している
 - includeしているentt.hppが大きい
が主な原因だと思われます。(全然違っていたらコメントください)
(CPUプロファイラを使ってキャッシュヒット率を調べたかったのですが、そこまでの余裕がありませんでした。。)

# まとめ
ちゃんと計測するのが大事。

# 参考
[https://github.com/skypjack/entt](https://github.com/skypjack/entt)
[https://ja.wikipedia.org/wiki/エンティティ・コンポーネント・システム](https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%B3%E3%83%86%E3%82%A3%E3%83%86%E3%82%A3%E3%83%BB%E3%82%B3%E3%83%B3%E3%83%9D%E3%83%BC%E3%83%8D%E3%83%B3%E3%83%88%E3%83%BB%E3%82%B7%E3%82%B9%E3%83%86%E3%83%A0)