内存池介绍_std::vector 使用外部内存池

1.什么是内存池

1.1池化技术

池是计算机中常用的一种设计模式，其特点是将资源提前申请好，放在’‘资源池’'之中由程序自己控制资源的使用，这样减少了与内核的交互

因为资源的申请是需要通过内核来完成的，与内核交互的频率越高， 程序的效率就越低，提前将资源申请出来，使用资源的时候不需要再向内核申请，直接就可以使用，在一定程度上提高了程序的效率

常见的池化技术有线程池，内存池等等

1.2内存池

通常我们使用内存是直接通过new/malloc直接申请，通过delete/free直接释放。

而内存池则是提前向系统申请一块较大的内存放在’池子‘中，当程序需要内存的时候，自动去池子之中获取内存，当使用完毕之后，再将内存释放回去，这样可以达到内存重复利用的目的

2.为什么需要内存池

• 解决内存碎片问题(外碎片)
• 减少与内核的交互，提高了申请的效率

3.内存池的发展

3.1早期内存池

• 优点：实现简单

• 缺点：分配时搜索合适的内存块效率低，释放回归内存后归并消耗大，实际中不实用

3.2定长内存池分配器

• 不会随意切割内存块出来，而是只会切割某些固定大小的内存块，只解决固定大小的内存块的申请和释放，如果给vector用，string对象用等等。固定的大小还回来后，再用链表连接管理起来，这个链表就叫做自由链表(FreeList)

• 优点：可以解决特定场景下的内存分配分体
• 缺点：功能单一，只能解决定长的内存需求，比如vector需要一个内存池，map也需要一个内存池，非常麻烦

3.3哈希映射的FreeList内存池

• 根据定长内存池进行优化，将可以固定分配的内存多样化，通过哈希映射起来

• 比如STL六大组件使用的内存池切割的方式就有8、16、24、32…128多种固定字节的内存块

• (sgi、linux下)STL中分为一级空间配置器和二级空间配置器，二级空间配置器就是内存池，最大可以切割的内存为128，超过128就使用一级空间配置器(其实就是调用malloc和free)

• 不是每个内存的大小都挂一个桶，所以会造成一定的内存浪费，比如要1-7字节分配的都是8字节

• 当给的内存比实际要的内存大的时候(不是每个内存都挂一个桶)，就会造成内存浪费，这个就叫做内碎片，外碎片是导致申请不出来空间，内碎片是空间浪费问题

• 申请固定内存块时，也不是一次只切一块下来，每次会切多块下来

• 优点：根据定长内存池改造，可以在一定程度上解决长度问题(多种固定长度)

• 缺点：

  1.多线程场景下，都在使用STL容器，在申请内存的时候需要加锁，会导致效率低

  2.大于128的内存就是malloc和free

  3.也会存在内存碎片问题(外碎片)，因为每次申请的memory大块内存会被切割分小，这些不能再组成大内存，因此当需要大块内存的时候，可能会存在内存碎片问题

4.实现一个定长内存池

注意事项：

• 自由链表中，用当前指针所指向的空间的前面几个字节，存储下一断空间的指针，由于不清楚指针类型的大小，所以采用特殊方法处理

*((int*)obj)=(int)_FreeLeft //取指针指向空间的前四个字节，存储下一个指针，但是在64位下，指针的大小是8个字节，就会出问题
    
//*((void**)obj) = _FreeList;//void**解引用出来 -> void*在32位就是4字节大小，64位就是8字节大小
1
2
3

• 当给定的类型，小于当前系统下指针的大小的时候，用其空间大小是无法存储下指针的，也需要进行特殊处理

//_memory += sizeof(T);//假如T为char，此时就会有问题，只给一个字节，释放的时候无法存储指针

static size_t GetObjSize()
	{
		if (sizeof(T) < sizeof(T*))//类型比指针小
			return sizeof(T*);

		return sizeof(T);
	}
1
2
3
4
5
6
7
8
9

• memory有可能有越界问题，因此需要记录剩余大块的内存的大小

int _LeftSize = 0;//申请的内存剩余大小，防止越界
1

• 内存池的释放：定义一个链式结构，将每次向系统申请的内存的起始地址保存起来，需要释放内存的时候，依次释放链表中保存的内存

• 实现代码：

<common.h>
#pragma once

#include <iostream>
using std::cout;
using std::cin;
using std::endl;
#include <exception>
#include <time.h>



#pragma once
#include "common.h"

template<class T>
class ObjectPool
{
private:
	size_t GetObjSize()
	{
		if (sizeof(T) < sizeof(T*))//类型比指针小
			return sizeof(T*);

		return sizeof(T);
	}

	void* &NextObj(void *obj)//从自由链表更新指针
	{
		return (*(void**)obj);//取前面8个字节的内容
	}

	struct BlockNode//存储大块内存的起始地址
	{
		BlockNode(char *memory = nullptr)
		:_memory(memory)
		,_next(nullptr)
		{}

		~BlockNode()
		{
			free (_memory);
		}

		char *_memory;
		BlockNode* _next;
	};

	void Add()//保存新开辟的大块内存
	{
		BlockNode* node = new BlockNode(_memory);
		node->_next = BlockHead->_next;
		BlockHead->_next = node;
	}

public:
	T *New()
	{
		T *obj = nullptr;


		if (_FreeList)//不为空，在自由链表中或者
		{
			obj = (T*)_FreeList;
			_FreeList = NextObj(_FreeList);//往下走一步
		}
		else
		{	
			if (_LeftSize < sizeof(T))//空间不够了
			{
				_LeftSize = 1024 * 200 * _count;
				_memory = (char*)malloc(_LeftSize);
				_count++;

				if (_memory==nullptr)//申请失败抛异常
					throw std::bad_alloc();

				//将新开辟的内存添加至保存大块内存起始地址的结构体中
				Add();
			}
			obj = (T*)_memory;

			//_memory += sizeof(T);//假如T为char，此时就会有问题，只给一个字节，释放的时候无法存储指针
			//_LeftSize -= sizeof(T);

			_memory += _ObjSize;
			_LeftSize -= _ObjSize;

		}

		new (obj)T;//定位new，初始化空间
		return obj;
	}

	void Delete(T *obj)//释放内存，将内存连接到自由链表之中
	{
		//头插 -> 用自由链表的前面的指针的前面的几个字节，存储下一个位置的指针

		//32位和64位指针的大小是不一样的，所以_FreeList 采用void*的形式
		//*((void**)obj) = _FreeList;//void**解引用出来 -> void*在32位就是4字节大小，64位就是8字节大小
		NextObj(obj) = _FreeList;//将上面的封装起来
		_FreeList = obj;//第一个点
	}

	void Destory()//释放所有内存
	{
		while (BlockHead->_next)
		{
			BlockNode *node = BlockHead->_next;
			BlockHead->_next = node->_next;
			_memory = nullptr;
			_FreeList = nullptr;
			_LeftSize = 0;
			delete node;
		}
	}

	~ObjectPool()
	{
		Destory();
	}

private:
	char *_memory = nullptr;//申请的大块内存
	void *_FreeList = nullptr;//自由链表
	int _LeftSize = 0;//申请的内存剩余大小，防止越界
	int _count = 1;//记录申请大块内存的次数
	size_t _ObjSize=GetObjSize();
	BlockNode *BlockHead = new BlockNode;
};

--------测试代码-------------
#pragma once
#include "common.h"
#include "ObjectPoll.h"

typedef struct Node
{
	struct Node *left;
	struct Node *right;
	int val;
}node;

int main()
{

	size_t t1 = clock();
	for (int i = 0; i < 10000000; i++)
	{
		node *p = (node*)malloc(sizeof(node));
	}
	size_t t2 = clock();
	cout <<"直接调用malloc使用的时间" <<t2 - t1 << endl;

	size_t t3 = clock();
	ObjectPool<node> pool;
	for (int i = 0; i < 10000000; i++)
	{
		node *p = pool.New();
	}
	
	size_t t4 = clock();
	cout <<"使用内存池的时间：" <<t4 - t3 << endl;

	getchar();
	return 0;
}

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168