神刀安全网

深夜学算法之Memory Pool:合理拖延

其实这篇在临走前完成度就差不多60%了,活生生拖了一个月,论人能懒到什么地步…

深夜学算法之Memory Pool:合理拖延
真是怠惰啊

1. 前言

本科找实习时阿里有道编程题是实现内存池,事后看了原理但没有自己实现过。这两天在实验楼看到课程,但写得不太清楚,所以直接参考Github上的Memory Pool源码自己写了一个劣化简化版。

我的实现:https://github.com/kophy/DSAF

2. 原理

2.1 整体认识

  • 什么是内存池?

引用一段wiki上的介绍:

Memory pools, also called fixed-size blocks allocation, is the use of pools for memory management that allows dynamic memory allocation comparable to malloc or C++’s operator new.

内存池是一种内存管理技术,通常提供allocate和deallocate两个方法,allocate相当于new,deallocate相当于delete,比如代码:

int *pd = new int;  // do something here  delete pd;

用内存池方式写就是:

MemoryPool<int> m; int *pd = m.allocate();  // do something here  m.deallocate(pd);

简而言之,内存池就是一种new和delete的替代机制

  • 内存池和new/delete有什么不同?

wiki上提到内存池通常是fixed-size,就是说通过内存池分配得到的内存大小是预定的,一个int的内存池只能分配int类型,double的内存池只能分配double类型。其实也可以通过一个内存池分配多种类型,比如C Interfaces and Implementations上就有变长版本的实现。

我个人理解,内存池的核心思想是预先分配延迟释放

举个例子,假设我跟同学借钱,每次虽然只借1元钱,但是重复次数特别多:

for (int i = 0; i < 100; ++i)      借1元钱

估计没几次受害同学就要扳着手指过来了:

深夜学算法之Memory Pool:合理拖延
cut your xiao huo ban

现在用上内存池的思想。
什么是预先分配?多借,比起精确地每次借1块,先借个20块。
什么是延迟释放?晚还,不管中间借了多少,全拖到最后一起还。
于是尽管我这边浪的飞起,同学看来只是借了5次20块,最后还了100块。

把同学当成操作系统,借钱是new,还钱是delete,大致就是这种感觉了。

2.2 算法概述

假设用fixed-size版本T类型的内存池。内存池中有两种大小的存储块:

  • slot
    slot是小存储块,通常大小正好容纳一个T类型变量。
  • block
    block是大存储块,通常大小能容纳N个T类型变量。

简单地讲,内存池里维护了一个空闲slot的链表。allocate时先检查空闲slot链表,链表非空则只要返回链表头上的slot,否则调用new向系统要求分配一个block,返回其中的一个slot给用户;deallocate时不真正调用delete方法,只是把释放的slot放回空闲链表头部。

深夜学算法之Memory Pool:合理拖延
Memory Pool原理图

如上图的内存池,free list是空闲slot链表,newest block是最近向系统要求的block,一个block里能容纳两个slot,第一个slot为灰色表示已经被分配掉了,第二个slot为白色表示可以分配。

当用户请求一个slot时,先检查free list,不空的话返回链表头部节点即可。现在假设free list为空,那么再检查newest block中是否有可用的slot,有的话返回该slot。最坏情况下是free list为空,newest block里slot全部分配掉,此时才需要调用new。

3. 实现

3.1 Memory Pool类定义

template <typename T, size_t seed = 16> class MemoryPool { public:     MemoryPool(void);     ~MemoryPool(void);      // Allocate/deallocate one T object at a time.     T *allocate(void);     void deallocate(T *sp);  private:     typedef union slot {         T data;         slot *next;     } slot;      typedef slot* slot_pointer;     typedef char* block_pointer;      int block_size;      block_pointer head_block;     slot_pointer current_slot;     slot_pointer last_slot;     slot_pointer free_slot; };

暂时先不管模板参数中的seed,可以看到slot定义是T和slot *类型的union,这样分配给用户时可以储存T类型数据,用户释放后可以组成链表,避免无意义的空间浪费。
free_slot是空闲slot链表的头部节点,current_slot指向newest block中第一个可用的slot,last_slot指向newest block的末尾,这些概念结合上面的原理图都很清晰。

为什么要有一个head_block呢?
其实是把向系统请求的所有block组织成了一个链表,这样整个内存池析构时就可以沿着block链表释放所有block,防止用户没有delete造成的内存泄漏。
所以block类型包含了N个slot的数组 + 指向下一个block的next指针。

3.2 实现allocate

template <typename T, size_t seed> T *MemoryPool<T, seed>::allocate(void) {     slot_pointer sp = nullptr;     if (free_slot) {         sp = free_slot;         free_slot = free_slot->next;     } else {         if (current_slot < last_slot) {             sp = current_slot;             ++current_slot;         } else {             block_pointer new_block = reinterpret_cast<block_pointer>(operator new(block_size));             reinterpret_cast<slot_pointer>(new_block)->next = reinterpret_cast<slot_pointer>(head_block);             head_block = new_block;             sp = reinterpret_cast<slot_pointer>((char *)head_block + sizeof(block_pointer));             current_slot = sp + 1;             last_slot = reinterpret_cast<slot_pointer>(head_block + block_size);         }     }     new (sp) T; // Call class T's constructor.     return reinterpret_cast<T *>(sp); }

有了之前的解释,这段代码应该不至于眼花缭乱,第一个if检查空闲链表,失败检查newest block,再失败向系统要一个block,更新block链表,返回第一个slot。
需要注意的是找到可用的slot后要手工调用构造函数,返回时要从slot_pointer转为T*。

3.3 其它成员函数

allocate是内存池的灵魂,其它成员函数实现方法都比较简单,比如deallocate:

template <typename T, size_t seed> void MemoryPool<T, seed>::deallocate(T *sp) {     sp->~T();   // Call class T's destructor.     reinterpret_cast<slot_pointer>(sp)->next = free_slot;     free_slot = reinterpret_cast<slot_pointer>(sp); }

关于模板参数中的seed,其实是为了辅助计算合适的block大小。具体地说,在MemoryPool的构造函数中有:

block_size = seed; while (block_size < sizeof(block_pointer) + sizeof(T))     block_size <<= 1;

也就是要保证一个block里至少能容纳一个block指针和一个T,否则就没有意义了。当然这只是为了试验的选择,实际中每个block里容纳的slot应该要足够多,平摊下来才能减少使用系统malloc/new的代价。

4. 参考资料

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » 深夜学算法之Memory Pool:合理拖延

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址