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