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