《提高C++性能的编程技术》阅读随笔 —— 第六章 单线程内存池

频繁的分配和回收内存会严重降低程序的性能。原因在于默认的内存管理器是通用的、应用程序可能会以某种特定的方式使用内存，并且为不需要的功能付出性能上的代价。通过开发专用的内存管理器可以解决这个问题。
两个方面考虑内存管理器的设计：大小和并发
固定大小、可变大小
单线程：内存管理器局限在一个线程内，内存被一个线程使用
多线程：内存管理器被多个线程并发的使用，需包含互斥执行的代码段。无论什么时候，只有一个线程在执行一个代码段

  1. 全局内存管理器（由new()和delete()执行）是通用的。因此代价较高
  2. 专用内存管理器，如单线程内存管理器，其可以省去new和delete的并发问题
    (指的是对于一个类重载实现他的new和delete方面。分配的大小根据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;  // 循环执行100万次，1500ms

版本1：专用的Rational内存管理器
避免频繁使用默认内存管理器，Rational需要维护一个预先分配的Rational对象的静态链接链表，列出空闲的可用对象，当需要Rational对象时，从空闲列表取出一个即可，使用后再把它放回空闲列表以便今后分配。

class NextOnFreeList{
public:
  NextOnFreeList *next;
};

空闲列表被声明为一个有NextOnFreeList元素组成的列表，这样空闲列表的每个元素都声明为NextOnFreeList结构，但他们也是Rational对象。
为了遍历对象，每个Rational对象的前几个字节用于指向空闲列表的下一个对象（next）。可以通过将Rational对象转换成指向NextOnFreeList类型的指针来实现。这样空闲列表双重身份：Rational对象的序列andNextOnFreeList元素的序列

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

空闲列表声明为Rational静态成员，Rational的New和delete操作符可以管理该静态列表，重载全局的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对象，列表为空就扩展列表。先去掉空闲列表的头部，调整完指针后再返回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变为delete调的空间，而其next则指向之前的freelist，因此可以继续形成一条链

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

Rational和NextOnFreeList之间的类型转换有危险。必须确保空闲列表的元素足够大以支持任意一种类型。因此，当我们用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];
  }

执行时间从1500描述将至43ms。

版本2：固定大小对象的内存池
版本1只可以管理Rational对象，想管理多个对象的话，用模板。因为Rational可以看出，内存管理逻辑是独立于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函数负责扩充，free函数负责把T元素放回空闲列表，以此来释放它。
Rational就不需要再维护自己的空闲列表，因此Rational变为

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的类型转换在编译时可能报错，可以采用强制类型转换

版本3：单线程可变大小的内存管理器
版本2分配的是固定大小的内存，但有些程序需要分配可变大小的内存。
下面是Web服务器中常用的方式：
MemoryChunk类取代了之前版本中使用的NextOnFreeList类，他把不同大小的内存块连接起来形成块序列。
完整代码如下（#####可运行）

#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指针从用于已分配对象的实际内存中分离出来。MemoryChunk使用显式的next和mem指针因此不需要转换。
//MemoryChunk首先确定内存块大小（mem指向），然后next链接下一个MemoryChunk内存块
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){}//无需担心空闲内存段的释放，对象被删除，内存块也就被释放了

//MemoryChunk只是辅助类,ByteMemoryPool类用它首先可变大小的内存管理。
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);
};
//内存块列表可能包含多个块，但只有第一块可用于分配的内存，其他块表示已分配的内存。即列表的首个元素是唯一能够分配可用内存的块。
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类的实现，用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();
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 216,240评论 6赞 498
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,328评论 3赞 392
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 162,182评论 0赞 353
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,121评论 1赞 292
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,135评论 6赞 388
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,093评论 1赞 295
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,013评论 3赞 417
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,854评论 0赞 273
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,295评论 1赞 310
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,513评论 2赞 332
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,678评论 1赞 348
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,398评论 5赞 343
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,989评论 3赞 325
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,636评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,801评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,657评论 2赞 368
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,558评论 2赞 352