【项目设计】高并发内存池(一)[项目介绍｜内存池介绍｜定长内存池的实现]

柔光的暖阳◎ 2024-04-20 06:45 7阅读 0赞

> **🎇C++学习历程：入门**
> 
> --------------------
> 
>  *  **博客主页：**[一起去看日落吗][Link 1]
>  *  **持续分享博主的C++学习历程**
>  *  **`博主的能力有限，出现错误希望大家不吝赐教`**
>  *  **分享给大家一句我很喜欢的话：** 也许你现在做的事情，暂时看不到成果，但不要忘记，树🌿成长之前也要扎根，也要在漫长的时光🌞中沉淀养分。静下来想一想，哪有这么多的天赋异禀，那些让你羡慕的优秀的人也都曾默默地翻山越岭🐾。
> 
> --------------------
> 
> ![在这里插入图片描述][eabca17da9704379a5f15832a495b4cc.jpeg_pic_center]

💐 🌸 🌷 🍀

--------------------

#### 目录 ####

*  💐1. 项目介绍
 *  💐2. 内存池介绍
 *  💐3. 定长内存池的实现
 *  💐4. 定长内存池代码
 *  💐5. 性能测试

## 💐1. 项目介绍 ##

*  本项目实现的是一个高并发的内存池，它的原型是Google的一个开源项目tcmalloc，tcmalloc全称Thread-Caching Malloc，即线程缓存的malloc，实现了高效的多线程内存管理，用于替换系统的内存分配相关函数malloc和free。
 *  tcmalloc的知名度也是非常高的，不少公司都在用它，比如Go语言就直接用它做了自己的内存分配器。
 *  该项目就是把tcmalloc中最核心的框架简化后拿出来，模拟实现出一个mini版的高并发内存池，目的就是学习tcmalloc的精华。
 *  该项目主要涉及C/C++、数据结构（链表、哈希桶）、操作系统内存管理、单例模式、多线程、互斥锁等方面的技术。

![在这里插入图片描述][1df9bf0aa4c0455c85d33c5beb920241.png]

--------------------

## 💐2. 内存池介绍 ##

*  池化技术

在说内存池之前，我们得先了解一下“池化技术”。所谓“池化技术”，就是程序先向系统申请过量的资源，然后自己进行管理，以备不时之需。

之所以要申请过量的资源，是因为申请和释放资源都有较大的开销，不如提前申请一些资源放入“池”中，当需要资源时直接从“池”中获取，不需要时就将该资源重新放回“池”中即可。这样使用时就会变得非常快捷，可以大大提高程序的运行效率。

在计算机中，有很多使用“池”这种技术的地方，除了内存池之外，还有连接池、线程池、对象池等。以服务器上的线程池为例，它的主要思想就是：先启动若干数量的线程，让它们处于睡眠状态，当接收到客户端的请求时，唤醒池中某个睡眠的线程，让它来处理客户端的请求，当处理完这个请求后，线程又进入睡眠状态。

--------------------

*  内存池

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

--------------------

*  内存池主要解决的问题

内存池主要解决的就是效率的问题，它能够避免让程序频繁的向系统申请和释放内存。其次，内存池作为系统的内存分配器，还需要尝试解决内存碎片的问题。

内存碎片分为内部碎片和外部碎片：

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

![在这里插入图片描述][9700f89454954fbe95c0cdee541a4dac.png]

**注意： 内存池尝试解决的是外部碎片的问题，同时也尽可能的减少内部碎片的产生。**

--------------------

*  malloc

C/C++中我们要动态申请内存并不是直接去堆申请的，而是通过malloc函数去申请的，包括C++中的new实际上也是封装了malloc函数的。

我们申请内存块时是先调用malloc，malloc再去向操作系统申请内存。malloc实际就是一个内存池，malloc相当于向操作系统“批发”了一块较大的内存空间，然后“零售”给程序用，当全部“售完”或程序有大量的内存需求时，再根据实际需求向操作系统“进货”。

![在这里插入图片描述][4c301eadfaa34831bcc2635540b518e4.png]  
malloc的实现方式有很多种，一般不同编译器平台用的都是不同的。比如Windows的VS系列中的malloc就是微软自行实现的，而Linux下的gcc用的是glibc中的ptmalloc。

--------------------

## 💐3. 定长内存池的实现 ##

malloc其实就是一个通用的内存池，在什么场景下都可以使用，但这也意味着malloc在什么场景下都不会有很高的性能，因为malloc并不是针对某种场景专门设计的。

定长内存池就是针对固定大小内存块的申请和释放的内存池，由于定长内存池只需要支持固定大小内存块的申请和释放，因此我们可以将其性能做到极致，并且在实现定长内存池时不需要考虑内存碎片等问题，因为我们申请/释放的都是固定大小的内存块。

我们可以通过实现定长内存池来熟悉一下对简单内存池的控制，其次，这个定长内存池后面会作为高并发内存池的一个基础组件。

![在这里插入图片描述][443d3dc3beb344de96d36efbe3381791.png]

--------------------

*  如何实现定长？

在实现定长内存池时要做到“定长”有很多种方法，比如我们可以使用非类型模板参数，使得在该内存池中申请到的对象的大小都是N。

template<size_t N>
    class ObjectPool
    {
        };

此外，定长内存池也叫做对象池，在创建对象池时，对象池可以根据传入的对象类型的大小来实现“定长”，因此我们可以通过使用模板参数来实现“定长”，比如创建定长内存池时传入的对象类型是int，那么该内存池就只支持4字节大小内存的申请和释放。

template<class T>
    class ObjectPool
    {
        };

*  如何直接向堆申请空间？

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

#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;
    }

这里我们可以通过条件编译将对应平台下向堆申请内存的函数进行封装，此后我们就不必再关心当前所在平台，当我们需要直接向堆申请内存时直接调用我们封装后的SystemAlloc函数即

*  定长内存池中应该包含哪些成员变量？

对于向堆申请到的大块内存，我们可以用一个指针来对其进行管理，但仅用一个指针肯定是不够的，我们还需要用一个变量来记录这块内存的长度。

由于此后我们需要将这块内存进行切分，为了方便切分操作，指向这块内存的指针最好是字符指针，因为指针的类型决定了指针向前或向后走一步有多大距离，对于字符指针来说，当我们需要向后移动n个字节时，直接对字符指针进行加n操作即可。

![在这里插入图片描述][b53b1f30262d400aa3b8d9ed99180f6f.png]  
其次，释放回来的定长内存块也需要被管理，我们可以将这些释放回来的定长内存块链接成一个链表，这里我们将管理释放回来的内存块的链表叫做自由链表，为了能找到这个自由链表，我们还需要一个指向自由链表的指针。

![在这里插入图片描述][fb7c8f491f134102b0c52ad75a52fd3e.png]

因此，定长内存池当中包含三个成员变量：

*  \_memory：指向大块内存的指针。
 *  \_remainBytes：大块内存切分过程中剩余字节数。
 *  \_freeList：还回来过程中链接的自由链表的头指针。
 *  内存池如何管理释放的对象？

对于还回来的定长内存块，我们可以用自由链表将其链接起来，但我们并不需要为其专门定义链式结构，我们可以让内存块的前4个字节（32位平台）或8个字节（64位平台）作为指针，存储后面内存块的起始地址即可。

因此在向自由链表插入被释放的内存块时，先让该内存块的前4个字节或8个字节存储自由链表中第一个内存块的地址，然后再让\_freeList指向该内存块即可，也就是一个简单的链表头插操作。

![在这里插入图片描述][7f53ec945792445b89f6128a02735259.png]

**如何让一个指针在32位平台下解引用后能向后访问4个字节，在64位平台下解引用后能向后访问8个字节？**

首先我们得知道，32位平台下指针的大小是4个字节，64位平台下指针的大小是8个字节。而指针指向数据的类型，决定了指针解引用后能向后访问的空间大小，因此我们这里需要的是一个指向指针的指针，这里使用二级指针就行了。

当我们需要访问一个内存块的前4/8个字节时，我们就可以先该内存块的地址先强转为二级指针，由于二级指针存储的是一级指针的地址，二级指针解引用能向后访问一个指针的大小，因此在32位平台下访问的就是4个字节，在64位平台下访问的就是8个字节，此时我们访问到了该内存块的前4/8个字节。

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

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

//释放对象
    void Delete(T* obj)
    {
        
    	//显示调用T的析构函数清理对象
    	obj->~T();
    
    	//将释放的对象头插到自由链表
    	NextObj(obj) = _freeList;
    	_freeList = obj;
    }

*  内存池如何为我们申请对象？

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

![在这里插入图片描述][14b3f81241a049dc9823a0e26e96ced6.png]  
如果自由链表当中没有内存块，那么我们就在大块内存中切出定长的内存块进行返回，当内存块切出后及时更新\_memory指针的指向，以及\_remainBytes的值即可。

![在这里插入图片描述][ed4726a23b8343caaa10de774b398f76.png]

需要特别注意的是，由于当内存块释放时我们需要将内存块链接到自由链表当中，因此我们必须保证切出来的对象至少能够存储得下一个地址，所以当对象的大小小于当前所在平台指针的大小时，需要按指针的大小进行内存块的切分。

此外，当大块内存已经不足以切分出一个对象时，我们就应该调用我们封装的SystemAlloc函数，再次向堆申请一块内存空间，此时也要注意及时更新\_memory指针的指向，以及\_remainBytes的值。

//申请对象
    T* New()
    {
        
    	T* obj = nullptr;
    
    	//优先把还回来的内存块对象，再次重复利用
    	if (_freeList != nullptr)
    	{
        
    		//从自由链表头删一个对象
    		obj = (T*)_freeList;
    		_freeList = NextObj(_freeList);
    	}
    	else
    	{
        
    		//保证对象能够存储得下地址
    		size_t objSize = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T);
    		//剩余内存不够一个对象大小时，则重新开大块空间
    		if (_remainBytes < objSize)
    		{
        
    			_remainBytes = 128 * 1024;
    			_memory = (char*)SystemAlloc(_remainBytes >> 13);
    			if (_memory == nullptr)
    			{
        
    				throw std::bad_alloc();
    			}
    		}
    		//从大块内存中切出objSize字节的内存
    		obj = (T*)_memory;
    		_memory += objSize;
    		_remainBytes -= objSize;
    	}
    	//定位new，显示调用T的构造函数初始化
    	new(obj)T;
    
    	return obj;
    }

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

--------------------

## 💐4. 定长内存池代码 ##

//
    //  ObjectPool.hpp
    //  ObjectPool
    //
    //  Created by 卜绎皓 on 2023/1/28.
    //
    
    #include <iostream>
    #include <vector>
    #include <time.h>
    using std::cout;
    using std::endl;
    
    //定长内存池
    template<class T>
    class ObjectPool
    {
        
    public:
        //申请对象
        T* New()
        {
        
            T* obj = nullptr;
    
            //优先把还回来的内存对象重复利用
            if(_freeList != nullptr)
            {
        
                //从自由链表删除一个对象
                void* next = *((void**)_freeList);
                obj = (T*)_freeList;
                _freeList = next;
            }
            else
            {
        
                //保证对象能够储存下地址
                size_t objSize = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T);
                //剩余内存不够一个对象大小时，则重新开大空间
                if(_remainBytes < objSize)
                {
        
                    _remainBytes = 128 * 1024;
                    _memory = (char*)malloc(_remainBytes);
                    if(_memory == nullptr)
                        throw std::bad_alloc();
                }
                //从大块内存中切除objSize字节的内容
                obj  = (T*)_memory;
                _memory += objSize;
                _remainBytes -= objSize;
            }
            //定位new，显示调用T的构造函数初始化
            new(obj) T;
            
            return obj;
    
        }
    
        //释放对象
        void Delete(T* obj)
        {
        
            //显示调用T的析构函数清理对象
            obj->~T();
            
    
            //将释放的对象头插到自由链表
            *(void**)obj = _freeList;
            _freeList = obj;
        }
        
    
    
    
    private:
        char* _memory = nullptr; // 指向大块内存的指针
        size_t _remainBytes = 0; // 大块内存切分剩余的字节数
        void* _freeList = nullptr; // 还回来过程中链接的自由链表的头指针
    };

--------------------

## 💐5. 性能测试 ##

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和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();
    
    	//定长内存池
    	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申请若干个TreeNode对象，然后再用delete将这些对象再释放，通过clock函数得到整个过程消耗的时间。（new和delete底层就是封装的malloc和free）

然后再重复该过程，只不过将其中的new和delete替换为定长内存池当中的New和Delete，此时再通过clock函数得到该过程消耗的时间。

![在这里插入图片描述][082dab52de4a46318aaf6171d621ac38.png]  
可以看到在这个过程中，定长内存池消耗的时间比malloc/free消耗的时间要短。这就是因为malloc是一个通用的内存池，而定长内存池是专门针对申请定长对象而设计的，因此在这种特殊场景下定长内存池的效率更高，正所谓“尺有所短，寸有所长”。

--------------------

[Link 1]: https://blog.csdn.net/m0_60338933?type=blog
[eabca17da9704379a5f15832a495b4cc.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/779423d4c59a4a5092cff4a6fb050933.jpeg
[1df9bf0aa4c0455c85d33c5beb920241.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/a64ab488239644719cd8d2fbd2f03f83.png
[9700f89454954fbe95c0cdee541a4dac.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/2afb0a106cdd4e79906886d772d91128.png
[4c301eadfaa34831bcc2635540b518e4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/2c55d6eee7054e71972078f324a4dbe5.png
[443d3dc3beb344de96d36efbe3381791.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/72e06e0864844293961d07ef693683ff.png
[b53b1f30262d400aa3b8d9ed99180f6f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/d7f7ad23ed7c4804a1ec2e8f62b9ca62.png
[fb7c8f491f134102b0c52ad75a52fd3e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/adcdff4eb2484669b1cfe5de458b6015.png
[7f53ec945792445b89f6128a02735259.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/88f95f98a2084f258d867a0007d8eefc.png
[14b3f81241a049dc9823a0e26e96ced6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/5036882327004f63ba90524076dd396a.png
[ed4726a23b8343caaa10de774b398f76.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/6c64e8e002304264855bd8f85a2ccd47.png
[082dab52de4a46318aaf6171d621ac38.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/4ef0b9e70eae45e0a7f8a227c407392e.png