项目介绍 + 定长内存池设计及实现

你好，我是安然无虞。

项目介绍

当前项目做的是什么?

这个项目是实现一个高并发的内存池, 它的原型是 Google 的一个开源项目 TCMalloc, 全称是 Thread-Caching Malloc, 即线程缓存的 malloc, 实现了高效的多线程内存管理, 用于替代系统中的内存分配函数(malloc, free).

这个项目并不是把 TCMalloc 从头到尾实现一遍, 而是把 TCMalloc 中最核心的框架简化后拿出来, 模拟实现一个我们自己的 mini 版本的高并发内存池, 目的就是学习 TCMalloc 的精华, 有点类似我们之前学习 STL 容器的方式(模拟实现, 不是为了造轮子, 而是向当时顶尖的C++前辈学习, 同时也方便我们更好的理解这部分内容).

技术栈

这个项目的技术栈主要用到了 C/C++, 数据结构(链表, 哈希桶), 单例模式, 操作系统内存管理, 互斥锁, 多线程等方面的知识.

---

内存池是什么?

池化技术

所谓的"池化技术", 指的是程序先向系统申请过量的资源, 然后自己管理, 以备不时之需. 之所以要申请过量的资源, 是因为每次申请该资源都有较大的开销, 所以我们提前申请好了, 这样使用时就会变得非常快捷, 以便提高程序的运行效率.

在计算机中, 有很多使用"池"这种技术的地方, 除了内存池, 常见的还有连接池, 线程池, 对象池等. 我们之前学习过线程池, 所以这里就以服务器上的线程池为例, 它的主要思想是: 一开始先启动若干数量的线程, 让它们处于睡眠状态, 当接受到客户端的请求时, 唤醒池中某个睡眠的线程, 让它来处理客户端的请求, 当处理完这个请求, 线程又进入睡眠状态.

内存池

内存池是指程序预先从操作系统中申请一块足够大的内存, 在此之后, 当程序中需要申请内存的时候, 不再是直接向操作系统申请, 而是直接从内存池中获取; 同理, 当程序释放内存的时候, 并不是真正将内存返回给操作系统, 而是返回给内存池. 当程序退出或在特定的时间, 内存池才将之前申请的内存真正释放.

内存池主要解决的问题

内存池主要解决的当然是效率的问题, 这是毋庸置疑的, 其次如果站在系统的内存分配器的角度, 还需要解决一下内存碎片的问题. 说到这里, 那什么是内存碎片呢?

string 对象和 list 对象销毁后, 释放空间, 所以图中还有256Bytes的空间, 但是此时我们要申请超过128Bytes的空间却申请不出来, 因为这两块空间不连续了, 即所谓的碎片化.

这里还需要补充说明的是: 内存碎片实际上分为外碎片和内碎片, 上面我们讲的是外碎片问题.

• 外碎片是一些空闲的小块内存区域，由于这些内存空间不连续，以至于合计的内存足够，但是不能满足一些内存分配申请需求。
• 内碎片是由于一些对齐的需要，导致分配出去的空间中一些内存无法被利用。

malloc

对于 malloc 函数, 我们是不陌生的, 因为在 C/C++ 中我们要动态申请内存都是通过调用 malloc 函数去申请(C++中的 new, 底层也是封装了 malloc 函数), 但是我们要知道, 实际上我们不是直接去堆上获取内存的, 我们所熟知的 malloc, 本质就是一个内存池.

用一个形象的比喻就是, malloc 函数相当于向操作系统"批发"了一块较大的内存空间, 然后"零售"给程序用. 当全部"售完"或程序有大量的内存需求时, 再根据实际需求向操作系统"进货".

malloc 的实现方式有很多种, 一般不同的编译器平台用的都是不同的. 比如常见的Windows的VS系列的编译器用的是微软自己写的一套, Linux gcc 用的是 glibc 中的 ptmalloc.

---

定长内存池

学习目的

作为 C/C++ 程序员, 我们知道申请内存使用的是 malloc, malloc 其实就是一个通用的大众货, 什么场景下都可以用, 这也就意味着它在什么场景下都不会有很高的性能, 而我们所学习的 tcmalloc 在多线程环境下比 malloc 性能高得多.

之所以先实现一个定长内存池, 是因为它在我们后面的高并发内存池中也是有价值的, 所以学习定长内存池有两个目的:

• 熟悉简单内存池是如何控制的;
• 将作为高并发内存池的一个基础组件.

定长内存池设计

所谓的定长内存池, 顾名思义就是固定大小的内存.

在讲解之前呢, 我们先解决一个问题:

如何直接向堆申请内存?

因为是内存池, 所以我们首先得向系统申请一块内存空间，然后对其进行管理。如果想直接向堆申请内存空间，在Windows下，可以调用 VirtualAlloc 函数；在Linux下，可以调用 brk 或 mmap 函数。

代码实现:

#ifdef _WIN32#include <Windows.h>
#else//...
#endif//直接去堆上按页申请空间
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32void* ptr = VirtualAlloc(0, kpage<<13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else// linux下brk mmap等
#endifif (ptr == nullptr)throw std::bad_alloc();return ptr;
}

---

如何实现定长内存池中的定长?

一开始我们可以使用非类型的模板参数, 使得在该内存池中申请到的对象的大小都是N。

template<size_t N>
class ObjectPool
{};

但是考虑到定长内存池在后面会作为高并发内存池的一个基础组件, 所以这里我们使用模板参数来实现定长. 比如创建定长内存池时传入的对象类型是int，那么该定长内存池就只支持4字节大小内存的申请和释放。

template<class T>
class ObjectPool
{};

---

如何设计定长内存池?

我们直接向堆中申请大块内存后, 需要使用一个指针对其进行管理, 由于需要对大块内存进行切分, 所以仅一个指针是不够的, 还需要一个整型变量用于标识内存块中剩余字节数.
同时为了便于对大块内存的切分操作, 该指针类型使用char*, 而不是void*, 因为指针类型决定了执行±操作向前或向后走一步的步长, 而 void* 的解引用和±操作都是没有意义的.

补充内容：指针类型的意义

• 指针类型决定了指针在解引用的时候一次能访问几个字节(也叫指针的权限)
• 指针类型决定了指针向前或向后走一步的步长(±整数)，单位是字节.

释放回来的小块内存也是需要被管理的, 那如何管理呢?可以使用一个链表对其进行管理, 定义一个指针指向这个链表的头, 我们把这个管理释放回来的小块内存的链表叫做自由链表.

对于释放回来的小块内存, 不需要专门为它们定义一个链式结构, 我们可以让小块内存的前4个字节(32位平台)或前8个字节(64位平台)存储后一个小块内存的首地址.

综上所述, 定长内存池的成员变量有:

• _memory: 指向大块内存的指针
• _leftBytes: 大块内存剩余的字节数
• _freeList: 管理还回来的内存对象的自由链表

---

内存池如何申请对象?

内存池申请对象的时候需要注意, 可以从大块内存中取, 也可以从自由链表中取, 如果自由链表有内存块对象的时候, 优先从自由链表中取, 即头删, 时间复杂度是O(1).

如果自由链表中没有内存块对象的时候, 那么我们就要在大块内存中切出定长的内存对象, 需要注意切出后及时更新 _memory 的指向和 _leftBytes 的值.

当大块内存剩余的字节数不足以存储下一个地址的值时, 则需要调用上方的 SystemAlloc 函数重新开辟大块空间.

代码实现:

// 申请空间
T* New()
{T* obj = nullptr;// 如果自由链表有对象, 直接取出一个(头删)// 优先从自由链表中取内存if (_freeList){obj = (T*)_freeList;_freeList = *((void**)_freeList);}else{// 注意:不管内存块对象有对大, 至少要存的下一个地址的值size_t objSize = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T);// 剩余内存不够开辟一个对象大小时, 则重新开辟大块内存if (_leftBytes < objSize){_leftBytes = 128 * 1024;// _memory = (char*)malloc(_leftBytes);_memory = (char*)SystemAlloc(_leftBytes >> 13);if (_memory == nullptr){throw std::bad_alloc();}}obj = (T*)_memory;_memory += objSize;_leftBytes -= objSize;}// 使用定位new调用T的构造函数初始化// 对已分配的原始内存空间中显示调用构造函数初始化new(obj)T;return obj;
}

---

内存池如何管理释放的对象?

将释放回来的内存块对象头插进自由链表, 时间复杂度是O(1)

试想我们如何保证一个指针解引用后在32位平台下能够访问4个字节, 在64位平台下能够访问8个字节? 前面我们说了, 指针类型决定了指针在解引用操作时一次能够访问几个字节. 所以只要是二级指针都能够完成上述要求.

我们将其封装成为一个函数:

void*& NextObj(void* ptr)
{return (*(void**)ptr);
}

还有一点需要注意，在释放对象的时候，我们应该显示调用该对象的析构函数清理该对象，因为该对象可能还管理着其他某些资源，如果不对其进行清理那么这些资源将无法被释放，从而导致内存泄漏。

代码实现:

// 释放对象
void Delete(T* obj)
{// 显示调用T的析构函数进行清理obj->~T();// 头插到_freeListNextObj(obj) = _freeList;_freeList = obj;
}

---

定长内存池整体代码

//定长内存池
template<class T>
class ObjectPool
{
public:T* New(){T* obj = nullptr;// 如果自由链表有对象, 直接取出一个(头删)// 优先从自由链表中取内存if (_freeList){obj = (T*)_freeList;_freeList = NextObj(_freeList);}else{// 注意:不管T对象有对大, 至少要存的下一个地址的值(4/8)size_t objSize = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T);// 剩余内存不够开辟一个对象大小时, 则重新开辟大块内存if (_leftBytes < objSize){_leftBytes = 128 * 1024;// _memory = (char*)malloc(_leftBytes);_memory = (char*)SystemAlloc(_leftBytes >> 13);if (_memory == nullptr){throw std::bad_alloc();}}obj = (T*)_memory;_memory += objSize;_leftBytes -= objSize;}// 使用定位new调用T的构造函数初始化// 对已分配的原始内存空间中显示调用构造函数初始化new(obj)T;return obj;}void*& NextObj(void* ptr){return (*(void**)ptr);}void Delete(T* obj){// 显示调用T的析构函数进行清理obj->~T();// 头插到_freeListNextObj(obj) = _freeList;_freeList = obj;}private:char* _memory = nullptr; // 指向大块内存的指针size_t _leftBytes = 0; // 大块内存剩余的字节数void* _freeList = nullptr; // 管理还回来的内存对象的自由链表(头指针)
};

---

性能测试

对比测试 malloc, free 与定长内存池:

struct TreeNode
{int _val;TreeNode* _left;TreeNode* _right;TreeNode():_val(0), _left(nullptr), _right(nullptr){}
};void TestObjectPool()
{// 申请释放的轮次const size_t Rounds = 3;// 每轮申请释放多少次const size_t N = 1000000;std::vector<TreeNode*> v1;v1.reserve(N);//malloc和freesize_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();//定长内存池ObjectPool<TreeNode> TNPool;std::vector<TreeNode*> v2;v2.reserve(N);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 cost time:" << end1 - begin1 << endl;cout << "object pool cost time:" << end2 - begin2 << endl;
}

结果如下:

我们发现使用定长内存池中的 New 和 Delete 明显比 malloc 和 free 消耗的时间少, 这是因为在申请定长的内存时, 定长内存池比 malloc 要高效, 毕竟定长内存池是为了申请定长的内存对象而专门设计的.