🕺作者： 主页

我的专栏
C语言从0到1
探秘C++
数据结构从0到1
探秘Linux
菜鸟刷题集

😘欢迎关注：👍点赞🙌收藏✍️留言

🏇码字不易，你的👍点赞🙌收藏❤️关注对我真的很重要，有问题可在评论区提出，感谢阅读！！！

1 项目简介

本项目的总目标是实现一个高并发的内存池，它的原型是google的一个开源项目tcmalloc，tcmalloc全称Thread-Caching Malloc，也就是线程缓存的malloc，实现了高效的多线程内存管理，用来替代系统的内存分配相关的函数(malloc、free)。而另一方面tcmalloc是全球大厂google开源的，并且Go语言直接用它做了自己内存分配器，所以这个项目是很值得学习的。

该项目用到的主要的知识储备有C/C++、数据结构（链表、哈希桶）、操作系统内存管理、单例模式、多线程、互斥锁等等方面的知识。

2 笔者的独白

这些知识在之前写的博客里面都讲了的，如果没有讲到会在接下来的学习中讲述，毕竟我也是边写边学的hhh，我之前也没有做过这个项目，所以接下来我都是以第一视角来讲述碰到的难关、知识盲区、一些心得或者是碎碎念，因为这个项目将可能是我在今年做的最后一个稍大的项目了（现在时间2023/11/15 18:24 ），所以它对我来说也是有一种特别的“感情”的hhh，本系列不以教学为目的，纯粹是我的所思所想，所以我估计会有点“乱”？如果对你有所帮助那肯定最好了。

3 一些概念

3.1 什么是池化技术

在讲多线程的博客中实现过线程池，它的意义就在于让程序向系统申请过量的的资源自己管理，这样就不用每次都向系统申请了，大大提高程序运行效率，因为每次申请都有较大的开销，如果提前申请好，这样使用就会十分快捷，怎么理解呢？就像是小时候我向我妈要零花钱，我一会儿要一次，一次5毛，我妈就会觉得我怎么老是要，还不如一次要多点，这样就不会总是烦她，我也可以有自由发挥的空间…好了，跑题了，在计算机中有很多使用“池”这种技术的地方，除了线程池，还有连接池、内存池、对象池等。以服务器上的线程池为例，它的主要思想是：先启动若干数量的线程，让它们处于睡眠状态，当接收到客户端的请求时，唤醒池中某个睡眠的线程，让它来处理客户端的请求，当处理完这个请求，线程又进入睡眠状态。

3.2 内存池

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

3.3 内存池主要解决的问题

内存池主要解决的问题是效率问题，其次从系统的内存分配器的角度还需要解决一下内存碎片的问题。

什么是内存碎片？

刚好最近学了操作系统的内存碎片问题，我还研究了一阵，这里大概讲一下：
内存碎片分为内部碎片和外部碎片
外部碎片是指内存中的空间大小足够外部申请，但是因为都是一些不连续的小碎片，导致申请不成功，就像下面这样

内部碎片就是分配出去的空间中有一些内存无法被有效利用，这通常发生在分配的内存块大于进程所需的内存大小时。以下是一个例子：假设有一个操作系统，它将内存以页（Page）为单位分配给进程。每个页的大小是8KB。现在，一个进程需要分配10KB的内存。操作系统分配了2个页面（16KB）给这个进程。由于内存以页为单位分配，而进程只使用了10KB内存，还有6KB是未被使用的，这部分未被使用的内存就是内部碎片。

3.4 malloc

在C++中我们要动态申请内存一般都是通过malloc去申请内存的，但是我们要知道，实际上我们不是直接去堆获取内存的，malloc就是一个内存池，malloc相当于向操作系统“批发”了一块较大的内存空间，然后“零售”给程序用。当全部“售完”或程序有大量的内存需求时，再根据实际需求向操作系统“进货”。malloc的实现方式有很多种，一般不同编译器平台用的都是不同的。比如windows的vs系列用的微软自己写的一套，linux gcc用的glibc中的ptmalloc。
下面是相关的文章：
Linux内存管理及malloc、free实现原理
malloc背后的实现原理–内存池
malloc的底层实现（ptmalloc）

4 定长内存池的实现

虽然我们知道申请内存用的是malloc，显然malloc是通用的，几乎什么场景都快要使用它，但是什么场景都可以用就意味着它在什么场景下都不会有很高的性能，那么就可以自己实现一个简单的malloc热热手，它和真的malloc的区别在于我实现的是定长的，也就是说向我写的内存池里申请空间时，只能申请一个**固定空间大小的内存，**比如说只能申请1byte或2byte等等，也就是说它只能应用于一种场景，不能同时应用于多种场景。

4.1 设计思路

定长内存池首先是一个内存池，那么就需要向系统申请一批空间保存在池子中，所以需要一个指针记录池子的起始地址，还要一个变量记录长度，还有就是向定长内存池申请的空间还回来的时候不能直接还给操作系统，而是把它们单独保存起来，这样做的好处有：

1. 减少内存分配的开销：内存分配和释放都需要一定的开销，特别是在多线程环境下，操作系统的内存分配器可能会面临锁竞争等问题，这会导致性能下降。通过将空闲的内存块保存在内存池中，可以减少频繁地与操作系统进行内存分配和释放的次数，从而提高性能。
2. 避免内存碎片化：频繁地向操作系统申请和释放小块内存会导致内存出现碎片化，即大量不连续的小块空闲内存无法被充分利用。通过内存池管理机制，可以在一定程度上避免内存碎片化问题，因为内存池可以根据需求自行管理内存块的分配和释放。
3. 更好地控制内存使用：内存池可以根据具体的应用场景进行优化，比如预先分配一定数量的内存块，并在需要时直接从内存池中获取，而不是每次都向操作系统请求内存。这样可以更好地控制内存的使用情况，避免出现意外的内存耗尽或内存泄漏问题。

那还回来的空间怎么保存呢？

使用链表，让链表的前几个字节记录下一个申请空间的地址即可
每次申请空间都优先在这个链表中查看是否有空间，没有再去内存池中查看是否有空间，都没有就会让内存池向堆申请空间，这样就可以减少申请空间的次数，减少开销。

4.2 代码实现

在写剩下代码前要思考一个问题 在不同的系统下申请空间的方式是不同的
下面是相关的博客介绍：
windows: VirtualAlloc
linux: brk和mmap

---

我们需要申请多大的空间作为内存池呢？有没有要求？

有的，在操作系统中，内存是以页为单位进行管理的。每个页的大小是固定的，通常为4KB或者8KB。当我们向操作系统申请内存时，操作系统会按照页的大小来进行分配。
如果申请的内存大小不是页大小的整数倍，操作系统可能会分配多个完整的页来满足需求，并浪费一部分内存空间。为了最大程度地利用内存并减少浪费，我们应该确保所申请的内存大小是页大小的整数倍。这里以申请128KB为例。

---

假设内存池的大小是128KB，代码应该怎么写（在windows环境下测试）

#ifdef _WIN32
	//宏定义_WIN32通常用于Windows平台的C和C++编程中，
	//它是一个预处理器宏，用于判断当前代码是否在Windows环境下编译
	#include<windows.h>
#else

#endif

// 直接去堆上按页申请空间
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;
}

上述代码中，当在Windows平台下编译时，_WIN32这个宏通常由编译器自动定义，无需手动设置，从而执行#ifdef _WIN32下的代码块。而在其他平台下编译时，将执行#else下的代码块，实现了跨平台兼容性。需要注意的是，Windows平台的64位版本上编译时，通常会定义_WIN64，同时也定义了_WIN32。在Windows平台的64位版本上编译时，只有_WIN32被定义。

---

需要哪些变量？

在知道怎么申请空间和设计思路以后就开始写主体代码了
之前设计思路的时候讲过需要三个变量：指向内存池的指针、长度、指向自由链表的指针。

char* _memory = nullptr; //内存池指针
size_t _remainBytes = 0;  //内存块剩余空间大小
void* _firstList = nullptr; //自由链表，用来回收空间

---

如何实现定长？

1. 使用非类型模板参数，使得在该内存池中申请到的对象大小是固定的N
2. 使用模板参数，让它可以根据申请对象的的类型改变大小

综合考虑，选择使用类模板，满足多种场景（int、double、自定义…

template <class T>
class FLMemoryPool
{
public:
	T* New()
	{}

	void Delete(T* obj)
	{}
private:
	char* _memory = nullptr; //内存池指针
	size_t _remainBytes = 0;  //内存块剩余空间大小
	void* _firstList = nullptr; //自由链表，用来回收空间

};

---

内存池怎么管理释放的对象？

在自由链表中，因为自己存了下一块空闲空间的地址，那就可以用当前空间的前几个字节(指针大小在32位平台4位，64位平台8位)存储下一空间的地址即可，这样想要找到下一个空间就只需要解引用自身即可，怎么说呢，就是不同类型的指针解引用会访问不同大小的空间，而且在不同的机器下同样类型的指针的大小也不同，那具体选用哪个类型的呢？这是个问题 ，想想发现我们的本质需求是想解引用一个指针的大小，而指针指向数据的类型，决定了指针解引用后能向后访问的空间大小，因此我们这里需要的是一个指向指针的指针，这里使用二级指针就行了。
当我们需要访问一个内存块的前4/8个字节时，我们就可以先该内存块的地址先强转为二级指针，由于二级指针存储的是一级指针的地址，二级指针解引用能向后访问一个指针的大小，因此在32位平台下访问的就是4个字节，在64位平台下访问的就是8个字节，此时我们访问到了该内存块的前4/8个字节。
对于还回来的定长内存块，我们将它像上面所说的用链表串起来，只要让该内存块的前4或8个字节存储第一个内存块的地址，然后再让_freeList指向该内存块即可，这也是所谓的“头插”。

void Delete(T* obj)
{
	obj->~T();
    /*
    obj->~T();用于显式地调用类型T的析构函数来销毁对象。
    它会执行对象的清理逻辑，包括释放资源、删除关联对象等等。
    通过这个调用，我们确保对象的析构函数被正确地执行，以避免内存泄漏或其他资源相关的问题。
	需要注意的是，手动调用析构函数后，对象的内存仍然是有效的，
    但对象已经被销毁。所以在这段代码中，析构函数调用后并没有释放内存，
    而是将该内存块添加到自由链表（_freeList）中，以便在以后的对象分配中可以重复使用该内存块。
    */
    *(void**)obj = _freeList;
    _freeList = obj;
}

---

怎么向内存池申请空间？

申请对象的时候，内存池应该优先把还回来的内存池对象再次重复利用，因此如果自由链表当中有内存块的话就直接从自由链表“头删”一个内存块返回即可。

如果自由链表中没有内存块，那么就在原来那大块内存中取出定长的内存块进行返回，当内存块切出后要及时更新_memory指针的指向，以及剩余空间_remainByte的值。

还要注意一点，之前说内存块的前几个字节要存一个内存块的地址，所以要保证每次申请的空间至少能够存下一个地址，所以当需要的空间小于存下一个地址所需要的空间时，就要以后者大小为准进行空间申请。
最后，当一开始申请的大块内存大小已经不足一个对象时，我们就应该使用封装的SystemAlloc函数，再次向堆申请一块内存空间，在上面这些操作中都需要及时更新_memory指针和_remainBytes值的更新。

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

		// 优先把还回来内存块对象，再次重复利用
		if (_freeList)
		{
			void* next = *((void**)_freeList);
			obj = (T*)_freeList;
			_freeList = next;
		}
		else
		{
			// 剩余内存不够一个对象大小时，则重新开大块空间
			if (_remainBytes < sizeof(T))
			{
				_remainBytes = 128 * 1024;
				_memory = (char*)SystemAlloc(_remainBytes >> 13);
				if (_memory == nullptr)
				{
					throw std::bad_alloc();
				}
			}

			obj = (T*)_memory;
			size_t objSize = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T);
			_memory += objSize;
			_remainBytes -= objSize;
		}

		// 定位new，显示调用T的构造函数初始化
		new(obj)T;

		return obj;
	}

需要注意的是，与释放对象时需要显示调用该对象的析构函数一样，当内存块切分出来后，我们也应该使用定位new，显示调用该对象的构造函数对其进行初始化。

---

new(obj)T;的含义？

new(obj)T;是C++中的定位new表达式，它的作用是在指定的内存地址上调用类型T的构造函数，以便创建一个对象。
普通的new T表达式会分配一块内存，并在这块内存上调用T类的构造函数来创建对象。而定位new表达式允许我们在已经分配好的内存地址上调用构造函数，这样就可以在特定的内存区域上创建对象，而不是在默认的堆内存上分配。

---

定长内存池的整体代码如下：

#pragma once
#include <iostream>
#include <vector>
#include <time.h>
using std::cout;
using std::endl;

#ifdef _WIN32
	#include<windows.h>
#else

#endif

// 直接去堆上按页申请空间
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;
}

template <class T>
class FLMemoryPool
{
public:
	T* New()
	{
		T* obj = nullptr;

		// 优先把还回来内存块对象，再次重复利用
		if (_freeList)
		{
			void* next = *((void**)_freeList);
			obj = (T*)_freeList;
			_freeList = next;
		}
		else
		{
			// 剩余内存不够一个对象大小时，则重新开大块空间
			if (_remainBytes < sizeof(T))
			{
				_remainBytes = 128 * 1024;
				_memory = (char*)SystemAlloc(_remainBytes >> 13);
				if (_memory == nullptr)
				{
					throw std::bad_alloc();
				}
			}

			obj = (T*)_memory;
			size_t objSize = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T);
			_memory += objSize;
			_remainBytes -= objSize;
		}

		// 定位new，显示调用T的构造函数初始化
		new(obj)T;

		return obj;
	}

	void Delete(T* obj)
	{
		obj->~T();
		*(void**)obj = _freeList;
		_freeList = obj;
	}
private:
	char* _memory = nullptr; //内存池指针
	size_t _remainBytes = 0;  //内存块剩余空间大小
	void* _freeList = nullptr; //自由链表，用来回收空间

};

---

性能对比

怎么测试它们的性能呢？
可以让使用new向它申请若干个TreeNode对象，然后再使用delete将这些对象释放，通过clock函数得到整个过程所消耗的时间。
然后再重复该过程，只不过将其中的new和delete替换为定长内存池当中的New和Delete，此时再通过clock函数得到该过程消耗的时间。

struct TreeNode
{
	int _val;
	TreeNode* _left;
	TreeNode* _right;
	TreeNode()
		:_val(0)
		, _left(nullptr)
		, _right(nullptr)
	{}
};

void TestFLMemoryPool()
{
	// 申请释放的轮次
	const size_t Rounds = 3;
	// 每轮申请释放多少次
	const size_t N = 1000000;
	std::vector<TreeNode*> v1;
	v1.reserve(N);

	//malloc和free
	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();

	//定长内存池
	FLMemoryPool<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 << "FLMemoryPool cost time:" << end2 - begin2 << endl;
}

结果如下，可以看到这个过程中，定长内存池消耗的时间比malloc/free少。这就是因为malloc是一个通用的内存池，而定长内存池是专门针对申请定长对象而设计的，所以这种场景下定长内存池的效率更高。

后记

最近好多考试…可能做的比较慢，加油吧