Memory Pool ACM 2012 5120379038 Yanqing Peng

Dynamic memory allocation in C #define N 10000 int main() { int* p = malloc(sizeof(int)); //allocate a pointer to an integer int* pa = malloc(sizeof(int) * N); //allocate an array with N integers /*statement*/ free(p); free(pa); return 0; }

Dynamic memory allocation in C++ const int N = 10000; int main() { int* p = new int; //allocate a pointer to an integer int* pa = new int[N]; //allocate an array with N integers /*statement*/ delete p; delete [] pa; return 0; }

Some Problems… Memory Leak Mismatching Operators Fragmentation Long Execution Time ……

Memory Leak void foo() throw(std::runtime_error) { int* p = new int; /*statement*/ if ( condition ) throw std::runtime_error(“This is a Memory Leak”); delete p; //May cause a memory leak }

Some Problems… Memory Leak Mismatching Operators Fragmentation Long execution time ……

Mismatching Operators const int N = 10000; int main() { int* p = static_cast<int*>(malloc(sizeof(int)); //allocate by malloc int* pa = new int[N]; //allocate by new[] /*statement*/ delete p; //de-allocate by delete delete pa; //de-allocate by delete return 0; }

Some Problems… Memory Leak Mismatching Operators Fragmentation Long execution time ……

Fragmentation Memory = 8 bytes Allocate the whole memory De-allocate odd bytes Allocate a 4-byte block : std::bad_alloc 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7

Some Problems… Memory Leak Mismatching Operators Fragmentation Long execution time  ……

Long execution time int main() { for (int n = ~0U >> 1; n; --n) //delete (new int()); return 0; } Time = 4235 ms

Long execution time int main() { for (int n = ~0U >> 1; n; --n) delete (new int()); return 0; } Time = 1038020 ms

Placement New and Memory Pool 使用Placement New可以在指定的内存上构造对象。指定的内存需要事先申请，并 且保证没有其它变量正在使用这块内存。对于非POD对象，需要显式调用其析构函数。 #include <new> struct obj {}; char* buffer = new char[1<<8]; void foo() { obj* p = new (buffer) obj; //placement new p -> ~obj(); //invoke the destructor explicitly delete p; } 如果预先申请好一大块buffer进行之后的分配……

Placement New and Memory Pool 使用内存池来管理这个buffer！ #include <new> struct obj {}; class MemoryPool; void foo() { obj* p = new (MemoryPool::allocate<obj>()) obj; p -> ~obj(); MemoryPool::deallocate<obj>(p); }

Fixed-size Memory Pool 预先申请好一块内存区域，并把它分成定长的块。 每次需要内存申请时，将一块尚未分配的块返回。每次释放时，将传入的内 存块重新标记为未分配。 定长内存池在工程中应用非常广泛。代码量少、效率高，非常适合用作大量 同类型小数据的内存管理器。

Prototype template <typename Type> class MemoryPool { char *memStart; void *head; Type *left, *right, *memEnd; public: MemoryPool(size_t); ~MemoryPool(); inline Type* allocate(); inline bool deallocate(Type*); };

Constructor template <typename Type> MemoryPool<Type>::MemoryPool(size_t _capacity) : memStart(new char[std::max(sizeof(Type), sizeof(void*)) * _capacity]), head(0), left(reinterpret_cast<Type*>(memStart)), right(left), memEnd(left + _capacity) {} 未初始化的内存 内存的开始地址 memStart=1 内存的结束地址的后一位 memEnd=7 初始化内存的开始地址 left=1 未初始化内存的开始地址 right=1 [left, right)为已初始化的内存地址区间 第一个初始化内存 head = NULL

Allocation 1 若没有空余的已初始化内存，则从未初始化的内存头部取出一块作为返回值 if (!head) return right++; 未初始化的内存 memStart=1 memEnd=7 left=1 right=1 head = NULL

Allocation 1 若没有空余的已初始化内存，则从未初始化的内存头部取出一块作为返回值 if (!head) return right++; 未初始化的内存 memStart=1 memEnd=7 left=1 分配的内存 right=2 已初始化内存 head = NULL

Allocation 1 若没有空余的已初始化内存，则从未初始化的内存头部取出一块作为返回值 if (!head) return right++; 未初始化的内存 memStart=1 memEnd=7 left=1 分配的内存 right=3 已初始化内存 head = NULL

Allocation 1 若没有空余的已初始化内存，则从未初始化的内存头部取出一块作为返回值 if (!head) return right++; 未初始化的内存 memStart=1 memEnd=7 left=1 分配的内存 right=4 已初始化内存 head = NULL

De-allocation 将返回的内存块（p）插入已初始化内存链表头部，内存块中存放下一个已初始化的 内存 void** newHead = reinterpret_cast<void**>(p); *newHead = head; head = newHead; 未初始化的内存 memStart=1 head = NULL memEnd=7 left=1 分配的内存 right=4 已初始化内存

De-allocation 将返回的内存块（p）插入已初始化内存链表头部，内存块中存放下一个已初始化的 内存 void** newHead = reinterpret_cast<void**>(p); *newHead = head; head = newHead; 未初始化的内存 memStart=1 head=1 memEnd=7 left=1 NULL right=4 已初始化内存 分配的内存

De-allocation 将返回的内存块（p）插入已初始化内存链表头部，内存块中存放下一个已初始化的 内存 void** newHead = reinterpret_cast<void**>(p); *newHead = head; head = newHead; 未初始化的内存 memStart=1 memEnd=7 left=1 NULL right=4 已初始化内存 分配的内存 1 head=3

De-allocation 将返回的内存块（p）插入已初始化内存链表头部，内存块中存放下一个已初始化的 内存 void** newHead = reinterpret_cast<void**>(p); *newHead = head; head = newHead; 未初始化的内存 memStart=1 memEnd=7 left=1 NULL right=4 已初始化内存 3 1 head=2

Allocation2 若已初始化内存块链表非空，则删除表首并返回该地址 Type* ret = reinterpret_cast<Type*>(head); head = *(reinterpret_cast<void**>(head)); return ret; 未初始化的内存 memStart=1 memEnd=7 left=1 NULL right=4 已初始化内存 3 1 head=2

Allocation2 若已初始化内存块链表非空，则删除表首并返回该地址 Type* ret = reinterpret_cast<Type*>(head); head = *(reinterpret_cast<void**>(head)); return ret; 未初始化的内存 memStart=1 memEnd=7 left=1 NULL right=4 已初始化内存 分配的内存 1 head=3

Allocation2 若已初始化内存块链表非空，则删除表首并返回该地址 Type* ret = reinterpret_cast<Type*>(head); head = *(reinterpret_cast<void**>(head)); return ret; 未初始化的内存 memStart=1 head=1 memEnd=7 left=1 NULL right=4 已初始化内存 分配的内存

Allocation2 若已初始化内存块链表非空，则删除表首并返回该地址 Type* ret = reinterpret_cast<Type*>(head); head = *(reinterpret_cast<void**>(head)); return ret; 未初始化的内存 memStart=1 head = NULL memEnd=7 left=1 分配的内存 right=4 已初始化内存

Destructor 这个就不画图了…… delete [] memStart;

Pseudo-code Initialization Store the start address, number of blocks and the number of uninitialized unused block Allocation Check if there any free blocks If necessary - initialize and append unused memory block to the list Go to the head of the unused block list Extract the block number from the head of the unused block in the list and set it as the new head Return the address for the old block head De-allocation Check the memory address is valid Calculate the memory addresses index id Set its contents to the index id of the current head of unused blocks and set itself as the head

Benchmark #include “memorypool.h” MemoryPool<int> pool(10); int main() { for (int n = ~0U >> 1; n; --n) pool.deallocate(pool.allocate()); return 0; } Time = 17904 ms

Resizing 使用类似vector的扩张方法 每次内存不够时，重新申请一块长度为已有内存两倍的内存块 使用一个类去维护多个相同长度的定长内存池

Thread-safety 线程安全是编程中的术语，指某个函数 (计算机科学)、函数库 在多线程环境中被调用时，能够正确地处理各个线程的局部变 量，使程序功能正确完成。 一般来说，线程安全的函数应该为每个调用它的线程分配专门 的空间，来储存需要单独保存的状态（如果需要的话），不依 赖于“线程惯性”，把多个线程共享的变量正确对待（如，通知 编译器该变量为“易失（volatile）”型，阻止其进行一些不恰当 的优化），而且，线程安全的函数一般不应该修改全局对象。 使用互斥锁保证线程安全。

Thread-safety (Using pthread) #include <pthread.h> template <typename Type> class mt_MemoryPool { MemoryPool<Type> pool; pthread_mutex_t lock; public: mt_MemoryPool(size_t capacity) : pool(capacity) pthread_mutex_init(&lock, 0); } inline Type* allocate(); inline bool deallocate(Type*); };

Thread-safety (Using pthread) template <typename Type> inline Type* mt_MemoryPool::allocate(); { pthread_mutex_lock(&lock); Type* ret = pool.allocate(); pthread_mutex_unlock(&lock); return ret; }

Thread-safety (Using pthread) template <typename Type> inline bool mt_MemoryPool::deallocate(Type* p); { pthread_mutex_lock(&lock); bool ret = pool.deallocate(p); pthread_mutex_unlock(&lock); return ret; }

Smart Pointer 用类似智能指针的思想实现内存池分配空间的自动归还 引用计数 在智能指针的析构中自动析构对象并归还

Smart Pointer void foo() throw(std::runtime_error) { MemoryPool<int>::pointer p = pool.allocate(); /*statement*/ if ( condition ) throw std::runtime_error(“No memory leak.”); } // p will be executed when leaving this scope

Variable-size Memory Pool 不同于定长内存池，不定长内存池可以在构造后申请各种不同 大小的内存块。 p = pool.allocate<int>(); 实现方法：内部维护多个定长内存池，每次找到最小的能满足 条件的内存池进行内存分配。如果申请的内存大于所有的内存 池大小，则直接调用malloc() 如：分别维护1,2,4,8,16,32,64,128,256,512,1024bytes的定长 内存池，对于每一个内存申请向上对齐到2的整次幂后分配对 应大小的内存块，此时空间最多浪费一倍 效率低于定长内存池

Singleton / Static Class 强制使类只生成一个实例。 使用单例模式：将构造函数声明为private，通过public函数GetInstance函数中的 static class reference获取唯一的实例 MemoryPool& pool = MemoryPool::GetInstance(); 静态类：将类的所有函数声明为static，全局静态实例保证唯一性。 p = MemoryPool::allocate<int>(); MemoryPool::deallocate<int>(p);

Allocator in SGI-STL 默认使用两级配置器 第一级配置器直接调用C的内存分配函数malloc()及realloc()，如果调用失败则执 行oom_malloc() 第二级配置器的做法是，如果区块够大，超过128bytes时，就移交第一级配置器处 理。当区块小于128bytes时，则以不定长内存池管理。 不定长内存池中维护16个定长内存池，大小分别为 8,16,24,32,40,48,56,64,72,80,88,96,104,112,120,128bytes，将所需的内存向上对 齐至8的倍数后交由对应的定长内存池分配 所有stl容器默认使用上述stl::alloc进行内存管理

Reference Stanley B.Lippman, Josee Lajoie, Barbara E. Moo C++ Primer[M] Addison-Wesley Educational Publishers Inc, 2012.08 候捷 STL源码剖析 [M] 华中科技大学出版社, 2002.06 SGI SGI STL Allocator Design [G/OL] from: http://www.sgi.com/tech/stl/alloc.html Wikipedia Memory Pool [G/OL], 2013.04 from: http://en.wikipedia.org/wiki/Memory_pool