定长内存池的实现

定长内存池的实现

• • 如何实现定长
  • 如何直接向堆申请空间？
  • 定长内存池中应该包含哪些成员变量？
  • 内存池如何管理释放的对象？
  • • 如何在32/64位平台下访问到内存块的前4/8个字节？
    • 释放对象
  • 内存池如何为我们申请对象？
  • 完整代码
  • 性能测试

如何实现定长

1. 使用非类型模板参数，使得内存池中申请的内存块大小都是N

template<size_t N>
class ObjectPool {};

2. 定长内存池也叫做对象池，在创建对象池时，可以根据传入的对象类型的大小来实现“定长”，因此我们可以通过使用模板参数来实现“定长”

template<typename T>
class ObjectPool {};

如何直接向堆申请空间？

在Windows下，可以调用VirtualAlloc函数；在Linux下，可以调用brk或mmap函数。

void* SystemAlloc(size_t kpage) {
#ifdef _WIN32
	void* ptr = VituralAlloc(NULL, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
	// linux brk mmap
#endif
	if (ptr == nullptr) {
		throw std::bad_alloc();
	}
	return ptr;
}

#if 0
LPVOID VirtualAlloc(
  LPVOID lpAddress,     // 指定分配内存的起始地址，传入 NULL 由系统决定地址
  SIZE_T dwSize,       // 要分配的内存大小（字节）
  DWORD  flAllocationType, // 内存分配类型
  DWORD  flProtect      // 内存保护属性
);
#endif

定长内存池中应该包含哪些成员变量？

_memory：指向大块内存的指针。
_remainBytes：大块内存切分过程中剩余字节数。
_freeList：还回来过程中链接的自由链表的头指针。

内存池如何管理释放的对象？

对于还回来的定长内存块，我们可以用自由链表将其链接起来，但我们并不需要为其专门定义链式结构，我们可以让内存块的前4个字节（32位平台）或8个字节（64位平台）作为指针，存储后面内存块的起始地址。
因此在向自由链表插入被释放的内存块时，先让该内存块的前4个字节或8个字节存储自由链表中第一个内存块的地址，然后再让_freeList指向该内存块即可，也就是一个简单的链表头插操作。

如何在32/64位平台下访问到内存块的前4/8个字节？

1. 首先，将原始指针ptr转换为指向指针的指针即(void**)ptr（32位下是4个字节、64位下是8个字节），接下来，通过解引用(void**)ptr 读取内存块的前4/8个字节。

void*& NextObj(void* ptr) {
	return *(void**)ptr;
}

2. 使用联合体

union Header {
    void* asPointer;
    uint64_t as64Bit;
    uint32_t as32Bit;
};

void processMemoryBlock(void* ptr) {
    Header header;
    header.asPointer = ptr;
    
    // 根据平台自动选择访问大小
    #ifdef _WIN64 // 或其他宏定义来检测64位平台
        uint64_t first8Bytes = header.as64Bit;
    #else
        uint32_t first4Bytes = header.as32Bit;
    #endif
}

释放对象

我们使用的是placement new，那么需要我们显示调用对象的析构函数清理对象。

void Delete(T* obj) {
	obj->~T();
	//将释放的对象头插到自由链表
	NextObj(obj) = _freeList;
	_freeList = obj;
}

内存池如何为我们申请对象？

• 当我们申请对象时，内存池应该优先把还回来的内存块对象再次重复利用，因此如果自由链表当中有内存块的话，就直接从自由链表头删一个内存块进行返回即可。
• 如果自由链表当中没有内存块，那么就在大块内存中切出定长的内存块进行返回，当内存块切出后及时更新_memory指针的指向，以及_remainBytes的值即可。

T* New() {
	T* obj = nullptr;
	if (_freeList != nullptr) {
		obj = (T*)_freeList;
		_freeList = NextObj(_freeList);
	} else {
		// 限制最小
		size_t objSize = sizeof(T) < sizeof(void*) ? void(*) : sizeof(T);
		// 开辟空间
		if (_remainBytes < objSize) {
			_remainBytes = 128 * 1024;
			_memory = (char*)SystemAlloc(_remainBytes >> 13);
			if (_memory == nullptr) {
				throw std::bad_alloc();
			}
		}
		obj = (T*)_memory;
		_memory += objSize;
		_remainBytes -= objSize;
	}
	// placement new
	new (obj) T;
	return obj;
}

完整代码

//定长内存池
template<class T>
class ObjectPool
{
public:
	//申请对象
	T* New()
	{
		T* obj = nullptr;

		//优先把还回来的内存块对象，再次重复利用
		if (_freeList != nullptr)
		{
			//从自由链表头删一个对象
			obj = (T*)_freeList;
			_freeList = NextObj(_freeList);
		}
		else
		{
			//保证对象能够存储得下地址
			size_t objSize = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T);
			//剩余内存不够一个对象大小时，则重新开大块空间
			if (_remainBytes < objSize)
			{
				_remainBytes = 128 * 1024;
				//_memory = (char*)malloc(_remainBytes);
				_memory = (char*)SystemAlloc(_remainBytes >> 13);
				if (_memory == nullptr)
				{
					throw std::bad_alloc();
				}
			}
			//从大块内存中切出objSize字节的内存
			obj = (T*)_memory;
			_memory += objSize;
			_remainBytes -= objSize;
		}
		//定位new，显示调用T的构造函数初始化
		new(obj)T;

		return obj;
	}
	//释放对象
	void Delete(T* obj)
	{
		//显示调用T的析构函数清理对象
		obj->~T();

		//将释放的对象头插到自由链表
		NextObj(obj) = _freeList;
		_freeList = obj;
	}
private:
	char* _memory = nullptr;     //指向大块内存的指针
	size_t _remainBytes = 0;     //大块内存在切分过程中剩余字节数

	void* _freeList = nullptr;   //还回来过程中链接的自由链表的头指针
};

性能测试

#include "../src/ObjectPool.cpp"
#include "cstddef"
#include <vector>
#include <iostream>

using namespace std;

struct TreeNode
{
	int _val;
	TreeNode* _left;
	TreeNode* _right;
	TreeNode()
		:_val(0)
		, _left(nullptr)
		, _right(nullptr)
	{}
};

void TestObjectPool()
{
	// 申请释放的轮次
	const size_t Rounds = 3;
	// 每轮申请释放多少次
	const size_t N = 1000000;
	std::vector<TreeNode*> v1;
	v1.reserve(N);

	//malloc和free
	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();

	//定长内存池
	ObjectPool<TreeNode> TNPool;
	std::vector<TreeNode*> v2;
	v2.reserve(N);
	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;
}

经过测试性能大概提升3倍！