艾莉兒的特殊配備：記憶體配置技巧

Shark：「遊戲引擎就是速度和火力！」

筆者做遊戲的一貫理念之一。↑

有的遊戲作者不重視底層技術，覺得反正玩家看不到不做也沒差，但即使現在CPU時脈動輒以GHz計，市面上還是不乏會lag的遊戲，表示效能優化有其重要性。而且現在手機遊戲流行，由於手機的硬體性能遠不如桌機，且對耗電量要斤斤計較，使得調效能技術更加重要。
(想起Rabi-Ribi初期的版本，lag這一粒老鼠屎壞了整個遊戲，動作遊戲很看重時機準確，是不能允許一點lag的。)
(還有在公司有一次做的遊戲有手機很燙的問題，但當時工作很多時間吃緊，只好放著不管了，而且Unity不讓我操作記憶體配置、SIMD指令等等的，想改良也無從改起。)

這次介紹另一個提升效能的技巧：記憶體配置
做法不像上次的calling convention那樣輕鬆，要改一些邏輯和語法，但寫程式還是多少該注意記憶體的狀況。

---

首先介紹一些C/C++語法和計算機科學知識。

C/C++的變數按照儲存位置可分成以下三種

種類	儲存位置	建立、刪除方式
區域變數	stack或暫存器	進入函式時配置空間，函式return時釋放。
全域變數	bss或data段	程式開始時就配置空間，程式執行期間會一直存在。
動態配置	heap	用malloc()等函式配置，用free()釋放。

stack、bss、data、heap各是什麼在本篇不解釋，自己去查data segment的資料吧。

全域變數包含以下三種
1.宣告在函式外面的變數
2.函式裡的static變數。
3.struct與class裡的static成員。
三種雖然在C/C++語法裡用法有別，但編譯成binary後就都存在全域變數的空間。

動態配置主要有四個函式：malloc()、calloc()、realloc()、strdup()，還有一些strdup()的變化。
strdup()在有的教學不會提到，但它也是記憶體配置函式之一，宣告是「char* strdup(char* src);」，src給一個null terminate string，此函式會malloc()一塊空間並把src的內容複製過去，傳回的指標要用free()釋放。

如果是C++的物件，建立是「配置記憶體→呼叫建構子」的兩個步驟，多了建構子、解構子呼叫時機的差別，就有以下的變化。
舉例來說有個class叫做SPImagePlane，建構子是「SPImagePlane()」，不需要參數。(這是艾莉兒身上實際配備的class)

種類	建立	刪除
區域變數	void function1(){   SPImagePlane plane; } 宣告同時呼叫建構子。	離開作用域時自動呼叫解構子並刪除。
全域變數 或class裡的static member	struct Class1{   static SPImagePlane plane; }; SPImagePlane Class1::plane; 儲存在全域空間，main()之前就會呼叫建構子。	main() return後呼叫解構子。
函式裡的static變數	void function1(){   static SPImagePlane plane; } 儲存在全域空間，第一次進入函式時呼叫建構子。 從產生的組合語言得知，compiler會加上判斷式檢查是否已呼叫過建構子，第二次以後進入函式就不呼叫。	main() return後呼叫解構子。
placement new	void* p=malloc(sizeof(SPImagePlane)); SPImagePlane* plane=new(p) SPImagePlane; 手動配置空間再直接呼叫建構子。 可以如上用malloc，或用其他自訂方法。	plane->~SPImagePlane(); free(p); 直接呼叫解構子再釋放空間。
new	SPImagePlane* plane=new SPImagePlane; 自動用系統預設方法配置空間(一般用malloc)，並呼叫建構子。	delete plane; 自動呼叫解構子，再用free()釋放空間。

在建構子、解構子裡放一行printf()就可以看出呼叫時機。

區域變數的刪除時機除了從函式return以外，大括號代表變數作用域，也可以用大括號控制資源釋放時機。

void function1(){   {     SPImagePlane paperDoll[4]; //配置四個SPImagePlane     …… //使用SPImagePlane   } //在此呼叫解構子並回收空間   …… //繼續處理 }

C++直接呼叫建構子、解構子的方法在很多教學都沒有提到，但有它的用處。直接呼叫建構子的方法就是上面的placement new，不能用「pointer->建構子名稱」。相對地解構子可以用「pointer->解構子名稱」呼叫。

---

了解基礎知識後，再來看實際做法。

原則一：三種儲存位置由快到慢是「區域變數>全域變數>動態分配」

詳細原因：
區域變數的話，在stack配置空間只要修改stack pointer的值即可(x64架構是RSP暫存器)，速度很快，而且因為函式return後就可以扔掉，會儘量用CPU內部的暫存器或cache儲存。
全域變數與stack在不同位址所以不能利用cache，必須從主記憶體讀取，修改後再寫回主記憶體，比CPU內部的空間慢。
動態配置為了能在任何時候分配任何大小，作業系統要用一些方法管理記憶體，malloc()要等作業系統做一些處理才能得到空間，比上面兩種慢。

技巧1a：

儘量使用區域變數，非必要不要使用全域變數和動態分配。
例如函式裡需要臨時物件，函式return前就刪除，可能有人會這樣寫

void function1(){   SPTextPlane* plane=new SPTextPlane;     ……   delete plane; }

使用動態配置有額外的效能消耗
比較好的方法是配置在stack上

void function1(){   SPTextPlane plane;     …… }

技巧1b：

區域變數離開作用域後就消失，所以如果有個函式是產生一個陣列或struct再傳回給上層的函式，可能無可避免要用new。
(此例取自引擎的繪圖部分，計算貼圖坐標填進陣列)

short* generateTexCoord(PlaneHasTexCoord* plane){   short* texCoord=new short[8];     …… //填入texCoord   return texCoord; } void outerFunction(){     ……   short* texCoord=generateTexCoord(plane);     …… //使用texCoord   delete[] texCoord; }

可以改寫成上層配置變數，然後把它的指標傳入函式。

void fillTexCoord(PlaneHasTexCoord* plane, short* texCoord){   texCoord[0]=……;   texCoord[1]=……;     …… //填入texCoord } void outerFunction(){     ……   short texCoord[8];   fillTexCoord(plane, texCoord);     …… //使用texCoord }

Windows API裡常見這種用法，Windows API要產生一個struct並填入資料通常是在外面宣告struct再把它的指標傳入，很少主動產生一個struct。

技巧1c：

如果是固定長度的陣列，即WCHAR wcharBuffer[10]，長度是寫在程式裡的數值或用const定義，可以如左邊宣告。
如果執行時期才能確定長度呢？即WCHAR wcharBuffer[len]的len是變數而不是常數。(這種稱為variable length array)
轉換文字編碼常碰到這種情況

//charArray為char*型態 int outLen=MultiByteToWideChar(CP_UTF8, 0, charArray, -1, NULL, 0); //傳回需要的buffer大小 WCHAR wcharBuffer[outLen]; //配置記憶體 MultiByteToWideChar(CP_UTF8, 0, charArray, -1, wcharBuffer, outLen); //實際做轉換

GCC和clang能接受陣列長度是變數，可以照上面寫。
但是VC不支援這種寫法，這樣寫編譯會跳error。

這時可用一個函式代替

#include<malloc.h> void* _alloca(size_t size);

用法跟malloc()差不多，不過它是配置在stack上，函式return時會自動回收空間，不用手動呼叫free()釋放。

上例要改成這樣

int outLen=MultiByteToWideChar(CP_UTF8, 0, charArray, -1, NULL, 0); WCHAR* wcharBuffer=(WCHAR*)_alloca(outLen*sizeof(WCHAR)); MultiByteToWideChar(CP_UTF8, 0, charArray, -1, wcharBuffer, outLen);

一個WCHAR佔兩byte，所以要乘以sizeof(WCHAR)才是byte數。

為此我寫了一個macro，可以根據compiler選擇能用的方式。

#ifdef _MSC_VER   #define VARARRAY(type,name,num) type* name=(type*)_alloca((num)*sizeof(type)) #elif defined __GNUC__ || defined __clang__   #define VARARRAY(type,name,num) type name[num] #endif //用法 VARARRAY(WCHAR, wcharBuffer, outLen);

---

原則二：如果有多個物件需要動態配置，先取得一塊大的空間再從裡面分，會比多次malloc()要快，這個技巧叫記憶體池(memory pool)。
每次malloc()都有額外的速度和空間消耗，而且malloc()呼叫越多次會產生越多記憶體碎片，即使實際用的空間不大，記憶體碎片最終也會導致空間被用光。

技巧2a：

如果物件內部用到好幾個陣列，這些陣列產生、刪除是同進退，把總共需要的byte數算出來再一次malloc()解決。
例如艾莉兒身上用來繪製tilemap的class，需要計算各格子的螢幕坐標和貼圖坐標，繪圖時傳給D3D和OpenGL的函式。

class SPTilePlane{   short* screenCoord; //螢幕坐標   short* texCoord; //貼圖坐標     …… };

一個矩形是4個坐標(D3D11和OpenGL 3.3不再有四邊形primitive，我用index array模擬出四邊形)，毎個坐標是兩個short，所以一個格子是8個short。
建構式、初始化和解構式有這樣的內容

SPTilePlane::SPTilePlane():texCoord(0){} //標示此class還沒初始化 void SPTilePlane::init(int planeID, int imageID,   const TilePlaneMetric* metric, int fill, int visible){     //TilePlaneMetric是關於尺寸的資訊     ……   this->cols=metric->cols; //欄數   this->rows=metric->rows; //列數   const int SHORTNUM=this->cols*this->rows*8; //需要的short數量   this->texCoord=(short*)malloc(SHORTNUM*sizeof(short)*2);     //一個short是2 byte，所以乘以sizeof(short)     //有screenCoord和texCoord兩個陣列要用，所以乘以2   this->screenCoord=this->texCoord+SHORTNUM;     //這樣screenCoord會緊接在texCoord之後     …… } SPTilePlane::~SPTilePlane(){   if(this->texCoord)     free(this->texCoord); }

class都做成建構子沒有任何參數，呼叫init()函式才真正初始化，這樣做目的是要能在struct和class裡靜態宣告，方便配置在stack上。

struct OptionMenu{     ……   //顯示模式   BorderCursor graphicModeCursor;   //vsync   BorderCursor vsyncCursor;   //音量   SPImagePlane bgmBar1;   SPImagePlane bgmBar2;   SPImagePlane seBar1;   SPImagePlane seBar2;     ……   OptionMenu(); //建構子裡呼叫各member的init()初始化 }; //像這樣使用 void optionMenu(){   OptionMenu optionMenu;     //之後操作物件member做option畫面的處理     …… }

技巧2b：

如果陣列元素是需要呼叫建構子的物件，要如何呼叫建構子呢？上面說的placement new在此就派上用場了。

//建立 StraightBullet* bullets=(StraightBullet*)malloc(sizeof(StraightBullet)*num); const float ANGLE_STEP=M_PI*0.5/(num-1); float nowAngle=0; for(int i=0;i<num;i++){   new(bullets+i) StraightBullet(startX, startY, nowAngle);   nowAngle+=ANGLE_STEP; } //刪除 for(int i=0;i<num;i++){   bullets[i].~StraightBullet(); } free(bullets);

雖然class叫StraightBullet，Cyber Sprite裡其實不是用這個方法管理子彈，只是隨便舉個比較簡單的例子。

技巧2c：

如果把pool allocator做成一個global的模組，做出這三個類似malloc()的函式呢？

void* REGPARM poolMalloc(uint32_t size); void* REGPARM poolRealloc(const void* ptr, uint32_t size); void REGPARM poolFree(const void* ptr);

內部處理是先用malloc()配置一大塊pool再從裡面切，呼叫一次poolMalloc()傳回一小塊，等一個pool用完再malloc()一塊新的。
要求空間小的時候提升速度的效果比較明顯，大塊就不太有需要使用，而且導致pool過大也不好，我是設成252 byte以下才能用這個分配器。
REGPARM是什麼請參照這篇：改造calling convention，我在艾莉兒身上用了很多提升速度的技巧。

根據實測，這個技巧威力很大，配置幾千個小塊空間時，自訂分配器速度是malloc()、free()的3倍，而且是一勞永逸的工，一次做好以後其他軟體也可以沿用。
不過，目前暫不想公開詳細做法，看我以後會不會改變主意。

---

雖然動態記憶體配置在C語言標準有定義，但記憶體管理實際上是作業系統的功能，屬於作業系統API的一部分，malloc()、free()背後隱藏了很多作業系統的細節，想查詢程式執行時記憶體的資訊也要透過作業系統API。

再介紹一個技巧：取得配置的空間有多少byte。

C語言動態配置記憶體時，malloc()等函式要填入需要的大小，但之後沒有方法知道配置的空間有多大。但仔細想想，作業系統一定要記錄這塊被使用的空間有多大，才有辦法管理記憶體，這個資訊一定存在某個地方。
如果用sizeof(char*)取得的是char*這個型態的大小，一如所有指標在64位元環境下是8 byte。sizeof的用途是取得資料型態的byte數，只能求得編譯期就能確定的東西，並不能取得runtime才能確定的資訊。

Windows和Linux其實有提供方法，這是獨自的擴充，不在C語言標準裡面。
Windows：

#include<malloc.h> size_t _msize(void* pointer);

Linux：

#include<malloc.h> size_t malloc_usable_size(void* pointer);

把malloc、calloc、realloc、strdup傳回的指標傳入這個函式，就能取得byte數了，_alloca因為不是配置在heap上面不能用這個方法。

在Windows實測，_msize()傳回的值就是之前malloc()給的值。
但在Linux有個現象，malloc_usable_size()傳回的數字常會大於先前給malloc()的數字，這時該相信哪個呢？

在筆者的電腦實測的結果，程式編譯成64 bit。

malloc()	malloc_usable_size()
7	24
125	136
5000	5016
1048320 (=1024×1024-256)	1048560
1048576 (=1024×1024)	1052656

答案是：該相信malloc_usable_size()的。給malloc()的數字只代表「至少要這個大小」，作業系統會因為4或8 byte對齊效能較好以及方便管理，配置較大的空間。如上面要求125 byte，malloc_usable_size()傳回136表示實際有136 byte可用。

---

如果有使用別人的函式庫，那它內部怎麼處理記憶體呢？根據我看一些open source函式庫的經驗……，除非說明書裡明講記憶體有特別處理，或是有讓使用者自訂記憶體分配器(如Lua函式庫的lua_newstate()可傳入一個函式指標)，還是假設它用效率最差的malloc()或new吧，可能很多軟體作者也不在乎執行速度，就沒有對效能調整。