記憶體配置:Pooled Allocation技術評比與效能測試

從剛進入遊戲業界開始,我就一直對於「記憶體配置」(Memory Allocation) 的系統架構與相關議題很感興趣。後來隨著閱讀書籍量的增加與工作經驗上的累積,逐漸接觸到各種不同設計架構與實作方法的記憶體管理機制,現在終於能夠將一些初步的心得整理出來了。

在遊戲程式設計的領域中,程式設計者經常需要即時且動態地產生出大量的小型物件,例如怪物、特效、場景物乃至於低階的節點物件等等。如果遊戲程式設計者只是天真爛漫地使用著單純無害的 operator new 以及 operator delete 程序,在經過遊戲執行中不斷反覆地配置與歸還記憶體的行為之後,很快就會使得完整的記憶體區段面臨嚴重的「記憶體破碎」(Memory Fragmentation) 問題。更糟的是,記憶體破碎的問題往往很難被偵測出來,而容易被開發者所忽略。

為了盡可能降低記憶體破碎的狀況,並且得到高效的物件配置程序,除了從高階層面利用資源管理 (Resource Management) 機制減少遊戲物件的生成與毀滅行為之外,同時也需要從比較低階的層面,也就是屬於記憶體配置的功能面向著手改善。在使用者每次進行 operator new 操作向作業系統索取記憶體空間時,C 語言的函式庫除了配置所要求的區塊大小以外,還會另外生成一小塊額外的區塊以簿記相關的資訊。對於經常進行生成與毀滅程序的小型物件來說,這樣的行為模式就顯得十分浪費而不具效率。如果能夠一次性的配置出一大塊記憶體,然後再依使用者的需求傳回部分區塊,可望就能夠改善 operator new 程序所產生的額外負擔。

為了能夠妥善管理一大塊的記憶體空間,程式設計者發展出了「Free List」這個用來處理動態配置記憶體的特殊資料結構。Free List 通常是以鏈結串列 (Linked List) 做為基底結構,將目前可使用以及使用中的記憶體空間紀錄並且連結起來。一般常聽到的「記憶體池」(Memory Pool) 或者「池式配置」(Pooled Allocation),就是利用 Free List 資料結構實作出來的記憶體管理機制,也是遊戲程式設計者不可不知的記憶體系統管理技巧。而應該如何實作出高效能的 Free List 結構,使創建物件與刪除物件時的負擔減至最小,更是池式配置記憶體機制中最關鍵的要點。

前陣子除了在《Modern C++ Design》與《Game Programming Gems 7》兩本書裡,學習了兩種池式配置的設計實作方法之外,最近正好也剛踏入 Boost C++ Libraries 的國界中,發現其中有個專門做為池式配置功能用途的記憶體管理函式庫 Boost.Pool,不禁使我非常好奇 Boost.Pool 函式庫與其他池式配置技術的效能相比如何,於是決定以下列四個項目做為這次效能試驗的目標:

  • operator new:原始的 C++ 記憶體配置操作。
  • Loki Library SmallObj:在《Modern C++ Design》書中,作者以 Policy-Based Design 設計思維做為起始點,實作了一個專為小型物件設計的池式配置機制,並且包裝在開源專案 Loki 函式庫中。而在本文的測試專案中,將只使用其中的 SmallObj 類別做為測試用途;在 SmallObj 的類別架構中,完整實作了書中所涵蓋的「小型物件配置器」。另外需注意的是,SmallObj 的預設行為只會處理大小在 256 bytes 以下的物件,若使用者要求創建更大的物件,系統便會直接交由 operator new 配置記憶體。
  • High Performance Heap Allocator:在《Game Programming Gems 7》裡,「High Performance Heap Allocator」(簡稱為 HPHA)一文的作者,對 Loki 的池式配置機制提出改善方法,將使用者對於記憶體的要求,分成了兩種不同的運作策略:在 256 bytes 以下的小型物件,使用 Win32 平台的 VirtualAlloc() 函式,配置出自然對齊的記憶體區塊,使物件的歸還程序能夠達到很好的執行效能;而對於超過 256 bytes 的大型物件,則使用「紅黑樹」(Red-Black Tree) 結構實作出特製化的管理機制。
  • Boost.Pool Library:從屬於 Boost C++ Libraries 內的函式庫之一,專門做為記憶體管理與池式配置的功能用途。

在使用方法上,Loki、HPHA 與 Boost.Pool 三者各不相同。若使用 Loki SmallObj 的技術,必須先讓使用者的類別繼承自 Loki::SmallObject 類別,而在 Loki::SmallObject 中已經覆寫了類別的 operator new,所以接下來就能夠直接使用 new 與 delete 進行配置與刪除動作;HPHA 則定義了二個全域函式 custom_new< T >() 與 custom_delete() 供使用者配置及刪除物件;最後,在 Boost.Pool 裡需要先建立出管理記憶體用的「物件池」boost::object_pool< T >,然後再以物件池的成員函式 construct() 與 destroy() 創建並且毀滅物件。程式碼如下所示:

class TestObject
{
    char data[8];
};

class TestLokiObject : public Loki::SmallObject<>
{
    char data[8];
};

// Loki SmallObj
TestLokiObject* obj = new TestLokiObject;
delete obj;

// HPHA
TestObject* obj = custom_new< TestObject >();
custom_delete(obj);

// Boost Pool
boost::object_pool< TestObject > objPool;
TestObject* obj = objPool.construct();
objPool.destroy(obj);

首先,在第一個測試套件中,採用的是「交錯配置」的方式,也就是在創建物件之後,立即將物件刪除:

Timer timer;

timer.Start();
for (unsigned int i = 0; i < testNum; i ++)
{
    // 創建物件
	TestObject* obj1 = new TestObject(i);
	// 立即刪除物件
	delete obj1;
	TestObject* obj2 = new TestObject(i);
	delete obj2;
	TestObject* obj3 = new TestObject(i);
	delete obj3;
	TestObject* obj4 = new TestObject(i);
	delete obj4;
	TestObject* obj5 = new TestObject(i);
	delete obj5;
}
timer.Stop();

其中的 testNum 變數,為使用者可指定的總測試次數,在此我輸入的測試次數為 500000 次。另外,為了量測物件的大小是否會對各項試驗目標產生影響,在測試專案中會對三個不同大小的物件類別,分別為 8 bytes、64 bytes 以及 280 bytes,進行相同的測試程序。結果如下圖所示:

Test Suite 1
Test Suite 1

由測試結果可以清楚地瞭解,無論物件大小為何,Boost Pool 的表現都獲得了壓倒性的勝利,特別是當物件大小為 8 bytes 與 64 bytes 時,更是呈現出超過其他試驗目標 10 倍以上的效能!此外,在 HPHA 與 Loki SmallObj 的比較上,在小型的 8 bytes 與 64 bytes 物件上,Loki 的表現仍然勝過 HPHA;而在 280 bytes 的物件上,HPHA 則毫無意外地超越了 Loki 的效能。

接著在第二項測試套件中,則採用「整體配置」的方式,先一次創建出所有的物件後,然後再將這些物件一一刪除:

Timer timerNew;
Timer timerDelete;

std::vector< TestObject* > pool;
pool.reserve(testNum);

// 創建所有的物件
timerNew.Start();
for (unsigned int i = 0; i < testNum; i ++)
{
	TestObject* obj = new TestObject(i);
	pool.push_back(obj);
}
timerNew.Stop();

// 一一刪除所有的物件
timerDelete.Start();
for (unsigned int i = 0; i < testNum; i ++)
{
	delete (pool[i]);
}
timerDelete.Stop();

測試次數為 50000 次,量測的時間數據則分成「Allocation」與「Deallocation」兩個部分,結果如下圖所示:

Test Suite 2
Test Suite 2

喔買尬,Boost Pool 的表現真是出人意表的慘烈!對各個物件一一進行刪除程序時,Boost Pool 竟然得出如此令人難以接受的結果,難道之前的「整體配置」測試成果不過是假象而已?為了找出挽救 Boost Pool 的可能性,繼續修改第二項測試,增加一項「Boost Pool Ptr」測試程序,在刪除程序時,不對物件一一進行刪除動作,而是直接刪除掉整個 Boost Pool 的物件池:

boost::object_pool< TestObject >* objPoolPtr = new boost::object_pool< TestObject >();

// 創建物件
timerNew.Start();
for (unsigned int i = 0; i < testNum; i ++)
{
	TestObject* obj = objPoolPtr->construct(i);
	pool.push_back(obj);
}
timerNew.Stop();

// 刪除 Boost Pool 物件池
timerDelete.Start();
delete objPoolPtr;
timerDelete.Stop();

測試結果如下圖所示:

Test Suite 2 Mod
Test Suite 2 Mod

由新增的 Boost Pool Ptr 試驗結果可知,如果直接對 Boost Pool 物件池進行刪除(池中所有物件都會被刪除),將能夠獲得非常出色的效能表現;但是如果對單一物件進行物件毀滅與記憶體歸還動作時,就只能夠得出非常緩慢而糟糕的效能表現。

量測出三者的執行時期效能之後,在其他面向的考量上,Loki Library 與 Boost Pool Library 都擁有能夠跨平台的優勢,而 HPHA 由於使用了 Win32 平台的特殊記憶體配置函式,所以沒辦法直接移植到其他平台上使用。評估跨平台、多執行緒支援、易用性與平均效能表現後,總的來說,我對於這三項池式配置技術的評比如下:

  • HPHA:★★★
  • Loki SmallObj:★★★
  • Boost Pool:★★★★

最後我所得出的結論是,只要程式設計者能夠確保在遊戲系統中,不會連續性地刪除單一的遊戲物件,就可以放心地使用 Boost Pool 進行記憶體池式配置與管理,保證能夠得到非常令人滿意的效能表現,遠遠勝過於使用傳統的 operator new 操作,以及 Loki Library 與 HPHA 的池式配置技術。

如果讀者有興趣深入瞭解 Boost.Pool 的設計架構與實作細節,請參考這篇由侯捷先生所寫的「Boost技術與應用系列文章(2)Boost.Pool」(PDF 檔)。我在網路上搜尋 Boost 函式庫的相關資訊時,恰巧挖到了這篇絕佳的文章,才知道侯捷在《Run! PC》雜誌上刊載過許多與 Boost C++ Libraries 主題相關的深入技術文章;可惜的是,目前我只有搜尋到唯一這篇文章可供下載。

對於任何程式系統來說,不論是再精巧神妙的設計或實作方式,都會具有獨特的優勢以及劣勢。有的解決方案執行時期效能很高,代價卻是多出一倍的記憶體使用量;有的解決方案記憶體用量極少,卻會佔去大量的 CPU 資源;有的解決方案兼具速度與空間的優勢,卻無法滿足跨平台的需求。這是程式系統的設計者與使用者都必然會遭遇到的「取捨」(Tradeoff) 難題,也正是程式設計領域裡最令人目眩神迷的樂趣之一。

執行檔及原始碼下載:PooledAllocation_TestSuite.7z (下載次數: 1427 )
(附註說明:如果要自行建置測試專案,專案裡已經包含了 HPHA 的原始碼以及編譯完成的 Loki Library 函式庫,另外還需要自行下載 Boost C++ Libraries,並且設定正確的表頭檔路徑才能夠順利建置專案。)

26 Replies to “記憶體配置:Pooled Allocation技術評比與效能測試”

  1. 在自己電腦上測試了一下原始碼,結果發現在我這裡Boost並沒有出現壓倒性的優勢,大概是配置不同?
    (因爲沒有Windows Library所以擅自把HPHA砍掉了)

    Test choice: 1
    Test object count: 500000
    [TestSuite1] object size = 8 bytes
    operator new: 464.478 ms
    Loki SmallObj: 348.21 ms
    Boost Pool: 303.65 ms

    [TestSuite1] object size = 64 bytes
    operator new: 466.355 ms
    Loki SmallObj: 353.146 ms
    Boost Pool: 305.463 ms

    [TestSuite1] object size = 280 bytes
    operator new: 1051.53 ms
    Loki SmallObj: 1151.07 ms
    Boost Pool: 859.474 ms

  2. 補充:

    1.看來是optimization的設置有很大影響:把optimization改成Full Optimization之後Boost就完全勝出了

    2.看到測試2中Deallocation的結果,我猜boost::pool内部會不會是使用普通array的方式存放物件,因而每次刪除都會把後面的物件往前移動,才導致效率的低下。
    稍微更改刪除部分的代碼如下:

    timerDelete.Start();
    unsigned int i = testNum;
    do {
    objPool.destroy(pool[–i]);
    } while (i > 0);
    timerDelete.Stop();

    果然這樣pool的日子好過多了。

  3. 關於boost::pool,本人也有使用在專案上。
    因為前人所寫的架構很差,導致要一個人物要建立上萬的物件(frame object),
    而且只能一個一個new,一個一個delete,所以當玩家愈多時,這效能真的差到不行。

    當初有把boost::pool來取代operator new,效率沒有比operator new好,
    所以滿讓我失望的。

    看了你的實驗之後,原來問題出在delete上。

    其實我剛進入此行業,就是研究記憶體管理部分,也在某專案上,
    前人所使用的Free List。但是我一看到使方式,就感到相當厭惡,
    因為對於online game來說,只要玩家一多和一少之後,這個東西只是佔著「茅坑不拉屎」,
    有許多的記憶體佔著不用而浪費掉。

    後來導入boost::shared_ptr方式,再加上「資源回收」的機制來取代Free List。

    之前有想過比較特殊的資源管理,優點是有效善用記體體,那就是table的方式,
    簡單說:利用玩家常常在練功的地方,對於此地方的資源作少次的資源釋放。
    不過此方式要經過玩家長久時間去遊玩,此table會更有幫助也更精準。
    但是玩家一直在地圖中環遊世界,此方式就等於廢物。

    以上是一些經驗,本人已經沒在研究記憶體管理了。
    滿感謝你的文章,讓我可以將boost::pool重出江湖XD。
    在未來的專案上會強力去支援它。

  4. @Wxy:
    非常感謝你的測試數據與刪除程序改良!

    我之前始終不能明白為何 Deallocation 的效能如此差勁,修改之後的刪除程序果然快上非常非常多!可見得 Boost Pool 的確會在歸還記憶體時進行某種搬移動作。但若在一般的使用情境中,恐怕很難限制程式系統由最末端開始刪除物件,而 random access deallocation 程序的效能我估計約為 O(n^2) 左右之差,在使用 Boost Pool 時還是需要特別留意才行。

    @gino:
    謝謝,歡迎分享你們的使用心得~

    @藍斯洛:
    謝謝,我也是才剛開始探索 Boost 的廣大世界而已。Boost 真的是妙用無窮也樂趣無窮哪~

    @vamper:
    我認為 Boost Pool 並不適合完全取代 operator new 操作。

    如果在物件數量不多或大致固定的情境中,使用 Boost Pool 反而會產生許多未被使用的閒置記憶體空間,所以在專案中,還是需要視系統架構與功能層面的實際需求來調整運用。最好能夠同時實作 operator new 與 Boost Pool 兩種記憶體配置方案,然後再 profiling 兩者於遊戲系統中的執行效能,才能確認使用 Boost Pool 是否真的能夠帶來益處。另外,high level 的資源管理系統同樣也很重要哩。

    感謝各位的回應~ :)

  5. 侯捷寫了一系列關於 boost 的文章,除了 Run!PC 外,也同時在對岸的(程序員〉雜誌上連載。
    有興趣的話可以到天龍書局,剛進門的地方會擺一些當期或過期的(程序員〉雜誌。
    基本上有侯捷這系列文章的雜誌,從封面就可以看出來了。

  6. 記憶體(循序)Deallocation,之所以效能如此差勁的原因,
    直接講結論的話,主要是在於
    「『Deallocate 時要找出前一塊空的 chunk』的這個動作是從第一個 chunk 循序向後找的」
    而之所以要找出前一塊空的 chunk, 則是因為 block 中的 freelist 不是雙向的 linklist,
    為了要維持 freelist, 因此當 chunk 歸還時, 需從頭找出 “被歸還chunk” 的前一個 free-chunk,
    以更新 list 的前後 link 關係。
    ==========
    前面這段或許有點模糊,具體來說,可以先看一下侯捷那篇文章中的圖22~圖24
    瞭解記憶體歸還的演算法。
    接著直接看 simple_segregated_storage.hpp 內的
    simple_segregated_storage.ordered_free() 函式
    這個是歸還(即圖22~圖24這一段操作)的程式碼實作,
    而這裡頭的 find_prev(chunk) 就是效能瓶頸所在了,進去看就不難瞭解原因所在。
    ==========
    這部份的複雜度,如你所推測的一般,是 O(n^2) 沒錯,
    通常來講,benchmark 不會這麼糟,只是你的 Test code, 跑得剛好是 worst case,
    所以所耗費的時間才會差上好幾個數量級

  7. @yuxioz:
    原來侯捷在《程序員》裡也有連載 Boost 的相關文章呀!下次再去天瓏書局挖寶。 = =+

    看完你的解釋之後,我終於瞭解 Boost Pool 背後的實作結構,以及 Deallocation 的複雜度為何會達到 O(n^2) 的程度了。Boost Pool 使用 single linked list 的優點在於能夠節省記憶體空間,而缺點就是歸還記憶體時必須付出額外的運算時間。

    大感謝你的迴響~ :D

  8. 把測試的次數改成500萬次,不知道為什麼Hpha大型物件的時間變的超級長,幾乎快要是new的10倍以上。

    底下請看最後一行的數據,HPHA:526044 ms 218.827 ms
    ====================================

    輸入測試項目> 2
    輸入測試次數> 5000000
    [TestSuite2] object size = 8 bytes

    operator new: 760.12 ms 866.539 ms
    HPHA: 268.646 ms 236.579 ms
    [TestSuite2] object size = 64 bytes

    operator new: 1155.29 ms 985.208 ms
    HPHA: 492.589 ms 272.771 ms
    [TestSuite2] object size = 280 bytes

    operator new: 58337.4 ms 44305 ms
    HPHA: 526044 ms 218.827 ms

  9. @LMJ:
    你好,

    500 萬次太多了。我想應該有兩種可能性,其一是記憶體使用量超過負荷了,其二是 operator new 的配置與歸還記憶體行為,影響了後續 HPHA 的配置需求。如果你需要進行極大數量的測試,我會建議將不同的記憶體配置方法分開進行獨立測試比較準確,例如:

    1. 重新開機,只測試 500 萬次 operator new。
    2. 再重新開機,只測試 500 萬次 HPHA。

    然後再將兩者的結果做比較。

  10. 想請問一下有關HPHA的問題:
    按照上面的範例,幾乎都是類似new一個單一類別,若是想要用陣列的形式呢?
    例如:char* p = new char[50];這樣的使用方法,如何在HPHA實現?

    我用您提供的HPHA源碼,寫了以下幾個小段,想請問這樣做是否正確?
    template
    inline T* custom_new_array(size_t count) {
    void* p = gAllocator.alloc( sizeof(T) * count );
    return new (p, custom_tag()) T[count];
    }

    template
    inline void custom_delete_array(T* ptr , size_t count)
    {
    T* head = ptr;

    for( size_t i=0 ; i~T();
    }
    ptr += i * sizeof(T);
    }

    //gAllocator.free(head);
    gAllocator.free(head, sizeof(T) * count );
    }
    使用的時候,我是用下面這種方法來模擬new char[50]的語句
    char* ptr = custom_new_array(12);
    custom_delete_array(ptr,12);

    因為不知道這樣到底正不正確,想請您幫忙測試

  11. 我發現<>角括號內容都消失了,所以重新發一次,請測試的時候把全型改成半型

    template<class T>
    inline T* custom_new_array(size_t count) {
    void* p = gAllocator.alloc( sizeof(T) * count );
    return new (p, custom_tag()) T[count];
    }

    template<class T>
    inline void custom_delete_array(T* ptr , size_t count)
    {
    T* head = ptr;

    for( size_t i=0 ; i~T();
    }
    ptr += i * sizeof(T);
    }

    //gAllocator.free(head);
    gAllocator.free(head, sizeof(T) * count );
    }
    ================

    char* ptr = custom_new_array<char>(12);
    custom_delete_array<char>(ptr,12);

  12. @LMJ:
    HPHA 的實作細節我沒有深入研究太多,但我認為你上述這樣的作法不太正確。而且配置一整個陣列物件的方式,與 Pooled Allocation 機制的原始用意有所抵觸。如果你需要使用陣列方式配置記憶體的話,或許可以考慮包裝成一個 struct 來使用,例如:

    struct CharArray
    {
    CharArray() {}
    char data[12];
    };

    CharArray* object = custom_new<CharArray>();

    P.S. 半形的角括號,會被辨識成 HTML 標籤,目前還不知道如何解決。 Orz

  13. 半形的大於小於會被當成html標籤..

    只要用& lt; (要連起來 -> <)跟 & gt; (一樣要連起來 -> >)

    就可以打出小於跟大於囉~~

  14. 以前幫實驗室架blog,用過一陣子的wordpress,我想應該有選項可以關閉對留言內容的html支援,將其視為純文字處理

  15. @larz:
    可是如果關掉 html 標籤,我就沒辦法在迴響中放超連結或者其他的東西了。所以我想還是用上面的密技來輸入大於和小於符號吧!或者是用全形的<和>代替也可以喔~ XD

    謝謝你的迴響。 ^^

  16. 最近我也在研究這個議題,不過我是從侯捷的STL源碼剖析下手的,不過奇怪的是有提到free list的配置,卻未提到如何釋放free list所佔用的空間。在網路上找到的相關資料有http://www.mscto.com/vc/2009022675140_4.html和http://stlport.sourceforge.net/FAQ.shtml#leaks。不曉得SGI STL是否真有把記憶體釋放交給OS的毛病?不曉得STLport是否真有修正此問題?

  17. @Isaac:
    你好,

    關於 Free list 的設計議題,建議可以去找《Modern C++ Design》這本書看看,其中有一整個章節著重在以 policy-based design 為基礎的 Free list 設計實做主題上。

    至於 STL,我自己是沒有用過 STLport 函式庫,但我想它的 FAQ 所述應該沒錯。而標準版的 STL,確實在記憶體釋放上有一些很特殊的「眉角」存在。

  18. @JK:
    你提供的連結只是那篇文章中的程式碼而已,原文對於 Boost.Pool 有進一步的深入介紹。我想八成是該雜誌將 PDF 檔移除了…… Orz

  19. 我覺得還是要看狀況來決定,比方command(記憶用量很小…)的話,也許用Small Object會比較好,因為會反覆地new or delete。

  20. @夢癡:
    是的,依照記憶體的使用量與使用頻率採用不同策略,盡可能地降低 new/delete 的呼叫次數才是上策。

  21. @匿名:
    這裡比較的是記憶體配置的速度,和 std::vector 的 reserve() 沒有關連性喔。vector 只是用來暫時儲存以 new operator 創建出來的物件的指標,以利後續的物件刪除作業。

Leave a Reply