定长内存池
介绍：向操作系统申请一块足够的内存，并以链表的方式来连接，该内存只能被固定的类型所申请。
windows和Linux下如何直接向堆申请页为单位的大块内存：
VirtualAlloc
框架：
_memory：先向操作系统申请一块足够大的空间，我们需要一个指针来指向这块空间。
_freelist：程序释放空间时，我们不用还给操作系统，而是用自由链表来连接起来，当下次申请空间时，先在自由链表中找，我们需要一个指针来指向链表的头部。
bySize：表示_memory所指向的内存所剩的大小。
#include<iostream>
#include<Windows.h>
#include<vector>
#include<time.h>
using namespace std;
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
// linux下brk mmap等
#endif
if (ptr == nullptr)
throw std::bad_alloc();
return ptr;
}
template<class T>//T的类型是固定的-定长内存池
class objMemoryPool
{
public:
objMemoryPool():_memory(nullptr),_freelist(nullptr),_bySize(0)
{}
~objMemoryPool(){}
T* New(){}//申请内存池中的空间
void Delete(T* obj){}//释放，连接到自由链表中
private:
char* _memory;//指向向操作系统申请的空间的指针(给char* 方便进行剪切)
void* _freelist;//指向自由链表的头部的指针
size_t _bySize;//申请空间的所剩的大小
};
自由链表：
如何把释放回来的内存块连接起来？
我们在这些内存块的头4或者8个字节中存放下一个内存块的指针。
T* obj=nullptr;
_freelist=obj;
*((int*)obj)=nullptr;
把obj强转成int*指针，当解引用的时候就可以拿到这块内存块前4个字节的位置来存放下一个内存块的指针。
但是，当前只对于32位下的有效，在64位下，指针的大小为8字节，解引用int*拿不到8字节。
修改方案为：
T* obj=nullptr;
_freelist=obj;
*((void**)obj)=nullptr;
在32位下解引用拿到4字节，64位下解引用拿到8字节。
New：
T* New()
{
T* obj=nullptr;
//首先判断_freelist是否为空（我们先到自由链表中申请内存块，
//如果没有再到_memory所指向的大快内存中申请）
if(_freelist){
//自由链表不为空，去自由链表中的头部
obj=(T*)_freelist;
_freelist=*((void**)_freelist);
*((void**)obj)=nullptr;
return obj;
}
else{
//自由链表为空，在大块内存中申请内存
//先判断所剩下的内存还够不够
if(_bySize<sizeof(T)){
//大快内存已经不够了，要在堆上申请
_bySize=8*1024;//一次申请8KB的大小
_memory=(char*)SystemAlloc(_bySize>>13);
if(_memory==nullptr){
throw std::bad_alloc();
}
}
}
//大块内存已经申请好了
obj=(T*)_memory;
size_t objSiz=0;
//如果需要申请的内存块大小不足一个指针的大小，则要给出一个指针的大小，方便释放的时候连接到自由链表中
objSize=sizeof(T)<sizeof(void*)?sizeof(void*):sizeof(T);
_memory+=objSize;
_bySize-=objSize;
//如果T是string、vector、map、set、等，那么我们要调用它们的构造函数来初始化
new(obj)T;
return obj;
}
Delete：
//释放相对简单一些，只需要连接到自由链表中
void Delete(T* obj){
//显示调用析构函数来清理
obj->~T();
//头插
*((void**)obj)=_freelist;
_freelist=obj;
}
性能测试
测试样例
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 = 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);
objMemoryPool<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();
retu
