引言

說到 C++ 的內存管理，我們可能會想到棧空間的本地變量、堆上通過 new 動態分配的變量以及全局命名空間的變量等，這些變量的分配位置都是由系統來控制管理的，而調用者只需要考慮變量的生命周期相關內容即可，而無需關心變量的具體布局。這對于普通軟件的開發已經足夠，但對于引擎開發而言，我們必須對內存有著更為精細的管理。

基礎概念

在文章的開篇，先對一些基礎概念進行簡單的介紹，以便能夠更好地理解后續的內容。

內存布局

如圖，描述了C++程序的內存分布。

Code Segment（代碼區）

也稱Text Segment，存放可執行程序的機器碼。

Data Segment (數據區）

存放已初始化的全局和靜態變量， 常量數據（如字符串常量）。

BSS（Block started by symbol)

存放未初始化的全局和靜態變量。（默認設為0）

Heap（堆）

從低地址向高地址增長。容量大于棧，程序中動態分配的內存在此區域。

Stack（棧）

從高地址向低地址增長。由編譯器自動管理分配。程序中的局部變量、函數參數值、返回變量等存在此區域。

函數棧

如上圖所示，可執行程序的文件包含BSS，Data Segment和Code Segment，當可執行程序載入內存后，系統會保留一些空間，即堆區和棧區。堆區主要是動態分配的內存（默認情況下），而棧區主要是函數以及局部變量等（包括main函數）。一般而言，棧的空間小于堆的空間。

當調用函數時，一塊連續內存(堆棧幀）壓入棧；函數返回時，堆棧幀彈出。

堆棧幀包含如下數據：

① 函數返回地址 ② 局部變量/CPU寄存器數據備份

全局變量

當全局/靜態變量（如下代碼中的x和y變量）未初始化的時候，它們記錄在BSS段。

?

?

int?x;
int?z?=?5;
void?func()
{
?????static?int?y;
}
int?main()
{
????return?0;
}

?

?

處于BSS段的變量的值默認為0，考慮到這一點，BSS段內部無需存儲大量的零值，而只需記錄字節個數即可。

系統載入可執行程序后，將BSS段的數據載入數據段(Data Segment） ，并將內存初始化為0，再調用程序入口（main函數）。

而對于已經初始化了的全局/靜態變量而言，如以上代碼中的z變量，則一直存儲于數據段(Data Segment)。

內存對齊

對于基礎類型，如float, double, int, char等，它們的大小和內存占用是一致的。而對于結構體而言，如果我們取得其sizeof的結果，會發現這個值有可能會大于結構體內所有成員大小的總和，這是由于結構體內部成員進行了內存對齊。

為什么要進行內存對齊

① 內存對齊使數據讀取更高效

在硬件設計上，數據讀取的處理器只能從地址為k的倍數的內存處開始讀取數據。這種讀取方式相當于將內存分為了多個"塊“，假設內存可以從任意位置開始存放的話，數據很可能會被分散到多個“塊”中，處理分散在多個塊中的數據需要移除首尾不需要的字節，再進行合并，非常耗時。

為了提高數據讀取的效率，程序分配的內存并不是連續存儲的，而是按首地址為k的倍數的方式存儲；這樣就可以一次性讀取數據，而不需要額外的操作。

② 在某些平臺下，不進行內存對齊會崩潰

內存對齊的規則

定義有效對齊值（alignment）為結構體中 最寬成員 和 編譯器/用戶指定對齊值 中較小的那個。

(1) 結構體起始地址為有效對齊值的整數倍

(2) 結構體總大小為有效對齊值的整數倍

(3) 結構體第一個成員偏移值為0，之后成員的偏移值為 min(有效對齊值, 自身大小) 的整數倍

相當于每個成員要進行對齊，并且整個結構體也需要進行對齊。

示例

?

?

struct?A
{
????int?i;
????char?c1;
????char?c2;
};

int?main()
{
????cout?<

	

	?

	?

	內存碎片

	程序的內存往往不是緊湊連續排布的，而是存在著許多碎片。我們根據碎片產生的原因把碎片分為內部碎片和外部碎片兩種類型：

	(1) 內部碎片：系統分配的內存大于實際所需的內存（由于對齊機制）；

	(2) 外部碎片：不斷分配回收不同大小的內存，由于內存分布散亂，較大內存無法分配；

	

	為了提高內存的利用率，我們有必要減少內存碎片，具體的方案將在后文重點介紹。

	繼承類布局

	繼承

	如果一個類繼承自另一個類，那么它自身的數據位于父類之后。

	含虛函數的類

	如果當前類包含虛函數，則會在類的最前端占用4個字節，用于存儲虛表指針（vpointer)，它指向一個虛函數表（vtable)。

	vtable中包含當前類的所有虛函數指針。

	字節序（endianness)

	大于一個字節的值被稱為多字節量，多字節量存在高位有效字節和低位有效字節 (關于高位和低位，我們以十進制的數字來舉例，對于數字482來說，4是高位，2是低位），微處理器有兩種不同的順序處理高位和低位字節的順序：

	● 小端（little_endian)：低位有效字節存儲于較低的內存位置

	● 大端（big_endian)：高位有效字節存儲于較低的內存位置

	我們使用的PC開發機默認是小端存儲。

	

	一般情況下，多字節量的排列順序對編碼沒有影響。但如果要考慮跨平臺的一些操作，就有必要考慮到大小端的問題。如下圖，ue4引擎使用了PLATFORM_LITTLE_ENDIAN 這一宏，在不同平臺下對數據做特殊處理（內存排布交換，確保存儲時的結果一致）。

	

	ue4針對大小端對數據做特殊處理（ByteSwap.h)

	操作系統

	對一些基礎概念有所了解后，我們可以來關注操作系統底層的一些設計。在掌握了這些特性后，我們才能更好地針對性地編寫高性能代碼。

	SIMD

	SIMD，即Single Instruction Multiple Data，用一個指令并行地對多個數據進行運算，是CPU基本指令集的擴展。

	例一

	處理器的寄存器通常是32位或者64位的，而圖像的一個像素點可能只有8bit，如果一次只能處理一個數據比較浪費空間；此時可以將64位寄存器拆成8個8位寄存器，就可以并行完成8個操作，提升效率。

	例二

	SSE指令采用128位寄存器，我們通常將4個32位浮點值打包到128位寄存器中，單個指令可完成4對浮點數的計算，這對于矩陣/向量操作非常友好（除此之外，還有Neon/FPU等寄存器）

	

	高速緩存

	一般來說CPU以超高速運行，而內存速度慢于CPU，硬盤速度慢于內存。

	當我們把數據加載內存后，要對數據進行一定操作時，會將數據從內存載入CPU寄存器。考慮到CPU讀/寫主內存速度較慢，處理器使用了高速的緩存（Cache)，作為內存到CPU中間的媒介。

	

	引入L1和L2緩存后，CPU和內存之間的將無法進行直接的數據交互，而是需要經過兩級緩存（目前也已出現L3緩存）。

	① CPU請求數據：如果數據已經在緩存中，則直接從緩存載入寄存器；如果數據不在緩存中（緩存命中失敗），則需要從內存讀取，并將內存載入緩存中。

	② CPU寫入數據：有兩種方案，(1) 寫入到緩存時同步寫入內存（write through cache) (2) 僅寫入到緩存中，有必要時再寫入內存(write-back)。

	為了提高程序性能，則需要盡可能避免緩存命中失敗。一般而言，遵循盡可能地集中連續訪問內存，減少”跳變“訪問的原則（locality of reference)。這里其實隱含了兩個意思，一個是內存空間上要盡可能連續，另外一個是訪問時序上要盡可能連續。像節點式的數據結構的遍歷就會差于內存連續性的容器。

	虛擬內存

	虛擬內存，也就是把不連續的物理內存塊映射到虛擬地址空間（virtual address space)。使內存頁對于應用程序來說看起來是連續的。一般而言，出于程序安全性和物理內存可能不足的考慮，我們的程序都會運行在虛擬內存上。

	這意味著，每個程序都有自己的地址空間，我們使用的內存存在一個虛擬地址和一個物理地址，兩者之間需要進行地址翻譯。

	缺頁

	在虛擬內存中，每個程序的地址空間被劃分為多個塊，每個內存塊被稱作頁，每個頁的包含了連續的地址，并且被映射到物理內存。并非所有頁都在物理內存中，當我們訪問了不在物理內存中的頁時，這一現象稱為缺頁，操作系統會從磁盤將對應內容裝載到物理內存；當內存不足，部分頁也會寫回磁盤。

	在這里，我們將CPU，高速緩存和主存視為一個整體，統稱為DRAM。由于DRAM與磁盤之間的讀寫也比較耗時，為了提高程序性能，我們依然需要確保自己的程序具有良好的“局部性”——在任意時刻都在一個較小的活動頁面上工作。

	分頁

	當使用虛擬內存時，會通過MMU將虛擬地址映射到物理內存，虛擬內存的內存塊稱為頁，而物理內存中的內存塊稱為頁框，兩者大小一致，DRAM和磁盤之間以頁為單位進行交換。

	簡單來說，如果想要從虛擬內存翻譯到物理地址，首先會從一個TLB（Translation Lookaside Buffer)的設備中查找，如果找不到，在虛擬地址中也記錄了虛擬頁號和偏移量，可以先通過虛擬頁號找到頁框號，再通過偏移量在對應頁框進行偏移，得到物理地址。為了加速這個翻譯過程，有時候還會使用多級頁表，倒排頁表等結構。

	置換算法

	到目前為止，我們已經接觸了不少和“置換”有關的內容：例如寄存器和高速緩存之間，DRAM 和磁盤之間，以及 TLB 的緩存等。這個問題的本質是，我們在有限的空間內存儲了一些快速查詢的結構，但是我們無法存儲所有的數據，所以當查詢未命中時，就需要花更大的代價，而所謂置換，也就是我們的快速查詢結構是在不斷更新的，會隨著我們的操作，使得一部分數據被裝在到快速查詢結構中，又有另一部分數據被卸載，相當于完成了數據的置換。

	常見的置換有如下幾種：

	● 最近未使用置換（NRU）

	出現未命中現象時，置換最近一個周期未使用的數據。

	● 先入先出置換（FIFO)

	出現未命中現象時，置換最早進入的數據。

	● 最近最少使用置換（LRU)

	出現未命中現象時，置換未使用時間最長的數據。

	C++語法

	位域（Bit Fields）

	表示結構體位域的定義，指定變量所占位數。它通常位于成員變量后，用 聲明符：常量表達式 表示。（參考資料）

	聲明符是可選的，匿名字段可用于填充。

	以下是ue4中Float16的定義：
struct
{
#if?PLATFORM_LITTLE_ENDIAN
????uint16?Mantissa?:?10;
????uint16?Exponent?:?5;
????uint16?Sign?:?1;
#else
????uint16?Sign?:?1;
????uint16?Exponent?:?5;
????uint16?Mantissa?:?10;???
#endif
}?Components;


	new 和 placement new

	new是C++中用于動態內存分配的運算符，它主要完成了以下兩個操作：

	① 調用operator new()函數，動態分配內存。

	② 在分配的動態內存塊上調用構造函數，以初始化相應類型的對象，并返回首地址。

	當我們調用new時，會在堆中查找一個足夠大的剩余空間，分配并返回；當我們調用delete時，則會將該內存標記為不再使用，而指針仍然執行原來的內存。

	new的語法
::(optional)?new?(placement_params)(optional)?(?type?)?initializer(optional)?


	● 一般表達式
p_var?=?new?type(initializer);?//?p_var?=?new?type{initializer};


	● 對象數組表達式
p_var?=?new?type[size];?//?分配
delete[]?p_var;?//?釋放


	● 二維數組表達式
auto?p?=?new?double[2][2];
auto?p?=?new?double[2][2]{?{1.0,2.0},{3.0,4.0}?};


	● 不拋出異常的表達式

	new?(nothrow)?Type?(optional-initializer-expression-list)

	默認情況下，如果內存分配失敗，new運算符會選擇拋出std::bad_alloc異常，如果加入nothrow，則不拋出異常，而是返回nullptr。

	● 占位符類型

	我們可以使用placeholder type（如auto/decltype）指定類型：

	auto?p?=?new?auto('c');

	● 帶位置的表達式（placement new）

	可以指定在哪塊內存上構造類型。

	它的意義在于我們可以利用placement new將內存分配和構造這兩個模塊分離（后續的allocator更好地踐行了這一概念），這對于編寫內存管理的代碼非常重要，比如當我們想要編寫內存池的代碼時，可以預申請一塊內存，然后通過placement new申請對象，一方面可以避免頻繁調用系統new/delete帶來的開銷，另一方面可以自己控制內存的分配和釋放。

	預先分配的緩沖區可以是堆或者棧上的，一般按字節(char)類型來分配，這主要考慮了以下兩個原因：

	① 方便控制分配的內存大小（通過sizeof計算即可）

	② 如果使用自定義類型，則會調用對應的構造函數。但是既然要做分配和構造的分離，我們實際上是不期望它做任何構造操作的，而且對于沒有默認構造函數的自定義類型，我們是無法預分配緩沖區的。

	以下是一個使用的例子：
class?A
{
private:
?int?data;
public:
?A(int?indata)?
??:?data(indata)?{?}
?void?print()
?{
??cout?<

	和數組越界訪問不一定崩潰類似，這里如果在未分配的內存上執行placement new，可能也不會崩潰。

	● 自定義參數的表達式

	當我們調用new時，實際上執行了operator new運算符表達式，和其它函數一樣，operator new有多種重載，如上文中的placement new，就是operator new以下形式的一個重載：

	

	placement new的定義

	新語法（C++17）還支持帶對齊的operator new：

	

	aligned new的聲明

	調用示例：

	auto?p?=?new(std::align_val_t{?32?})?A;

	new的重載

	在C++中，我們一般說new和delete動態分配和釋放的對象位于自由存儲區(free store)，這是一個抽象概念。默認情況下，C++編譯器會使用堆實現自由存儲。

	前文已經提及了new的幾種重載，包括數組，placement，align等。

	如果我們想要實現自己的內存分配自定義操作，我們可以有如下兩個方式：

	① 編寫重載的operator new，這意味著我們的參數需要和全局operator new有差異。

	② 重定義operator new，根據名字查找規則，會優先在申請內存的數據內部/數據定義處查找new運算符，未找到才會調用全局::operator new()。

	需要注意的是，如果該全局operator new已經實現為inline函數，則我們不能重定義相關函數，否則無法通過編譯，如下：
//?Default?placement?versions?of?operator?new.
inline?void*?operator?new(std::size_t,?void*?__p)?throw()?{?return?__p;?}
inline?void*?operator?new[](std::size_t,?void*?__p)?throw()?{?return?__p;?}

//?Default?placement?versions?of?operator?delete.
inline?void??operator?delete??(void*,?void*)?throw()?{?}
inline?void??operator?delete[](void*,?void*)?throw()?{?}


	但是，我們可以重寫如下nothrow的operator new：
void*?operator?new(std::size_t,?const?std::nothrow_t&)?throw();
void*?operator?new[](std::size_t,?const?std::nothrow_t&)?throw();
void?operator?delete(void*,?const?std::nothrow_t&)?throw();
void?operator?delete[](void*,?const?std::nothrow_t&)?throw();


	為什么說 new 是低效的?

	① 一般來說，操作越簡單，意味著封裝了更多的實現細節。new作為一個通用接口，需要處理任意時間、任意位置申請任意大小內存的請求，它在設計上就無法兼顧一些特殊場景的優化，在管理上也會帶來一定開銷。

	② 系統調用帶來的開銷。多數操作系統上，申請內存會從用戶模式切換到內核模式，當前線程會 block 住，上下文切換將會消耗一定時間。

	③ 分配可能是帶鎖的。這意味著分配難以并行化。

	alignas 和 alignof

	不同的編譯器一般都會有默認的對齊量，一般都為2的冪次。

	在C中，我們可以通過預編譯命令修改對齊量：

	#pragma?pack(n)

	在內存對齊篇已經提及，我們最終的有效對齊量會取結構體最寬成員 和 編譯器默認對齊量（或我們自己定義的對齊量）中較小的那個。

	C++中也提供了類似的操作：

	alignas

	用于指定對齊量。

	可以應用于類/結構體/union/枚舉的聲明/定義；非位域的成員變量的定義；變量的定義（除了函數參數或異常捕獲的參數）；

	alignas 會對對齊量做檢查，對齊量不能小于默認對齊，如下面的代碼，struct U 的對齊設置是錯誤的：
struct?alignas(8)?S?
{
????//?...
};

struct?alignas(1)?U?
{
????S?s;
};


	以下對齊設置也是錯誤的：
struct?alignas(2)?S?{
?int?n;
};


	此外，一些錯誤的格式也無法通過編譯，如：

	struct?alignas(3)?S?{?};

	例子：
//?every?object?of?type?sse_t?will?be?aligned?to?16-byte?boundary
struct?alignas(16)?sse_t
{
????float?sse_data[4];
};

//?the?array?"cacheline"?will?be?aligned?to?128-byte?boundary
alignas(128)
char?cacheline[128];

	alignof operator

	返回類型的std::size_t。如果是引用，則返回引用類型的對齊方式，如果是數組，則返回元素類型的對齊方式。

	例子：
struct?Foo?{
????int?i;
????float?f;
????char?c;
};

struct?Empty?{?};

struct?alignas(64)?Empty64?{?};

int?main()
{
????std::cout?<

	std::max_align_t

	一般為16bytes，malloc返回的內存地址，對齊大小不能小于max_align_t。

	allocator

	當我們使用C++的容器時，我們往往需要提供兩個參數，一個是容器的類型，另一個是容器的分配器。其中第二個參數有默認參數，即C++自帶的分配器（allocator)：

	template??>?class?vector;?//?generic?template

	我們可以實現自己的 allocator，只需實現分配、構造等相關的操作。在此之前，我們需要先對 allocator 的使用做一定的了解。

	new操作將內存分配和對象構造組合在一起，而 allocator 的意義在于將內存分配和構造分離。這樣就可以分配大塊內存，而只在真正需要時才執行對象創建操作。

	假設我們先申請n個對象，再根據情況逐一給對象賦值，如果內存分配和對象構造不分離可能帶來的弊端如下：

	① 我們可能會創建一些用不到的對象；

	② 對象被賦值兩次，一次是默認初始化時，一次是賦值時；

	③ 沒有默認構造函數的類甚至不能動態分配數組；

	使用allocator之后，我們便可以解決上述問題。

	分配

	為 n 個 string 分配內存：
allocator?alloc;?//?構造allocator對象
auto?const?p?=?alloc.allocate(n);?//?分配n個未初始化的string


	構造

	在剛才分配的內存上構造兩個string：
auto?q?=?p;
alloc.construct(q++,?"hello");?//?在分配的內存處創建對象
alloc.construct(q++,?10,?'c');


	銷毀

	將已構造的string銷毀：

	while(q?!=?p)
????alloc.destroy(--q);

	釋放

	將分配的n個string內存空間釋放：

	alloc.deallocate(p,?n);

	注意：傳遞給deallocate的指針不能為空，且必須指向由allocate分配的內存，并保證大小參數一致。

	拷貝和填充
uninitialized_copy(b,?e,?b2)
//?從迭代器b, e 中的元素拷貝到b2指定的未構造的原始內存中；

uninitialized_copy(b,?n,?b2)
//?從迭代器b指向的元素開始，拷貝n個元素到b2開始的內存中；

uninitialized_fill(b,?e,?t)
//?從迭代器b和e指定的原始內存范圍中創建對象，對象的值均為t的拷貝；

uninitialized_fill_n(b,?n,?t)
//?從迭代器b指向的內存地址開始創建n個對象；


	為什么stl的allocator并不好用

	如果仔細觀察，我們會發現很多商業引擎都沒有使用stl中的容器和分配器，而是自己實現了相應的功能。這意味著allocator無法滿足某些引擎開發一些定制化的需求：

	① allocator內存對齊無法控制

	② allocator難以應用內存池之類的優化機制

	③ 綁定模板簽名

	shared_ptr, unique_ptr和weak_ptr

	智能指針是針對裸指針可能出現的問題封裝的指針類，它能夠更安全、更方便地使用動態內存。

	shared_ptr

	shared_ptr的主要應用場景是當我們需要在多個類中共享指針時。

	多個類共享指針存在這么一個問題：每個類都存儲了指針地址的一個拷貝，如果其中一個類刪除了這個指針，其它類并不知道這個指針已經失效，此時就會出現野指針的現象。為了解決這一問題，我們可以使用引用指針來計數，僅當檢測到引用計數為0時，才主動刪除這個數據，以上就是shared_ptr的工作原理。

	shared_ptr的基本語法如下：

	初始化

	shared_ptr?p?=?make_shared(42);

	拷貝和賦值
auto?p?=?make_shared(42);
auto?r?=?make_shared(42);
r?=?q;?//?遞增q指向的對象，遞減r指向的對象


	只支持直接初始化

	由于接受指針參數的構造函數是explicit的，因此不能將指針隱式轉換為shared_ptr:
shared_ptr?p1?=?new?int(1024);?//?err
shared_ptr?p2(new?int(1024));?//?ok


	不與普通指針混用

	(1) 通過get()函數，我們可以獲取原始指針，但我們不應該delete這一指針，也不應該用它賦值/初始化另一個智能指針；

	(2) 當我們將原生指針傳給shared_ptr后，就應該讓shared_ptr接管這一指針，而不再直接操作原生指針。

	重新賦值

	p.reset(new?int(1024));

	unique_ptr

	有時候我們會在函數域內臨時申請指針，或者在類中聲明非共享的指針，但我們很有可能忘記刪除這個指針，造成內存泄漏。此時我們可以考慮使用unique_ptr，由名字可見，某一時刻只有一個 unique_ptr 指向給定的對象，且它會在析構的時候自動釋放對應指針的內存。

	unique_ptr的基本語法如下：

	初始化

	unique_ptr?p?=?make_unique("test");

	不支持直接拷貝/賦值

	為了確保某一時刻只有一個unique_ptr指向給定對象，unique_ptr不支持普通的拷貝或賦值。
unique_ptr?p1(new?string("test"));
unique_ptr?p2(p1);?//?err
unique_ptr?p3;
p3?=?p2;?//?err


	所有權轉移

	可以通過調用release或reset將指針的所有權在unique_ptr之間轉移：
unique_ptr?p2(p1.release());
unique_ptr?p3(new?string("test"));
p2.reset(p3.release());


	不能忽視 release 返回的結果

	release 返回的指針通常用來初始化/賦值另一個智能指針，如果我們只調用release，而沒有刪除其返回值，會造成內存泄漏：
p2.release();?//?err
auto?p?=?p2.release();?//?ok,?but?remember?to?delete(p)


	支持移動
unique_ptr?clone(int?p)?{
????return?unique_ptr(new?int(p));
}

	weak_ptr

	weak_ptr 不控制所指向對象的生存期，即不會影響引用計數。它指向一個shared_ptr 管理的對象。通常而言，它的存在有如下兩個作用：

	(1) 解決循環引用的問題

	(2) 作為一個“觀察者”：

	詳細來說，和之前提到的多個類共享內存的例子一樣，使用普通指針可能會導致一個類刪除了數據后其它類無法同步這一信息，導致野指針；之前我們提出了shared_ptr，也就是每個類記錄一個引用，釋放時引用數減一，直到減為0才釋放。

	但在有些情況下，我們并不希望當前類影響到引用計數，而是希望實現這樣的邏輯：假設有兩個類引用一個數據，其中有一個類將主動控制類的釋放，而無需等待另外一個類也釋放才真正銷毀指針所指對象。對于另一個類而言，它只需要知道這個指針已經失效即可，此時我們就可以使用weak_ptr。

	我們可以像如下這樣檢測weak_ptr所有對象是否有效，并在有效的情況下做相關操作：
auto?p?=?make_shared(42);
weak_ptr?wp(p);

if(shared_ptr?np?=?wp.lock())
{
???//?...
}

	分配與管理機制

	到目前為止，我們對內存的概念有了初步的了解，也掌握了一些基本的語法。接下來我們要討論如何進行有效的內存管理。

	設計高效的內存分配器通常會考慮到以下幾點：

	① 盡可能減少內存碎片，提高內存利用率

	② 盡可能提高內存的訪問局部性

	③ 設計在不同場合上適用的內存分配器

	④ 考慮到內存對齊

	含 freelist 的分配器

	我們首先來考慮一種能夠處理任何請求的通用分配器。

	一個非常樸素的想法是，對于釋放的內存，通過鏈表將空閑內存鏈接起來，稱為freelist。

	分配內存時，先從freelist中查找是否存在滿足要求的內存塊，如果不存在，再從未分配內存中獲取；當我們找到合適的內存塊后，分配合適的內存，并將多余的部分放回freelist。

	釋放內存時，將內存插入到空閑鏈表，可能的話，合并前后內存塊。

	其中，有一些細節問題值得考慮：

	① 空閑空間應該如何進行管理？

	我們知道freelist是用于管理空閑內存的，但是freelist本身的存儲也需要占用內存。我們可以按如下兩種方式存儲freelist:

	● 隱式空閑鏈表

	將空閑鏈表信息與內存塊存儲在一起。主要記錄大小，已分配位等信息。

	● 顯式空閑鏈表

	單獨維護一塊空間來記錄所有空閑塊信息。

	● 分離適配（segregated-freelist）

	將不同大小的內存塊放在一起容易造成外部碎片，可以設置多個freelist，并讓每個freelist存儲不同大小的內存塊，申請內存時選擇滿足條件的最小內存塊。

	● 位圖

	除了freelist之外，還可以考慮用0，1表示對應內存區域是否已分配，稱為位圖。

	② 分配內存優先分配哪塊內存？

	一般而言，從策略不同來分，有以下幾種常見的分配方式：

	● 首次適應(first-fit）:找到的第一個滿足大小要求的空閑區

	● 最佳適應(best-fit) : 滿足大小要求的最小空閑區

	● 循環首次適應(next-fit) :在先前停止搜索的地方開始搜索找到的第一個滿足大小要求的空閑區

	③ 釋放內存后如何放置到空閑鏈表中？

	● 直接放回鏈表頭部/尾部

	● 按照地址順序放回

	這幾種策略本質上都是取舍問題：分配/放回時間復雜度如果低，內存碎片就有可能更多，反之亦然。

	buddy分配器

	按照一分為二，二分為四的原則，直到分裂出一個滿足大小的內存塊；合并的時候看buddy是否空閑，如果是就合并。

	可以通過位運算直接算出buddy，buddy的buddy，速度較快。但內存碎片較多。

	含對齊的分配器

	一般而言，對于通用分配器來說，都應當傳回對齊的內存塊，即根據對齊量，分配比請求多的對齊的內存。

	如下，是ue4中計算對齊的方式，它返回和對齊量向上對齊后的值，其中Alignment應為2的冪次。
template?
FORCEINLINE?constexpr?T?Align(T?Val,?uint64?Alignment)
{
?static_assert(TIsIntegral::Value?||?TIsPointer::Value,?"Align?expects?an?integer?or?pointer?type");

?return?(T)(((uint64)Val?+?Alignment?-?1)?&?~(Alignment?-?1));
}


	其中~(Alignment - 1) 代表的是高位掩碼，類似于 11110000 的格式，它將剔除低位。在對Val進行掩碼計算時，加上 Alignment-1 的做法類似于（x + a) % a，避免Val 值過小得到 0 的結果。

	單幀分配器模型

	用于分配一些臨時的每幀生成的數據。分配的內存僅在當前幀適用，每幀開始時會將上一幀的緩沖數據清除，無需手動釋放。

	

	雙幀分配器模型

	它的基本特點和單幀分配器相近，區別在于第i+1幀適用第i幀分配的內存。它適用于處理非同步的一些數據，避免當前緩沖區被重寫（同時讀寫）

	

	堆棧分配器模型

	堆棧分配器，它的優點是實現簡單，并且完全避免了內存碎片，如前文所述，函數棧的設計也使用了堆棧分配器的模型。

	

	雙端堆棧分配器模型

	可以從兩端開始分配內存，分別用于處理不同的事務，能夠更充分地利用內存。

	

	池分配器模型

	池分配器可以分配大量同尺寸的小塊內存。它的空閑塊也是由freelist管理的，但由于每個塊的尺寸一致，它的操作復雜度更低，且也不存在內存碎片的問題。

	tcmalloc的內存分配

	tcmalloc是一個應用比較廣泛的內存分配第三方庫。

	對于大于頁結構和小于頁結構的內存塊申請，tcmalloc分別做不同的處理。

	小于頁的內存塊分配

	使用多個內存塊定長的freelist進行內存分配，如：8，16，32……，對實際申請的內存向上“取整”。

	freelist采用隱式存儲的方式。

	

	大于頁的內存塊分配

	可以一次申請多個page，多個page構成一個span。同樣的，我們使用多個定長的span鏈表來管理不同大小的span。

	

	對于不同大小的對象，都有一個對應的內存分配器，稱為CentralCache。具體的數據都存儲在span內，每個CentralCache維護了對應的spanlist。如果一個span可以存儲多個對象，spanlist內部還會維護對應的freelist。

	容器的訪問局部性

	由于操作系統內部存在緩存命中的問題，所以我們需要考慮程序的訪問局部性，這個訪問局部性實際上有兩層意思：

	(1) 時間局部性：如果當前數據被訪問，那么它將在不久后很可能在此被訪問；

	(2) 空間局部性：如果當前數據被訪問，那么它相鄰位置的數據很可能也被訪問；

	我們來認識一下常用的幾種容器的內存布局：

	數組/順序容器：內存連續，訪問局部性良好；

	map：內部是樹狀結構，為節點存儲，無法保證內存連續性，訪問局部性較差（flat_map支持順序存儲）；

	鏈表：初始狀態下，如果我們連續順序插入節點，此時我們認為內存連續，訪問較快；但通過多次插入、刪除、交換等操作，鏈表結構變得散亂，訪問局部性較差；

	碎片整理機制

	內存碎片幾乎是不可完全避免的，當一個程序運行一定時間后，將會出現越來越多的內存碎片。一個優化的思路就是在引擎底層支持定期地整理內存碎片。

	簡單來說，碎片整理通過不斷的移動操作，使所有的內存塊“貼合”在一起。為了處理指針可能失效的問題，可以考慮使用智能指針。

	由于內存碎片整理會造成卡頓，我們可以考慮將整理操作分攤到多幀完成。

	ue4內存管理

	自定義內存管理

	

	ue4的內存管理主要是通過FMalloc類型的GMalloc這一結構來完成特定的需求，這是一個虛基類，它定義了malloc，realloc，free等一系列常用的內存管理操作。其中，Malloc的兩個參數分別是分配內存的大小和對應的對齊量，默認對齊量為0。
/**?The?global?memory?allocator's?interface.?*/
class?CORE_API?FMalloc??:?
?public?FUseSystemMallocForNew,
?public?FExec
{
public:
?virtual?void*?Malloc(?SIZE_T?Count,?uint32?Alignment=DEFAULT_ALIGNMENT?)?=?0;
?virtual?void*?TryMalloc(?SIZE_T?Count,?uint32?Alignment=DEFAULT_ALIGNMENT?);
?virtual?void*?Realloc(?void*?Original,?SIZE_T?Count,?uint32?Alignment=DEFAULT_ALIGNMENT?)?=?0;
?virtual?void*?TryRealloc(void*?Original,?SIZE_T?Count,?uint32?Alignment=DEFAULT_ALIGNMENT);
?virtual?void?Free(?void*?Original?)?=?0;
??
?//?...
};


	FMalloc 有許多不同的實現，如 FMallocBinned，FMallocBinned2等，可以在HAL文件夾下找到相關的頭文件和定義，如下：

	

	內部通過枚舉量來確定對應使用的Allocator：
?/**?Which?allocator?is?being?used?*/
?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
??Mimalloc,?//?mimalloc
?};


	對于不同平臺而言，都有自己對應的平臺內存管理類，它們繼承自FGenericPlatformMemory，封裝了平臺相關的內存操作。具體而言，包含FAndroidPlatformMemory，FApplePlatformMemory，FIOSPlatformMemory，FWindowsPlatformMemory等。

	通過調用PlatformMemory的BaseAllocator函數，我們取得平臺對應的FMalloc類型，基類默認返回默認的C allocator，而不同平臺會有自己特殊的實現。

	在PlatformMemory的基礎上，為了方便調用，ue4又封裝了FMemory類，定義通用內存操作，如在申請內存時，會調用FMemory::Malloc，FMemory內部又會繼續調用GMalloc->Malloc。如下為節選代碼：
struct?CORE_API?FMemory
{
?/**?@name?Memory?functions?(wrapper?for?FPlatformMemory)?*/

?static?FORCEINLINE?void*?Memmove(?void*?Dest,?const?void*?Src,?SIZE_T?Count?)
?{
??return?FPlatformMemory::Memmove(?Dest,?Src,?Count?);
?}

?static?FORCEINLINE?int32?Memcmp(?const?void*?Buf1,?const?void*?Buf2,?SIZE_T?Count?)
?{
??return?FPlatformMemory::Memcmp(?Buf1,?Buf2,?Count?);
?}

?//?...
?static?void*?Malloc(SIZE_T?Count,?uint32?Alignment?=?DEFAULT_ALIGNMENT);
?static?void*?Realloc(void*?Original,?SIZE_T?Count,?uint32?Alignment?=?DEFAULT_ALIGNMENT);
?static?void?Free(void*?Original);
?static?SIZE_T?GetAllocSize(void*?Original);

????//?...
};


	為了在調用new/delete能夠調用ue4的自定義函數，ue4內部替換了operator new。這一替換是通過IMPLEMENT_MODULE宏引入的：

	

	IMPLEMENT_MODULE通過定義REPLACEMENT_OPERATOR_NEW_AND_DELETE宏實現替換，如下圖所示，operator new/delete內實際調用被替換為FMemory的相關函數。

	

	FMallocBinned

	我們以FMallocBinned為例介紹ue4中通用內存的分配。

	基本介紹

	（1） 空閑內存如何管理？

	FMallocBinned使用freelist機制管理空閑內存。每個空閑塊的信息記錄在FFreeMem結構中，顯式存儲。

	（2）不同大小內存如何分配？

	FMallocBinned使用內存池機制，內部包含POOL_COUNT(42)個內存池和2個擴展的頁內存池；其中每個內存池的信息由FPoolInfo結構體維護，記錄了當前FreeMem內存塊指針等，而特定大小的所有內存池由FPoolTable維護；內存池內包含了內存塊的雙向鏈表。

	（3）如何快速根據分配元素大小找到對應的內存池？

	為了快速查詢當前分配內存大小應該對應使用哪個內存池，有兩種辦法，一種是二分搜索O(logN)，另一種是打表(O1)，考慮到可分配內存數量并不大，MallocBinned選擇了打表的方式，將信息記錄在MemSizeToPoolTable。

	（4）如何快速刪除已分配內存？

	為了能夠在釋放的時候以O(1)時間找到對應內存池，FMallocBinned維護了PoolHashBucket結構用于跟蹤內存分配的記錄。它組織為雙向鏈表形式，存儲了對應內存塊和鍵值。

	內存池

	● 多個小對象內存池（內存池大小均為PageSize，但存儲的數據量不一樣）。數據塊大小設定如下：

	?

	

	?

	● 兩個額外的頁內存池，管理大于一個頁的內存池，大小為3*PageSize和6*PageSize

	● 操作系統的內存池

	分配策略

	分配內存的函數為void* FMallocBinned::Malloc(SIZE_T Size, uint32 Alignment)。

	其中第一個參數為需要分配的內存的大小，第二個參數為對齊的內存數。

	如果用戶未指定對齊的內存大小，MallocBinned內部會默認對齊于16字節，如果指定了大于16字節的對齊內存大小，則對齊于用戶指定的對齊大小。根據對齊量，計算出最終實際分配的內存大小。

	MallocBinned內部對于不同的內存大小有三種不同的處理：

	(1) 分配小塊內存（0，PAGE_SIZE_LIMIT/2）

	根據分配大小從MemSizeToPoolTable中獲取對應內存池，并從內存池的當前空閑位置讀取一塊內存，并移動當前內存指針。如果移動后的內存指針指向的內存塊已經使用，則將指針移動到FreeMem鏈表的下一個元素；如果當前內存池已滿，將該內存池移除，并鏈接到耗盡的內存池。

	如果當前內存池已經用盡，下次內存分配時，檢測到內存池用盡，會從系統重新申請一塊對應大小的內存池。

	(2) 分配大塊內存 [PAGE_SIZE_LIMIT/2, PAGE_SIZE_LIMIT*3/4]∪(PageSize，PageSize + PAGE_SIZE_LIMIT/2)

	需要從額外的頁內存池分配，分配方式和（1）一樣。

	(3) 分配超大內存

	從系統內存池中分配。

	Allocator

	對于ue4中的容器而言，它的模板有兩個參數，第一個是元素類型，第二個就是對應的分配器（Allocator）:
template
class?TArray
{
???//?...
};


	如下圖，容器一般都指定了自己默認的分配器：

	

	默認的堆分配器
template?
class?TSizedHeapAllocator?{?...?};

//?Default?Allocator
using?FHeapAllocator?=?TSizedHeapAllocator<32>;


	默認情況下，如果我們不指定特定的Allocator，容器會使用大小類型為int32堆分配器，默認由FMemory控制分配（和new一致）

	含對齊的分配器
template
class?TAlignedHeapAllocator
{
????//?...
};


	由FMemory控制分配，含對齊。

	可擴展大小的分配器
template?
class?TInlineAllocator
{
????//...
};


	可擴展大小的分配器存儲大小為NumInlineElements的定長數組，當實際存儲的元素數量高于NumInlineElements時，會從SecondaryAllocator申請分配內存，默認情況下為堆分配器。

	對齊量總為DEFAULT_ALIGNMENT。

	不可重定位的可擴展大小的分配器
template?
class?TNonRelocatableInlineAllocator
{
????//?...
};


	在支持第二分配器的基礎上，允許第二分配器存儲指向內聯元素的指針。這意味著Allocator不應做指針重定向的操作。但ue4的Allocator通常依賴于指針重定向，因此該分配器不應用于其它Allocator容器。

	固定大小的分配器
template?
class?TFixedAllocator
{
????//?...
};


	類似于InlineAllocator，會分配固定大小內存，區別在于當內聯存儲耗盡后，不會提供額外的分配器。

	稀疏數組分配器
template
class?TSparseArrayAllocator
{
public:

?typedef?InElementAllocator?ElementAllocator;
?typedef?InBitArrayAllocator?BitArrayAllocator;
};


	稀疏數組本身的定義比較簡單，它主要用于稀疏數組（Sparse Array），相關的操作也在對應數組類中完成。稀疏數組支持不連續的下標索引，通過BitArrayAllocator來控制分配哪個位是可用的，能夠以O(1)的時間刪除元素。

	默認使用堆分配。

	哈希分配器
template<
?typename?InSparseArrayAllocator???????????????=?TSparseArrayAllocator<>,
?typename?InHashAllocator??????????????????????=?TInlineAllocator<1,FDefaultAllocator>,
?uint32???AverageNumberOfElementsPerHashBucket?=?DEFAULT_NUMBER_OF_ELEMENTS_PER_HASH_BUCKET,
?uint32???BaseNumberOfHashBuckets??????????????=?DEFAULT_BASE_NUMBER_OF_HASH_BUCKETS,
?uint32???MinNumberOfHashedElements????????????=?DEFAULT_MIN_NUMBER_OF_HASHED_ELEMENTS
?>
class?TSetAllocator
{
public:
?static?FORCEINLINE?uint32?GetNumberOfHashBuckets(uint32?NumHashedElements)?{?//...?}

?typedef?InSparseArrayAllocator?SparseArrayAllocator;
?typedef?InHashAllocator????????HashAllocator;
};


	用于TSet/TMap等結構的哈希分配器，同樣的實現比較簡單，具體的分配策略在TSet等結構中實現。其中SparseArrayAllocator用于管理Value，HashAllocator用于管理Key。Hash空間不足時，按照2的冪次進行擴展。

	默認使用堆分配。

	除了使用默認的堆分配器，稀疏數組分配器和哈希分配器都有對應的可擴展大小（InlineAllocator)/固定大小(FixedAllocator)分配版本。

	動態內存管理

	TSharedPtr
template
class?TSharedPtr
{
????//?...
private:
?ObjectType*?Object;
?SharedPointerInternals::FSharedReferencer?SharedReferenceCount;
};


	TSharedPtr是ue4提供的類似stl sharedptr的解決方案，但相比起stl，它可由第二個模板參數控制是否線程安全。

	如上所示，它基于類內的引用計數實現(SharedReferenceCount)，為了確保多個TSharedPtr能夠同步當前引用計數的信息，引用計數被設計為指針類型。在拷貝/構造/賦值等操作時，會增加或減少引用計數的值，當引用計數為0時將銷毀指針所指對象。

	TSharedRef
template
class?TSharedRef
{
????//?...
private:
?ObjectType*?Object;
?SharedPointerInternals::FSharedReferencer?SharedReferenceCount;
};


	和TSharedPtr類似，但存儲的指針不可為空，創建時需同時初始化指針。類似于C++中的引用。

	TRefCountPtr
template
class?TRefCountPtr
{
????//?...
private:
?ReferencedType*?Reference;
};


	TRefCountPtr是基于引用計數的共享指針的另一種實現。和TSharedPtr的差異在于它的引用計數并非智能指針類內維護的，而是基于對象的，相當于TRefCountPtr內部只存儲了對應的指針信息（ReferencedType* Reference)。

	基于對象的引用計數，即引用計數存儲在對象內部，這是通過從FRefCountBase繼承引入的。這也就意味著TRefCountPtr引用的對象必須從FRefCountBase繼承，它的使用是有局限性的。

	但是在如統計資源引用而判斷資源是否需要卸載的應用場景中，TRefCountPtr可手動添加/釋放引用，使用上更友好。
class?FRefCountBase
{
public:
????//?...
private:
?mutable?int32?NumRefs?=?0;
};


	TWeakPtr
template
class?TWeakPtr
{
};


	類似的，TWeakObjectPtr是ue4提供的類似stl weakptr的解決方案，它將不影響引用計數。

	TWeakObjectPtr
template
struct?TWeakObjectPtr?:?private?TWeakObjectPtrBase
{
????//?...
};

struct?FWeakObjectPtr
{
????//?...

private:
?int32??ObjectIndex;
?int32??ObjectSerialNumber;
};


	特別的，由于UObject有對應的gc機制，TWeakObjectPtr為指向UObject的弱指針，用于查詢對象是否有效（是否被回收）

	垃圾回收

	C++語言本身并沒有垃圾回收機制，ue4基于內部的UObject，單獨實現了一套GC機制，此處僅做簡單介紹。

	首先，對于UObject相關對象，為了維持引用（防止被回收），通常使用UProperty()宏，使用容器（如TArray存儲），或調用AddToRoot的方法。

	ue4的垃圾回收代碼實現位于GarbageCollection.cpp中的CollectGarbage函數中。這一函數會在游戲線程中被反復調用，要么在一些情況下手動調用，要么在游戲循環Tick()中滿足條件時自動調用。

	GC過程中，首先會收集所有不可到達的對象（無引用）。

	

	之后，根據當前情況，會在單幀（無時間限制）或多幀（有時間限制）的時間內，清理相關對象（IncrementalPurgeGarbage）

	SIMD

	合理的內存布局/對齊有利于SIMD的廣泛應用，在編寫定義基礎類型/底層數學算法庫時，我們通常有必要考慮到這一點。

	我們可以參考ue4中封裝的sse初始化、加法、減法、乘法等操作，其中，__m128類型的變量需程序確保為16字節對齊，它適用于浮點數存儲，大部分情況下存儲于內存中，計算時會在SSE寄存器中運用。
typedef?__m128?VectorRegister;

FORCEINLINE?VectorRegister?VectorLoad(?const?void*?Ptr?)
{
?return?_mm_loadu_ps((float*)(Ptr));
}

FORCEINLINE?VectorRegister?VectorAdd(?const?VectorRegister&?Vec1,?const?VectorRegister&?Vec2?)
{
?return?_mm_add_ps(Vec1,?Vec2);
}

FORCEINLINE?VectorRegister?VectorSubtract(?const?VectorRegister&?Vec1,?const?VectorRegister&?Vec2?)
{
?return?_mm_sub_ps(Vec1,?Vec2);
}

FORCEINLINE?VectorRegister?VectorMultiply(?const?VectorRegister&?Vec1,?const?VectorRegister&?Vec2?)
{
?return?_mm_mul_ps(Vec1,?Vec2);
}


	除了SSE外，ue4還針對Neon/FPU等寄存器封裝了統一的接口，這意味調用者可以無需考慮過多硬件的細節。

	我們可以在多個數學運算庫中看到相關的調用，如球諧向量的相加：
?/**?Addition?operator.?*/
?friend?FORCEINLINE?TSHVector?operator+(const?TSHVector&?A,const?TSHVector&?B)
?{
??TSHVector?Result;
??for(int32?BasisIndex?=?0;BasisIndex?

	編輯：黃飛