《提高C++性能的編程技術(shù)》閱讀隨筆 —— 第六章 單線程內(nèi)存池

頻繁的分配和回收內(nèi)存會嚴重降低程序的性能。原因在于默認的內(nèi)存管理器是通用的、應用程序可能會以某種特定的方式使用內(nèi)存，并且為不需要的功能付出性能上的代價。通過開發(fā)專用的內(nèi)存管理器可以解決這個問題。
兩個方面考慮內(nèi)存管理器的設計：大小和并發(fā)
固定大小、可變大小
單線程：內(nèi)存管理器局限在一個線程內(nèi)，內(nèi)存被一個線程使用
多線程：內(nèi)存管理器被多個線程并發(fā)的使用，需包含互斥執(zhí)行的代碼段。無論什么時候，只有一個線程在執(zhí)行一個代碼段

  1. 全局內(nèi)存管理器（由new()和delete()執(zhí)行）是通用的。因此代價較高
  2. 專用內(nèi)存管理器，如單線程內(nèi)存管理器，其可以省去new和delete的并發(fā)問題
    (指的是對于一個類重載實現(xiàn)他的new和delete方面。分配的大小根據(jù)sizeof，然后用new char[]來分配，delete[] 來刪除)

示例：

  1. 全局的new和delete
class Rational{
public:
  Rational (int a = 0, int b = 1) : n(a), d(b) {}
private:
  int n; //分子
  int d; //分母
};

Rational *array = new Rational(i);
delete array;  // 循環(huán)執(zhí)行100萬次，1500ms

版本1：專用的Rational內(nèi)存管理器
避免頻繁使用默認內(nèi)存管理器，Rational需要維護一個預先分配的Rational對象的靜態(tài)鏈接鏈表，列出空閑的可用對象，當需要Rational對象時，從空閑列表取出一個即可，使用后再把它放回空閑列表以便今后分配。

class NextOnFreeList{
public:
  NextOnFreeList *next;
};

空閑列表被聲明為一個有NextOnFreeList元素組成的列表，這樣空閑列表的每個元素都聲明為NextOnFreeList結(jié)構(gòu)，但他們也是Rational對象。
為了遍歷對象，每個Rational對象的前幾個字節(jié)用于指向空閑列表的下一個對象（next）?？梢酝ㄟ^將Rational對象轉(zhuǎn)換成指向NextOnFreeList類型的指針來實現(xiàn)。這樣空閑列表雙重身份：Rational對象的序列andNextOnFreeList元素的序列

class Rational{
  ...
  static NextOnFreeList *freelist;
};

空閑列表聲明為Rational靜態(tài)成員，Rational的New和delete操作符可以管理該靜態(tài)列表，重載全局的new和delete。

class Rational{
public:
  inline void *operator new (size_t size);
  inline void operator delete (void *doomed, size_t size);
  static void newMemPool() { expandTheFreeList(); }
  static void deleteMemPool();
private:
  static NextOnFreeList *freelist;
  static void expandTheFreeList();
  enum { EXPANSION_SIZE = 32};
  int n;
  int d;
};

new()是在空閑列表中分配一個Rational對象，列表為空就擴展列表。先去掉空閑列表的頭部，調(diào)整完指針后再返回head。

inline void* Rational::operator new(szie_t size) {
  if(0 == freelist) {
    expandTheFreeList();
  }
  NextOnFreeList *head = freelist;
  freelist = head->next;
  return head; 
}

delete()把Rational對象直接添加到空閑列表的頭部，以返回一個Rational對象。這樣每次delete都會使得freelist變?yōu)閐elete調(diào)的空間，而其next則指向之前的freelist，因此可以繼續(xù)形成一條鏈

inline void Rational::operator delete(void *doomed, size_t size) {
  NextOnFreeList *head = static_cast<NextOnFreeList *> doomed;
  head->next = freelist;
  freelist = head;
}

Rational和NextOnFreeList之間的類型轉(zhuǎn)換有危險。必須確?？臻e列表的元素足夠大以支持任意一種類型。因此，當我們用Rational對象填充空閑列表時，需要比較兩個類型之間的大小，從而分配較大的一個。

void Rational::expandTheFreeList() {
  size_t size = (sizeof(Rational) > sizeof(NextOnFreeList *)) ? 
                sizeof(Rational) : sizeof(NextOnFreeList *);
  NextOnFreeList *runner = static_cast<NextOnFreeList *> new char[size];
  freelist = runner;
  for(int i = 0; i < EXPANSION_SIZE; i++) {
    runner->next = static_cast<NextOnFreeList *> new char[size];
    runner = runner->next;
  }
  runner->next = 0;
}
void Rational::deleteMemPool() {
  NextOnFreeList *nextPtr;
  for(nextPtr = freelist; nextPtr != NULL; nextPtr = freelist) {
    freelist = freelist->next;
    delete []nextPtr;
  }
}

重復性能測試

for(500){
  for(1000){
    array[1-1000] = new Rational(i);
  }
  for(1000){
    delete array[1-1000];
  }

執(zhí)行時間從1500描述將至43ms。

版本2：固定大小對象的內(nèi)存池
版本1只可以管理Rational對象，想管理多個對象的話，用模板。因為Rational可以看出，內(nèi)存管理邏輯是獨立于Rational之外的。

template <class T>
class MemoryPool {
public:
  MemoryPool (size_t size = EXPANSION_SIZE) ;
  ~MemoryPool ();
  inline void* alloc (size_t size);
  inline void free (void *someElement);
private:
  MemoryPool<T> *next;
  void expandTheFreeList (int howMany = EXPANSION_SIZE);
};

template <class T>
MemoryPool<T>:: MemoryPool (size_t size = EXPANSION_SIZE) {
  expandTheFreeList(size);
}

template <class T>
MemoryPool<T>::  ~MemoryPool () {
  MemoryPool<T> *nextPtr = next;
  for(nextPtr =next; nextPtr != NULL; nextPtr = next) {
   next = next->next;
    delete []nextPtr;
  }
}

template <class T>
 inline void* MemoryPool<T>:: alloc (size_t size) {
  if(!next) expandTheFreeList();
  MemoryPool<T> *head = next;
  next = head->next;
  return head;
}

template <class T>
inline void MemoryPool<T>:: free (void *doomed) {
  MemoryPool<T> *head = static_cast<MemryPool<T> *> doomed;
  head->next = next;
  next = head;
}

template <class T>
void MemoryPool<T>:: expandTheFreeList (int howMany = EXPANSION_SIZE) {
  size_t size = (sizeof(T) > sizeof(MemoryPool<T> *)) ? 
                sizeof(T) > sizeof(MemoryPool<T> *);
  MemoryPool<T> *runner = static_cast< MemoryPool<T> *> new char[size];
 next = runner;
  for(int i = 0; i < howmany; i++) {
    runner->next = static_cast< MemoryPool<T> *> new char[size];
    runner = runner->next;
  }
  runner->next = 0;
}

上述代碼解析：與版本1類似，alloc函數(shù)負責擴充，free函數(shù)負責把T元素放回空閑列表，以此來釋放它。
Rational就不需要再維護自己的空閑列表，因此Rational變?yōu)?/p> 

class Rational{
public:
  Rational (int a = 0, int b = 1) : n(a), d(b) {}
  void* operator new(size_t size) { return memPool->alloc(szie); } 
  void operator delete (void *doomed, size_t size) { memPool->free(doomed); }
  static void newMemPool() { memPool = new MemoryPool<Rational>(); }
  static void deleteMemPool() { delete memPool; }
private:
  static MemryPool<Rational> *memPool;
  int n;
  int d;
};

MemoryPool<Rational> *Rational::memPool = 0;
int main(){
  Rational *array[1000];
  Rational::newMemPool();
  for(01-500)
    for(1-1000)
      array[i] = new Rational(i);
    for(1-1000)
      delete array[i];

  Rational::deleteMemPool();
}

這里的耗時大約是63ms
注意：之前的static_cast的類型轉(zhuǎn)換在編譯時可能報錯，可以采用強制類型轉(zhuǎn)換

版本3：單線程可變大小的內(nèi)存管理器
版本2分配的是固定大小的內(nèi)存，但有些程序需要分配可變大小的內(nèi)存。
下面是Web服務器中常用的方式：
MemoryChunk類取代了之前版本中使用的NextOnFreeList類，他把不同大小的內(nèi)存塊連接起來形成塊序列。
完整代碼如下（#####可運行）

#include<iostream>
using namespace std;
#include <string>

class MemoryChunk{
public:
    MemoryChunk(MemoryChunk *nextChunk, size_t chunkSize);
    ~MemoryChunk();
    inline void *alloc(size_t size);
    inline void free(void* someElement);
    MemoryChunk *nextMemChunk(){ return next; }
    size_t spaceAvailable(){ return chunkSize - bytesAlreadyAllocated; }
    enum {DEFAULT_CHUNK_SIZE = 4096};
private:
    MemoryChunk *next;
    void *mem;
    size_t chunkSize;
    size_t bytesAlreadyAllocated;
};
// MemoryChunk是NextOnFreeList的一個更為簡潔的版本。將next指針從用于已分配對象的實際內(nèi)存中分離出來。MemoryChunk使用顯式的next和mem指針因此不需要轉(zhuǎn)換。
//MemoryChunk首先確定內(nèi)存塊大小（mem指向），然后next鏈接下一個MemoryChunk內(nèi)存塊
MemoryChunk::MemoryChunk(MemoryChunk *nextChunk, size_t reqSize){
    chunkSize = (reqSize > DEFAULT_CHUNK_SIZE) ? reqSize : DEFAULT_CHUNK_SIZE;
    next = nextChunk;
    bytesAlreadyAllocated = 0;
    mem = new char[chunkSize];
}
MemoryChunk::~MemoryChunk() {
    delete[]mem;
}

void* MemoryChunk::alloc(size_t requestSize){
    void *addr = (void*)((size_t)mem + bytesAlreadyAllocated);
    bytesAlreadyAllocated += requestSize;
    return addr;
}
inline void MemoryChunk::free(void *doomed){}//無需擔心空閑內(nèi)存段的釋放，對象被刪除，內(nèi)存塊也就被釋放了

//MemoryChunk只是輔助類,ByteMemoryPool類用它首先可變大小的內(nèi)存管理。
class ByteMemoryPool{
public:
    ByteMemoryPool(size_t initSize = MemoryChunk::DEFAULT_CHUNK_SIZE);
    ~ByteMemoryPool();
    inline void* alloc(size_t size);
    inline void free(void* someElement);
private:
    MemoryChunk *listOfMemChunks;
    void expandStorage(size_t reqSize);
};
//內(nèi)存塊列表可能包含多個塊，但只有第一塊可用于分配的內(nèi)存，其他塊表示已分配的內(nèi)存。即列表的首個元素是唯一能夠分配可用內(nèi)存的塊。
ByteMemoryPool::ByteMemoryPool(size_t initSize){
    expandStorage(initSize);
}
ByteMemoryPool::~ByteMemoryPool(){
    MemoryChunk *memChunk = listOfMemChunks;
    while (memChunk){
        listOfMemChunks = memChunk->nextMemChunk();
        delete memChunk;
        memChunk = listOfMemChunks;
    }
}

//alloc如果確保有足夠的可用空間，則會把分配任務托付給列表頭的MemoryChunk:
void* ByteMemoryPool::alloc(size_t requestSize){
    size_t space = listOfMemChunks->spaceAvailable();
    if (space < requestSize){
        expandStorage(requestSize); //表示如果當前塊的大小不夠的話就需要另外擴充新的request大小的MemoryChunk,并把它放在列表頭部返回
    }
    return listOfMemChunks->alloc(requestSize);
}
inline void ByteMemoryPool::free(void *doomed){ listOfMemChunks->free(doomed); }

void ByteMemoryPool::expandStorage(size_t reqSize){
    listOfMemChunks = new MemoryChunk(listOfMemChunks, reqSize);
}
//這里需要修改Rational類的實現(xiàn)，用ByteMemoryPool代替MemoryPool<Rational>對象。
class Rational{
public:
    Rational(int a = 0, int b = 1) : n(a), d(b){}
    void *operator new(size_t size){ return memPool->alloc(size); }
    void operator delete(void *doomed){ memPool->free(doomed); }
    static void newMemPool(){ 
        memPool = new ByteMemoryPool(); 
    }
    static void deleteMemPool(){ delete memPool; }
    
private:
    static ByteMemoryPool *memPool;
    int n, d;
    
};

ByteMemoryPool* Rational::memPool = nullptr;
int main(){
    Rational *array[1000];
    
    Rational::newMemPool();
    for (int j = 0; j < 500; j++){
        for (int i = 0; i < 1000; i++){
            array[i] = new Rational(i);
        }
        for (int i = 0; i < 1000; i++){
            delete array[i];
        }
    }
    Rational::deleteMemPool();
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

友情鏈接更多精彩內(nèi)容