初探C++内存池项目 ---(一)链式栈的实现和原理详解

一.项目介绍

本项目是楼主在实验楼中学习的,这里主要分享一下学习心得和总结一些经验~

在 C/C++ 中,内存管理是一个非常棘手的问题,我们在编写一个程序的时候几乎不可避免的要遇到内存的分配逻辑,这时候随之而来的有这样一些问题:是否有足够的内存可供分配? 分配失败了怎么办? 如何管理自身的内存使用情况? 等等一系列问题。在一个高可用的软件中,如果我们仅仅单纯的向操作系统去申请内存,当出现内存不足时就退出软件,是明显不合理的。正确的思路应该是在内存不足的时,考虑如何管理并优化自身已经使用的内存,这样才能使得软件变得更加可用。本次项目我们将实现一个内存池,并使用一个栈结构来测试我们的内存池提供的分配性能。

二.内存池介绍

内存池是池化技术中的一种形式。通常我们在编写程序的时候回使用 new delete 这些关键字来向操作系统申请内存,而这样造成的后果就是每次申请内存和释放内存的时候,都需要和操作系统的系统调用打交道,从堆中分配所需的内存。如果这样的操作太过频繁,就会找成大量的内存碎片进而降低内存的分配性能,甚至出现内存分配失败的情况。
而内存池就是为了解决这个问题而产生的一种技术。从内存分配的概念上看,内存申请无非就是向内存分配方索要一个指针,当向操作系统申请内存时,操作系统需要进行复杂的内存管理调度之后,才能正确的分配出一个相应的指针。而这个分配的过程中,我们还面临着分配失败的风险。
所以,每一次进行内存分配,就会消耗一次分配内存的时间,设这个时间为 T,那么进行 n 次分配总共消耗的时间就是 nT;如果我们一开始就确定好我们可能需要多少内存,那么在最初的时候就分配好这样的一块内存区域,当我们需要内存的时候,直接从这块已经分配好的内存中使用即可,那么总共需要的分配时间仅仅只有 T。当 n 越大时,节约的时间就越多。

三.项目源码及分析

源码地址:
https://github.com/82457097/Linux/tree/master/MemoryPool

1.链式栈的实现

1#ifndef STACK_ALLOC_H 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函数测试效果

1#include<iostream> 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用法的说明

1//关于 typedef typename Alloc<T>::template rebind<Node>::other allocator 的解释 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的实现,有什么不懂得欢迎讨论,有错误或者建议也欢迎指正!
先附上最终性能比较图:次数都是100000x100
在这里插入图片描述
效果还是很明显的~

代码交流 2021