【C++】实现一个定长内存池(Object Pool)

本文主要是介绍【C++】实现一个定长内存池(Object Pool)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

为什么要有定长内存池？

什么是定长内存池？

如何实现定长内存池？

---

为什么要有定长内存池？

C++中，申请释放空间一般使用new和delete。为了解决自定义类型初始化和清理的问题，new的底层封装了operator new和构造函数，delete的底层封装了析构函数和operator delete。又为了配合C++面向对象的异常机制，operator new和operator delete又分别封装了malloc和free，并在申请空间失败时抛出bad_alloc异常。malloc和free为了综合考虑各种场景，在某些场景下无法发挥出最高的效率，比如：每次只申请固定大小的空间时。为了解决这个问题，我们可以手动写一个定长的内存池(object pool)。

---

什么是定长内存池？

每次都new和delete固定长度的对象，简单起见，我们假设每次都new和delete同一类型的对象（假设类型是T）。

---

如何实现定长内存池？

先来考虑如何new。在堆上申请一大块内存（比如128KB），每次在这块内存中“切分”出一个T类型的对象并返回。当大块内存的空间不够时，再重新申请一大块内存。我们需要记录大块内存中还没使用的起始位置(_memory)和还没使用的字节数(_remainBytes)。对象大小(objSize)至少是一个指针的大小，原因我稍后讲解。为了符合new会自动调用构造函数的特点，我们在返回obj前调用定位new(placement new)完成初始化的工作。如何“切分”呢？记录并返回_memory的地址，并让_memory向后挪动objSize字节即可。

	// 剩余空间不够一个对象大小时，重新申请大块内存size_t objSize = std::max<size_t>(sizeof(T), sizeof(void*));if (_remainBytes < objSize){_remainBytes = 128 * 1024;_memory = static_cast<char*>(SystemAlloc(_remainBytes >> 13));}// 分配空间obj = reinterpret_cast<T*>(_memory);_memory += objSize;_remainBytes -= objSize;
}new (obj) T;
return obj;

其中SystemAlloc直接在堆上按页（一般是8KB）申请空间。比如，WIN32可以直接调用VirtualAlloc。

inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32void* ptr = VirtualAlloc(0, kpage << 13,MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else// ...
#endif // _WIN32if (nullptr == ptr){throw std::bad_alloc();}return ptr;
}

接下来考虑如何delete。当我们delete obj时，为了符合delete会自动调用析构函数的特点，需要显示调用析构函数完成清理工作。obj这块空间不能“丢了”，我们用单向链表来管理delete的空间，把obj指向的这块空间当作一个节点链接到一个链表中，我们称这个链表为自由链表(free list)。每个节点的头4或者8字节（具体取决于环境是x86还是x64）存储下一个节点的地址。用_freeList记录头节点的地址。我们把obj插入到自由链表中，就完成了对还回来的空间的管理。由于我们只有头节点的地址，所以头插(push front)的效率非常高，如果尾插(push back)的话还需要遍历链表找到尾节点。

void Delete(T* obj)
{if (obj){obj->~T();// 把obj头插到自由链表中NextObj(obj) = _freeList;_freeList = obj;}
}

我们把obj下一个节点的地址存储在obj的前4或者8字节的空间中。如何取出这个地址呢？只需要把obj的类型转换为void**，再解引用，就能取出一个void*了。

inline static void*& NextObj(void* obj)
{assert(obj);return *static_cast<void**>(obj);
}

由于节点必须能存下一个指针，所以每次申请的空间大小(objSize)至少是一个指针的大小。另外，每次new的时候，如果自由链表非空，优先重复利用自由链表的空间。由于我们只有自由链表的头指针，所以直接返回头节点的地址，并且对自由链表执行头删(pop front)操作，不尾删(pop back)同样是因为找尾节点需要遍历链表导致效率太低。

if (_freeList)
{// 重复利用还回来的内存块obj = static_cast<T*>(_freeList);_freeList = NextObj(_freeList); // 自由链表的头删
}

附上ObjectPool的完整代码。

template <class T>
class ObjectPool
{
public:T* New(){T* obj = nullptr;if (_freeList){// 重复利用还回来的内存块obj = static_cast<T*>(_freeList);_freeList = NextObj(_freeList); // 自由链表的头删}else{// 剩余空间不够一个对象大小时，重新申请大块内存size_t objSize = std::max<size_t>(sizeof(T), sizeof(void*));if (_remainBytes < objSize){_remainBytes = 128 * 1024;_memory = static_cast<char*>(SystemAlloc(_remainBytes >> 13));}// 分配空间obj = reinterpret_cast<T*>(_memory);_memory += objSize;_remainBytes -= objSize;}new (obj) T;return obj;}void Delete(T* obj){if (obj){obj->~T();// 把obj头插到自由链表中NextObj(obj) = _freeList;_freeList = obj;}}private:char*  _memory = nullptr; // 指向大块内存size_t _remainBytes = 0;  // 大块内存还剩多少字节没用void* _freeList = nullptr; // 自由链表，管理还回来的内存块
};

---

简单测试一下效率，和C++原生的new和delete作对比。

template <class T>
class TreeNode
{using Node = TreeNode<T>;public:T _val;Node* _parent = nullptr;Node* _left = nullptr;Node* _right = nullptr;TreeNode(const T& val = T()): _val(val){}
};void TestObjectPool()
{const size_t ROUNDS = 5;  // 申请释放多少轮const size_t N = 1000000; // 每轮申请释放多少次std::vector<TreeNode<int>*> v1;std::vector<TreeNode<int>*> v2;v1.reserve(N);v2.reserve(N);// 测试new和delete申请释放空间clock_t begin1 = clock();for (size_t i = 0; i < ROUNDS; ++i){for (size_t j = 0; j < N; ++j){v1.emplace_back(new TreeNode<int>);}for (auto ptr : v1){delete ptr;}v1.clear();}clock_t end1 = clock();// 测试ObjectPool申请释放空间clock_t begin2 = clock();ObjectPool<TreeNode<int>> treeNodePool;for (size_t i = 0; i < ROUNDS; ++i){for (size_t j = 0; j < N; ++j){v2.emplace_back(treeNodePool.New());}for (auto ptr : v2){treeNodePool.Delete(ptr);}v2.clear();}clock_t end2 = clock();std::cout << "new and delete cost time: " << end1 - begin1 << std::endl;std::cout << "object pool cost time: "    << end2 - begin2 << std::endl;
}

在Release x64环境下输出：

new and delete cost time: 296
object pool cost time: 30

芜湖！这效率一下就上来了！

这篇关于【C++】实现一个定长内存池(Object Pool)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---