定长内存池原理及实现

一、池化技术

        所谓“池化技术”，就是程序先向系统申请过量的资源，然后⾃⼰管理，以备不时之需。之所以要申请过量的资源，是因为每次申请该资源都有较⼤的开销，不如提前申请好了，这样使⽤时就会变得⾮常快捷，⼤⼤提⾼程序运⾏效率。
        在计算机中，有很多使⽤“池”这种技术的地⽅，除了内存池，还有连接池、线程池、对象池等。以服务器上的线程池为例，它的主要思想是：先启动若⼲数量的线程，让它们处于睡眠状态，当接收到客户端的请求时，唤醒池中某个睡眠的线程，让它来处理客户端的请求，当处理完这个请求，线程⼜进⼊睡眠状态。

二、内存池

       内存池是指程序预先从操作系统申请⼀块⾜够⼤的内存，此后，当程序中需要申请内存的时候，不是直接向操作系统申请，⽽是直接从内存池中获取；同理，当程序释放内存的时候，并不真正将内存返回给操作系统，⽽是返回内存池。当程序退出(或者特定时间)时，内存池才将之前申请的内存真正释放。

三、内存池主要解决的问题

        内存池主要解决的当然是效率的问题，其次如果作为系统的内存分配器的⻆度，还需要解决⼀下内存碎⽚的问题。那么什么是内存碎⽚呢？
        内存碎⽚分为外碎⽚和内碎⽚，外部碎⽚是⼀些空闲的连续内存区域太⼩，这些内存空间不连续，以⾄于合计的内存⾜够，但是不能满⾜⼀些的内存分配申请需求。内部碎⽚是由于⼀些对⻬的需求，导致分配出去的空间中⼀些内存⽆法被利⽤。

        malloc申请内存能适应于大多数场景，是通用的，但在某些特定场景下效率并不高，而且可能会产生大量的内存碎片。

四、定长内存池的实现

1.定长内存池的原理

        如上所述，我们先向系统申请一大块空间，然后当我们需要申请内存时就从这块空间上获取，我们把空间用完后不用急着释放回系统，而是把它用一个自由链表连接起来，进行二次利用。也就是说我们再次申请空间时可以在这块废弃的空间上找，如果没有再去大空间上找，如果还不够再去向系统申请。

2.框架

        封装一个类，它的成员变量应包括：一个size_t类型储存该块空间的字节大小，一个void*指针储存自由链表的头，char*指针指向这块空间的起始地址，char*类型指针每加1只向后移动一字节，方便指针的移动。因为我们每被用户申请一小块空间后，指针往后移动到下一个为没利用的空间的起始地址。

template <typename T>
class FixedMemoryPool
{
public:T *New();void Delete(T *p);
private:size_t _sumSize = 0;char *_memory = nullptr;void *_list_head = nullptr;
};

        初始化操作只需要在成员变量声明这里进行，然后使用默认的构造函数就可以，主要需要我们来实现New和Delete的逻辑。

3.Delete实现

        Delete主要就是来维护自由链表，我们先来实现自由链表，因为在New中需要先在自由链表中查找空间。首先执行它的析构清空在它身上申请的空间。因为头插比较方便，我们直接把它头插到自由链表中。接下来就是头插操作：

        我们把这块需要插入到链表的废弃空间记为p，首先把_list_head储存到p空间的前4/8字节，因为并不确定用户用的是32位系统还是64位系统，所以可以用这样一个操作来解决：

*(void **)p = _list_head;

然后_list_head = p，如下：

void Delete(T *p)
{p->~T();*(void **)p = _list_head;_list_head = p;
}

4.New实现

        我们先来定义一个T* ret用来储存返回值，然后先去自由链表里找空间，如：

if (_list_head != nullptr)
{ret = (T *)_list_head;_list_head = *(void **)_list_head;
}

        大家看到 _list_head = *(void **)_list_head 这个代码可能会一点懵我来逐一讲解以下：

        _list_head是一个void*指针，储存了一个地址，而这个地址空间里面又储存了下一个节点的指针，(void**)相当于告诉编译器我是指向一个void*类型的指针，然后进行解引用得到这块地址，并更新_list_head。

如果链表里没有空间向大空间里获取：

else
{int objSize = max(sizeof(T), sizeof(void *));if (_sumSize < objSize)//空间不够向系统申请{_memory = (char *)malloc(128 * 1024);_sumSize = 128 * 1024;}ret = (T *)_memory;_memory += objSize;//移向未被利用的起始空间_sumSize -= objSize;//更新剩余空间的大小
}

objSize的作用：

        因为我们要保证这块空间至少要能存放得下一个地址，要不然被弃用后无法连接到自由链表。

        注意这里_sumSize不能是+=128*1024，因为_memory的初始地址已经更新了，要与_memory匹配。

最后对ret使用定位 new 后返回即可。

5.性能测试

源码已放在下文，如下是测试结果：

我们可以看到用定长内存池比new申请内存要快得多得多。

注：new的底层调用的就是malloc。

五、源码

FixedMemoryPool.h

#include <iostream>
#include <string>
#include <algorithm>
#include <memory>
using namespace std;
namespace my_MemoryPool
{template <typename T>class FixedMemoryPool{public:T *New(){T *ret = nullptr;if (_list_head != nullptr){ret = (T *)_list_head;_list_head = *(void **)_list_head;}else{int objSize = max(sizeof(T), sizeof(void *));if (_sumSize < objSize){_memory = (char *)malloc(128 * 1024);_sumSize = 128 * 1024;}ret = (T *)_memory;_memory += objSize;_sumSize -= objSize;}new (ret) T;return ret;}void Delete(T *p){p->~T();*(void **)p = _list_head;_list_head = p;}private:size_t _sumSize = 0;char *_memory = nullptr;void *_list_head = nullptr;};
}

test.cc

#include "FixedMemoryPool.h"
#include <vector>
using namespace my_MemoryPool;
struct TreeNode
{int _val;TreeNode* _left;TreeNode* _right;TreeNode():_val(0), _left(nullptr), _right(nullptr){}
};void TestObjectPool()
{// 申请释放的轮次const size_t Rounds = 5;// 每轮申请释放多少次const size_t N = 10000;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);FixedMemoryPool<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;
}
int main()
{TestObjectPool();return 0;
}