[UE4] Memory Allocationについて

この記事ではUE4のmalloc(Memory Allocation)、
メモリアロケーターについて紹介していきたいと思います。

知らなくてもUnrealEngineを使うことはできますが、
概要だけでも理解しておくとメモリまわりの不具合を踏んだときに理解が早いかも、しれません。

## なぜメモリアロケーターが必要か
一般的に、必要な時に必要な分のメモリを確保しようとすると時間がかかるため、
独自に管理することで高速化を図ったり、トラッキング、エラーハンドリングを行います。
またUnreal Engineでは複数のプラットフォームに対応する上で、
メモリのアライメントに注意する必要があり関連する実装が含まれています。
メモリアライメントについては以下ページが非常にわかりやすいと思います。

**メモリアライメントの話 @ゲームプログラマの小話[開発:メモリ] - Qiita**
https://qiita.com/hoboaki/items/46700f03b522193e9747

## 各種環境によって変わってきます
UE4のメモリ管理は各環境によって変わってきます。
各プラットフォームでどのように行われているか確認したい場合は、
それぞれ確認する必要がありますが、今回はWindows向けの実装を中心に紹介していきます。

Windowsだと以下のフォルダにあるBaseAllocator()の実装をみると
メモリアロケーターの切り替えを行っています。
設定や引数で切り替えられるようになっているので、
各プラットフォームで変更してみたい場合はこちらを確認するとよいかと思います。
**.\Engine\Source\Runtime\Core\Private\Windows\WindowsPlatformMemory.cpp**
FMalloc* FWindowsPlatformMemory::BaseAllocator()
![2019-12-20_13h05_02.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/363894/5308640c-17f3-3aef-0f09-67846aba9eea.png)

例えばAndroidやUnixでは以下のようなファイルで実装されています。
**.\Engine\Source\Runtime\Core\Private\Android\AndroidPlatformMemory.cpp**
**.\Engine\Source\Runtime\Core\Private\Unix\UnixPlatformMemory.cpp**


アロケーターとしては以下のような種類の実装が存在しており、
Enumにそれぞれの説明が簡単に書かれています。

```c++
	enum EMemoryAllocatorToUse
	{
		Ansi, // Default C allocator
		Stomp, // Allocator to check for memory stomping
		TBB, // Thread Building Blocks malloc
		Jemalloc, // Linux/FreeBSD malloc
		Binned, // Older binned malloc
		Binned2, // Newer binned malloc
		Binned3, // Newer VM-based binned malloc, 64 bit only
		Platform, // Custom platform specific allocator
	};
```

UE4の独自のものとしてはBinned Allocatorが存在します。

## Binned Allocator
Binned Allocatorに関しては3つのものがあり、開発順にナンバリングされたものとなっています。
順に最適化が行われており、MallocBinned3に切り替えると数十MBのメモリ削減ができるケースもあるようです。
(タイトルの使用状況によっても結果は異なるかと思います。)

中身を見る前に事前知識として、仮想メモリやページングという単語について紹介していきます。

### 仮想メモリとページング
実際のメモリは1byte(8bit)ずつメモリの番地が振られて管理されていたりしますが、
効率よく扱うためにページという単位で扱うという手法があります。
これはたとえば4KB(4096byte)ずつの塊として、仮想の番地を割り当てるといったことをします。


イメージを掴むために、ものすごく単純化したものを図に示します。
まず物理メモリは1byteずつ1番地のアドレスが振られているとします。
<img width="465" alt="2019-12-23_06h33_22.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/363894/c666c099-281c-cb71-1fc1-f680a5bd1ea7.png">

次に物理メモリが総容量6byte、また2byteずつページングした図です。
仮想メモリは論理上のアドレスと参照先も持ち、
ページ化された物理メモリのアドレスの先頭が参照先のアドレスとして登録されています。 
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/363894/163a0005-ecc1-a838-0f8b-648eca1a031f.png)

仮想メモリ、仮想メモリアドレスと参照先を用意したときの利点は、
実際のメモリは間が空いていなくても連続したページを仮想メモリ上で割り当てることで
不連続なメモリを、プログラミング上などで連続したアドレスでメモリを使うことができます。
このような仕組みを仮想メモリやページングとよんでいます。
<img width="1394" alt="2019-12-23_14h52_09.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/363894/0640c506-85b3-c23b-8935-07370f47871c.png">


仮想メモリの考え方として物理のメモリ、そこで外部ディスクにデータを逃がす事が可能です。
仮想メモリのページ単位で転送を行い、仮想アドレスにマッピングを行うことで
物理メモリ以上のデータを扱うことが可能になる、という利点もあります。
<img width="1274" alt="2019-12-23_15h21_49.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/363894/51a476b8-0953-7383-cba0-26d20db6f52a.png">


上記は簡単にしていたので、実際にはもう少し考えないといけないことがあります。
仮想メモリのマッピングを参照先として先頭のアドレスを示していましたが、
実際の物理メモリはbyteごとの番地なので、
ページの中のどこを指し示したいのか、といった情報が必要になります。

そこでアドレスの中に2つの情報を含ませる、という方法がでてきます。
数字が大きくなってしまうので32bitベースのものを紹介しますが、
先頭の20bitでページの番号を指定し、残りの12bitでページ内のアドレスを指定するようにします。
このようにアドレスを持つことでメモリを指定します。
(これはページのサイズが4096byteになっていた理由に繋がります。）
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/363894/d8fbee20-e3e9-514f-208e-c808def74d63.png)

ここまでの例で、間接的にメモリを扱う利点が見えてきたかと思います。

**・参考リンク**
ページに関しては以下の情報もイメージを掴む上で分かりやすいかもしれません。
**ページング方式とは｜「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典**
https://wa3.i-3-i.info/word13352.html

**ページング方式 - Wikipedia**
https://ja.wikipedia.org/wiki/%E3%83%9A%E3%83%BC%E3%82%B8%E3%83%B3%E3%82%B0%E6%96%B9%E5%BC%8F

### Binned Allocatorの基本アルゴリズム
基本的な考え方としては、特定のサイズのメモリ(ブロック)をまとめて確保しメモリプールを作成します。

<img width="1250" alt="2019-12-25_04h40_17.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/363894/074f053c-5996-d495-80d7-1417ee00d664.png">

小さいサイズのメモリを使いたい場合は、
そのサイズからプールを選択して予め確保してあるブロックのメモリを使用します。
例えば16バイトより多く、32バイト以下の場合は32のブロックのプールの空いているブロック返し、
32バイトより多く、64バイト以下の場合は64のブロックのプールで空いているブロックを返します。
<img width="1283" alt="2019-12-25_04h49_22.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/363894/e49533ae-f221-6f35-e867-9c8ee3d5c856.png">

各ブロックのプールが足りなくなったり、
事前に用意していたサイズ以上のものが来たときには、随時確保を行います。
そしてこの時bit情報やハッシュテーブルを組み合わせて、
メモリのポインタからプールを特定しやすくしておき、
対象のポインターのブロックを効率的に探し出す、といったことを行っています。
Binned Allocatorの基本のアルゴリズムは以上のようになっています。

### Malloc Binnedの実装について
ここからはBinned Allocator(Malloc Binned)の中身を見ていきます。

#### 初期化について
Malloc Binnedの基本的な流れとしてはメモリのPoolを確保し、Poolからメモリを取得します。
このPoolの確保が少し特殊で、まずBlockのSizeをが以下のように、
8と16それ以降は16の倍数でBlockSizeを定義しています。
<img width="551" alt="2019-12-25_01h07_27.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/363894/927df6bb-26ca-8bf0-a321-5496cdbec2a5.png">

このBlockSizeをもとにPoolを作るためのPoolTableを初期化します。
<img width="457" alt="2019-12-25_01h10_21.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/363894/afc34f5a-7e60-4a01-98f6-4565696594ac.png">

そして次に登場するMemSizeToPoolTableが、必要とするメモリのサイズによって、
どのBlockサイズのPoolTableに格納するか、のマッピング用テーブルになります。
<img width="432" alt="2019-12-25_01h16_42.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/363894/9b1eba86-b0ac-4f74-498c-59faf4c6fb1a.png">

**ここまでが初期化過程になります。**

#### メモリ取得処理について(Malloc)

ここからメモリ取得時(Malloc)について見ていきます。
取得したいサイズによって4つの処理に分かれるようになっています。

##### 分岐1
まずは、SMALL_BLOCK_POOL_SIZEより小さいと実行されるコードです。
これは追ってみると主にiOS向けの特殊な実装のようです。その他プラットフォームだと0が設定されています。
<img width="695" alt="2019-12-25_01h27_13.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/363894/ca4904fb-d329-d753-b970-7a1dff47e13d.png">

##### 分岐2
次がSizeがBlockSizeで定義されているものの最大以下のものに関する処理です。
ここがメインとなる予め確保していたPoolを使う処理です。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/363894/0c6ce238-2514-61ca-576b-f627f007d2b0.png)

Poolがない場合はAllocatePoolMemoryでPoolの確保を行い、
Poolがあれば、AllocateBlockFromPoolで、Poolの中からひとつのBlockを割り当てます。

##### 分岐3
次がBlockサイズ以上かつ、特殊なサイズ以下のものについての処理です。
BinnedSizeLimitにBinnedSizeLimit/2を足したBlockサイズのPoolの処理です。
> Private::PAGE_SIZE_LIMIT ? BinnedSizeLimit+(BinnedSizeLimit/2) : 0;

基本的には2と同じ処理です。
<img width="900" alt="2019-12-25_01h52_51.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/363894/1c79b631-8e1c-5b62-fd5a-9becfb98a759.png">

##### 分岐4
それ以外が最後の処理です。求められたサイズからアラインを行い、確保を行います。
<img width="688" alt="2019-12-25_01h58_29.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/363894/bec436db-874b-4874-a80a-08b4ce40cfa0.png">

ここまでがメモリ取得(Malloc)の話になります。

#### Pool情報の探索について
最後に紹介したいのがPool情報を取得するGetPoolInfoについてです。
ここでメモリのポインタからどのPoolのものか探す、といった処理を行っています。
ポインタをキーに探索を行っていますが、詳しくは実装をご確認ください。
<img width="727" alt="2019-12-25_02h17_16.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/363894/719aeacd-7aaa-3fd5-122a-5b4aab16c452.png">
以上がMallocBinned(無印)の実装についての紹介になります。

#### MallocBinned2とMallocBinned3
ここからはMallocBinned2とMallocBinned3についての補足です。

##### MallocBinned2
基本的な考え方は無印と殆ど似ていますが、
実装自体が関数化されていたり、Statなど含まれていたり無印と比べて洗練されている印象です。
今回細かく実装を追えていませんが、キーとなるPool情報を取得するGetPoolInfoが、
2ではGetOrCreatePoolInfoになっているので、こちらを見ると良いかと思います。

##### MallocBinned3
1、2からの大きな変更点として仮想メモリのアドレス(論理メモリアドレス)を活用している点です。
まず論理メモリアドレスを予約し、こちらは広く使えるので、
メモリのポインタから対象のサイズのPoolを割り出せるように配置することにより、
PoolのIndex検索を高速に行えるようにしています。

実装を見る場合のポイントとしては、
AllocateVirtual関数で、仮想メモリの予約(Reserve)のみを行っており、
PushNewPoolToFrontからPointerを渡して実際のメモリを確保(Commit)を行います。

プラットフォーム固有の実装は、起点となっているXXXPlatformMemory.cppの方に行われています。
例えば、MallocBinned3で呼ばれているメモリの確保の実装は以下にあります。

```c++:\Engine\Source\Runtime\Core\Private\Windows\WindowsPlatformMemory.cpp
FWindowsPlatformMemory::FPlatformVirtualMemoryBlock FWindowsPlatformMemory::FPlatformVirtualMemoryBlock::AllocateVirtual(size_t InSize, size_t InAlignment)
void FWindowsPlatformMemory::FPlatformVirtualMemoryBlock::FreeVirtual()
void FWindowsPlatformMemory::FPlatformVirtualMemoryBlock::Commit(size_t InOffset, size_t InSize)
```

# その他アロケーターの紹介
ここからはその他のアロケーターについて紹介していきます。
基本的には外部ライブラリ等をラップしているようなモノが多いです。

## ANSI Allocator
基本的に各OSの機能を使って逐次確保、開放を行うアロケーターです。
WindowsではLow-fragmentation Heapという機能を有効化しているようです。
**Low-fragmentation Heap - Win32 apps | Microsoft Docs**
https://docs.microsoft.com/en-us/windows/win32/memory/low-fragmentation-heap?redirectedfrom=MSDN
![2019-12-20_13h32_57.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/363894/3cfc721a-f7e5-5bcd-b730-b2ca13564940.png)

## Stomp Allocator
Stompの特徴は物理メモリを解放しながら仮想アドレス範囲を予約したままにすることが特徴です。
この特徴から、メモリ解放後に別の箇所で同じポインタを使用してしまっていると例外を発生させます。
メモリのチェックを厳密に行っているものなので、なにかしら不具合をトラッキングしたい場合などに有効かと思います。
副作用として仮想アドレスと物理アドレスを紐付けるOSのページテーブルに大量のメモリを消費します。

Win10上のプロセスの仮想メモリ制限は128TBとなっていますが、
ソースコードのメモによるとInfiltratorデモを実行すると
1秒あたり最大700MBの仮想アドレススペースが消費されるそうです。

## TBB Allocator
TBBはIntelさんが提供するマルチスレッドを扱うためのライブラリです。
tbbがついているアロケーターは、TBBライブラリの機能を利用してメモリを管理しています。
**​Intel® Threading Building Blocks | Intel® Software** 
https://software.intel.com/en-us/tbb

UE4の実装としては以下のフォルダパスに存在し、TBBのscalable_allocatorに含まれる関数を使って
MallocやFreeがラップされている単純なものとなっております。
**.\Engine\Source\Runtime\Core\Private\HAL\MallocTBB.cpp**
![2019-12-20_13h03_04.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/363894/9017d6db-aac1-6f89-a7b2-7ff1bf52e280.png)

## Jemalloc
主にUnix系で使用されているメモリアロケーターで、jemallocというライブラリを使用しています。
**jemalloc**
http://jemalloc.net/
**jemalloc/jemalloc**
https://github.com/jemalloc/jemalloc

コメントを見るとFirefoxやFacebookのサーバーで使われているらしく調べてみましたが、
過去の情報しか見つからなかったので現在はどうなのか分かりません。
**Scalable memory allocation using jemalloc | Facebook**
https://www.facebook.com/notes/facebook-engineering/scalable-memory-allocation-using-jemalloc/480222803919/

# おわりに
今回はUE4で使用することができるMemory Allocatorの概要について紹介しました。
各プラットフォームで使用されている実装で最適なものは違ってくるかと思いますので、
この記事が入り口として参考になれば幸いです。