徐州网站设计师,深圳模板网站建设哪家好,金华手机建站模板,装修公司报价项目介绍 本项目实现的是一个高并发的内存池#xff0c;它的原型是Google的一个开源项目tcmalloc#xff0c;tcmalloc全称Thread-Caching Malloc#xff0c;即线程缓存的malloc#xff0c;实现了高效的多线程内存管理#xff0c;用于替换系统的内存分配相关函数malloc和fr…项目介绍 本项目实现的是一个高并发的内存池它的原型是Google的一个开源项目tcmalloctcmalloc全称Thread-Caching Malloc即线程缓存的malloc实现了高效的多线程内存管理用于替换系统的内存分配相关函数malloc和free。tcmalloc的知名度也是非常高的不少公司都在用它比如Go语言就直接用它做了自己的内存分配器。该项目就是把tcmalloc中最核心的框架简化后拿出来模拟实现出一个mini版的高并发内存池目的就是学习tcmalloc的精华。该项目主要涉及C/C、数据结构链表、哈希桶、操作系统内存管理、单例模式、多线程、互斥锁等方面的技术。
内存池介绍
池化技术 在说内存池之前我们得先了解一下“池化技术”。所谓“池化技术”就是程序先向系统申请过量的资源然后自己进行管理以备不时之需。 之所以要申请过量的资源是因为申请和释放资源都有较大的开销不如提前申请一些资源放入“池”中当需要资源时直接从“池”中获取不需要时就将该资源重新放回“池”中即可。这样使用时就会变得非常快捷可以大大提高程序的运行效率。 在计算机中有很多使用“池”这种技术的地方除了内存池之外还有连接池、线程池、对象池等。以服务器上的线程池为例它的主要思想就是先启动若干数量的线程让它们处于睡眠状态当接收到客户端的请求时唤醒池中某个睡眠的线程让它来处理客户端的请求当处理完这个请求后线程又进入睡眠状态。
内存池 内存池是指程序预先向操作系统申请一块足够大的内存此后当程序中需要申请内存的时候不是直接向操作系统申请而是直接从内存池中获取同理当释放内存的时候并不是真正将内存返回给操作系统而是将内存返回给内存池。当程序退出时或某个特定时间内存池才将之前申请的内存真正释放。
内存池主要解决的问题 内存池主要解决的就是效率的问题它能够避免让程序频繁的向系统申请和释放内存。这里我们可以举一个例子就好比我们要生活费今天早上你吃了一碗面花了五元然后你里面打电话告诉你的爸爸妈妈说今天早上花了五元吃面你给我转5元中午吃了一个黄焖鸡花了12元告诉爸爸妈妈说今天中午花了12元那么给我转12元我们会发现这里太低效了每次都需要向爸爸妈妈要不如这样告诉爸爸妈妈你这个月大概需要800元生活费让爸爸妈妈一次性给你这样你就不需要频繁的打电话告诉爸爸妈妈要生活费非常高效其次内存池作为系统的内存分配器还需要尝试解决内存碎片的问题。
内存碎片分为内部碎片和外部碎片 外部碎片是一些空闲的小块内存区域由于这些内存空间不连续以至于合计的内存足够但是不能满足一些内存分配申请需求。 内部碎片是由于一些对齐的需求导致分配出去的空间中一些内存无法被利用。 注意 内存池尝试解决的是外部碎片的问题同时也尽可能的减少内部碎片的产生。
malloc 我们之前一直说C/C我们要申请内存我们就需要在堆空间中申请但是实际上C/C中我们要动态申请内存一般情况下并不是直接去堆申请的而是通过malloc函数去申请的包括C中的new实际上也是调用了operator new它底层也是封装了malloc函数的因为它要符合C抛异常的机制。
我们申请内存块时是先调用mallocmalloc再去向操作系统申请内存。malloc实际就是一个内存池malloc相当于向操作系统“批发”了一块较大的内存空间然后“零售”给程序用当全部“售完”或程序有大量的内存需求时再根据实际需求向操作系统“进货”。
malloc的实现方式有很多种一般不同编译器平台用的都是不同的。比如Windows的VS系列中的malloc就是微软自行实现的而Linux下的gcc用的是glibc中的ptmalloc。
定长内存池的实现 malloc其实就是一个通用的内存池在什么场景下都可以使用但这也意味着malloc在什么场景下都不会有很高的性能因为malloc并不是针对某种场景专门设计的。 定长内存池就是针对固定大小内存块的申请和释放的内存池由于定长内存池只需要支持固定大小内存块的申请和释放因此我们可以将其性能做到极致并且在实现定长内存池时不需要考虑内存碎片等问题因为我们申请/释放的都是固定大小的内存块。 我们可以通过实现定长内存池来熟悉一下对简单内存池的控制其次这个定长内存池后面会作为高并发内存池的一个基础组件。既然我们这里是实现定长的内存池所以我们第一步就需要实现定长的功能如何实现呢
使用我们的非类型模板参数表示此时申请的对象的空间大小都是N。
// 非类型的模板参数
template size_t N
class ObjectPool
{};
还有另外一种方式根据传入的模板参数的大小来获得申请的空间比如传入的是int那就是4个字节传入的是double那就是8个字节。
// 模板参数
// 定长内存池
template class T
class ObjectPool
{};
我们现在实现的是第二种方式为了更贴切第二中方式的含义这也就是为什么我们给这个类起名为ObjectPool因为它是根据对象的大小来申请空间的我们再来看看定长内存池的需要一些什么样的成员呢首先我们肯定需要一大块的堆空间内存
// 模板参数
// 定长内存池
template class T
class ObjectPool
{
private:void* _memory; // 申请一大块堆上的内存空间的指针
};
此时我们看看我们设计的成员变量有没有什么问题我们申请的这一大块的堆空间内存首先我们肯定是要划分出一段空间来供调用者使用比如调用者说他需要10个字节的空间难道此时我们直接将memory的起始地址并且加上10将这个段空间给调用者嘛此时我们要记住void*它是不支持解引用和加加减减的操作的所以此时要想切割出10个字节的空间我们就需要将void*强制类型转换为char*才可以那为什么我们不直接将memory的类型设置为char*呢这样不就更方便一点嘛 // 模板参数
// 定长内存池
template class T
class ObjectPool
{
private:char* _memory; // 申请一大块堆上的内存空间的指针
};
同时我们应该还要想到未来有很多个人需要不同大小的内存空间于是就想我们的内存池中拿但是未来当他们部分人用完了要归还的时候我们不能直接把它释放归还给操作系统因为我们当时申请了多少就应该释放多少同时我们也不能归还到我们的内存池这样会出现碎片化的问题所以我们是不是还要对这些释用完的内存进行管理起来我们可以将这些释放回来的定长内存块链接成一个链表这里我们将管理释放回来的内存块的链表叫做自由链表为了能找到这个自由链表我们还需要一个指向自由链表的指针此时在这个链表中我们不进行解引用和加加减减的操作并且我们也不知道归还的内存的指针的类型我们此时指针的类型可以定义成void*。此时有一个小细节我们这个内存块的空间在32位平台下内存块空间至少大于4字节因为我们还要存储下一个内存块的指针这样我们才能管理起来我们规定内存块的前4个字节存储下一个内存块的地址。 // 模板参数
// 定长内存池
template class T
class ObjectPool
{
private:char* _memory; // 申请一大块堆上的内存空间的指针void* _freeList; // 自由链表
};
随后我们利用构造函数的初始化列表将成员进行初始化这里我们都设置位空指针即可。
// 模板参数
// 定长内存池
template class T
class ObjectPool
{
public:ObjectPool(): _memory(nullptr), _freeList(nullptr){}
private:char* _memory; // 申请一大块堆上的内存空间的指针void* _freeList; // 自由链表
};
随后我就要申请一大块内存空间如果此时申请空间失败我们抛出一个异常并让程序直接退出。
# include iostreamusing std::cin;
using std::cout;
using std::bad_alloc;// 模板参数
// 定长内存池
template class T
class ObjectPool
{
public:ObjectPool(): _memory(nullptr), _freeList(nullptr){}T* New(){if (_memory nullptr){// malloc的返回值是void*,这里需要强制类型转换_memory (char*)malloc(128 * 1024); // 128KBif (_memory nullptr){throw bad_alloc();}}}
private:char* _memory; // 申请一大块堆上的内存空间的指针void* _freeList; // 自由链表
};
现在我们就可以根据传入的模板参数T的类型给它分配一个T*的空间。 // 模板参数
// 定长内存池
template class T
class ObjectPool
{
public:ObjectPool(): _memory(nullptr), _freeList(nullptr){}T* New(){if (_memory nullptr){// malloc的返回值是void*,这里需要强制类型转换_memory (char*)malloc(128 * 1024); // 128KBif (_memory nullptr){throw bad_alloc();}}T* obj (T*)_memory;_memory sizeof(T);return obj;}
private:char* _memory; // 申请一大块堆上的内存空间的指针void* _freeList; // 自由链表
};
我们看看此时我们的代码有没有问题当我们申请的空间都被用完的时候此时我们应该再去申请空间但是此时的_memory的指针不为空指针此时还是有地址的不过此时不属于你你是不可以使用的所以我们的代码还是有问题的我们不应该使用_memory为空来判断申请空间它只适用于第一次申请空间的情况此时为了解决这个问题我们还可以定义一个成员变量表示剩余空间的大小然后根据这个来判断是否需要申请空间。
template class T
class ObjectPool
{
public:ObjectPool(): _memory(nullptr), _freeList(nullptr){}T* New(){if (_remainBytes 0){// malloc的返回值是void*,这里需要强制类型转换_remainBytes 128 * 1024;_memory (char*)malloc(_remainBytes); // 128KBif (_memory nullptr){throw bad_alloc();}}T* obj (T*)_memory;_memory sizeof(T);_remainBytes - sizeof(T);return obj;}
private:char* _memory; // 申请一大块堆上的内存空间的指针void* _freeList; // 自由链表size_t _remainBytes 0; //指向大块内存在切分过程中剩余字节数
};
同时我们这里如果最后剩余的空间不够一个T类型的大小那么我们上面的判断还是有问题的此时就可能出现越界的问题所以我们还要改一下判断。
// 模板参数
// 定长内存池
template class T
class ObjectPool
{
public:ObjectPool(): _memory(nullptr), _freeList(nullptr){}T* New(){// 当剩余的内存不够一个对象大小时,需要重现开一个大块空间if (_remainBytes sizeof(T)){// malloc的返回值是void*,这里需要强制类型转换_remainBytes 128 * 1024;_memory (char*)malloc(_remainBytes); // 128KBif (_memory nullptr){throw bad_alloc();}}T* obj (T*)_memory;_memory sizeof(T);_remainBytes - sizeof(T);return obj;}
private:char* _memory; // 申请一大块堆上的内存空间的指针void* _freeList; // 自由链表size_t _remainBytes 0; //指向大块内存在切分过程中剩余字节数
};
现在我们再来处理一下对象归还回来的空间改怎么处理呢当现在有一个内存块归还了我们要让freeList指向这个内存块这个内存的前4个字节指向NULL怎么做呢我们肯定需要找到这个4字节可以直接对象归还回来的空间强制类型转换为int*此时解引用就可以访问到这个这个空间然后将其设置为空。
void Delete(T* obj)
{if (_freeList nullptr){_freeList obj;*((int*)obj) nullptr;}
}
但是还有点问题指针在不同的平台下指针的大小是不同的32位平台下指针的大小是4个字节64位平台下的指针的大小是8个字节所以我们的代码不具有移植性但是我们怎么知道我们的平台是32位的还是64位的呢当然我们可以通过sizeof来判断但是不够优雅我们写一个优雅的方法。
void Delete(T* obj)
{if (_freeList nullptr){_freeList obj;// *((int*)obj) nullptr;*((void**)obj) nullptr;}
}
此时我们是将obj强制类型转化位void**void**解引用看的就是一个void*的大小此时void*是一个指针32位平台下指针的大小是4个字节64位平台下的指针的大小是8个字节很好的就做到了平台的区分随后在来归还一个内存块此时肯定要进自由链表来管理的此时是头插还是尾插呢我们知道尾插需要找尾时间复杂度尾O(N)而头插的效率为O(1)所以我们选择头插法。 void Delete(T* obj)
{if (_freeList nullptr){_freeList obj;// *((int*)obj) nullptr;*((void**)obj) _freeList;}else{// 头插法*((void**)obj) _freeList;_freeList obj;}
}
此时我们会发现我们的头插方法也适用于freeList为空的情况所以我们的代码就可以简省一点。
void Delete(T* obj)
{// 头插法*((void**)obj) _freeList;_freeList obj;
}
同时我们这里需要注意一个点我们并不是每次都会向我们的大块内存拿空间如果我们的freeList里面有了很多归还的空间我们可以来使用一下他们此时就需要拿ferrList的第一个空间块需要进行头删。 // 模板参数
// 定长内存池
template class T
class ObjectPool
{
public:ObjectPool(): _memory(nullptr), _freeList(nullptr){}T* New(){T* obj nullptr;// 优先把还回来的内存块对象再次重复利用if (_freeList ! nullptr){void* next *((void**)_freeList);obj (T*)_freeList;_freeList next;return obj;}else{// 当剩余的内存不够一个对象大小时,需要重现开一个大块空间if (_remainBytes sizeof(T)){// malloc的返回值是void*,这里需要强制类型转换_remainBytes 128 * 1024;_memory (char*)malloc(_remainBytes); // 128KBif (_memory nullptr){throw bad_alloc();}}obj (T*)_memory;_memory sizeof(T);_remainBytes - sizeof(T);return obj;}}void Delete(T* obj){// 头插法*((void**)obj) _freeList;_freeList obj;}
private:char* _memory; // 申请一大块堆上的内存空间的指针void* _freeList; // 自由链表size_t _remainBytes 0; //指向大块内存在切分过程中剩余字节数
};
同时我们上面的代码还存在一个问题如果此时调用者需要的空间只需要一个字节那么此时它要归还的时候存储自由链表中但是节点中至少要大于4个字节不然存储不了下一个内存块的指针啊所以我们这里还需要处理一下对于不满足存储一个指针的空间我们将空间的大小设置为指针的大小。
// 模板参数
// 定长内存池
template class T
class ObjectPool
{
public:ObjectPool(): _memory(nullptr), _freeList(nullptr){}T* New(){T* obj nullptr;// 优先把还回来的内存块对象再次重复利用if (_freeList ! nullptr){void* next *((void**)_freeList);obj (T*)_freeList;_freeList next;}else{// 当剩余的内存不够一个对象大小时,需要重现开一个大块空间if (_remainBytes sizeof(T)){// malloc的返回值是void*,这里需要强制类型转换_remainBytes 128 * 1024;_memory (char*)malloc(_remainBytes); // 128KBif (_memory nullptr){throw bad_alloc();}}obj (T*)_memory;size_t objSize sizeof(T) sizeof(void*) ? sizeof(void*) : sizeof(T);_memory objSize;_remainBytes - objSize;}return obj;}void Delete(T* obj){// 头插法*((void**)obj) _freeList;_freeList obj;}
private:char* _memory; // 申请一大块堆上的内存空间的指针void* _freeList; // 自由链表size_t _remainBytes 0; //指向大块内存在切分过程中剩余字节数
};
同时我们这里申请了空间但是我们没有初始化我们可以将传入的对象通过构造函数进行初始化并且再归还的时候调用析构函数释放对象。
// 模板参数
// 定长内存池
template class T
class ObjectPool
{
public:ObjectPool(): _memory(nullptr), _freeList(nullptr){}T* New(){T* obj nullptr;// 优先把还回来的内存块对象再次重复利用if (_freeList ! nullptr){void* next *((void**)_freeList);obj (T*)_freeList;_freeList next;}else{// 当剩余的内存不够一个对象大小时,需要重现开一个大块空间if (_remainBytes sizeof(T)){// malloc的返回值是void*,这里需要强制类型转换_remainBytes 128 * 1024;_memory (char*)malloc(_remainBytes); // 128KBif (_memory nullptr){throw bad_alloc();}}obj (T*)_memory;size_t objSize sizeof(T) sizeof(void*) ? sizeof(void*) : sizeof(T);_memory objSize;_remainBytes - objSize;}// 定位new显示调用构造函数进行初始化new(obj)T;return obj;}void Delete(T* obj){// 显示调用析构函数清理对象obj-~T();// 头插法*((void**)obj) _freeList;_freeList obj;}
private:char* _memory; // 申请一大块堆上的内存空间的指针void* _freeList; // 自由链表size_t _remainBytes 0; //指向大块内存在切分过程中剩余字节数
};
此时我们的定长内存池就已经实现完成啦我们来测试一下。
struct TreeNode
{int _val;TreeNode* _left;TreeNode* _right;TreeNode():_val(0), _left(nullptr), _right(nullptr){}
};void TestObjectPool()
{// 申请释放的轮次const size_t Rounds 3;// 每轮申请释放多少次const size_t N 1000000;std::vectorTreeNode* v1;v1.reserve(N);//malloc和freesize_t begin1 clock();for (size_t j 0; j Rounds; j){for (int i 0; i N; i){v1.push_back(new TreeNode);}for (int i 0; i N; i){delete v1[i];}v1.clear();}size_t end1 clock();//定长内存池ObjectPoolTreeNode TNPool;std::vectorTreeNode* v2;v2.reserve(N);size_t begin2 clock();for (size_t j 0; j Rounds; j){for (int i 0; i N; i){v2.push_back(TNPool.New());}for (int i 0; i N; i){TNPool.Delete(v2[i]);}v2.clear();}size_t end2 clock();cout new cost time: end1 - begin1 endl;cout object pool cost time: end2 - begin2 endl;
} 我们上面也提到我们的malloc本章也是一个内存池如果我们不想要这个内存池我们也可以自己去堆上申请空间此时在Windows下可以调用VirtualAlloc函数在Linux下可以调用brk或mmap函数。
#ifdef _WIN32#include Windows.h
#else//...
#endif//直接去堆上申请按页申请空间
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32void* ptr VirtualAlloc(0, kpage13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else// linux下brk mmap等
#endifif (ptr nullptr)throw std::bad_alloc();return ptr;
}可以看到在这个过程中定长内存池消耗的时间比malloc/free消耗的时间要短。这就是因为malloc是一个通用的内存池而定长内存池是专门针对申请定长对象而设计的因此在这种特殊场景下定长内存池的效率更高正所谓“尺有所短寸有所长”最后我们这里的定长内存也不需要手动释放因为我们也无法释放因为归还的内存已经乱了那此时不就会出现内存泄漏的问题嘛不会只要我们的进程是正常退出的最后会自动帮我们释放内存的所以不用担心。
