实现定长的内存池

池化技术

        所谓的池化技术，就是程序预先向系统申请过量的资源，然后自己管理起来，以备不时之需。这个操作的价值就是，如果申请与释放资源的开销较大，提前申请资源并在使用后并不释放而是重复利用，能够提高程序运行效率和减少开销。

        在计算机领域，池化技术有非常多的应用场景，如内存池、连接池、线程池和对象池等。以服务器中的线程池为例，它的主要思想是：预先启动一批线程，让它们先进入睡眠状态，当有客户端请求到来时，唤醒一个线程进行处理，并在处理完请求后，继续睡眠，等待下一次被唤醒。

什么是定长池

        我们C语言中使用的malloc实际上是标准库的函数，底层实现实际上就使用了内存池技术，它支持根据我们的需求分配不同大小的内存空间，而我们今天要设计的定长池则每次只能分配固定大小的空间，在频繁申请大小相同的空间的情况下，效率比malloc更优秀。

系统调用

        在windows环境下进行开发，所以使用windows内存申请的API：

VirtualAlloc

在进程的虚拟地址空间中分配或保留内存

#include <windows.h>LPVOID VirtualAlloc
(LPVOID IpAddress,      // 要分配的内存区域的地址SIZE_T dwSize,         // 分配的大小DWORD  flAllocationType,// 分配的类型DWORD  flProtect       // 该内存的初始保护属性
);

参数解释：

lpAddress：指定要分配的内存区域的起始地址。如果此参数为nullptr，则系统会自动决定分配内存区域的位置，并且按64KB向上取整。

dwSize：指定要分配或保留的区域的大小，以字节为单位。系统会根据这个大小一直分配到下页的边界。

flAllocationType：指定分配类型，可以是指定或合并以下标志：

• MEM_COMMIT：为指定地址空间提交物理内存。
• MEM_RESERVE：保留指定地址空间，不分配物理内存。这样可以阻止其他内存分配函数（如malloc和LocalAlloc等）再使用已保留的内存范围，直到它被释放。
• MEM_TOP_DOWN：在尽可能高的地址分配内存。
• MEM_LARGE_PAGES：分配内存时使用大页面支持。大小和对齐必须是一个大页面的最低倍数。

flProtect：指定被分配区域的访问保护方式。可能的值包括：

• PAGE_READWRITE：区域可以执行代码，应用程序可以读写该区域。
• PAGE_READONLY：区域为只读。如果应用程序试图访问区域中的页，将会被拒绝访问。
• PAGE_NOACCESS：任何访问该区域的操作将被拒绝。
• PAGE_GUARD：区域第一次被访问时进入一个STATUS_GUARD_PAGE异常，这个标志要和其他保护标志合并使用。
• PAGE_NOCACHE：RAM中的页映射到该区域时将不会被微处理器缓存（cached）。

返回值：

如果函数调用成功，则返回分配的首地址；
如果调用失败，则返回nullptr。可以通过GetLastError函数来获取错误信息。

// 直接去堆上按页申请空间
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32// 8K一页为单位向操作系统申请内存空间void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else// linux下brk mmap等
#endifif (ptr == nullptr)throw std::bad_alloc();return ptr;
}static void*& NextObj(void* obj)
{return *(void**)obj;
}

定长池设计

一个分配固定大小内存的模板类，由于申请的内存大小固定，所以申请固定大小的空间时，性能比malloc更好一些，目前暂时不考虑内存碎片问题。

管理的成员：

• 预先申请的内存空间的指针memory

• 管理用户释放空间的空闲链表的指针freelist

  • 空闲链表连接的方式是：用户将内存释放后，该内存空间的前4/8字节（取决于系统位数）空间用于存放下一块内存空间的地址。

  • 插入新空间到空闲链表：通过头插法实现，由于系统位数不确定，所以使用二级指针解引用来获得指针的大小，从而可以适用于32/64位系统。

• 记录空间剩余大小的字段remain_size

template<class T>
class ObjectPool
{
private:char* _memory = nullptr; // 预先申请的内存空间size_t _remain_size = 0; // 剩余空间大小void* _freelist = nullptr; // 管理用户释放空间的空闲链表
};

提供的方法：

• New：用户申请空间的接口。

  • 如果剩余空间大小不足一个空间，则重新开辟一块新的固定大小的内存空间。

  • 使用定位new，显示调用构造函数后返回对象指针给用户

  • 更新memory指针偏移量和remain_size大小，如果T类型大小不足以存放下一块空间的地址，则更新大小应为指针的大小。

T* New()
{T* obj = nullptr;// 优先使用空闲链表中的空间if (_freelist != nullptr){void* next = *((void**)_freelist);obj = (T*)_freelist;_freelist = next;}else{// 当空间不足时，开辟固定大小的空间if (_remain_size < sizeof T){_remain_size = 128 * 1024;//_memory = (char*)malloc(128 * 1024); // 定长池，开辟128KB的内存空间_memory = (char*)SystemAlloc(128 * 1024); // 定长池，开辟128KB的内存空间if (_memory == nullptr){throw std::bad_alloc();}}obj = (T*)_memory;// 分配的空间的大小至少要能够存放下一块空间的地址size_t objSize = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T);_memory += objSize; // 分配定长空间后，指针向后偏移_remain_size -= objSize; // 更新剩余空间大小}// 定位new，显式调用T的构造进行初始化new(obj)T;return obj;
}

• Delete，释放T*类型的指针指向的空间，但不会返回给操作系统，而是通过空闲链表管理起来。

  • 显式调用析构函数清理指针指向对象的资源，并将空闲空间头插到空闲链表。

  • 空闲链表连接的方式是：用户将内存释放后，该内存空间的前4/8字节（取决于系统位数）空间用于存放下一块内存空间的地址。

  • 插入新空间到空闲链表：通过头插法实现，由于系统位数不确定，所以使用二级指针解引用来获得指针的大小，从而可以适用于32/64位系统。

// 将用户要释放的空间用空闲链表管理起来
// 空闲链表连接的方式是：空间的前4/8字节（其实就是指针的大小，具体取决于系统位数）存放下一块空间的地址
void Delete(T* obj)
{obj->~T();// 使用二级指针获取指针，头插法将空间添加到空闲链表*(void**)obj = _freelist;_freelist = obj;
}

性能测试

接下来我们对定长池进行性能测试，并与malloc进行比较，以下是测试代码：

void TestPool()
{const int round = 5;const int times = 50000;std::vector<TreeNode*> v1;v1.reserve(5);size_t begin1 = clock();for (size_t j = 0; j < round; ++j){for (int i = 0; i < times; ++i){v1.push_back(new TreeNode);}for (int i = 0; i < times; ++i){delete v1[i];}v1.clear();}size_t end1 = clock();ObjectPool<TreeNode> TNPool;std::vector<TreeNode*> v2;v2.reserve(50000);size_t begin2 = clock();for (int i = 0; i < round; i++){for (int j = 0; j < times; j++){v2.push_back(TNPool.New());}for (int j = 0; j < times; j++){TNPool.Delete(v2[i]);}v2.clear();}size_t end2 = clock();std::cout << "malloc耗时：" << end1 - begin1 << std::endl;std::cout << "ObjectPool耗时：" << end2 - begin2 << std::endl;
}

Debug版本的比较：

Release版本的比较：

可以发现，在高频分配固定大小对象的场景下，定长池的效率要比malloc更高，这是因为：

定长池只用于分配固定大小的对象，每次开辟的都是固定大小的内存块，管理空闲空间也只需要使用简单的空闲链表就能完成；而malloc需要处理各种各样的场景，根据用户需要分配不同大小的内存块，空闲空间的管理也要复杂得多。