【项目日记(二)】定长内存池实现

【项目日记(二)】定长内存池实现

引用

CSDN

1.

https://blog.csdn.net/m0_75256358/article/details/145501506

前言

我们知道在C/C++下申请内存一般是使用malloc，即什么场景下都可以用它。这就注定了他在一些特殊场景下性能就不会很高，本期我们就专门来设计一个特定场景下的定长内存池。实现它的目的有两个：1、熟悉一下简单内存池是如何控制的 2、定长内存池也是后面的一个子组件
目录
前言
一、定长内存池的框架搭建
1.1 如何实现定长？
1.2 定长内存池的成员有哪些？
1.3 什么是自由链表？
二、定长内存池 New 具体实现
三、定长内存池 Delete 实现
四、性能测试
五、细节优化

一、定长内存池的框架搭建

1.1 如何实现定长？

实现 内存池的定长有很多的方式，比如：我可以使用 非类型模板参数，是的在该内存池中申请的内存对象的大小都是固定的N

template<size_t N>
class ObjectPool
{};

此外，内存池又称对象池。我们也可以根创建对象池 的类型实现 定长，即使用模板参数控制

template<class T>
class ObjectPool
{};

1.2 定长内存池的成员有哪些？

定长内存池中的成员有三个：1、_memory 2、_remainSize 3、_freelist

• _memory: 管理向堆申请的大块内存的指针
• _remainSize: 记录大块内存的剩余量的变量
• _freelist: 管理还回来的内存对象的自由链表

至于成员方法也很简单：申请定长的内存对象（New） 和 释放内存对象 (Delete)
所以定长内存池的大致框架如下：

template<class T>
class ObjectPool
{
public:
    // 申请定长内存对象
    T* New()
    {
        // ....
    }
    // 释放内存对象
    void Delete(T* obj)
    {
        // ....
    }
private:
    char* _memory = nullptr;   // 指向大块内存块的指针
    size_t _remainSize = 0;    // 大块内存的剩余量
    void* _freelist = nullptr; // 管理还回来的内存对象的自由链表
};

这里直接使用C++11的在声明时给一个初始值，就不用专门写构造了！
为什么要将_memory的类型是char而不是其他？
其实原因很简单，因为我们内存池有可能申请1字节等小块的内存对象，而char就占 1个字节，刚合适。另外，char在申请玩一个内存对象后，_memory在进行向后移动时 指针的加也是好计算的。关于第二点后面介绍申请的时候详谈

1.3 什么是自由链表？

上面介绍成员的时候说了 还回来的内存对象是由自由链表统一管理的。
什么是自由链表？
因为还回来的对象本身就是一块定长的内存，所以我们管理它不再需要去专门的创建链式结构存储了。而是直接使用他们头部的4/8字节（32/64位）来存储下一个内存对象的地址，这样的结构称为自由链表
自由链表具体是如何做管理的？
上面说了，自由链表 是将还回来的内存对象的前4/8个字节进行存储下一个内存对象的地址。
现在有个问题：
不同平台下 如何拿到一个内存对象头部的4/8字节？
做法也有两种：1.计算指针 2、使用二级指针
首先第一种方式 ：计算指针的大小判定平台这个应该很好理解

if (sizeof(int*) == 4)// 32 位
{
    (int*)obj;
    // ....
}
else // 64 位
{
    (long long*)obj;
    // ....
}

第二种方式就是使用二级指针：具体做法就是将 对象的指针强转为 二级指针，然后对二级指针解引用即可。原因也很简单：二级指针存储的是一级指针的地址，当解引用后就是一级指针，此时32位平台下就是 4 字节, 64位平台下就是 8字节

*(void**)obj；// 此时就拿到了 对象的 头部的 4/8 个字节  

OK基本框架就介绍到这里，下面来实现一下 申请 和 释放

二、定长内存池 New 具体实现

申请一个对象思路分为三步：
第一，优先使用已经还回来的自由链表中的内存对象。
第二，自由链表中没有时，取向大块内存申请，如果有分割。没有先大块内存申请，在分割！
最后，调用T对应的构造函数初始化，即使用定位new

• 定位new（Placement new）是一个特殊的内存分配方式，它允许开发者在已经分配好的内存上构造对象。
• 定位new的语法格式有两种：
  1. new (place_address) type
  2. new (place_address) type(initializer-list)
• 定位new常用于以下场景：
  1. 内存池：内存池是一种高效的内存分配方式，它预先分配一块大内存，然后从中分配小内存给对象。由于内存池分配出的内存没有初始化，所以如果是自定义类型的对象，需要使用定位new来调用构造函数进行初始化。
  2. 自定义内存管理：在某些情况下，开发者可能需要自定义内存管理策略，如使用特定的内存分配器或对齐要求。此时，可以使用定位new在已分配的内存上构造对象，以满足特定的内存管理需求
     代码实现如下：

// 申请定长内存对象
T* New()
{
    T* obj = nullptr;
    // 先判断自由链表中是否有还回来的
    if (_freelist)
    {
        // 存储下一个内存对象的地址
        void* next = *(void**)_freelist;
        obj = (T*)_freelist;
        _freelist = next;
    }
    else
    {
        // 当大块内存不足一个对象的大小时，向堆区申请
        if (_remainSize < sizeof(T))
        {
            _remainSize = 128 * 1024;// 默认是 128 KB
            _memory = (char*)malloc(_remainSize);// TODO
            if (_memory == nullptr)
            {
                throw std::bad_alloc();
            }
        }
        // 从大块内存切一个 T 对象 给obj
        obj = (T*)_memory;
        // 为了保证一个内存对象至少可以存的下，下一个对象的地址
        size_t objSize = sizeof(T) < sizeof(T*) ? sizeof(T*) : sizeof(T);
        _memory += objSize;
        _remainSize -= objSize;
    }
    // 使用定位 new 调用 T 的构造进行初始化
    new(obj)T;
    return obj;
}

这批还有一个注意的点：当在大块内存切割 obj 对象时，在 64 位下有可能存不下指针！
例如：在 64 位下申请了一个 int 大小的内存对象，但是当释放后挂在 自由链表中时，发现存不下一个8个字节的指针。所以，为了保证存的下一个指针，我们特殊的处理一下，当对象的大小，小于对象指针的大小时，就给成一个指针大小空间！

三、定长内存池 Delete 实现

释放的逻辑相比申请就很简单了，直接将还回来的内存，头插到自由链表即可！
需要注意的是，还回来的对象需要掉用T的析构函数，去释放T所管理的资源，避免内存泄漏

// 释放内存对象
void Delete(T* obj)
{
    // 显示的调用析构清理资源
    obj->~T();
    // 头插
    *(void**)obj = _freelist;
    _freelist = obj;
}

四、性能测试

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

我们使用以上代码测试一下我们定长内存池的性能！上面代码的意思就是分别使用 new 和 我们实现定长内存池的 New 分别申请和释放 N次，每次是 十万/一百万次
debug下：
release下：
我们可以看到，我们的内存池是由于 new 的而 new 的底层实际上就是 malloc，所以我们的整体还是很优秀的！

五、细节优化

我们上面刚测试了性能是不错的，但是我们有一个缺陷就是：我们再申请大块内存时还是使用的是 malloc 。我们知道 malloc 属于库函数，库函数是封装了系统调用的，所以我们可以在这里优化一下，让申请大内存块的操作直接使用系统调用去堆上申请！
上述操作不同的平台有不同的方式：
windows下的：VirtualAlloc
Linux下的：brk和mmap
对于不同平台，我们可以使用条件编译控制，我这里是 windows 就只写了 win 的：

#ifdef _WIN32
    #include<windows.h>
#else
    // ....
#endif
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
    void* ptr = VirtualAlloc(0, kpage * (1 << 12), MEM_COMMIT | MEM_RESERVE,
        PAGE_READWRITE);
#else
    // linux下brk mmap等
#endif
    if (ptr == nullptr)
        throw std::bad_alloc();
    return ptr;
}

所以，我们可以在申请大块内存那里直接换成系统调用的方式
因为OS 是以页为单位进行申请的，所以我们先将 _remainSize >> 12 就是算出页数，然后系统调用在按照 页数 << 12 （4KB） 开出来
再来测试一下：
OK，本期内容就到这里，我们下期再见！