程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> C++ STL內存配置的設計思想與關鍵源碼分析

C++ STL內存配置的設計思想與關鍵源碼分析

編輯:關於C語言
 

下面會結合關鍵源碼分析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. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved