定长内存池

二肥是只大懒蓝猫

发布于 2024-02-06 10:52:12

890

发布于 2024-02-06 10:52:12

文章被收录于专栏：热爱C嘎嘎

定长内存池介绍

定长内存池就是一个固定内存申请或释放大小的内存池，其特点是：①性能达到极致。②不需要考虑内存碎片问题。

①性能达到极致：由于内存池中的内存块大小一致，内存申请和释放操作通常只需要从池中取出或归还相应大小的内存块即可，避免了频繁的系统调用（如malloc和free），从而在一定程度上提高了内存管理效率，特别是在大量进行小对象内存分配和回收的场景下，性能优势更为明显。 ②不需要考虑内存碎片问题：因为内存池中的所有内存块大小相同，在分配和回收过程中不会产生不同大小的内存空洞，因此能够有效减少内存碎片。

定长内存池的实现思想

向系统申请一大块内存，使用一个指针指向内存，每次申请，就从这块内存中拿一块固定大小的内存（4字节或8字节，按32位系统或64位系统）。当使用者释放内存时，直接使用一个自由链表，将这一块块内存使用头插的形式连接起来，进行管理，当后续需要申请内存时，可以在自由链表上取内存块。

细节问题

1.获取系统下指针的大小用于链表链接

由于使用链表将还回来的内存管理，因此每一块内存至少需要4字节或者8字节，那么如果申请的内存小于4字节或者8字节就不好进行管理了，而如果使用64位系统，指针的大小是8字节。

因此需要保证的是在32位系统下，内存块要大于4字节，64位系统下，要大于8字节。因此需要将内存对象强转为二级指针，再解引用。比如（*(void**)），这样就是获取到当前系统下指针的大小。

2.内存申请释放问题

当一块内存块用完，需要再开辟的时候，其判断条件是当前的对象类型的大小，是否大于内存池剩余内存的大小，如果是，那么需要再向系统申请一大块内存。如果不是，则直接分配给使用者。

其次，当自由链表中有内存了，那么申请内存的时候，直接从自由链表中申请。

最后，需要显示调用对象的构造函数和析构函数。

代码实现

向堆申请内存

既然自己动手实现内存池，脱离malloc和new了，就直接使用Windows提供的原生库函数。

LPVOID VirtualAlloc(
  LPVOID lpAddress,
  SIZE_T dwSize,
  DWORD  flAllocationType,
  DWORD  flProtect
);
//lpAddress：指定分配内存的起始地址。如果为NULL，则由系统选择一个地址。
//dwSize：指定要分配的内存大小（以字节为单位）。
//flAllocationType：指定内存分配的类型。
//flProtect：指定内存保护标志

kpage << 13表示：分配Kpage页4或8KB的内存。

MEM_COMMIT | MEM_RESERVE表示：提交和保留内存

PAGE_READWRITE表示：允许读写访问。

#include<Windows.h>
// 直接去堆上按页申请空间
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 //_WIN64

	if (ptr == nullptr)
		throw std::bad_alloc();

	return ptr;
}

获取obj指向的内存对象中的下一个内存对象的地址。

将内存块对象obj强转为void**，表示obj是一个指向void*的指针，接着这个指针解引用，获得这个指针指向的对象，也就是next了。

//获取obj指向的内存对象中的下一个内存对象的地址。
static void*& NextObj(void* obj)
{
	return *((void**)obj);
}

申请内存

思想：

①首先去自由链表上看看有没有空闲的内存块，如果有，则采取头删的方式，将内存块取出来。

②如果自由链表上没有内存块，则从_memory指向的大块内存中取。

③在第二步上，首先判断大块内存块剩余的内存大小是否满足对象类型的大小，如果满足，则分配出去。如果不满足，需要向堆再次申请128KB的内存。

④在第三步上，如果满足对象类型大小，在分配前，需要计算出_memory指针偏移量。这个偏移量需要保证分配出去的内存块大小，必须大于对象类型大小，因为需要存储下一个指针的地址。

⑤最后，在返回指向内存块的指针前，需要显示调用对象的构造函数，这是C++的new的特性。

T* New()
{
	T* obj = nullptr;
	/*判断自由链表中有没有内存*/
	if (_freeList != nullptr)
	{
		void* next = NextObj(_freeList);
		obj = (T*)_freeList;
		_freeList = next;
	}
	else
	{
		/*自由链表中没有内存，则向_memory指向的内存块获取*/
		/*需要先判断当前内存池剩下的内存是否足够，如果不够，则需要向堆申请*/
		if (_remainBytes < sizeof(T))
		{
			_remainBytes = 128 * 1024;//128KB
			//128KB，右移13位，相当于除8KB，算出需要的页数（每页8KB，不管32位还是64位）
			_memory = (char*)SystemAlloc(_remainBytes >> 13);
			if (_memory == nullptr)
			{
				//出错抛异常
				throw std::bad_alloc();
			}
		}
		//足够
		obj = (T*)_memory;
		//算出_memory偏移量，需要注意的是，偏移量必须足够一个对象类型大小，因为需要存指针
		size_t objSize = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T);
		_memory += objSize;//偏移
		_remainBytes -= objSize;//减去分配出去的量
	}

	//显示调用构造函数，显示调用T类型的构造函数
	new(obj)T;

	return obj;//返回内存的指针
}

释放内存

思想：

①首先显示调用析构函数，这是C++中free()的特性！

②使用头插的方式，将释放的内存块挂到自由链表中。

	void Delete(T* obj)
	{
		//显示调用析构函数
		obj->~T();

		//将内存块挂到自由链表上,采取头插的方式
		NextObj(obj) = _freeList;
		_freeList = obj;

	}

完整代码

#pragma once
#include<iostream>
#include<Windows.h>
// 直接去堆上按页申请空间
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 //_WIN64

	if (ptr == nullptr)
		throw std::bad_alloc();

	return ptr;
}
//获取obj指向的内存对象中的下一个内存对象的地址。
static void*& NextObj(void* obj)
{
	return *((void**)obj);
}

template<class T>
class objectPool
{
private:
	char* _memory = nullptr;//指向内存块的指针
	void* _freeList = nullptr;//管理归还回来的内存的自由链表
	size_t _remainBytes = 0;//内存池剩余的内存大小（字节），用于判断是否需要扩容
public:
	T* New()
	{
		T* obj = nullptr;
		/*判断自由链表中有没有内存*/
		if (_freeList != nullptr)
		{
			void* next = NextObj(_freeList);
			obj = (T*)_freeList;
			_freeList = next;
		}
		else
		{
			/*自由链表中没有内存，则向_memory指向的内存块获取*/
			/*需要先判断当前内存池剩下的内存是否足够，如果不够，则需要向堆申请*/
			if (_remainBytes < sizeof(T))
			{
				_remainBytes = 128 * 1024;//128KB
				//128KB，右移13位，相当于除8KB，算出需要的页数（每页8KB，不管32位还是64位）
				_memory = (char*)SystemAlloc(_remainBytes >> 13);
				if (_memory == nullptr)
				{
					//出错抛异常
					throw std::bad_alloc();
				}
			}
			//足够
			obj = (T*)_memory;
			//算出_memory偏移量，需要注意的是，偏移量必须足够一个对象类型大小，因为需要存指针
			size_t objSize = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T);
			_memory += objSize;//偏移
			_remainBytes -= objSize;//减去分配出去的量
		}

		//显示调用构造函数，显示调用T类型的构造函数
		new(obj)T;

		return obj;//返回内存的指针
	}

	void Delete(T* obj)
	{
		//显示调用析构函数
		obj->~T();

		//将内存块挂到自由链表上,采取头插的方式
		NextObj(obj) = _freeList;
		_freeList = obj;

	}
};

测试

接下来，测试定长内存池相比较C++提供的new/delete，它们的性能差距。测试方法：

创建一棵二叉树，通过不断地对其进行创建对象以及销毁对象，测试它们使用的时间成本。

//一棵二叉树
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)
		{
			//通过new创建对象，即申请了内存
			v1.push_back(new TreeNode);
		}
		for (int i = 0; i < N; ++i)
		{
			//通过delete销毁对象，即释放内存
			delete v1[i];
		}
		v1.clear();
	}

	size_t end1 = clock();

	std::vector<TreeNode*> v2;
	v2.reserve(N);

	objectPool<TreeNode> TNPool;
	size_t begin2 = clock();
	for (size_t j = 0; j < Rounds; ++j)
	{
		for (int i = 0; i < N; ++i)
		{
			//通过定长内存池的New申请对象
			v2.push_back(TNPool.New());
		}
		for (int i = 0; i < N; ++i)
		{
			//通过定长内存池的Dlete释放内存
			TNPool.Delete(v2[i]);
		}
		v2.clear();
	}
	size_t end2 = clock();

	std::cout << "new cost time:" << end1 - begin1 << std::endl;
	std::cout << "object pool cost time:" << end2 - begin2 << std::endl;
}