對(duì)C++程序內(nèi)存管理的精雕細(xì)琢

2019-11-17 05:48:46

字體：大中小

供稿：網(wǎng)友

　　應(yīng)用程序分配內(nèi)存的方法，對(duì)程序的執(zhí)行性能有著深刻的影響。目前，通用的內(nèi)存分配方法本質(zhì)上已非常高效，但仍有改進(jìn)的空間。

　　內(nèi)存分配，不可一層不變

　　今天，對(duì)絕大多數(shù)程序來說，通用的內(nèi)存分配方法--此處指代分配算符（Allocator：即malloc或new），已達(dá)到了理想的速度及滿足了低碎片率的要求，然而，在內(nèi)存分配領(lǐng)域，一丁點(diǎn)的信息都值得探討很久，某些特定程序關(guān)于分配模式的信息，將有助于實(shí)現(xiàn)專門的分配算符，可顯著地提高大多數(shù)高性能要求程序的性能底線。有時(shí)，當(dāng)通用內(nèi)存分配算符平均耗費(fèi)幾百個(gè)時(shí)鐘周期時(shí)，一個(gè)良好的自定義內(nèi)存分配算符可能只需要不到半打的周期。

　　這就是為什么大多數(shù)高性能、高要求的應(yīng)用程序（如GCC、Apache、Microsoft SQL Server），都有著它們自己的內(nèi)存分配算符。也許，把這些專門的內(nèi)存分配算符歸納起來，放進(jìn)一個(gè)庫(kù)中，是個(gè)不錯(cuò)的想法，但是，你的程序可能有不同的分配模式，其需要另外的內(nèi)存分配算符，那怎么辦呢？

　　等等，還有呢，假如我們?cè)O(shè)計(jì)了一種非凡用途的內(nèi)存分配算符，就可以不斷發(fā)展下去，由此可從中篩選出一些，來組成一個(gè)通用目的的內(nèi)存分配算符，假如此通用分配算符優(yōu)于現(xiàn)有的通用分配算符，那么此項(xiàng)設(shè)計(jì)就是有效及實(shí)用的。

　　下面的示例使用了Emery小組的庫(kù)--HeapLayers（http://heaplayers.org/），為了定義可配置的分配算符，其中使用了mixins（在C++社區(qū)中，也被稱為Coplien遞歸模式）：通過參數(shù)化的基來定義類，每一層中只定義兩個(gè)成員函數(shù)，malloc和free：

template <class T>
strUCt Allocator : public T {
　void * malloc(size_t sz);
　void free(void* p);
　//系統(tǒng)相關(guān)的值
　enum { Alignment = sizeof(double) };
　//可選接口e
　size_t getSize(const void* p);
};
　　在每一層的實(shí)現(xiàn)中，都有可能向它的基類請(qǐng)求內(nèi)存，一般來說，一個(gè)不依靠于外界的內(nèi)存分配算符，都會(huì)處在層次的頂層--直接向前請(qǐng)求系統(tǒng)的new和delete操作符、malloc和free函數(shù)。在HeapLayers的術(shù)語(yǔ)中，沒有頂層堆，以下是示例：

struct MallocHeap {
　void * malloc(size_t sz) {
　　return std::malloc(sz);
　}
　void free(void* p) {
　　return std::free(p);
　}
};
　　為獲取內(nèi)存，頂層堆也能通過系統(tǒng)調(diào)用來實(shí)現(xiàn)，如Unix的sbrk或mmap。getSize函數(shù)的情況就比較非凡，不是每個(gè)人都需要它，定義它只是一個(gè)可選項(xiàng)。但假如定義了它，你所需做的只是插入一個(gè)存儲(chǔ)內(nèi)存塊大小的層，并提供getSize函數(shù)，見例1：

　　例1：

template <class SuperHeap>
class SizeHeap {
　union freeObject {
　　size_t sz;
　　double _dummy; //對(duì)齊所需
　};
public:
　void * malloc(const size_t sz) {
　　//添加必要的空間
　　freeObject * ptr = (freeObject *)SuperHeap::malloc(sz + sizeof(freeObject));
　　//存儲(chǔ)請(qǐng)求的大小
　　ptr->sz = sz;
　　return ptr + 1;
　}
　void free(void * ptr) {
　　SuperHeap::free((freeObject *) ptr - 1);
　}
　static size_t getSize (const void * ptr) {
　　return ((freeObject *)ptr - 1)->sz;
　}
};
　　SizeHeap是怎樣實(shí)現(xiàn)一個(gè)實(shí)用的層，并掛鉤于它基類的malloc與free函數(shù)的最好示例，它在完成一些額外的工作之后，把修改好的結(jié)果返回給使用者。SizeHeap為存儲(chǔ)內(nèi)存塊大小，分配了額外的內(nèi)存，再加上適當(dāng)?shù)男⌒恼{(diào)整（指union），盡可能地避免了內(nèi)存數(shù)據(jù)對(duì)齊問題。不難想像，我們可構(gòu)建一個(gè)debug堆，其通過特定模式在內(nèi)存塊之前或之后填充了一些字節(jié)，通過檢查是否模式已被保留，來確認(rèn)內(nèi)存的溢出。事實(shí)上，這正是HeapLayers的DebugHeap層所做的，非常的簡(jiǎn)潔。

　　讓我們?cè)賮砜纯?，以上還不是最理想的狀態(tài)，某些系統(tǒng)已經(jīng)提供了計(jì)算已分配內(nèi)存塊大小的原語(yǔ)（此處指操作符，即前述的分配算符），在這些系統(tǒng)上，SizeHeap實(shí)際上只會(huì)浪費(fèi)空間。在這種情況下（如Microsoft Visual C++），你將不需要SizeHeap與MallocHeap的銜接，因?yàn)镸allcoHeap將會(huì)實(shí)現(xiàn)getSize：

struct MallocHeap {
　... 與上相同 ...
　size_t getSize(void* p) {
　　return _msize(p);
　}
};
　　但似乎還有一些不足之處。想一想，我們是在統(tǒng)計(jì)時(shí)鐘周期，假如一個(gè)系統(tǒng)的malloc聲明了內(nèi)存的塊大小將存儲(chǔ)在實(shí)際塊之前的一個(gè)字中，那將會(huì)怎樣呢？在這種情況下，SizeHeap還是會(huì)浪費(fèi)空間，因?yàn)樗詴?huì)在緊接著系統(tǒng)已植入的塊后存儲(chǔ)一個(gè)字。此處所需的，只是一個(gè)用SizeHeap的方法實(shí)現(xiàn)了getSize的層，但未掛鉤malloc與free。這就是為什么HeapLayers把前面的SizeHeap分成了兩個(gè)，見例2：

　　例2：

template <class Super>
struct UseSizeHeap : public Super {
　static size_t getSize(const void * ptr) {
　　return ((freeObject *) ptr - 1)->sz;
　}
PRotected:
　union freeObject {
　　size_t sz;
　　double _dummy; //對(duì)齊所需
　};
};

template <class SuperHeap>
class SizeHeap: public UseSizeHeap<SuperHeap>{
　typedef typename
　UseSizeHeap<SuperHeap>::freeObject
　freeObject;
public:
　void * malloc(const size_t sz) {
　　//添加必要的空間
　　freeObject * ptr = (freeObject *)SuperHeap::malloc(sz + sizeof(freeObject));
　　//存儲(chǔ)請(qǐng)求的大小
　　ptr->sz = sz;
　　return (void *) (ptr + 1);
　}
　void free(void * ptr) {
　　SuperHeap::free((freeObject *)ptr - 1);
　}
};
　　現(xiàn)在，SizeHeap就會(huì)正確地添加UseSizeHeap層，并利用它的getSize實(shí)現(xiàn)了，而UseSizeHeap也能通過其他配置來使用--這是一個(gè)非常優(yōu)雅的設(shè)計(jì)。

　　一個(gè)實(shí)用的示例：FreelistHeap

　　到目前為止，我們還處于一個(gè)預(yù)備的階段，只有架構(gòu)，還不知怎樣利用這些層來編寫一個(gè)高效專用的內(nèi)存分配算符，也許一個(gè)比較合適的開發(fā)步驟可如下所示：

　　·收集有關(guān)程序?yàn)槊糠N內(nèi)存塊大小進(jìn)行分配次數(shù)的信息。

　　·為最經(jīng)常請(qǐng)求的大小（在此稱為S），維持一個(gè)私有、逐一鏈接的列表。
　
　　·對(duì)S的內(nèi)存分配盡可能地從列表中返回內(nèi)存，或者從默認(rèn)分配算符中返回（在分層架構(gòu)中，從上級(jí)層中）。

　　·對(duì)S大小內(nèi)存塊的釋放，把內(nèi)存塊放回至列表中。

　　·一個(gè)精心設(shè)計(jì)的分配策略，應(yīng)可對(duì)范圍大小從S1至S2，使用相同的釋放列表，并消耗同等的內(nèi)存。而所需鏈接列表的操作開銷為O(1)，實(shí)際上只有幾條指令。另外，指向下一條目的指針，能存儲(chǔ)在實(shí)際的塊中（塊中存儲(chǔ)了無(wú)用的數(shù)據(jù)--總為一個(gè)釋放了的塊），因此，對(duì)每個(gè)塊就不需要額外的內(nèi)存了。正因?yàn)榇蠖鄶?shù)應(yīng)用程序分配內(nèi)存的大小都是不同的，所以，對(duì)任何分配算符的實(shí)現(xiàn)來說，釋放列表就必不可少了。

　　下面讓我們來實(shí)現(xiàn)一個(gè)層，由其對(duì)已知靜態(tài)范圍大小從S1至S2，實(shí)現(xiàn)了一個(gè)釋放列表，見例3：

　　例3：

template <class Super, size_t S1, size_t S2>
struct FLHeap {
　~FLHeap() {
　　while (myFreeList) {
　　　freeObject* next = myFreeList->next;
　　　Super::free(myFreeList);
　　　myFreeList = next;
　　}
　}
　void * malloc(const size_t s) {
　　if (s < S1 s > S2)) {
　　　return Super::malloc(s);
　　}
　　if (!myFreeList) {
　　　return Super::malloc(S2);
　　}
　　void * ptr = myFreeList;
　　myFreeList = myFreeList->next;
　　return ptr;
　}
　void free(void * p) {
　　const size_t s = getSize(p);
　　if (s < S1 s > S2) {
　　　return Super::free(p);
　　}
　　freeObject p =reinterpret_cast<freeObject *>(ptr);
　　p->next = myFreeList;
　　myFreeList = p;
　}
private:
　// 嵌入在釋放的對(duì)象中的鏈接列表指針
　class freeObject {
　　public:
　　　freeObject * next;
　};
　//釋放的對(duì)象鏈接列表頭
　freeObject * myFreeList;
};
　　現(xiàn)在，你像如下所示可定義一個(gè)自定義的堆：

typedef FLHeap<
SizeHeap<MallocHeap>,
24,
32>
SmartoHeapo;
　　SmartoHeapo在分配的大小在24至32之間時(shí)，速度相當(dāng)快，對(duì)其它大小來說，也基本上一樣。 QQRead.com 推出數(shù)據(jù)恢復(fù)指南教程數(shù)據(jù)恢復(fù)指南教程數(shù)據(jù)恢復(fù)故障解析常用數(shù)據(jù)恢復(fù)方案硬盤數(shù)據(jù)恢復(fù)教程數(shù)據(jù)保護(hù)方法數(shù)據(jù)恢復(fù)軟件
專業(yè)數(shù)據(jù)恢復(fù)服務(wù)指南原地重新分配（Inplace Resizing）

　　許多的C++程序員都?jí)裘乱郧笥幸环N標(biāo)準(zhǔn)的原語(yǔ)（也即操作符），用于原地重新分配內(nèi)存。眾所周知，C語(yǔ)言中有realloc，其盡可能的原地重新分配內(nèi)存，并在涉及到復(fù)制數(shù)據(jù)時(shí)使用memcpy，但memcpy并不適合于C++對(duì)象，所以，realloc也不適用于C++的對(duì)象。因此，任何一種renew原語(yǔ)都不能用標(biāo)準(zhǔn)C分配符來實(shí)現(xiàn)，這就是為什么C++中沒有renew的原因。

　　以下演示了一種改進(jìn)后的方法，可應(yīng)用于C++代碼中的原地重新分配，請(qǐng)看：

const int n = 10000;
Vec v;
for (int i = 0; i < n; ++i)
v.push_back(0);
　　Metrowerks的Howard Hinnant一直在為實(shí)現(xiàn)應(yīng)用于CodeWarrior標(biāo)準(zhǔn)庫(kù)的原地?cái)U(kuò)展而努力，用他自己的話來說：

　　現(xiàn)在有一個(gè)可進(jìn)行原地重新分配的vector<T, malloc_allocator<T>>，當(dāng)Vec為一個(gè)不帶原地?cái)U(kuò)展的vector<int>時(shí)，耗時(shí)為0.00095674秒；當(dāng)Vec為一個(gè)帶有原地?cái)U(kuò)展的vector<int>時(shí)，耗時(shí)為0.000416943。由此可看出，內(nèi)存的原地重新分配，所帶來的性能提升，非常之明顯。

　　既然有了原地重新分配所帶來的好處，而堆中的每個(gè)層都能控制其自己的分配算法和數(shù)據(jù)結(jié)構(gòu)，請(qǐng)看下面的堆層接口：

template <class T>
struct Allocator : public T {
　void * malloc(size_t sz);
　void free(void* p);
　size_t eXPand(void* p, size_t min, size_t max);
};
　　擴(kuò)展在語(yǔ)義上的意思是，嘗試通過p擴(kuò)展指向在兩者之間最大尺寸的塊，并返回期望擴(kuò)展的任意大小內(nèi)存塊。幸運(yùn)的是，一個(gè)層不必關(guān)心用于擴(kuò)展的子程序，假如所有頂層的分配方法都繼續(xù)自以下的類，那么一切都將工作正常：

struct TopHeap {
　size_t expand(void*, size_t, size_t) {
　　return 0;
　}

　protected:
　　~TopHeap() {}
};
　　結(jié)論

　　可配置的內(nèi)存分配算符，是一種實(shí)用的、一體化的解決方案，可取代專門或通用的內(nèi)存分配操作符。此外，HeapLayers的分層架構(gòu)支持更簡(jiǎn)單的調(diào)試，并且具有非并行的可擴(kuò)展性。表1演示了一個(gè)在HeapLayers中，層實(shí)現(xiàn)的相關(guān)子集，其中有許多值得討論的地方，如多線程操作中的閉鎖堆、STL適配程序、各種不同的工具堆、還有怎樣結(jié)合多個(gè)層來創(chuàng)建一個(gè)通用的內(nèi)存分配算符，另外，千萬(wàn)記住不要忘了在析構(gòu)函數(shù)中釋放內(nèi)存，祝大家編程愉快！

　　表1：部分HeapLayers庫(kù)

頂層堆 mallocHeap 取代malloc的層mmapHeap 取代虛擬內(nèi)存治理的層sbrkHeap取代sbrk（連續(xù)內(nèi)存）構(gòu)建塊堆的層AdaptHeap使數(shù)據(jù)結(jié)構(gòu)可作為堆使用BoundedFreelistHeap 有長(zhǎng)度限制的釋放列表ChunkHeap 以給定大小的塊來治理內(nèi)存CoalesceHeap 執(zhí)行拼接與拆分FreelistHeap 一個(gè)釋放列表（用于捕捉釋放的對(duì)象）組合堆 HybridHeap對(duì)小對(duì)象使用一個(gè)堆，而對(duì)大對(duì)象使用另一個(gè)堆SegHeap 用于分配方法的一般分割StrictSegHeap用于分配方法的嚴(yán)格分割工具層ANSIWrapper提供與ANSI-malloc的兼容性DebugHeap檢查多種分配錯(cuò)誤LockedHeap為保證線程安全的閉鎖堆PerClassHeap使用一個(gè)堆作為每個(gè)類的分配算符PHOThreadHeap帶有自有分配算符私有堆ProfileHeap 收集并輸出碎片統(tǒng)計(jì)ThreadHeap 一個(gè)純私有堆分配算符ExceptionHeap 當(dāng)父類堆超出內(nèi)存時(shí)，拋出一個(gè)異常TraceHeap 輸出有關(guān)內(nèi)存分配的跟蹤信息UniqueHeap 引用一個(gè)堆對(duì)象的堆類型對(duì)象表示 CoalesceableHeap為拼接提供支持SizeHeap在頭部中記錄對(duì)象大小非凡用途的堆 ObstackHeap專門優(yōu)化用于類似堆棧行為或快速大小調(diào)整的堆ZoneHeap一個(gè)區(qū)域分配算符XallocHeap 優(yōu)化用于類似堆棧行為的堆通用堆KingsleyHeap快速但多碎片的堆LeaHeap 速度不快，但碎片很少的堆

上一篇：字母的幾種排法

下一篇：C語(yǔ)言中的指針和內(nèi)存泄漏