一.项目介绍
本项目是楼主在实验楼中学习的，这里主要分享一下学习心得和总结一些经验~
在 C/C++ 中，内存管理是一个非常棘手的问题，我们在编写一个程序的时候几乎不可避免的要遇到内存的分配逻辑，这时候随之而来的有这样一些问题：是否有足够的内存可供分配? 分配失败了怎么办? 如何管理自身的内存使用情况? 等等一系列问题。在一个高可用的软件中，如果我们仅仅单纯的向操作系统去申请内存，当出现内存不足时就退出软件，是明显不合理的。正确的思路应该是在内存不足的时，考虑如何管理并优化自身已经使用的内存，这样才能使得软件变得更加可用。本次项目我们将实现一个内存池，并使用一个栈结构来测试我们的内存池提供的分配性能。
二.内存池介绍
内存池是池化技术中的一种形式。通常我们在编写程序的时候回使用 new delete 这些关键字来向操作系统申请内存，而这样造成的后果就是每次申请内存和释放内存的时候，都需要和操作系统的系统调用打交道，从堆中分配所需的内存。如果这样的操作太过频繁，就会找成大量的内存碎片进而降低内存的分配性能，甚至出现内存分配失败的情况。
而内存池就是为了解决这个问题而产生的一种技术。从内存分配的概念上看，内存申请无非就是向内存分配方索要一个指针，当向操作系统申请内存时，操作系统需要进行复杂的内存管理调度之后，才能正确的分配出一个相应的指针。而这个分配的过程中，我们还面临着分配失败的风险。
所以，每一次进行内存分配，就会消耗一次分配内存的时间，设这个时间为 T，那么进行 n 次分配总共消耗的时间就是 nT；如果我们一开始就确定好我们可能需要多少内存，那么在最初的时候就分配好这样的一块内存区域，当我们需要内存的时候，直接从这块已经分配好的内存中使用即可，那么总共需要的分配时间仅仅只有 T。当 n 越大时，节约的时间就越多。
三.项目源码及分析
源码地址：
https://github.com/82457097/Linux/tree/master/MemoryPool
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
2#define STACK_ALLOC_H
3
4#include<memery> //std::allocator函数需要的头文件
5
6template<typename T>
7struct StackNode { //创建模板化链表
8 T data;
9 StackNode* next;
10};
11
12template<typename T, typename Alloc = std::allocator<T>>
13class StackAlloc { //链式栈的模板类，主要实现栈的一些基本功能，push、pop、top、还有判空empty、销毁clear等等~
14public:
15 //取别名，方便书写。
16 typedef StackNode Node;
17 typedef typename Alloc::template rebind<Node>::other allocator;//这里下面会做详细解释
18
19 //构造函数,将链表的头结点初始化一下就好了
20 StackAlloc() { m_head = nullptr; }
21 //析构函数，直接调用Clear()销毁销毁所有内存
22 ~StackAlloc() { Clear(); }
23 //入栈函数Push()
24 void Push(T element) {
25 //先调用allocate和construct创建一个新的节点，建议先去看一下std::allocator的成员函数说明
26 Node* curr = m_allocator.allocate(1);
27 m_allocator.construct(curr, Node());
28 //然后直接头插法将新建的节点插入链表
29 curr->data = element;
30 curr->next = m_head;
31 m_head = curr;
32 }
33 //弹栈Pop()
34 T Pop() {
35 //思路就是将节点的数据弹出，然后销毁节点。
36 T result = m_head->data;
37 //创建一个临时节点保存m_head->next
38 Node* ptemp = m_head->next;
39 //销毁头指针所指节点
40 m_allocator.destroy(m_head);
41 m_allocator.deallocate(m_head, 1);
42 m_head = ptemp;
43
44 return result;
45 }
46 //清空链式栈Clear()
47 void Clear() {
48 //循环判空销毁节点，直至每个节点都被销毁，内存被释放
49 Node* curr = m_head;
50 //从头结点开始判断
51 while(curr != nullptr) {
52 //新建一个Node来存放curr->next
53 Node* ptemp = curr->next;
54 //不为空则销毁此节点
55 m_allocator.destroy(curr);
56 m_allocator.deallocate(curr, 1);
57 curr = ptemp;
58 }
59 m_head = nullptr;
60 }
61 //判断栈是否为空的函数Empty()
62 bool Empty() { return (m_head == nullptr); }
63 //取栈顶元素Top()
64 T Top() { return m_head->data; }
65
66private:
67 Node* m_head;
68 allocator m_allocator;
69};
70
71#endif
72
73
2.main函数测试效果
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
2#include<ctime>
3#include<cassert>
4#include"StackAlloc.h"
5
6#define ELEMS 100000 //这里是分配的个数 可以自己随便改
7#define REPS 100 //重复分配次数
8
9using namespace std;
10
11int main() {
12 clock_t start; //clock()不清楚的去看一下clock()怎么用
13 start = clock();
14 StackAlloc<int, allocator<int>> stackDefault;
15 for(int i = 0; i < REPS; ++i) { //测试push和pop 100000x100 次所耗的时间
16 assert(stackDefault.Empty()); //断言stackDefault未分配前是空的
17 for(int j = 0; j < ELEMS; ++j)
18 stackDefault.Push(j);
19 for(int j = 0; j < ELEMS; ++j)
20 stackDefault.Pop(j);
21 }
22 cout << "Default Alloc Time: ";
23 cout << (((double)clock() - start) / CLOCKS_PER_SEC) << endl; //算出实际花费的时间
24
25 return 0;
26}
27
28
以上代码完全是手打的，不确保没有小错误，这里只做思路的解释，项目源码连接已经放在上面了~
3.关于typedef typename Alloc::template rebind::other allocator用法的说明
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
2
3//我们用 typedef 给一个东西取了别名叫 allocator
4//这个东西是
5
6 typename Alloc::template rebind<Node>::other
7
8//它其实是为了解决编译器不认识的代码的问题而出现的写法
9//首先我们定义了 Alloc = std::allocator<T>，而 rebind 其实是 std::allocator 的一个成员。
10//巧就巧在，rebind 本身又是另一个模板， C++ 称其为 dependent name。完整的形式本来应该是：
11
12 std::allocator<T>::rebind<Node>::other
13
14//但是模板的相关解析已经在 <T> 出现过了，后面的 <Node> 中的 < 只能被解释为小于符号，这会导致编译出错。
15//为了表示 dependent name 是一个模板，就必须使用 template 前缀。
16//如果没有 template 前缀，< 会被编译器解释为小于符号。所以，我们必须写成下面的形式：
17
18 std::allocator<T>::template rebind<Node>::other
19
20//最后，编译器在其实根本没有任何办法来区分 other 究竟是一个类型，还是一个成员。
21//但我们其实知道 other 是一个类型（见这里），所以使用 typename 来明确指出这是一个类型，最终才有了：
22
23 typename std::allocator<T>::template rebind<Node>::other
24
25//rebind的作用是，对于给定的类型T的分配器（typename Alloc = std::allocator<T>），
26//想根据相同的策略得到另一个类型U的分配器（这里得到了std::allocator<StackNode_<T>>）。
27 template<typename U>
28 struct rebind {
29 typedef allocator other;
30 };
31
32
四.小结
这一篇主要解释了链式栈的作用及其原理，我们这里所测试的是系统的内存分配函数std::allocator的性能，下一篇我们将会实现自己的MemoryPool，与其进行性能上的比较，小伙伴们可以先自己研究MemoryPool的实现，有什么不懂得欢迎讨论，有错误或者建议也欢迎指正！
先附上最终性能比较图：次数都是100000×100
效果还是很明显的~
