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

## 2. 原理

### 2.1 整体认识

• 什么是内存池？

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.

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

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

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

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

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

### 2.2 算法概述

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

Memory Pool原理图

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

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

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

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