如何用源碼分析C++ STL內存配置的設計思想

這篇文章將為大家詳細講解有關如何用源碼分析C++ STL內存配置的設計思想，文章內容質量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關知識有一定的了解。

下面會結合關鍵源碼分析C++STL(SGI版本)的內存配置器設計思想。

1、allocator的簡短介紹

我閱讀的源碼是SGI公司的版本，也是看起來最清楚的版本，各種命名最容易讓人看懂。allocator有人叫它空間配置器，因為空間不一定是內存，也可以是磁盤或其他輔助存儲介質。我說的內存配置就是指的allocator。

C++標準規范了allocator的一些必要接口，由各個廠家實現。SGI的版本與眾不同，也與標準規范不同，它的名稱是alloc而不是allocator，且不接受任何參數。

假設你在程序中顯示寫出allocator，不能像下面這樣寫：

vector<int, std::allocator<int> > iv;        //錯誤的

必須要這樣寫才對：

vector<int, std::alloc> iv                    //好的

雖然SGI STL并不符合規范，但我們用起來好像很自然。這是因為我們使用時空間配置器是缺省的，不需要我們自行指定。例如，STL中vector的聲明如下：

注意：下文我基本就用截圖來解釋代碼了，因為我發現比起粘貼代碼，這樣更清晰（有顏色對比）。

2、源碼文件簡單介紹

STL標準規定：STL的allocator定義于<Memory>文件中，<Memory>主要包含了一些頭文件，我們主要說的是兩個：

<stl_alloc.h>負責內存空間的配置與釋放；<stl_construct.h>負責對象內容的構造與析構

3、構造和析構工具：construct()和destroy()

先來說一下簡單的<stl_construct.h>文件。這部分也不涉及什么思想，只是有一個版本的destroy()應該認真看看。

（1）構造工具：construct()

construct()只有一個版本：

這里使用了placement new表達式（定位new 表達式），它的作用是p指向的內存類型為T1，用value值初始化這塊內存。

（2）析構工具

destroy()倒是有幾個版本：

***個版本：

這種顯示調用析構函數的做法，你也應該要熟悉。

第二個版本：

第二個版本可有點說法。調用層次是這樣的：destroy-> __destroy-> __destroy_aux，__destroy_aux最終調用***個版本的destroy。這個版本的destroy接受一對迭代器作為參數，析構迭代器所指向的范圍內元素。

講解這個流程前，先簡單說一下trivial_destructor。

如果用戶不定義析構函數，而是用編譯器合成的，則說明析構函數基本沒有什么用（但默認會被調用），稱之為trivial destructor。

那么，如果一對迭代器所指向的元素都是trivial destructor的，就沒必要浪費時間對每個對象依次執行它的析構函數了，依靠編譯器的行為就好了。這樣在效率上是一種提升。這是STL allocator優化的一個點。

首先利用value_type()取得迭代器指向對象的型別，再利用__type_traits<T>判斷對象的析構函數是否為trivial_destructor。如果是__true_type就什么都不做，否則循環調用***版本的destroy()。

第三個版本：

這是針對迭代器為char*和wchar_t*的特化版本，看到它們的函數體為空，你應該猜到了，無須執行析構操作。

4、內存的申請與銷毀，std::alloc

內存的申請和銷毀由<stl_alloc.h>負責。SGI關于這一點的設計哲學是：

（1）向system heap要求空間。

（2）考慮多線程狀態。

（3）考慮內存不足時的應變策略。

（4）考慮過多“小型區塊”可能造成的內存碎片問題。

其實我最主要想說的是（3）（4）的設計策略，尤其是內存池的思路。

std::alloc的整體設計思想為：

SGI設計了雙層級配置器，***級配置器直接使用malloc和free；第二級配置器視情況不同采用不同策略：當配置區塊超過128bytes 時，視為“足夠大”，調用***級配置器處理；當配置區塊小于128bytes時，視為“過小”，為降低額外負擔，采用memory  pool（內存池）處理方式，不再借助于***級配置器。

一、***級內存配置器解析

***級配置器主要函數有：allocate分配內存、deallocate釋放內存、reallocate重新分配內存等。

（1）allocate

直接調用C函數malloc，如果內存無法滿足需求，就調用oom_malloc函數。

原來，這是自己實現的handler函數啊，為什么自己實現呢？因為它使用的并不是operator new配置的內存，所以無法使用C++new-handler機制。

關于這個機制，實際上能有不少東西可說呢，如果你不熟悉它的用途或自己實現的方法，我建議你看看《Effective C++》，或者看看我對《Effective C++》做的筆記。我這里主要不是想分析語法方面的東西。

（2）deallocate

代碼放上去就應該明白了。

（3）reallocate

這里依然是調用C的realloc函數，如果調用失敗，就調用oom_realloc函數。

可以看出oom_realloc也是個handler函數。

基本上***級內存配置器就解釋清楚了。這里再提一點：SGI以malloc而非operator new來配置內存一方面是歷史原因，另一方面C++并未提供realloc函數。這樣造成了SGI不能直接使用C++的set_new_handler()，只能自己仿真一個。如何仿真set_new_handler，是有特定模式的。

二、第二級內存配置器解析

第二級內存配置器增加了一些機制，避免太多小額區塊造成的內存碎片。小額區塊帶來的不僅是內存碎片，配置時的額外負擔也是個大問題。額外負擔永遠無法避免，畢竟系統要靠這多出來的空間來管理內存，但區塊越小，額外負擔所占的比例越大，自然越浪費。

第二級內存配置器的整體思想是：

（1）如果申請的區塊超過128bytes，就交給***級內存配置器處理。

（2）如果申請的區塊小于等于128bytes，用內存池管理。

具體為：第二級內存配置器會將任何小額區塊的內存需求上調至8的倍數，并維護16個free-lists，各自管理大小為8、16、24、32、40、48、56、64、72、80、88、96、104、112、120、128字節的小額區塊。

free-lists中節點結構如下：（我已經將這個union注釋）

注意：union的這種用法，也被稱為”柔性數組“成員。本質上，與小端對齊這種存儲方式有關，這是一種技巧。

（1）allocate

第二級內存配置器__default_alloc_template的內存分配接口是allocate函數。

關鍵部分我已經用紅框注釋過了。FREELIST_INDEX(n)函數根據n的值返回16個free-list中合適的那個list的下標。

再看看ROUND_UP(n)，這個函數我認為寫的挺巧妙的，將bytes值調整至8字節的倍數。

理解這個函數你可以先舉幾個bytes值，看看返回值是什么，自然就理解了。refill()函數很有用處，我放在下面再來介紹。

（2）deallocate()

首先判斷區塊大小，大于128字節就調用***級配置器，否則就根據需要回收的字節大小，判斷出應該把它回歸到哪個free list，然后由這個free list回收。

（3）refill()

這個函數挺重要的，所以要單獨拿出來介紹。當free list中沒有可用的區塊時，就調用這個函數，為該free  list重新填充一部分空間。新的空間取自內存池（由chunk_alloc完成）。缺省取得20個新區塊，如果內存池空間不足，獲得的新區塊數目可能小 于20。

圖中兩個紅框是值得注意的兩個點。一旦從內存池獲得內存區塊后，拿出一個給調用者，另外的還要找到合適的free list”穿“起來。

（4）內存池函數chunk_alloc()

內存池一直用來供給free list。下面要將這個函數分開截圖說明了。

***個分支：看看內存池內的容量夠不夠，夠的話直接拿走就好。

第二個分支：內存池不夠20個塊的容量，但是大于等于1個塊的長度，就把剩下的都給出去了。此時，內存池是空的。

第三個分支：如果內存池連1個對應的塊都不能提供了，比如需要32字節，但只有8字節了，這時候***的做法是把這8個字節鏈接到相應的free list利用上。不出意料，此時內存池也是空的。

第四個分支：內存池空空如也，所以內存池求助于運行時堆，堆也沒有那么多空間了，于是就檢查這16個free list中有哪些塊沒用過呢，把這些補充到內存池。

第五個分支：沒錯，heap也無能為力了，內存池干脆直接調用***級配置器，因為***級配置器有new-handler機制，或許有機會釋放其他內存拿來此處調用呢。如果可以，就成功否則拋出bad-alloc異常。

小結：

如果別人問我STL內存配置的思想。我可能會這樣說：C++STL是兩級配置內存的，具體來說：***級負責管理大塊內存，要保證有類似new- handler的機制；第二級負責管理小塊內存，為了更好的管理內存碎片，建立16個鏈表，每個鏈表“穿”著一塊一塊固定大小的內存，這16個鏈表（0至 15）分別“穿”的內存是8、16、24&hellip;128倍數關系。需要內存時，從“合適”的鏈表取走，如果“合適”的鏈表內存不夠用了，從內存池里拿，如果內存 池不夠用了，從運行時heap里拿，如果heap也溢出了，就交給***級配置器，因為它有new-handler機制。

關于如何用源碼分析C++ STL內存配置的設計思想就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。