低調做技術__歡迎移步我的獨立博客 codemaro.com 微博 kevinlynx
stl中各種容器都有一個可選的模板參數：allocator，也就是一個負責內存分配的組件。STL標準規定的allcator被定義在memory文件中。STL標準規定的allocator只是單純地封裝operator new，效率上有點過意不去。
SGI實現的STL里，所有的容器都使用SGI自己定義的allocator。這個allocator實現了一個small object的內存池。Loki里為了處理小對象的內存分配，也實現了類似的內存管理機制。
該內存池大致上，就是一大塊一大塊地從系統獲取內存，然后將其分成很多小塊以鏈表的形式鏈接起來。其內部有很多不同類型的鏈表，不同的鏈表維護不同大小的內存塊。每一次客戶端要求分配內存時，allcator就根據請求的大小找到相應的鏈表(最接近的尺寸)，然后從鏈表里取出內存。當客戶端歸還內存時，allocator就將這塊內存放回到對應的鏈表里。
我簡單地畫了幅圖表示整個結構：
allocator內部維護一個鏈表數組，數組元素全部是鏈表頭指針。鏈表A每一個節點維護一個8bytes的內存塊，鏈表B每一個節點維護一個16bytes的內存塊。
當客戶端請求分配10bytes的內存時，allocator將10調整為最接近的16bytes(只能大于10bytes)，然后發現16bytes這個鏈表(鏈表B)里有可用內存塊，于是從B里取出一塊內存返回。當客戶端歸還時，allocator找到對應的鏈表，將內存重新放回鏈表B即可。
大致過程就這么簡單，也許有人要說用鏈表維護一塊內存，鏈表本身就會浪費一些內存(在我很早前接觸內存池時，總會看到類似的論點= =|)，其實通過一些簡單的技巧是完全可以避免的。例如，這里allocator維護了很多內存塊，反正這些內存本身就是閑置的，因此我們就可以直接在這些內存里記錄鏈表的信息(下一個元素)。
還是寫點代碼詳細說下這個小技巧：
這樣，通過header指針和next域，就可以逐塊(這里是10byts)地訪問mem所指向的內存，而這些鏈表的節點，都是直接保存在這塊內存里的，所以完全沒有額外消耗。
我用C模仿著SGI的這個allocator寫了個可配置的內存池，在其上按照STL的標準包裝了一個allocator，可以直接用于VC自帶的STL里。測試代碼稍微測試了下，發現在不同的機器上有明顯的差距。
posted on 2008-06-12 21:26 Kevin Lynx 閱讀(8062) 評論(10) 編輯 收藏 引用 所屬分類: c/c++ 、game develop 、通用編程
我自己也曾經做過一個內存池，方法沒去比較不知道如何。 我的內存池是一個模板，專門用于產生特定類型的對象。因此構造函數讓人制定一次創建的Buffer的尺寸。然后使用平衡樹組織了一個不可變大小的池從而獲得一個可變大小的池。平衡樹的比較由池之間的起始指針的比較結果決定，于是尋找一個指針屬于哪個池也比較快。Buffer的尺寸可以根據實際需要調整，我用這個池實現自己的Yacc的時候，發現平衡樹最多就三個節點，不過文法數量也不多，僅有100條，不能當壓力測試看待。 每一個固定尺寸的池還有一個可變長度實現的堆棧，用于存放空閑位置。這樣的話從一個固定尺寸的池獲取和刪除都是O(1)。 空間浪費在平衡樹和這個空閑索引堆棧了。 回復 更多評論
唉 水已經滿了 會錯過很多東西的 回復 更多評論
以前我也試著這樣子去造個輪子，但是到最后發現沒有必要,STL這個就是一個free-list，但是如果你的這個用在多線程中就很崩潰的，你想想，不同的桶都有自己的一個瑣，這樣子瑣就會很多，另外增加了復雜度還不討好，除非在很關鍵的地方我使用我的內存管理器，其他的地方還是stl吧 回復 更多評論
@關中刀客 STL默認那個內存池。。。STL默認沒內存池。SGI的STL里那個內存池不是標準的。VC下的STL就沒這個。 回復 更多評論
終于對allocator有一點了解了，自己寫的allocator里面放的內存池結構也可以用C++封裝吧？還有allocator中的rebind結構是干什么用的呢？ 回復 更多評論
@Gohan rebind可以讓allocator<Tp>的保存者分配其他類型的內存。例如，當實例化list時(例如list<int,my_allocator<int> > )，在list內部就保存著一個my_allocator<int>，但是list需要為自己分配list_node，就是說它需要另一個allocator，那么這個時候就可以通過rebind來完成。 回復 更多評論
@Kevin Lynx明白了，容器根據模板參數Alloc，可以用Alloc::rebind<list_node>::other這樣就能得到一個list_node類型的內存分配對象了吧，多謝指點 回復 更多評論
很好；） 回復 更多評論
既然要這樣設計，那為何不直接使用數組呢？ 回復 更多評論
有個疑問，如果創建很多個map，list，是否只能用同一個內存池？可以各個map對應不同的內存池嗎？ 回復 更多評論
Powered by: C++博客 Copyright © Kevin Lynx