不积跬步，无以至千里；不积小流，无以成江海，做项目也是一样，先从简单的部分做起，在正式的项目开始前，可以先来个开胃菜，一是可以熟悉简单的内存池是如何控制的，二是会作为之后内存池的一个基本组件。

malloc和定长内存池对比

malloc场景如下，malloc是一个通用的内存池，在什么场景下都可以使用，但这也意味着malloc在什么场景下都不会有很高的性能，因为malloc并不是针对某种场景专门设计的。

定长内存池就是针对固定大小内存块申请和释放的内存池，由于定长内存池只需要支持固定大小内存块的申请和释放，因此我们可以将其性能做到极致，并且在实现定长内存池时不需要考虑内存碎片等问题，因为我们申请/释放的都是固定大小的内存块。

定长内存池实现

框架设计

我们的思路是先申请大块内存，每次申请就切sizeof(T)大小的内存块，释放后，用链表组织起来，每个内存块前4/8个字节存下一个内存块的地址，再次申请内存时，如果_freeList不为空，就重复利用

image.png

核心成员

  • _ memory：指向申请大块内存的空间
  • _ freeList：组织归还的内存块的链表
  • _ remainBytes：大块内存剩余字节数

存在问题

  • 大块内存，剩下的内存不足一个T的大小如何处理？
  • T的类型大小若是小于指针的大小如何处理？
  • 内存块的前段内存存指针，这个大小是4？还是8？能不能考虑平台兼容？
  • 如何取一块内存的前4/8个字节？

这些问题怎么解决呢？我们在下面的内容详细讲解

成员函数

New

申请内存，返回对应类型的指针，我们首先看一下流程图

eeee.png

如果按照上述流程，先申请了大块内存之后，每次切T类型大小的内存块，但是最后的时候剩余的内存块不够的话，就会出现越界问题，所有，我们有了remainBytes成员，这个标识剩余的容量，当剩下的内存不足一个T的大小，我们就直接申请大块内存，初始的时候remainBytes为0，也是小于T的大小，同样进行申请，这就回答了第一个问题，和remainBytes成员的用处。

然后我们来看一下具体申请的两种操作：

1、在大块内存上切内存块，返回_memory的地址，然后让_memory往后移动sizeof(T)的距离。这也是我们为什么将memory成员设置为char * 的原因，因为+1操作就是往后移动一个字节。

image.png

2、如过freeList不为空，就头删取头节点返回即可

image.png

New代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
T* New()
{
	T* obj = nullptr;
	if (_freeList) //freeList不为空
	{
		// 直接进行头删
		obj = (T*)_freeList;
		/* freeList指向下一个节点，我们首先得取出来freeList指向得内存块中得前
		指针大小的字节，但是32位平台下，指针的大小为4，64位平台指针的大小为8，如果是4的话，我们可以将freeList强转为int* 然后解引用拿到了前4个字节，但是在64位平台下指针的大小占8个字节，这个就不行了。
		我们可以将 freeList强转为二级指针，解引用就是一级指针，这样就能拿到4或者8个字节了。这就回答了后边两个问题

		*/
		_freeList = *(void**)_freeList;
	}
	else
	{
		//说明需要先申请大块内存

		if (_remainBytes < sizeof(T))
		{
			//说明需要先申请大块内存
			_remainBytes = 128 * 1024;
			_memory = (char*)malloc(_remainBytes);
		}
		size_t objSize = sizeof(T) > sizeof(void*) ? sizeof(T) : sizeof(void*);
		obj = (T*)_memory;
		_memory += objSize;
		_remainBytes -= objSize;
	}
	//对T类型初始化-使用定位new
	new(obj)T;
	return obj;
}

Delete

释放内存（归还内存）, 直接对freeList进行头插操作即可，具体细节放到代码注释部分

image.png
Delete代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Delete(T* obj)
{
	if (obj == nullptr)
	{
		return;
	}
	else
	{
		//先显示调用析构
		obj->~T();
		//头插 进freeList链表
		*(void**)obj = _freeList;
		_freeList = (void*)obj;
	}
}

性能测试

性能测试代码很简单，就是不断的申请释放节点，申请的指针用vector保存，然后记录固定次数的申请释放时间就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
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 = 1000000;

	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);

	ObjectPool<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花费时间:" << end1 - begin1 << endl;
	cout << "定长内存池花费时间:" << end2 - begin2 << endl;
}

经过性能测试，当N是1000000，Release模式下，定长内存池速度大概为new的10几倍

image.png

整体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#pragma once
#include <iostream>
#include <vector>
#include <time.h>
using std::cout;
using std::endl;
#ifdef _WIN32
	#include<Windows.h>
#else
	#include <unistd.h>
#endif // _WIN32

template<class T>
class ObjectPool
{
public:
	T* New()
	{
		T* obj = nullptr;
		if (_freeList)
		{
			// 直接进行头删
			obj = (T*)_freeList;
			_freeList = *(void**)_freeList;
		}
		else
		{
			//说明需要先申请大块内存

			if (_remainBytes < sizeof(T))
			{
				//说明需要先申请大块内存
				_remainBytes = 128 * 1024;
				_memory = (char*)malloc(_remainBytes);
			}
			size_t objSize = sizeof(T) > sizeof(void*) ? sizeof(T) : sizeof(void*);
			obj = (T*)_memory;
			_memory += objSize;
			_remainBytes -= objSize;
		}


		//对T类型初始化-使用定位new
		new(obj)T;
		return obj;
	}

	void Delete(T* obj)
	{
		if (obj == nullptr)
		{
			return;
		}
		else
		{
			//先显示调用析构
			obj->~T();
			//头插 进freeList链表
			*(void**)obj = _freeList;
			_freeList = (void*)obj;
		}
	}
private:
	char* _memory = nullptr; // 指向大块内存的指针
	size_t _remainBytes = 0; // 大块内存在切分过程中剩余字节数

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

内存申请（系统接口）补充

在Windows下，可以调用VirtualAlloc函数，申请堆内存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 直接去堆上按页申请空间
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;
}

VirtualAlloc是Windows API中的一个函数，它在进程的虚拟地址空间内保留或提交内存页。

传递给VirtualAlloc的参数包括：

  • 0：要分配的区域的起始地址。0表示系统将选择起始地址。
  • kpage<<13：要分配的内存区域的大小（以字节为单位）。kpage<<13表示“kpage乘以2的13次方”。
  • MEM_COMMIT | MEM_RESERVE：分配的类型，在本例中，分配的是提交内存和保留内存。
  • PAGE_READWRITE：分配所需的内存保护，在这种情况下，指定了读写访问。

该函数返回指向分配内存的第一个字节的指针，该字节存储在ptr变量中

采用系统调用后，New的申请内存可以按下方的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
T* New()
{
	T* obj = nullptr;
	if (_freeList)
	{
		// 直接进行头删
		obj = (T*)_freeList;
		_freeList = *(void**)_freeList;
	}
	else
	{
		//说明需要先申请大块内存

		if (_remainBytes < sizeof(T))
		{
			//说明需要先申请大块内存
			_remainBytes = 128 * 1024;
			//_memory = (char*)malloc(_remainBytes);
			_memory = (char*)SystemAlloc(_remainBytes >> 13);
		}
		size_t objSize = sizeof(T) > sizeof(void*) ? sizeof(T) : sizeof(void*);
		obj = (T*)_memory;
		_memory += objSize;
		_remainBytes -= objSize;
	}


	//对T类型初始化-使用定位new
	new(obj)T;
	return obj;
}