MemoryPool

发表于 更新于

c++ 的高性能内存池

一般，使用malloc free和 new delete来动态管理内存，因为牵扯到系统调用，因此效率很低。内存池的思想就是使用很少的系统调用，申请一大块内存自己管理。内存池向系统申请大块内存，然后再分为小片给程序使用，每次请求内存，起始都是在内存池里拿内存而非通过系统调用。（线程池和对象池有着类似的思想）。内存池的优点：

  • 原理上比malloc和new快
  • 分配内存时不存在开销（overhead）
  • 几乎不存在内存碎片（为什么？？？）
  • 无需一个个释放对象，只需要释放内存池即可

缺点：

  • 需要知道分配对象的大小
  • 需要根据应用的情况来调节
1
2
3
4
5
6
/*******
* 赋值 *
*******/
//  使用 = delete 禁用拷贝赋值，只保留移动赋值
MemoryPool& operator=(const MemoryPool& mp) = delete;
MemoryPool& operator=(const MemoryPool&& mp) noexcept;
1
2
// static_assert: 编译期断言检查
static_assert(BlockSize >= 2 * sizeof(Slot_), "BlockSize too small.")

每个slot作为一个块

1
2
3
4
union Slot_ {
      value_type element;
      Slot_* next;
    };

一个奇怪的构造函数

1
2
3
4
5
6
7
8
9
// MemoryPool.h
MemoryPool(const MemoryPool& mp) noexcept; // 拷贝构造函数

// MemoryPool.cpp
template <typename T, size_t BlockSize>
MemoryPool<T, BlockSize>::MemoryPool(const MemoryPool& mp) noexcept: MemoryPool() {}

// 推测其意思就是调用无参数构造函数。
// 可是明明走的是拷贝构造函数

析构函数中的强制类型转换

1
2
3
4
5
6
7
8
9
10
11
template <typename T, size_t BlockSize>
MemoryPool<T, BlockSize>::~MemoryPool()
noexcept
{
  slot_pointer_ curr = currentBlock_;
  while (curr != nullptr) {
    slot_pointer_ prev = curr->next;
    operator delete(reinterpret_cast<void*>(curr));
    curr = prev;
  }
}
img 
1
2
3
4
Slot_ *currentBlock_;
Slot_ *currentSlot_;
Slot_ *lastSlot_;
Slot_ *freeSlots_;

内存池拥有四个指针，freeSlots应该就是空闲slot

一个内存池MemoryAlloc包含若干个block块，空闲内存块通过链表的形式记录，block内以slot呈现。

首先我们使用 typedef 定义了某个东西成为了 allocator，这是毫无疑问的，而这个东西却是：

1
typename Alloc::template rebind<Node>::other

它长得很奇怪，这其实是为了解决让编译器不认识代码的问题而出现的写法（语法）。

首先我们定义了 Alloc = std::allocator<T>，而 rebind 其实是 std::allocator 的一个成员。巧就巧在，rebind 本身又是另一个模板， C++ 称其为 dependent name。完整的形式本来应该是：

1
std::allocator<T>::rebind<Node>::other

但是模板的相关解析已经在 <T> 出现过了，后面的 <Node> 中的 < 只能被解释为小于符号，这会导致编译出错。为了表示 dependent name 是一个模板，就必须使用 template 前缀。如果没有 template 前缀，< 会被编译器解释为小于符号。所以，我们必须写成下面的形式：

1
std::allocator<T>::template rebind<Node>::other

最后，编译器在其实根本没有任何办法来区分 other 究竟是一个类型，还是一个成员。但我们其实知道 other 是一个类型，所以使用 typename 来明确指出这是一个类型，最终才有了：

1
typename std::allocator<T>::template rebind<Node>::other

四个文件

memory_pool

​ |– MemoryPool.h

​ |– MemoryPool.cpp

​ |– StackAlloc.h

​ |– Test.cpp

MemoryPool.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
//
// Created by 张庆 on 2022/7/22.
//

#ifndef TINY_RECORD_MEMORYPOOL_H
#define TINY_RECORD_MEMORYPOOL_H

#pragma once
#include <cstddef>  // for size_t
#include <cstdint>  // for uintptr_t
#include <utility>  // for std::swap, std::forward

template <typename T, size_t BlockSize = 4096> class MemoryPool {
public:
    template<typename U>
    struct rebind{  // 结构体 rebind
        typedef MemoryPool<U> other;
    };

    /***********************
     * T 类型的构造和析构
     * ********************/
    // 内存池的构造和析构
    MemoryPool() noexcept;  // 构造函数
    MemoryPool(const MemoryPool &mem) noexcept;  // 拷贝构造
    MemoryPool(MemoryPool &&mem) noexcept;  // 移动构造

    // 拷贝构造函数,以另一个类型为模板 MemoryPool<U>
    template <typename U>
    MemoryPool(const MemoryPool<U> &mem) noexcept;

    // 析构函数
    ~MemoryPool() noexcept;


    // 赋值，禁用拷贝赋值，只保留移动赋值
    // 我猜测拷贝复制对于内存池而言会出现和c++ string使用cow一样的问题
    MemoryPool &operator = (const MemoryPool &mem) = delete;
    MemoryPool &operator = (MemoryPool &&mem) noexcept;

    // 获取元素的地址
    // 返回引用类型变量地址
    inline T *address(T &element) const noexcept{return  &element;} // 括号后的const不可修改函数内的内容
    // 返回常量引用类型变量地址
    inline const T *address(const T &element) const noexcept{return &element;}


    /***********************
     * Allocator
     * ********************/
    /** 拥有四个接口
       1. 从内存池为对象分配内存
       2. 从内存池为对象释放内存a
       3. 构造和析构对象
       4. new与delete
     **/

    /***********************
     * 从内存池为对象分配内存
     * ********************/
    // 分配足够的存储空间来存储T的n个对象实例
    // hint 是建议地址，没有特别需求设为0。
    // 函数会返回一个实际map的地址
    inline T *allocate(size_t n = 1, const T *hint = nullptr){
        // 有freeSLot_，那么可以直接往后使用
        if(freeSlot_ !=nullptr){
            T *result = reinterpret_cast<T *>(freeSlot_); // 指针的一个强制转换
            freeSlot_ = freeSlot_->next;
            return result;
        }else{  // do not have freeSlot_
            // freeSlot_还未初始化或者已经用完
            if(currentSlot_ >= lastSlot_){  // 耗尽
                allocateBlock();
            }
            return reinterpret_cast<T *>(currentSlot_++);
        }
    }


    /***********************
     * 从内存池为对象释放内存
     * ********************/
    inline void deallocate(T *p, size_t n = 1){  // n是对象个数
        // TODO：解决？？？ 只释放了一个SLot. Block貌似就是一个对象
        if(p != nullptr){
            // freeSlot 头插法建立
            // 释放的链表头插法进去，如果freeSlot_目前是A->B->C, 释放了个X，那么变为X->A->B->C
            reinterpret_cast<Slot_ *>(p)->next = freeSlot_;
            freeSlot_ = reinterpret_cast<Slot_ *>(p);
        }
    }


    /***********************
     * 构造与析构对象
     * ********************/
     // 使用p指向的args参数构造一个对象
    template<typename U, typename... Args>
    inline void construct(U* p, Args &&... args){
        new (p) U(std::forward<Args>(args)...);
        // 在p指向的内存，用给定模板参数列表（转发、解包）新建一个U类型的对象
    }

    // 调用p指向的对象的析构函数
    template<typename U>
    inline void destroy(U *p){
        p->~U();
    }


    /***********************
     * new 与 delete
     * ********************/
    template<typename... Args>  // 变参模板
    inline T *newElement(Args &&... args){
        T *result = allocate();
        construct(result, std::forward<Args>(args)...);
        // std::forward的模板参数必须是<Args>,而不能是<Args...>
        // 这是由于我们不能对Args进行解包之后传递给std::forward
        return result;
    }

    inline void deleteElement(T *p){
        if(p != nullptr){  // p指向的对象不为空
            p->~T();  // 对象析构
            deallocate(p);  // 释放指针
        }
    }

    /***********************
     * 最多能容纳多少个对象
     * ********************/
    inline size_t max_size() const noexcept{
        // -1 表示当前能寻址的最大内存地址
        size_t max_Block = -1/BlockSize;
        // 每个Block能容纳T的个数
        size_t max_T = (BlockSize - sizeof(char *))/sizeof(Slot_);
        return max_Block*max_T;
    }

private:
    union Slot_{
        T element;
        Slot_ *next;
    };

    Slot_ *currentBlock_;
    Slot_ *currentSlot_;
    Slot_ *lastSlot_;
    Slot_ *freeSlot_;

    void allocateBlock();

    /***********************
     * 对齐align
     * ********************/
     // uintptr_t是可以容纳指针大小的integer type，
     // 但是size_t不一定是，在一些具有分段寻址机制的平台，size_t可能比一个指针的大小还小。
     // padding代表需要往后移多少个位置，才能按照align的大小进行对齐
     // 比如  2  4， 那么还需要后移2个位置
     inline size_t padPointer(char* p, size_t align) const noexcept{
         uintptr_t addr = reinterpret_cast<uintptr_t>(p);
         size_t padding = (align - addr) % align;
         // 测试一下，开源代码给的测试用例
         // printf("addr = %08lx\n, align = %02lx, and padding = %02lx\n", addr, align, padding);
         return padding;
     }

     // 编译期断言检查
    static_assert(BlockSize >= 2*sizeof(Slot_),"static_assert: Block is too small!");
};








#endif //TINY_RECORD_MEMORYPOOL_H

MemoryPool.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
//
// Created by 张庆 on 2022/7/22.
//
#include "MemoryPool.h"
using namespace std;

// 默认构造函数
template<typename T, size_t BlockSize>
MemoryPool<T, BlockSize>::MemoryPool() noexcept{
    currentBlock_ = nullptr;
    currentSlot_ = nullptr;
    lastSlot_ = nullptr;
    freeSlot_ = nullptr;
}

// 拷贝构造函数
template<typename T, size_t BlockSize>
MemoryPool< T, BlockSize>::MemoryPool(const MemoryPool &mem) noexcept
        :MemoryPool() {}
        // TODO: // 为什么调用无参数构造函数???

// 拷贝构造
template<typename T, size_t BlockSize>
MemoryPool<T, BlockSize>::MemoryPool(MemoryPool &&mem) noexcept{
currentBlock_ = mem.currentBlock_;
mem.currentBlock_ = nullptr;  //  释放之前的block指针
currentSlot_ = mem.currentSlot_;
lastSlot_ = mem.lastSlot_;
freeSlot_ = mem.freeSlot_;
}

// 另一个类型U
template<typename T, size_t BlockSize>
template<typename U>
MemoryPool< T, BlockSize>::MemoryPool(const MemoryPool<U> &mem) noexcept
        :MemoryPool() {}

// 析构一个Block
template<typename T, size_t BlockSize>
MemoryPool<T, BlockSize>::~MemoryPool() noexcept {
    Slot_ * cur = currentBlock_;
    while(cur !=nullptr){
        Slot_ *nxt = cur->next;
        ::operator delete(reinterpret_cast<void *>(cur));
        cur = nxt;
    }
}

// 移动赋值
// 拷贝赋值已经被delete， 即禁用
// 重载operator=
template<typename T, size_t BlockSize>
MemoryPool<T, BlockSize> &MemoryPool<T, BlockSize>::
operator=(MemoryPool &&mem) noexcept {
    if(this != &mem){  // 若不是给自己赋值
        // 交换第一块Block的位置
        // swap内部也是移动赋值机制，确保了不会有多个指针指向一块空间
        // 这样不会出现一块空间被重复释放的问题
       std::swap(currentBlock_, mem.currentBlock_);
       currentSlot_ = mem.currentSlot_;
       lastSlot_ = mem.lastSlot_;
       freeSlot_ = mem.freeSlot_;
    }
    return *this; // 对象
}

// 为内存池分配内存
// allocateBlock()
template<typename T, size_t BlockSize>
void MemoryPool<T, BlockSize>::allocateBlock() {
    // Block 也按照头插法建立
    char *newBlock = reinterpret_cast<char *>(::operator new(BlockSize));
    reinterpret_cast<Slot_ *>(newBlock)->next = currentBlock_; // 头插
    currentBlock_ = reinterpret_cast<Slot_ *>(newBlock);
    // 需要做一个内存对齐，因为第一个指针指向Block，而不是Slot_
    // 第一个指针之后的都是Slot_
    char *curPoint = newBlock + sizeof(Slot_ *);
    // alignof(type)将指定类型的对齐方式返回为类型的值 size_t
    size_t padding = padPointer(curPoint, alignof(Slot_));
    currentSlot_ = reinterpret_cast<Slot_ *>(curPoint + padding);
    lastSlot_ = reinterpret_cast<Slot_ *>(newBlock + BlockSize - sizeof(Slot_) + 1);
}

StackAlloc.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
//
// Created by 张庆 on 2022/7/22.
//

#ifndef TINY_RECORD_STACKALLOC_H
#define TINY_RECORD_STACKALLOC_H

#include <memory>

/**
 * 实现堆栈结构的模板类
 * 使用allocator_traits(specifically with MemoryPool)
 * **/

template<typename T>
struct StackNode_{
    T data;
    StackNode_* prev;
};

/**
 * T 是存储在stack中的对象，alloc 是所使用的allocator
 * **/
template<typename T, typename alloc = std::allocator<T>>
class StackAlloc {
public:
    typedef StackNode_<T> node;
    // rebind 是 std::allocator的一个成员
    // rebind本身就是另一个模板， 形式类似于 std::allocator<T>::rebind<Node>::other
    // template 是为了说明other是个类型，而不是一个成员
    typedef typename alloc::template rebind<node>::other allocator;

    /** 构造函数 **/
    StackAlloc(){head_ = 0;}

    /** 析构函数 **/
    ~StackAlloc(){clear();}

    /** 当前栈是否为空 */
    bool isEmpty(){
        return (head_ == 0);
    }

    /** 清除所有元素，stack清空 **/
    void clear(){  // T is an object
        node* cur = head_;
        while(cur!=0){
            node* temp = cur->prev;
            allocator_.destroy(cur);
            allocator_.deallocate(cur,1);
            cur = temp;
        }
        head_ = 0;
    }


    /** put an element on the top of the stack*/
    // element is an object
    void push(T element){
        node* newEle = allocator_.allocate(1); // 分配一个新的Slot_
        allocator_.construct(newEle, node()); // inline void construct(U* p, Args&&... args){
        newEle->data = element;
        newEle->prev = head_;
        head_ = newEle;
    }

    T top(){
        return head_->data;
    }
    /** 移除顶端元素,返回对象 */
    T pop(){
        node* cur = head_->prev;
        T cur_ele = head_->data;
        allocator_.destroy(head_);
        allocator_.deallocate(head_,1);
        head_ = cur;
        return cur_ele;
    }

private:
    allocator allocator_;
    node* head_;
};


#endif //TINY_RECORD_STACKALLOC_H

Test.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
//
// Created by 张庆 on 2022/7/22.
//

#include <iostream>
#include <cassert>
#include <time.h>
#include <vector>

#include "MemoryPool.cpp"
#include "StackAlloc.h"


#define MAXELES 100000
#define REPS 50

using namespace std;


int main(){
    /*****************
     *
     * use default allocator
     *
     * ***************/
    cout<< "======Use default allocator======"<<endl;
    clock_t start;

    // 使用 StackAlloc, 此时allocator为默认allocator<int>
    StackAlloc<int, std::allocator<int>> stackDefault;

    start = clock();
    for(int i = 0;i<REPS;++i){
        assert(stackDefault.isEmpty());   // 为0则中断
        for(int j = 0;j<MAXELES/4;++j){
            stackDefault.push(j);
            stackDefault.push(j);
            stackDefault.push(j);
            stackDefault.push(j);
        }

        for(int j = 0;j<MAXELES/4;++j){
            stackDefault.pop();
            stackDefault.pop();
            stackDefault.pop();
            stackDefault.pop();
        }
    }

    cout<<"default allocator time: ";
    cout<< ((double)(clock() - start)/CLOCKS_PER_SEC) <<endl;


    /*****************
     *
     * use MemoryPool
     *
     * ***************/
    cout<< "======Use MemoryPool======"<<endl;
    StackAlloc<int, MemoryPool<int>> stackWithMem;

    start = clock();
    for(int i = 0;i<REPS;++i){
        assert(stackWithMem.isEmpty());   // 为0则中断
        for(int j = 0;j<MAXELES/4;++j){
            stackWithMem.push(j);
            stackWithMem.push(j);
            stackWithMem.push(j);
            stackWithMem.push(j);
        }

        for(int j = 0;j<MAXELES/4;++j){
            stackWithMem.pop();
            stackWithMem.pop();
            stackWithMem.pop();
            stackWithMem.pop();
        }
    }

    cout<<"default allocator time: ";
    cout<< ((double)(clock() - start)/CLOCKS_PER_SEC) <<endl;


    /**
     * 用动态数组vector代替stack
     * */
    cout<< "======Use vector======"<<endl;
    std::vector<int> vec;
    start = clock();

    for(int i = 0;i<REPS;++i){
        assert(vec.empty());   // 为0则中断
        for(int j = 0;j<MAXELES/4;++j){
            vec.push_back(j);
            vec.push_back(j);
            vec.push_back(j);
            vec.push_back(j);
        }

        for(int j = 0;j<MAXELES/4;++j){
            vec.pop_back();
            vec.pop_back();
            vec.pop_back();
            vec.pop_back();
        }
    }

    cout<<"vector time: ";
    cout<< ((double)(clock() - start)/CLOCKS_PER_SEC) <<endl;
    return 0;
}

image-20220723224515428