構造体の高速な使い方

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

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

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

ここで得られるもの

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

検証環境

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パターンの構造体を用意しました。
コメントにはフィールドが占有するバイト数を記載しています。

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 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 に加えるというシンプルな計算式で計測しています。

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といったところで役に立ちがちな最適化でもあるため、ここに時間を費やさなくても良い環境が揃っていたりするのでなんともなところではあります。