Part 6：空间配置器
背景：频繁使用 malloc 分配内存的造成的问题：
- 系统调用，系统开销较大
- 产生大量的内存碎片（外部碎片）。
注：内存碎片
- 内部碎片：页式管理、段式管理、段页式管理，无法避免，可以通过算法优化。
- 外部碎片：申请堆空间之间的片段空隙，空间配置器优化的是外部碎片。
因此，引入空间配置器 allocator。可以感知类型的空间分配器，用于分配和释放内存，将内存的分配释放与对象的创建销毁分开。
1、allocator 接口层
1.1、接口层源码
针对容器来说，空间的分配 construct 与对象的创建 allocate 是分开的，并不是绑定在一起。提供的接口如下：
// 1、空间分配 // 1.1、申请未初始化的空间 pointer allocate( size_type n, const void * hint = 0 ); T* allocate( std::size_t n, const void * hint); T* allocate( std::size_t n ); // 1.2、释放空间 void deallocate( T* p, std::size_t n ); // 2、对象创建 // 2.1、对象的构建。 void construct( pointer p, const_reference val ); // 2.2、对象的销毁 void destroy( pointer p );
源码位于stl_alloc.h，接口层的源码如下：
// 空间配置器的接口层 template <class _Tp> class allocator { typedef alloc _Alloc; _Tp* allocate(size_type __n, const void* = 0) { return __n != 0 ? static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp))) : 0; } void deallocate(pointer __p, size_type __n) { _Alloc::deallocate(__p, __n * sizeof(_Tp)); } void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); } void destroy(pointer __p) { __p->~_Tp(); } };
1.2、定位 new 表达式
定位 new 表达式：在 p 指向的未初始化的内存中构造 T 类型对象。
void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }
1.3、实例
例：使用std::allocator实现自定义的Vector类
vector 模型
Vector模型 ______________________________ |_|_|_|_|_|____________________| ↑ ↑ ↑ _start _finish _end_of_storage
接口形式：
template<typename T> class Vector { public: Vector(); ~Vector(); void push_back(const T &); void pop_back(); int size(); int capacity(); private: void reallocate();//重新分配内存,动态扩容要用的 private: static std::allocator<T> _alloc; T *_start; // 指向数组中的第一个元素 T *_finish; // 指向最后一个实际元素之后的那个元素 T *_end_of_storage; // 指向数组本身之后的位置 };
实现代码：
#include <algorithm> #include <iostream> #include <memory> using std::cout; using std::endl; template<typename T> class Vector { public: Vector() : _start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) {} ~Vector(); void push_back(const T &); void pop_back(); int size() const { return _finish - _start; } int capacity() const { return _end_of_storage - _start; } // 定义迭代器 typedef T * iterator; typedef const T * const_iterator; const_iterator begin() const { return _start; } const_iterator end() const { return _finish; } private: void reallocate(); // 重新分配内存，动态扩容 private: // 定义空间配置器，静态共享 static std::allocator<T> _alloc; T *_start; //指向数组中的第一个元素 T *_finish; //指向最后一个实际元素之后的那个元素 T *_end_of_storage; //指向数组本身之后的位置 }; // 初始化 allocator template <class T> std::allocator<T> Vector<T>::_alloc; template <typename T> void Vector<T>::push_back(const T & t) { // 数组扩容 if(size() == capacity()) { reallocate(); } // 在 finish 所指位置构造对象 if(size() < capacity()) { _alloc.construct(_finish++, t); } } template <typename T> void Vector<T>::pop_back() { if(size() > 0) { _alloc.destroy(--_finish); } } template <typename T> Vector<T>::~Vector() { // 1. 先析构对象 while(_finish != _start) { _alloc.destroy(--_finish); } // 2. 回收空间 if(_start) { _alloc.deallocate(_start, capacity()); } } template <typename T> void Vector<T>::reallocate() // 重新分配内存，动态扩容 { // 当 size == capacity，需要动态扩容 int oldCapacity = capacity(); int newCapacity = (oldCapacity == 0 ? 1 : 2 * oldCapacity); // 2 倍扩容 // 1、开辟新的空间 T * ptmp = _alloc.allocate(newCapacity); if(_start) { // 2、将原来空间上的对象复制到新空间 // 新开辟的空间上没有对象，无法使用 copy, memcpy 等算法 std::uninitialized_copy(_start, _finish, ptmp); // 3、释放原来的空间 // 3.1、销毁原来空间上的对象 while(_finish != _start) { _alloc.destroy(--_finish); } // 3.2、释放原来的空间 _alloc.deallocate(_start, oldCapacity); } // 5. 重置3个指针, 指向新的空间 _start = ptmp; _finish = _start + oldCapacity; _end_of_storage = _start + newCapacity; } template <class Container> void print(const Container & c) { // for 循环需要迭代器，自定义 vector 需要提供迭代器 for( auto & elem : c) { cout << elem << " "; } cout << endl; } void test0 () { Vector<int> vec; vec.push_back(1); cout << "vec's size:" << vec.size() << endl; cout << "vec's capa:" << vec.capacity() << endl; vec.push_back(2); cout << "vec's size:" << vec.size() << endl; cout << "vec's capa:" << vec.capacity() << endl; vec.push_back(3); cout << "vec's size:" << vec.size() << endl; cout << "vec's capa:" << vec.capacity() << endl; vec.push_back(4); cout << "vec's size:" << vec.size() << endl; cout << "vec's capa:" << vec.capacity() << endl; vec.push_back(5); cout << "vec's size:" << vec.size() << endl; cout << "vec's capa:" << vec.capacity() << endl; print(vec); } int main(void) { test0(); return 0; }
2、allocator 实现层
真正进行分配空间的是std::alloc，见源码：
template <class _Tp> class allocator { typedef alloc _Alloc; _Tp* allocate(size_type __n, const void* = 0) { return __n != 0 ? static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp))) : 0; } };
使用两级空间配置器。在分配空间的时候，若申请的空间大小：
- 大于 128 字节，调用一级配置器，使用 malloc / free
- 小于等于 128 字节，调用二级配置器（默认空间配置器），使用内存池 + 16个自由链表。
// 空间配置器的实现层 // 1、一级配置器，使用 malloc 进行空间分配 # ifdef __USE_MALLOC typedef malloc_alloc alloc; // 2、二级配置器，默认的空间分配器，使用内存 + 16个自由链表 # else typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc; # endif
2.1、一级空间配置器
对于大块内存（大于 128 字节），第一级空间配置器使用 malloc / free 分配和释放内存，对应的源码：
// 一级空间配置器（对 malloc/free 的封装） template <int __inst> class __malloc_alloc_template { public: // allocate 接口：封装 malloc static void* allocate(size_t __n) { void* __result = malloc(__n); if (0 == __result) __result = _S_oom_malloc(__n); return __result; } // deallocate 接口：封装 free static void deallocate(void* __p, size_t /* __n */) { free(__p); } ... }; // 定义 alloc 类 typedef __malloc_alloc_template<0> malloc_alloc typedef malloc_alloc alloc
2.2、二级空间配置器
默认空间配置器，所有的容器最终调用它完成空间的分配和释放。由内存池 + 16 个自由空闲链表组成。
简单来说，allocator根据用户申请的空间大小（8 的整数倍，向上取整），先向堆申请大块内存，然后拿出其中一部分将其分割成固定大小的内存块，并组织成空闲链表；另一部分作为内存池备用。此后，每次申请内存先向空闲链表申请空间，对应的空闲链表不存在则向内存池申请空间，否则向堆申请大块内存。
二级空间配置器源码部分如下：
typedef __default_alloc_template alloc template <bool threads, int inst> class __default_alloc_template { public: static void* allocate(size_t __n); static void deallocate(void* __p, size_t __n) private: // 内存分配 // 1、填充自由空闲链表 static void* _S_refill(size_t __n); // 2、申请内存 static char* _S_chunk_alloc(size_t __size, int& __nobjs); // 通过申请的字节数，得到自由空闲链表的下标 // 例如申请 25~32 个字节，对应的链表下标就是 3 static size_t _S_freelist_index(size_t __bytes) { return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1); } // 将申请的字节数，向上取整，得到 8 的整数倍，申请连续的空间 static size_t _S_round_up(size_t __bytes) { return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1)); } private: enum {_ALIGN = 8}; enum {_MAX_BYTES = 128}; enum {_NFREELISTS = 16}; // 链表结点（指针） union _Obj { union _Obj* _M_free_list_link; char _M_client_data[1]; }; // 16 个自由空闲链表 static _Obj* _S_free_list[_NFREELISTS]; // 内存池，一次申请大空间，之后只需要在内存池上进行切割 static char* _S_start_free; // 内存池的起始位置 static char* _S_end_free; // 内存池的结束位置 static size_t _S_heap_size; // 16个自由空闲链表 + 内存池，即堆上申请的总空间 };
allocate
static void* allocate(size_t __n) // __n 要申请的字节数 { void* __ret = 0; // 1、当__n > 128 字节时，使用一级空间配置器完成空间的申请 if (__n > (size_t) _MAX_BYTES) { __ret = malloc_alloc::allocate(__n); } // 2、当 __n <= 128 字节时，使用二级空间配置器完成空间的申请 else { // 通过 __n 的值获取对应的到自由的空闲链表。 // _S_freelist_index 函数根据 __n 的值获得链表下标 _Obj** __my_free_list = _S_free_list + _S_freelist_index(__n); _Obj* __result = *__my_free_list; // 第一次申请 __n 空间，链表结点地址是 0，堆上还未申请这条自由链表 if (__result == 0) // 从堆空间中去找内存块，填充该自由空闲链表。 // _S_round_up 函数申请的空间大小向上取整，是 8 的倍数 __ret = _S_refill(_S_round_up(__n)); else { // 当再次申请 __n 空间，直接从已经申请的链表头部取下链表结点，时间复杂度 O(1) *__my_free_list = __result -> _M_free_list_link; __ret = __result; } } return __ret; }
空间分配的核心函数在于：_S_refill和 _S_chunk_alloc函数
_S_refill函数：填充__nobjs个结点大小为 __n的自由空闲链表。其中__nobjs默认是 20，若内存池不够分割，则重新计算。
// _S_refill 函数：填充自由空闲链表 template <bool __threads, int __inst> void* __default_alloc_template<__threads, __inst>::_S_refill(size_t __n) { int __nobjs = 20; // 申请 20 个 __n 字节大小的大块内存 char* __chunk = _S_chunk_alloc(__n, __nobjs); _Obj* __STL_VOLATILE* __my_free_list; _Obj* __result; _Obj* __current_obj; _Obj* __next_obj; int __i; if (1 == __nobjs) return(__chunk); // 根据 __n 获取对应的空闲链表下标 __my_free_list = _S_free_list + _S_freelist_index(__n); /* Build free list in chunk */ // 将申请的大块内存 chunk 切分 __nobjs 个空间大小为 __n 的链表结点，并组织成一条自由空闲链表 __result = (_Obj*)__chunk; *__my_free_list = __next_obj = (_Obj*)(__chunk + __n); for (__i = 1; ; __i++) { __current_obj = __next_obj; __next_obj = (_Obj*)((char*)__next_obj + __n); if (__nobjs - 1 == __i) { __current_obj -> _M_free_list_link = 0; break; } else { __current_obj -> _M_free_list_link = __next_obj; } } return(__result); }
_S_chunk_alloc函数：申请空间。比较内存池剩余空间与本次申请的内存空间大小：
- 内存池剩余空间足够，则内存池一次分配相应大小的内存
- 内存池剩余空间不足，则判断剩余空间能否分割，若不能分割，则向堆上申请大块内存
template <bool __threads, int __inst> char* __default_alloc_template<__threads, __inst>::_S_chunk_alloc(size_t __size, int& __nobjs) { char* __result; // 本次申请的内存块大小 size_t __total_bytes = __size * __nobjs; // 内存池剩余空间大小 size_t __bytes_left = _S_end_free - _S_start_free; // 1、内存池剩余空间大小 > 本次申请的内存块大小， // 给它一次分配本次要申请的内存块大小 if (__bytes_left >= __total_bytes) { __result = _S_start_free; _S_start_free += __total_bytes; return(__result); } // 2、内存池剩余空间大小 < 本次申请的内存块大小，则判断内存池剩余空间大小是否足够分割 // 2.1、内存池剩余空间够分割，将内存池剩余空间分割成固定大小的内存块（用户指定大小__size ） else if (__bytes_left >= __size) { __nobjs = (int)(__bytes_left/__size); __total_bytes = __size * __nobjs; __result = _S_start_free; _S_start_free += __total_bytes; return(__result); } // 3、剩余的堆空间不够切分:__bytes_left = 0 < __size // 重新向堆上申请空间 else { // 计算需要申请的空间大小 size_t __bytes_to_get = 2 * __total_bytes + _S_round_up(_S_heap_size >> 4); // 内存池开始申请空间 _S_start_free = (char*)malloc(__bytes_to_get); _S_heap_size += __bytes_to_get; _S_end_free = _S_start_free + __bytes_to_get; // 递归调用 return(_S_chunk_alloc(__size, __nobjs)); } }
deallocate
- 回收的空间大于 128 字节，直接使用 free 回收空间
- 回收的空间小于等于 128 字节，直接链回自由空闲链表
static void deallocate(void* __p, size_t __n) { // 回收的空间大于 128 字节，直接使用 free 回收空间 if (__n > (size_t) _MAX_BYTES) malloc_alloc::deallocate(__p, __n); // 回收的空间小于等于 128 字节，采用链表头插法，将空闲链表结点重新挂回到空闲链表 else { // 获取空闲链表的首地址 _Obj* __STL_VOLATILE* __my_free_list = _S_free_list + _S_freelist_index(__n); // 链表的头插法 _Obj* __q = (_Obj*)__p; __q -> _M_free_list_link = *__my_free_list; *__my_free_list = __q; } }
源码流程分析
第一次申请 32 字节的空间
// 1、调用 _S_refill 函数 int __nobjs = 20; // 向 _S_chunk_alloc 申请 20 * 32 = 640 空间 char* __chunk = _S_chunk_alloc(__n, __nobjs); // 2、调用 _S_chunk_alloc 函数 size_t __total_bytes = __size * __nobjs; // __total_bytes = 32 * 20 = 640 size_t __bytes_left = _S_end_free - _S_start_free; // __bytes_left = 0 // 第一次申请空间 __bytes_left = 0 < __size else { // __bytes_to_get = 2 * 640 + 0 = 1280 size_t __bytes_to_get = 2 * __total_bytes + _S_round_up(_S_heap_size >> 4); // 向内存池申请 1280 个字节的空间 _S_start_free = (char*)malloc(__bytes_to_get); // _S_heap_size = 1280 _S_heap_size += __bytes_to_get; // _S_end_free = 1280 _S_end_free = _S_start_free + __bytes_to_get; // 递归调用自身 return(_S_chunk_alloc(__size, __nobjs)); } // 3、递归调用 _S_chunk_alloc 函数 char* __result; size_t __total_bytes = __size * __nobjs; // 32 * 20 = 640; size_t __bytes_left = _S_end_free - _S_start_free; // 1280 - 0 = 1280; // 1280 > 640 if (__bytes_left >= __total_bytes) { __result = _S_start_free; // __result = 640 _S_start_free += __total_bytes; // _S_start_free = 640 return(__result); } // 5、返回 _S_refill 函数 __result = (_Obj*)__chunk; *__my_free_list = __next_obj = (_Obj*)(__chunk + __n); // 将 640 空间大小切分成 20 个空间大小为 32 字节的链表结点，并组织成一条链表 for (__i = 1; ; __i++) { __current_obj = __next_obj; __next_obj = (_Obj*)((char*)__next_obj + __n); if (__nobjs - 1 == __i) { __current_obj -> _M_free_list_link = 0; break; } else { __current_obj -> _M_free_list_link = __next_obj; } } return(__result);
如图所示，可以看到 stl::allocator 内存空间消耗较大，只需要一个 32 字节的空间，就一次性申请了 1280 个字节，此时 640 字节的空间作为空闲链表，640 空间作为内存池备用。
第二次申请 64 字节的空间
// 1、调用 _S_refill 函数 int __nobjs = 20; // 向 _S_chunk_alloc 申请 20 * 64 = 1280 空间 char* __chunk = _S_chunk_alloc(__n, __nobjs); // 2、调用 _S_chunk_alloc 函数 size_t __total_bytes = __size * __nobjs; // __total_bytes = 64 * 20 = 1280 size_t __bytes_left = _S_end_free - _S_start_free; // __bytes_left = 1280 - 640 = 640 // __bytes_left: 640 > __size: 64 else if (__bytes_left >= __size) { // 剩余空间可以被分割为 640 / 64 = 10 个节点 __nobjs = (int)(__bytes_left/__size); __total_bytes = __size * __nobjs; __result = _S_start_free; _S_start_free += __total_bytes; return(__result); } // 3、返回 _S_refill 函数 __result = (_Obj*)__chunk; *__my_free_list = __next_obj = (_Obj*)(__chunk + __n); // 将 640 空间大小切分成 10 个空间大小为 64 字节的链表结点，并组织成一条链表 // 此时申请的堆空间全部分配完毕 for (__i = 1; ; __i++) { __current_obj = __next_obj; __next_obj = (_Obj*)((char*)__next_obj + __n); if (__nobjs - 1 == __i) { __current_obj -> _M_free_list_link = 0; break; } else { __current_obj -> _M_free_list_link = __next_obj; } } return(__result);
如图所示，内存池全部用于分配内存，申请的堆空间耗尽。生成的空闲链表，分配一个 64 字节的结点，剩余 9 个结点。
第三次申请 96 字节的空间
// 1、调用 _S_refill 函数 int __nobjs = 20; // 向 _S_chunk_alloc 申请 96 * 20 = 1920 空间 char* __chunk = _S_chunk_alloc(__n, __nobjs); // 2、调用 _S_chunk_alloc 函数 size_t __total_bytes = __size * __nobjs; // __total_bytes = 96 * 20 = 1920 size_t __bytes_left = _S_end_free - _S_start_free; // __bytes_left = 0 // 第一次申请空间 __bytes_left = 0 < __size else { // __bytes_to_get = 2 * 1920 + 80 = 3920 size_t __bytes_to_get = 2 * __total_bytes + _S_round_up(_S_heap_size >> 4); // 向内存池申请 3920 个字节的空间 _S_start_free = (char*)malloc(__bytes_to_get); // _S_heap_size = 1280 + 3920 = 5200 _S_heap_size += __bytes_to_get; _S_end_free = _S_start_free + __bytes_to_get; // 递归调用自身 return(_S_chunk_alloc(__size, __nobjs)); } // 3、递归调用 _S_chunk_alloc 函数 char* __result; size_t __total_bytes = __size * __nobjs; // 96 * 20 = 1920; size_t __bytes_left = _S_end_free - _S_start_free; // 3920; // 3920 > 1920 if (__bytes_left >= __total_bytes) { __result = _S_start_free; _S_start_free += __total_bytes; return(__result); } // 5、返回 _S_refill 函数 __result = (_Obj*)__chunk; *__my_free_list = __next_obj = (_Obj*)(__chunk + __n); // 将 1920 空间大小切分成 20 个空间大小为 96 字节的链表结点，并组织成一条链表 for (__i = 1; ; __i++) { __current_obj = __next_obj; __next_obj = (_Obj*)((char*)__next_obj + __n); if (__nobjs - 1 == __i) { __current_obj -> _M_free_list_link = 0; break; } else { __current_obj -> _M_free_list_link = __next_obj; } } return(__result);
第四次申请 72 字节的空间，堆空间耗尽，内存池耗尽
向后面大于 72 字节的链表借用结点，例如 96，将其分割为 24 + 72。
if (0 == _S_start_free) { size_t __i; _Obj* __STL_VOLATILE* __my_free_list; _Obj* __p; // if (i = 72; i <= 128; i += 8) for (__i = __size; __i <= (size_t) _MAX_BYTES; __i += (size_t) _ALIGN) { __my_free_list = _S_free_list + _S_freelist_index(__i); __p = *__my_free_list; // 找到了链表结点（96 > 72） // 将该 96 字节的结点分配给它 if (0 != __p) { *__my_free_list = __p -> _M_free_list_link; _S_start_free = (char*)__p; _S_end_free = _S_start_free + __i; return(_S_chunk_alloc(__size, __nobjs)); } }
3、allocator 问题
内存空间消耗比较大，内存不可控。如果硬件的性能不支持，例如嵌入式系统，则不能使用 std::allocator做内存的分配。
