【高性能内存池】基本框架 + 固定长度内存池实现 1

1. 基本框架

高并发内存池主要由三个部分构成：
1.thread cache:用于小于256KB的内存的分配。线程缓存是每个线程独有的，线程从这⾥申请内存不需要加锁，每个线程独享⼀个cache，这也就是这个并发线程池⾼效的地⽅。

2.cetral cache:中心缓存是所有线程所共享，thread cache是按需从central cache中获取的对象。central cache合适的时机回收thread cache中的对象，避免⼀个线程占⽤了太多的内存，⽽其他线程的内存吃紧，达到内存分配在多个线程中更均衡的按需调度的⽬的。

central cache是存在竞争的，所以从这⾥取内存对象是需要加锁，⾸先这里用的是桶锁，其次只有thread cache的没有内存对象时才会找central cache，所以这⾥竞争不会很激烈。

3.page cache : ⻚缓存是在central cache缓存上⾯的⼀层缓存，存储的内存是以⻚为单位存储及分配的，central cache没有内存对象时，从page cache分配出⼀定数量的page，并切割成定长大小的小块内存，分配给central cache。

当⼀个span的⼏个跨度⻚的对象都回收以后，page cache会回收central cache满⾜条件的span对象，并且合并相邻的⻚，组成更⼤的⻚，缓解内存碎片的问题。

2. 定长内存池的实现

实现一个定长内存池，主要完成的功能就是两个：申请和释放。

2.1 介绍定长内存池

从图中可以看到_memory是我们向系统申请的一大块内存。
_freeList表示的是自由链表。

这里需要说明一下，为什么会使用自由链表：因为我们写的内存池，所以，申请得到的内存不是用完就立马还回去，而是用完之后用一个自由链表链接起来，这样下次再申请内存的时候就不用在堆里面申请了，而是直接在自由链表里面获取，大大的提高了效率。

定长内存池使用的流程：
1.申请内存的时候，判断系统中是否有_freeList,如果有，判断_freeList的大小是否大于等于申请的内存，如果是，就直接从_freeList中拿。这些都不满足就去堆里申请了。

2.还回来内存的时候，直接将还回来的内存链入到_freeList的后面。

框架如下：

template<class T>
class ObjectPool
{
public:T* New(){}void Delete(T* obj){}
private:char* _memory = nullptr; // 指向大块内存的指针size_t _remainBytes = 0; // 大块内存在切分过程中剩余字节数void* _freeList = nullptr; // 还回来过程中链接的自由链表的头指针
};

2.2 T* New()

首先理解自由链表的结构：

每一个_freeList前面的部分存下一个自由链表的地址，这样就每个_freeList就链接起来了。

处理T* New()的逻辑：当系统要申请一块内存，我们设定为T* obj = nullptr;
此时需要判断是在堆上申请还是在从_freeList中拿。
如果_freeList不为空，就代表可以从_freeList中拿。

下面处理从_freeList中拿内存的逻辑：
可以理解为从_freeList中头删。

思考在单链表中是如何头删的？先保存下一个节点，然后让头节点指向下一个节点。

这里涉及一个问题：next如何取？
为什么说这是一个问题，因为我们不知道所要取用的大小，如果是char类型，就是1；如果是int类型，就是4；如果是double类型，就是8；这里要取用的是next,是一个地址，大小是指针大小。我们不知道指针大小是多少（这根据不同的平台会有不同）。

那么，我们该如何取一个指针的大小呢？
int*,存的是int的地址，int存的是int*的地址。(int)解引用就是int*的大小。

因此，我们可以使用 * (void**)表示的就是void*类型，而*((void**)_freeList)就表示取_freeList前指针大小个字节，也就是地址。

第二种情况，就是没有还回来的内存，没有_freeList，该怎么办呢？

这里没什么好说的。

当obj取到了T大小的空间，还需要判断一下，这个T大小的空间是否比void*大，如果比void*小，要给void*大小的内存。这是因为我们至少要保证取下来的内存能存一个地址，不然无法链接回来了。

最终代码如下：

	T* New(){T* obj = nullptr;//1.优先把换回来的内存块再次重复利用if (_freeList)  //代表有还回来的内存块对象{//重复利用，进行单链表的头删 //这里的*(void**)_freeList表示取freeLiset的前指针大小个字节 -->也就是取next的地址void* next = *((void**)_freeList);     //?  这里为什么使用void**//obj是取整个对象obj = (T*)_freeList;//往后移动一位_freeList = next;}else  //如果没有还回来的内存块{//判断开辟的一大块空间是否够这次申请的if (_remainBytes < sizeof(T))  {//如果不够_remainBytes = 1024 * 128;   //申请128KB//这里为什么要这么写?_memory = (char*)malloc(_remainBytes);//SystemAlloc是系统调用接口//_memory = (char*)SystemAlloc(_remainBytes >> 13);//异常处理if (_memory == nullptr){throw std::bad_alloc();}}//创建一个对象指向memory,这个obj也就是我们申请内存给到的实体obj = (T*)_memory;//这里判断的意义是：如果我们申请的空间大于指针的大小，就返回我们申请的空间，//否则返回指针的大小  --> 这样做是为了内存块至少能存下地址size_t objSize = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T);//大块内存的指针向后移动_memory += objSize;//可用空间减少_remainBytes -= objSize;}new(obj) T;return obj;}

2.3 void Delete(T* obj)

这个过程可以看成是对_freeList的头插。

	void Delete(T* obj){//显式调用函数清理对象obj->~T();//头插//将obj内存块的前指针大小的字节存入_freeList的地址*(void**)obj = _freeList;//将_freeList移动为头结点_freeList = obj;}

3. 源码（附赠测试）

#pragma once
#include"Common.h"template<class T>
class ObjectPool
{
public://申请内存T* New(){T* obj = nullptr;//1.优先把换回来的内存块再次重复利用if (_freeList)  //代表有还回来的内存块对象{//重复利用，进行单链表的头删 //这里的*(void**)_freeList表示取freeLiset的前指针大小个字节 -->也就是取next的地址void* next = *((void**)_freeList);     //?  这里为什么使用void**//obj是取整个对象obj = (T*)_freeList;//往后移动一位_freeList = next;}else  //如果没有还回来的内存块{//判断开辟的一大块空间是否够这次申请的if (_remainBytes < sizeof(T))  {//如果不够_remainBytes = 1024 * 128;   //申请128KB//这里为什么要这么写?_memory = (char*)malloc(_remainBytes);//SystemAlloc是系统调用接口//_memory = (char*)SystemAlloc(_remainBytes >> 13);//异常处理if (_memory == nullptr){throw std::bad_alloc();}}//创建一个对象指向memory,这个obj也就是我们申请内存给到的实体obj = (T*)_memory;//这里判断的意义是：如果我们申请的空间大于指针的大小，就返回我们申请的空间，//否则返回指针的大小  --> 这样做是为了内存块至少能存下地址size_t objSize = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T);//大块内存的指针向后移动_memory += objSize;//可用空间减少_remainBytes -= objSize;}new(obj) T;return obj;}//这是释放的过程，将释放的小内存块挂到_freeList前面void Delete(T* obj){//显式调用函数清理对象obj->~T();//头插//将obj内存块的前指针大小的字节存入_freeList的地址*(void**)obj = _freeList;//将_freeList移动为头结点_freeList = obj;}
private:char* _memory = nullptr;         //指向大块内存的指针size_t _remainBytes = 0;         //大块内存切分过程中剩余字节数void* _freeList = nullptr;      //还回来过程中链接的滋有链表的头指针
};//测试
struct TreeNode
{int _val;TreeNode* _left;TreeNode* _right;TreeNode():_val(0), _left(nullptr), _right(nullptr){}
};void Test1()
{// 申请释放的轮次const size_t Rounds = 5;// 每轮申请释放多少次const size_t N = 100000;std::vector<TreeNode*> v1;v1.reserve(N);size_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();std::vector<TreeNode*> v2;v2.reserve(N);ObjectPool<TreeNode> TNPool;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;
}

4. 总结

本文主要讲了两个方面的内容，分别是高并发内存池的结构和实现定长内存池。

1. 实现定长内存池的思路：
   1.1 从系统中申请T大小的内存obj，首先要判断系统中是否有_freeList,如果有，直接将_freeList头删，将切出来的节点给obj.
   1.2 如果没有_freeList，就直接从之前申请的大内存_memory中申请，如果_memory的大小不够申请的T的大小，就从堆上申请。如果_memory够大，就从_memory中切一个大小为T的内存块给obj.

2.如何取_freeList的前指针大小个节点。*(void**) obj = _freeList这句话就等价于obj->next = _freeList。

*(void**) next = _freeList就表示取_freeList 的前指针大小个字节，而_freeList的前指针大小个字节存的是下一个内存块的地址，因此这句话表示取_freeList的下一个内存块，等价于next = _freeList->next.