應用程序分配內存的方法，對程序的執行性能有著深刻的影響。目前，通用的內存分配方法本質上已非常高效，但仍有改進的空間。
內存分配，不可一層不變
今天，對絕大多數程序來說，通用的內存分配方法--此處指代分配算符（Allocator：即malloc或new），已達到了理想的速度及滿足了低碎片率的要求，然而，在內存分配領域，一丁點的信息都值得探討很久，某些特定程序關於分配模式的信息，將有助於實現專門的分配算符，可顯著地提高大多數高性能要求程序的性能底線。有時，當通用內存分配算符平均耗費幾百個時鐘周期時，一個良好的自定義內存分配算符可能只需要不到半打的周期。
這就是為什麼大多數高性能、高要求的應用程序（如GCC、Apache、Microsoft SQL Server），都有著它們自己的內存分配算符。也許，把這些專門的內存分配算符歸納起來，放進一個庫中，是個不錯的想法，但是，你的程序可能有不同的分配模式，其需要另外的內存分配算符，那怎麼辦呢？
等等，還有呢，如果我們設計了一種特殊用途的內存分配算符，就可以不斷發展下去，由此可從中篩選出一些，來組成一個通用目的的內存分配算符，如果此通用分配算符優於現有的通用分配算符，那麼此項設計就是有效及實用的。
下面的示例使用了Emery小組的庫--HeapLayers（http://heaplayers.org/），為了定義可配置的分配算符，其中使用了mixins（在C++社區中，也被稱為Coplien遞歸模式）：通過參數化的基來定義類，每一層中只定義兩個成員函數，malloc和free：
template <class T>
struct Allocator : public T {
void * malloc(size_t sz);
void free(void* p);
//系統相關的值
enum { Alignment = sizeof(double) };
//可選接口e
size_t getSize(const void* p);
};
在每一層的實現中，都有可能向它的基類請求內存，一般來說，一個不依賴於外界的內存分配算符，都會處在層次的頂層--直接向前請求系統的new和delete操作符、malloc和free函數。在HeapLayers的術語中，沒有頂層堆，以下是示例：
struct MallocHeap {
void * malloc(size_t sz) {
return std::malloc(sz);
}
void free(void* p) {
return std::free(p);
}
};
為獲取內存，頂層堆也能通過系統調用來實現，如Unix的sbrk或mmap。getSize函數的情況就比較特殊，不是每個人都需要它，定義它只是一個可選項。但如果定義了它，你所需做的只是插入一個存儲內存塊大小的層，並提供getSize函數，見例1：
例1：
template <class SuperHeap>
class SizeHeap {
union freeObject {
size_t sz;
double _dummy; //對齊所需
};
public:
void * malloc(const size_t sz) {
//添加必要的空間
freeObject * ptr = (freeObject *)SuperHeap::malloc(sz + sizeof(freeObject));
//存儲請求的大小
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是怎樣實現一個實用的層，並掛鉤於它基類的malloc與free函數的最好示例，它在完成一些額外的工作之後，把修改好的結果返回給使用者。SizeHeap為存儲內存塊大小，分配了額外的內存，再加上適當的小心調整（指union），盡可能地避免了內存數據對齊問題。不難想像，我們可構建一個debug堆，其通過特定模式在內存塊之前或之後填充了一些字節，通過檢查是否模式已被保留，來確認內存的溢出。事實上，這正是HeapLayers的DebugHeap層所做的，非常的簡潔。
讓我們再來看看，以上還不是最理想的狀態，某些系統已經提供了計算已分配內存塊大小的原語（此處指操作符，即前述的分配算符），在這些系統上，SizeHeap實際上只會浪費空間。在這種情況下（如Microsoft Visual C++），你將不需要SizeHeap與MallocHeap的銜接，因為MallcoHeap將會實現getSize：
struct MallocHeap {
... 與上相同 ...
size_t getSize(void* p) {
return _msize(p);
}
};
但似乎還有一些不足之處。想一想，我們是在統計時鐘周期，如果一個系統的malloc聲明了內存的塊大小將存儲在實際塊之前的一個字中，那將會怎樣呢？在這種情況下，SizeHeap還是會浪費空間，因為它仍會在緊接著系統已植入的塊後存儲一個字。此處所需的，只是一個用SizeHeap的方法實現了getSize的層，但未掛鉤malloc與free。這就是為什麼HeapLayers把前面的SizeHeap分成了兩個，見例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; //對齊所需
};
};
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));
//存儲請求的大小
ptr->sz = sz;
return (void *) (ptr + 1);
}
void free(void * ptr) {
SuperHeap::free((freeObject *)ptr - 1);
}
};
現在，SizeHeap就會正確地添加UseSizeHeap層，並利用它的getSize實現了，而UseSizeHeap也能通過其他配置來使用--這是一個非常優雅的設計。
一個實用的示例：FreelistHeap
到目前為止，我們還處於一個准備的階段，只有架構，還不知怎樣利用這些層來編寫一個高效專用的內存分配算符，也許一個比較合適的開發步驟可如下所示：
·收集有關程序為每種內存塊大小進行分配次數的信息。
·為最經常請求的大小（在此稱為S），維持一個私有、逐一鏈接的列表。
·對S的內存分配盡可能地從列表中返回內存，或者從默認分配算符中返回（在分層架構中，從上級層中）。
·對S大小內存塊的釋放，把內存塊放回至列表中。
·一個精心設計的分配策略，應可對范圍大小從S1至S2，使用相同的釋放列表，並消耗同等的內存。而所需鏈接列表的操作開銷為O(1)，實際上只有幾條指令。另外，指向下一條目的指針，能存儲在實際的塊中（塊中存儲了無用的數據--總為一個釋放了的塊），因此，對每個塊就不需要額外的內存了。正因為大多數應用程序分配內存的大小都是不同的，所以，對任何分配算符的實現來說，釋放列表就必不可少了。
下面讓我們來實現一個層，由其對已知靜態范圍大小從S1至S2，實現了一個釋放列表，見例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:
// 嵌入在釋放的對象中的鏈接列表指針
class freeObject {
public:
freeObject * next;
};
//釋放的對象鏈接列表頭
freeObject * myFreeList;
};
現在，你像如下所示可定義一個自定義的堆：
typedef FLHeap<
SizeHeap<MallocHeap>,
24,
32>
SmartoHeapo;
SmartoHeapo在分配的大小在24至32之間時，速度相當快，對其它大小來說，也基本上一樣。
原地重新分配（Inplace Resizing）
許多的C++程序員都夢寐以求有一種標准的原語（也即操作符），用於原地重新分配內存。眾所周知，C語言中有realloc，其盡可能的原地重新分配內存，並在涉及到復制數據時使用memcpy，但memcpy並不適合於C++對象，所以，realloc也不適用於C++的對象。因此，任何一種renew原語都不能用標准C分配符來實現，這就是為什麼C++中沒有renew的原因。
以下演示了一種改進後的方法，可應用於C++代碼中的原地重新分配，請看：
const int n = 10000;
Vec v;
for (int i = 0; i < n; ++i)
v.push_back(0);
Metrowerks的Howard Hinnant一直在為實現應用於CodeWarrior標准庫的原地擴展而努力，用他自己的話來說：
現在有一個可進行原地重新分配的vector<T, malloc_allocator<T>>，當Vec為一個不帶原地擴展的vector<int>時，耗時為0.00095674秒；當Vec為一個帶有原地擴展的vector<int>時，耗時為0.000416943。由此可看出，內存的原地重新分配，所帶來的性能提升，非常之明顯。
既然有了原地重新分配所帶來的好處，而堆中的每個層都能控制其自己的分配算法和數據結構，請看下面的堆層接口：
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);
};
擴展在語義上的意思是，嘗試通過p擴展指向在兩者之間最大尺寸的塊，並返回期望擴展的任意大小內存塊。幸運的是，一個層不必關心用於擴展的子程序，如果所有頂層的分配方法都繼承自以下的類，那麼一切都將工作正常：
struct TopHeap {
size_t expand(void*, size_t, size_t) {
return 0;
}
protected:
~TopHeap() {}
};
結論
可配置的內存分配算符，是一種實用的、一體化的解決方案，可取代專門或通用的內存分配操作符。此外，HeapLayers的分層架構支持更簡單的調試，並且具有非並行的可擴展性。表1演示了一個在HeapLayers中，層實現的相關子集，其中有許多值得討論的地方，如多線程操作中的閉鎖堆、STL適配程序、各種不同的工具堆、還有怎樣結合多個層來創建一個通用的內存分配算符，另外，千萬記住不要忘了在析構函數中釋放內存，祝大家編程愉快！
表1：部分HeapLayers庫
頂層堆 mallocHeap 取代malloc的層 mmapHeap 取代虛擬內存管理的層 sbrkHeap 取代sbrk（連續內存）構建塊堆的層 AdaptHeap 使數據結構可作為堆使用 BoundedFreelistHeap 有長度限制的釋放列表 ChunkHeap 以給定大小的塊來管理內存 CoalesceHeap 執行拼接與拆分 FreelistHeap 一個釋放列表（用於捕捉釋放的對象） 組合堆 HybridHeap 對小對象使用一個堆，而對大對象使用另一個堆 SegHeap 用於分配方法的一般分割 StrictSegHeap 用於分配方法的嚴格分割 工具層 ANSIWrapper 提供與ANSI-malloc的兼容性 DebugHeap 檢查多種分配錯誤 LockedHeap 為保證線程安全的閉鎖堆 PerClassHeap 使用一個堆作為每個類的分配算符 PHOThreadHeap 帶有自有分配算符私有堆 ProfileHeap 收集並輸出碎片統計 ThreadHeap 一個純私有堆分配算符 ExceptionHeap 當父類堆超出內存時，拋出一個異常 TraceHeap 輸出有關內存分配的跟蹤信息 UniqueHeap 引用一個堆對象的堆類型 對象表示 CoalesceableHeap 為拼接提供支持 SizeHeap 在頭部中記錄對象大小 特殊用途的堆 ObstackHeap 專門優化用於類似堆棧行為或快速大小調整的堆 ZoneHeap 一個區域分配算符 XallocHeap 優化用於類似堆棧行為的堆 通用堆 KingsleyHeap 快速但多碎片的堆 LeaHeap 速度不快，但碎片很少的堆
