建站
咨詢
售后
建站咨詢
新聞中心
下面會(huì)結(jié)合關(guān)鍵源碼分析C++STL(SGI版本)的內(nèi)存配置器設(shè)計(jì)思想。關(guān)鍵詞既然是“思想”，所以重點(diǎn)也就呼之欲出了。
成都創(chuàng)新互聯(lián)公司成立于2013年，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢(mèng)想脫穎而出為使命，1280元下陸做網(wǎng)站,已為上家服務(wù),為下陸各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話:18982081108
1、allocator的簡(jiǎn)短介紹
我閱讀的源碼是SGI公司的版本，也是看起來最清楚的版本，各種命名最容易讓人看懂。allocator有人叫它空間配置器，因?yàn)榭臻g不一定是內(nèi)存，也可以是磁盤或其他輔助存儲(chǔ)介質(zhì)。我說的內(nèi)存配置就是指的allocator。
C++標(biāo)準(zhǔn)規(guī)范了allocator的一些必要接口，由各個(gè)廠家實(shí)現(xiàn)。SGI的版本與眾不同，也與標(biāo)準(zhǔn)規(guī)范不同，它的名稱是alloc而不是allocator，且不接受任何參數(shù)。
假設(shè)你在程序中顯示寫出allocator，不能像下面這樣寫：
vector
必須要這樣寫才對(duì)：
vector
雖然SGI STL并不符合規(guī)范，但我們用起來好像很自然。這是因?yàn)槲覀兪褂脮r(shí)空間配置器是缺省的，不需要我們自行指定。例如，STL中vector的聲明如下：
注意：下文我基本就用截圖來解釋代碼了，因?yàn)槲野l(fā)現(xiàn)比起粘貼代碼，這樣更清晰（有顏色對(duì)比）。
2、源碼文件簡(jiǎn)單介紹
STL標(biāo)準(zhǔn)規(guī)定：STL的allocator定義于
3、構(gòu)造和析構(gòu)工具：construct()和destroy()
先來說一下簡(jiǎn)單的
（1）構(gòu)造工具：construct()
construct()只有一個(gè)版本：
這里使用了placement new表達(dá)式（定位new 表達(dá)式），它的作用是p指向的內(nèi)存類型為T1，用value值初始化這塊內(nèi)存。
（2）析構(gòu)工具
destroy()倒是有幾個(gè)版本：
***個(gè)版本：
這種顯示調(diào)用析構(gòu)函數(shù)的做法，你也應(yīng)該要熟悉。
第二個(gè)版本：
第二個(gè)版本可有點(diǎn)說法。調(diào)用層次是這樣的：destroy-> __destroy-> __destroy_aux，__destroy_aux最終調(diào)用***個(gè)版本的destroy。這個(gè)版本的destroy接受一對(duì)迭代器作為參數(shù)，析構(gòu)迭代器所指向的范圍內(nèi)元素。
講解這個(gè)流程前，先簡(jiǎn)單說一下trivial_destructor。
如果用戶不定義析構(gòu)函數(shù)，而是用編譯器合成的，則說明析構(gòu)函數(shù)基本沒有什么用（但默認(rèn)會(huì)被調(diào)用），稱之為trivial destructor。
那么，如果一對(duì)迭代器所指向的元素都是trivial destructor的，就沒必要浪費(fèi)時(shí)間對(duì)每個(gè)對(duì)象依次執(zhí)行它的析構(gòu)函數(shù)了，依靠編譯器的行為就好了。這樣在效率上是一種提升。這是STL allocator優(yōu)化的一個(gè)點(diǎn)。
首先利用value_type()取得迭代器指向?qū)ο蟮男蛣e，再利用__type_traits
第三個(gè)版本：
這是針對(duì)迭代器為char*和wchar_t*的特化版本，看到它們的函數(shù)體為空，你應(yīng)該猜到了，無須執(zhí)行析構(gòu)操作。
4、內(nèi)存的申請(qǐng)與銷毀，std::alloc
內(nèi)存的申請(qǐng)和銷毀由
（1）向system heap要求空間。
（2）考慮多線程狀態(tài)。
（3）考慮內(nèi)存不足時(shí)的應(yīng)變策略。
（4）考慮過多“小型區(qū)塊”可能造成的內(nèi)存碎片問題。
其實(shí)我最主要想說的是（3）（4）的設(shè)計(jì)策略，尤其是內(nèi)存池的思路。
std::alloc的整體設(shè)計(jì)思想為：
SGI設(shè)計(jì)了雙層級(jí)配置器，***級(jí)配置器直接使用malloc和free；第二級(jí)配置器視情況不同采用不同策略：當(dāng)配置區(qū)塊超過128bytes 時(shí)，視為“足夠大”，調(diào)用***級(jí)配置器處理；當(dāng)配置區(qū)塊小于128bytes時(shí)，視為“過小”，為降低額外負(fù)擔(dān)，采用memory pool（內(nèi)存池）處理方式，不再借助于***級(jí)配置器。
一、***級(jí)內(nèi)存配置器解析
***級(jí)配置器主要函數(shù)有：allocate分配內(nèi)存、deallocate釋放內(nèi)存、reallocate重新分配內(nèi)存等。
（1）allocate
直接調(diào)用C函數(shù)malloc，如果內(nèi)存無法滿足需求，就調(diào)用oom_malloc函數(shù)。
原來，這是自己實(shí)現(xiàn)的handler函數(shù)啊，為什么自己實(shí)現(xiàn)呢？因?yàn)樗褂玫牟⒉皇莖perator new配置的內(nèi)存，所以無法使用C++new-handler機(jī)制。
關(guān)于這個(gè)機(jī)制，實(shí)際上能有不少東西可說呢，如果你不熟悉它的用途或自己實(shí)現(xiàn)的方法，我建議你看看《Effective C++》，或者看看我對(duì)《Effective C++》做的筆記。我這里主要不是想分析語法方面的東西。
（2）deallocate
代碼放上去就應(yīng)該明白了。
（3）reallocate
這里依然是調(diào)用C的realloc函數(shù)，如果調(diào)用失敗，就調(diào)用oom_realloc函數(shù)。
可以看出oom_realloc也是個(gè)handler函數(shù)。
基本上***級(jí)內(nèi)存配置器就解釋清楚了。這里再提一點(diǎn)：SGI以malloc而非operator new來配置內(nèi)存一方面是歷史原因，另一方面C++并未提供realloc函數(shù)。這樣造成了SGI不能直接使用C++的set_new_handler()，只能自己仿真一個(gè)。如何仿真set_new_handler，是有特定模式的。
#p#
二、第二級(jí)內(nèi)存配置器解析
第二級(jí)內(nèi)存配置器增加了一些機(jī)制，避免太多小額區(qū)塊造成的內(nèi)存碎片。小額區(qū)塊帶來的不僅是內(nèi)存碎片，配置時(shí)的額外負(fù)擔(dān)也是個(gè)大問題。額外負(fù)擔(dān)永遠(yuǎn)無法避免，畢竟系統(tǒng)要靠這多出來的空間來管理內(nèi)存，但區(qū)塊越小，額外負(fù)擔(dān)所占的比例越大，自然越浪費(fèi)。
第二級(jí)內(nèi)存配置器的整體思想是：
（1）如果申請(qǐng)的區(qū)塊超過128bytes，就交給***級(jí)內(nèi)存配置器處理。
（2）如果申請(qǐng)的區(qū)塊小于等于128bytes，用內(nèi)存池管理。
具體為：第二級(jí)內(nèi)存配置器會(huì)將任何小額區(qū)塊的內(nèi)存需求上調(diào)至8的倍數(shù)，并維護(hù)16個(gè)free-lists，各自管理大小為8、16、24、32、40、48、56、64、72、80、88、96、104、112、120、128字節(jié)的小額區(qū)塊。
free-lists中節(jié)點(diǎn)結(jié)構(gòu)如下：（我已經(jīng)將這個(gè)union注釋）
注意：union的這種用法，也被稱為”柔性數(shù)組“成員。本質(zhì)上，與小端對(duì)齊這種存儲(chǔ)方式有關(guān)，這是一種技巧。
（1）allocate
第二級(jí)內(nèi)存配置器__default_alloc_template的內(nèi)存分配接口是allocate函數(shù)。
關(guān)鍵部分我已經(jīng)用紅框注釋過了。FREELIST_INDEX(n)函數(shù)根據(jù)n的值返回16個(gè)free-list中合適的那個(gè)list的下標(biāo)。
再看看ROUND_UP(n)，這個(gè)函數(shù)我認(rèn)為寫的挺巧妙的，將bytes值調(diào)整至8字節(jié)的倍數(shù)。
理解這個(gè)函數(shù)你可以先舉幾個(gè)bytes值，看看返回值是什么，自然就理解了。refill()函數(shù)很有用處，我放在下面再來介紹。
（2）deallocate()
首先判斷區(qū)塊大小，大于128字節(jié)就調(diào)用***級(jí)配置器，否則就根據(jù)需要回收的字節(jié)大小，判斷出應(yīng)該把它回歸到哪個(gè)free list，然后由這個(gè)free list回收。
（3）refill()
這個(gè)函數(shù)挺重要的，所以要單獨(dú)拿出來介紹。當(dāng)free list中沒有可用的區(qū)塊時(shí)，就調(diào)用這個(gè)函數(shù)，為該free list重新填充一部分空間。新的空間取自內(nèi)存池（由chunk_alloc完成）。缺省取得20個(gè)新區(qū)塊，如果內(nèi)存池空間不足，獲得的新區(qū)塊數(shù)目可能小 于20。
圖中兩個(gè)紅框是值得注意的兩個(gè)點(diǎn)。一旦從內(nèi)存池獲得內(nèi)存區(qū)塊后，拿出一個(gè)給調(diào)用者，另外的還要找到合適的free list”穿“起來。
（4）內(nèi)存池函數(shù)chunk_alloc()
內(nèi)存池一直用來供給free list。下面要將這個(gè)函數(shù)分開截圖說明了。
***個(gè)分支：看看內(nèi)存池內(nèi)的容量夠不夠，夠的話直接拿走就好。
第二個(gè)分支：內(nèi)存池不夠20個(gè)塊的容量，但是大于等于1個(gè)塊的長度，就把剩下的都給出去了。此時(shí)，內(nèi)存池是空的。
第三個(gè)分支：如果內(nèi)存池連1個(gè)對(duì)應(yīng)的塊都不能提供了，比如需要32字節(jié)，但只有8字節(jié)了，這時(shí)候***的做法是把這8個(gè)字節(jié)鏈接到相應(yīng)的free list利用上。不出意料，此時(shí)內(nèi)存池也是空的。
第四個(gè)分支：內(nèi)存池空空如也，所以內(nèi)存池求助于運(yùn)行時(shí)堆，堆也沒有那么多空間了，于是就檢查這16個(gè)free list中有哪些塊沒用過呢，把這些補(bǔ)充到內(nèi)存池。
第五個(gè)分支：沒錯(cuò)，heap也無能為力了，內(nèi)存池干脆直接調(diào)用***級(jí)配置器，因?yàn)?**級(jí)配置器有new-handler機(jī)制，或許有機(jī)會(huì)釋放其他內(nèi)存拿來此處調(diào)用呢。如果可以，就成功否則拋出bad-alloc異常。
小結(jié)：
如果別人問我STL內(nèi)存配置的思想。我可能會(huì)這樣說：C++STL是兩級(jí)配置內(nèi)存的，具體來說：***級(jí)負(fù)責(zé)管理大塊內(nèi)存，要保證有類似new- handler的機(jī)制；第二級(jí)負(fù)責(zé)管理小塊內(nèi)存，為了更好的管理內(nèi)存碎片，建立16個(gè)鏈表，每個(gè)鏈表“穿”著一塊一塊固定大小的內(nèi)存，這16個(gè)鏈表（0至 15）分別“穿”的內(nèi)存是8、16、24…128倍數(shù)關(guān)系。需要內(nèi)存時(shí)，從“合適”的鏈表取走，如果“合適”的鏈表內(nèi)存不夠用了，從內(nèi)存池里拿，如果內(nèi)存 池不夠用了，從運(yùn)行時(shí)heap里拿，如果heap也溢出了，就交給***級(jí)配置器，因?yàn)樗衝ew-handler機(jī)制。
本文名稱：C++STL內(nèi)存配置的設(shè)計(jì)思想與關(guān)鍵源碼分析
標(biāo)題路徑：http://fisionsoft.com.cn/article/cdpihps.html
