構造体の高速な使い方

使ってますか「構造体」。

C#に限らずですが、C#では特にGCを回避するためだったり、メモリレイアウトを決めたいときに役立ちます。
でもさらに高速化するためのテクニックがあるとしたら？今回はそんな構造体について考察していきたいと思います。

<!-- vim-markdown-toc GFM -->

* [ここで得られるもの](#ここで得られるもの)
* [検証環境](#検証環境)
* [本日のレシピ](#本日のレシピ)
* [構造体のパフォーマンスの違いを比べる](#構造体のパフォーマンスの違いを比べる)

<!-- vim-markdown-toc -->

## ここで得られるもの

* ちょっぴり得した気持ちになれる高速化

## 検証環境

| | |
| :---: | :--- |
| CPU | 2.4 GHz 8-Core Interl Core i9 |
| Memory | 32 GB 2667 MHz DDR4 |
| OS | Max OS Ventura 13.2.1 |
| Unity | 2021.3.16f1 |

## 本日のレシピ

* 構造体のパフォーマンスの違いを比べる
* なぜパフォーマンスに差がでるのかについて

## 構造体のパフォーマンスの違いを比べる

まず構造体を設計していきます。

キャラクタ情報を持つ **Simple** と **Ex** の2パターンの構造体を用意しました。
コメントにはフィールドが占有するバイト数を記載しています。

```csharp
struct CharacterSimple
{
  public Vector3 position;  // 12
  public Vector3 direction; // 12
  public float mass;        //  4
  public float speed;       //  4
}
```

```csharp
struct CharacterEx
{
  public Vector3 position;  // 12
  public Vector3 euler;     // 12
  public float mass;        //  4
  public float speed;       //  4
  public int agi;           //  4
  public int dex;           //  4
  public int str;           //  4
  public int vit;           //  4
  public int luk;           //  4
  public int maximumScore;  //  4
  public int winCount;      //  4
  public int loseCount;     //  4
}
```

次に、この構造体を利用してキャラクタ配列を簡単なループ計算をし、Stopwatchで時間を計測しそれぞれどのような差が出るかみていきます。

キャラクタの持つ `direction` に `speed` を掛け合わせた速度と `mass` から算出した重力速度 `g` を `position` に加えるというシンプルな計算式で計測しています。

```csharp
using System.Diagnostics;
using UnityEngine;

struct CharacterSimple
{
  public Vector3 position;  // 12
  public Vector3 direction; // 12
  public float mass;        //  4
  public float speed;       //  4
}

struct CharacterEx
{
  public Vector3 position;  // 12
  public Vector3 direction; // 12
  public float mass;        //  4
  public float speed;       //  4
  public int agi;           //  4
  public int dex;           //  4
  public int str;           //  4
  public int vit;           //  4
  public int luk;           //  4
  public int maximumScore;  //  4
  public int winCount;      //  4
  public int loseCount;     //  4
}

class Test : MonoBehaviour
{
	void Start()
	{
		const int count = 30000000;
		var gravity = new Vector3(0.0f, -9.8f, 0.0f);
		var simples = new CharacterSimple[count];
		var exs = new CharacterEx[count];
		var time = Random.Range(0, 1);

		var sw = Stopwatch.StartNew();
		for (var i = 0; i < count; ++i)
		{
			ref CharacterSimple player = ref simples[i];
			var velocity = player.direction * player.speed * time;
			var g = player.mass * gravity * time;
			player.position += (velocity + gravity);
		}
		var simpleTime = sw.ElapsedMilliseconds;

		sw.Reset();
		sw.Start();
		for (var i = 0; i < count; ++i)
		{
			ref CharacterEx player = ref exs[i];
			var velocity = player.direction * player.speed * time;
			var g = player.mass * gravity * time;
			player.position += (velocity + gravity);
		}
		var exTime = sw.ElapsedMilliseconds;

		UnityEngine.Debug.Log("Simple: " + simpleTime);
		UnityEngine.Debug.Log("Ex    : " + exTime);
	}
}
```

**Result:**
| Struct | Time(ms) |
| :---: | :---: |
| Simple | 3375 |
| Ex | 3677 |

**Simple** に比べ **Ex** の方は 約1.01倍もの時間がかかっていることが確認できました。ループ内のコードを同じなのに、なぜこういった差が出るのでしょう？

答えは、反復時に参照される構造体のサイズが原因です。CPUが計算を行うにはメモリに配置されている `position` や `direction` といったフィールドをロードする必要があります。CPUは `position` を参照する際、そのフィールドの `x` や `mass` の単体をロードするのではなく64byte単位でキャッシュという場所ににロードします。

データはRAMとCPUの間にある「キャッシュメモリ」というところでCPUが頻繁にアクセスするデータを高速に提供する役割を果たしています。そのキャッシュメモリ内には「キャッシュライン」というキャッシュメモリの最小単位のデータブロックを表した領域があり、CPUがメモリからデータを要求した場合、キャッシュラインは一度に転送され、その後のアクセスではキャッシュライン内のデータが使用されることになります。

テストコードにある `simples` 配列と `exs` 配列のメモリ配置の違いを見てみましょう。
| address | simples | exs |
| :---: | :---: | :---: |
| 0x00 | position.x | position.x |
| 0x04 | position.y | position.y |
| 0x08 | position.z | position.z |
| 0x0c | direction.x | direction.x |
| 0x10 | direction.y | direction.y |
| 0x14 | direction.z | direction.z |
| 0x18 | mass | mass |
| 0x1c | speed | speed |
| 0x20 | position.x | agi |
| 0x24 | position.y | dex |
| 0x28 | position.z | str |
| 0x2c | direction.x | vit |
| 0x30 | direction.y | luk |
| 0x34 | direction.z | maximumScore |
| 0x38 | mass | winCount |
| 0x3c | speed | loseCount |
| 0x40 | position.x | position.x |

このアドレス配置からもわかるように **exs** の方は **ex** 1つで64byte全体を占有しているのに対し、 **simples** の方は **simple** 2つでキャッシュライン全体を占有しています。

このため **ex** を反復処理する際、CPUは1つ目の計算が終わり2つ目の計算を行う場合、新しいキャッシュラインをRAMからロードする必要がでてきてしまいます。

それと比べ **simple** の方は一度に2つのデータが転送されているため、配列の2つ目の要素をRAMからロードするのではなく、既にキャッシュされているものを使用することができるため、ロード回数が削減されていることで高速化が為されています。

構造体を反復処理することがあらかじめわかっているような設計では、構造体のサイズを小さく保ちCPUキャッシュを効率的に使用することができるようになるため、ゲーム開発といった多数のオブジェクトが存在しがちな環境ではより力を発揮します。

ですが、ナノ秒世界の話でもあり、昨今のハードウェアの性能はバカみたいに強いのと、UnrealEngineやUnityといったミドルウェアに内包されているような低レベルのグラフィックスやPhysicsといったところで役に立ちがちな最適化でもあるため、ここに時間を費やさなくても良い環境が揃っていたりするのでなんともなところではあります。