空间配置器 (Allocator 的标准接口)
template<class _Tp>
class allocator {
typedef alloc _Alloc;
public:
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef _Tp *pointer;
typedef const _Tp *const_pointer;
typedef _Tp &reference;
typedef const _Tp &const_reference;
typedef _Tp value_type;
template<class _Tp1>
struct rebind {
typedef allocator<_Tp1> other;
};
allocator() __STL_NOTHROW {}
allocator(const allocator &) __STL_NOTHROW {}
template<class _Tp1>
allocator(const allocator<_Tp1>&) __STL_NOTHROW {}
~allocator() __STL_NOTHROW {}
pointer address(reference __x) const { return &__x; }
const_pointer address(const_reference __x) const { return &__x; }
_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));
}
size_type max_size() const __STL_NOTHROW {
return size_t(-1) / sizeof(_Tp);
}
void construct(pointer __p, const _Tp &__val) {
new(__p) _Tp(__val);
}
void destroy(pointer __p) {
__p->~_Tp();
}
};
上述是 C++ 标准设计的 Allocator 源代码,通过阅读我们获得一些启发:空间配置器不是单纯的使用 new 和 delete 来分配空间。
空间的分配分为两步:
- 先通过
::operator new 来申请原始内存空间,在这一步的时候就类似于 malloc 并不会构造对象。
- 再通过
placement new -> new(__p) T(value) 来构造对象并将对象放入 __p 指向的空间中。
空间的回收在注释中有写则不再重复。如此做的好处是,方便控制 STL 构造和析构对象的时机。
但是,SGI STL 并没有采用这种空间配置的方式,主要原因是在频繁分配小对象的时候效率不佳,且整个类只是对 ::operator new 和 ::operator delete 做了简单的封装。
SGI STL 则使用了一种与众不同的配置器 (alloc),它具有次配置力 (sub-allocation),且它不接受任何参数,它对配置器做了分级结构,分为一级配置器和二级配置器,尤其在分配小空间的时候效率极佳。
SGI 的特殊空间配置器 std::alloc
为了精密分工,在上面提到了,STL allocator 将 内存空间的配置/释放 和 对象内容的构造/析构 拆解开来,空间配置器写在 <memory> 中。
SGI 的 <memory> 则包含了这三个文件 (节选了与空间配置器有关的):
#include <stl_alloc.h>
#include <stl_construct.h>
#include <stl_uninitialized.h>
构造和析构的基本工具 construct() 和 destroy()
为了更好的理解构造和析构过程,节选一段 stl_construct.h 的源代码,观察对象构造和析构的过程。
#include <new.h>
template<class _T1, class _T2>
inline void _Construct(_T1 *__p, const _T2 &__value) {
new ((void*)__p) _T1(__value);
}
template<class _T1>
inline void _Construct(_T1 *__p) {
new ((void*)__p) _T1();
}
template<class _Tp>
inline void _Destroy(_Tp *__pointer) {
__pointer->~_Tp();
}
template<class _ForwardIterator>
inline void _Destroy(_ForwardIterator __first, _ForwardIterator __last) {
__destroy(__first, __last, __VALUE_TYPE(__first));
}
template<class _ForwardIterator, class _Tp>
inline __destroy(_ForwardIterator __first, _ForwardIterator __last, _Tp *) {
__type_traits<_Tp>::has_trivial_destructor _Trivial_destructor;
__destroy_aux(__first, __last, _Trivial_destructor());
}
< >
__destroy_aux(_ForwardIterator, _ForwardIterator, __true_type) {}
< >
__destroy_aux(_ForwardIterator __first, _ForwardIterator __last, __false_type) {
(; __first != __last; ++__first) (&*__first);
}
_Destroy(*, *) {}
_Destroy(*, *) {}
_Destroy(*, *) {}
_Destroy(*, *) {}
_Destroy(*, *) {}
从上述源码中可以观察到,stl 提供了一种通过迭代器大范围销毁对象的方式,但是我们也不知道这个范围有多大。如果这个范围很大 (上百万个对象),如果不分青红皂白一律调用 ~T() 就会大大损失性能,所以这里根据元素类型做了一些判断。
当使用传入两个迭代器析构对象时,函数会先判断元素数值类型,紧接着再去观察这种类型有没有 trivial destructor (编译器生成的析构)。如果有则不执行任何操作,如果是 non-trivial destructor 则按顺序依次执行析构函数。
下面举个例子来观察优化前后的区别:
vector<int> v(1000000);
当上面这个 vector 销毁时,如果不进行类型判断,就会默认调用 100 万次析构 (然而这个析构并无任何作用)。但是当进行优化后,整个过程不需要调用一次析构。
空间的配置和释放 std::alloc
C++ 内存的基本配置操作为 ::operator new,内存释放的基本操作为 ::operator delete 这俩全局函数,就相当于 C 的 malloc() 和 free(),而 SGI 正是通过 malloc() 和 free() 完成的内存配置和释放。
考虑到标准 allocator 无法解决小型区块导致内存破碎的问题,所以 SGI 配置了双层级配置器。一级配置器直接使用 malloc(), free(),而第二级配置器则根据不同情况来选择不同策略。
- 当配置区块大于 128byte 的时候,会被视为'足够大',会调用第一级配置器。
- 当配置区块小于 128byte 的时候,被视为'过小',则会使用复杂的 memory pool 方式来管理内存。
而是只使用第一级配置器还是同时开放第二级配置器则通过是否 define __USE_MALLOC 来决定 (但是不管无论如何,都要使用 malloc)。
#ifdef __USE_MALLOC
typedef __malloc_alloc_template<0> malloc_alloc;
typedef malloc_alloc alloc;
#else
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;
typedef __default_alloc_template<false, 0> single_client_alloc;
#endif
其中 __malloc_alloc_template 就是第一级配置器,__default_alloc_template 为第二级配置器。但是不管 alloc 被定义为第一或者第二级配置器,SGI 都会给它再包一层接口,使整个配置器能够符合 STL 的规格。
template<class _Tp, class _Alloc>
class simple_alloc {
public:
static _Tp *allocate(size_t __n) {
return 0 == __n ? 0 : (_Tp *)_Alloc::allocate(__n * sizeof(_Tp));
}
static _Tp *allocate(void) {
return (_Tp *)_Alloc::allocate(sizeof(_Tp));
}
static void deallocate(_Tp *__p, size_t __n) {
if (0 != __n) _Alloc::deallocate(__p, __n * sizeof(_Tp));
}
static void deallocate(_Tp *__p) {
_Alloc::deallocate(__p, sizeof(_Tp));
}
};
上述四个内部成员都是简单的转调用,调用传递给配置器 (可以是第一级也可以是第二级),配置单位则从 byte 转化到一个元素的大小。SGI 的所有 STL 容器都使用这个 simple_alloc 接口。
第一级配置器 __malloc_alloc_template 剖析
这里贴出第一级配置器源码,剖析则放在注释中。
template<int __inst>
class __malloc_alloc_template {
private:
static void *_S_oom_malloc(size_t);
static void *_S_oom_realloc(void*, size_t);
#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
static void (*__malloc_alloc_oom_handler)();
#endif
public:
static void *allocate(size_t __n) {
void *__result = malloc(__n);
if (0 == __result)
__result = _S_oom_malloc(__n);
return __result;
}
static void deallocate(void *__p, size_t ) {
free(__p);
}
static void *reallocate(void *__p, size_t , size_t __new_sz) {
*__result = (__p, __new_sz);
( == __result) __result = _S_oom_realloc(__p, __new_sz);
__result;
}
{
(*__old)() = __malloc_alloc_oom_handler;
__malloc_alloc_oom_handler = __f;
(__old);
}
};
= ;
< __inst>
*__malloc_alloc_template<__inst>::_S_oom_malloc( __n) {
(*__my_malloc_handler)();
*__result;
(;;) {
__my_malloc_handler = __malloc_alloc_oom_handler;
( == __my_malloc_handler) {
__THROW_BAD_ALLOC;
}
(*__my_malloc_handler)();
__result = (__n);
(__result) (__result);
}
}
< __inst>
*__malloc_alloc_template<__inst>::_S_oom_realloc( *__p, __n) {
(*__my_malloc_handler)();
*__result;
(;;) {
__my_malloc_handler = __malloc_alloc_oom_handler;
( == __my_malloc_handler) {
__THROW_BAD_ALLOC;
}
(*__my_malloc_handler)();
__result = (__p, __n);
(__result) (__result);
}
}
第一级配置器使用 malloc, realloc, free 等 C 语言函数来配置空间,同时还实现了类似 C++ new-handle 的机制。它无法直接使用 new-handle 机制,因为它没有使用 ::operator new,而是使用了 malloc。
new-handle 机制:当系统无法满足用户的内存配置要求时,调用一个用户所指定的函数,即在调用 ::operator new 时内存空间不足,在抛出 bad_alloc() 之前,会先调用用户传入的处理例程。
第一级配置器在调用 allocate 和 reallocate 失败后就会执行 _S_oom_malloc 和 _S_oom_realloc,希望可以通过用户传入的方法来找到一些空内存,但是当用户没有传入方法的时候,则会直接抛出 bad_alloc 异常。
第二级配置器 __default_alloc_template
第二级配置器多了一些机制,避免太多小额区块造成的内存的碎片 (主要解决的是内碎片问题)。第二层配置器会将大于 128byte 的内存配置交给第一层配置器,而小于 128byte 的则使用 memory pool 来管理。
- 每次将会配置一大块内存,并维护 free-list。
- 如果下次有相同的内存配置请求则直接去查找对应的 free-list,从 free-list 中取出一个空间的内存块。
- 当内存被归还时,也会查找对应大小的 free-list 并挂到上面。
- 为了方便管理,会将内存申请自动对齐 (RoundUp) 到 8 的倍数,free-list 的个数 = 128 / 8 = 16 个。
下面是第二级内存配置器实现部分源码。
enum { _ALIGN = 8 };
enum { _MAX_BYTES = 128 };
enum { _NFREELISTS = 16 };
template<bool threads, int inst>
class __default_alloc_template {
private:
static size_t _S_round_up(size_t __bytes) {
return (((__bytes) + (size_t)_ALIGN - 1) & ~((size_t)_ALIGN - 1));
}
__PRIVATE:
{
*_M_free_list_link;
_M_client_data[];
};
:
_Obj *__STL_VOLATILE _S_free_list[];
_S_freelist_index( __bytes) {
(((__bytes) + ()_ALIGN - ) / ()_ALIGN - );
}
*_S_refill( __n);
*_S_chunk_alloc( __size, &__nobjs);
*_S_start_free;
*_S_end_free;
_S_heap_size;
:
{
*__ret = ;
(__n > ()_MAX_BYTES) {
__ret = malloc_alloc::(__n);
} {
_Obj *__STL_VOLATILE *__my_free_list = _S_free_list + _S_freelist_index(__n);
_Obj *__RESTRICT __result = *__my_free_list;
(__result == )
__ret = _S_refill(_S_round_up(__n));
{
*__my_free_list = __result->_M_free_list_link;
__ret = __result;
}
}
__ret;
}
{
(__n > ()_MAX_BYTES) malloc_alloc::(__p, __n);
{
_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;
}
}
;
};
< __threads, __inst>
*__default_alloc_template<__threads, __inst>::_S_refill( __n) {
__nobjs = ;
*__chunk = _S_chunk_alloc(__n, __nobjs);
_Obj *__STL_VOLATILE *__my_free_list;
_Obj *__result;
_Obj *__current_obj;
_Obj *__next_obj;
__i;
( == __nobjs) (__chunk);
__my_free_list = _S_free_list + _S_freelist_index(__n);
__result = (_Obj *)__chunk;
*__my_free_list = __next_obj = (_Obj *)(__chunk + __n);
(__i = ;; __i++) {
__current_obj = __next_obj;
__next_obj = (_Obj *)((*)__next_obj + __n);
(__nobjs - == __i) {
__current_obj->_M_free_list_link = ;
;
} {
__current_obj->_M_free_list_link = __next_obj;
}
}
(__result);
}
< __threads, __inst>
*__default_alloc_template<__threads, __inst>::_S_chunk_alloc( __size, &__nobjs) {
*__result;
__total_bytes = __size * __nobjs;
__bytes_left = _S_end_free - _S_start_free;
(__bytes_left >= __total_bytes) {
__result = _S_start_free;
_S_start_free += __total_bytes;
(__result);
} (__bytes_left >= __size) {
__nobjs = ()(__bytes_left / __size);
__total_bytes = __size * __nobjs;
__result = _S_start_free;
_S_start_free += __total_bytes;
(__result);
} {
__bytes_to_get = * __total_bytes + _S_round_up(_S_heap_size >> );
(__bytes_left > ) {
_Obj *__STL_VOLATILE *__my_free_list = _S_free_list + _S_freelist_index(__bytes_left);
((_Obj *)_S_start_free)->_M_free_list_link = *__my_free_list;
*__my_free_list = (_Obj *)_S_start_free;
}
_S_start_free = (*)(__bytes_to_get);
( == _S_start_free) {
__i;
_Obj *__STL_VOLATILE *__my_free_list;
_Obj *__p;
(__i = __size; __i <= ()_MAX_BYTES; __i += ()_ALIGN) {
__my_free_list = _S_free_list + _S_freelist_index(__i);
__p = *__my_free_list;
( != __p) {
*__my_free_list = __p->_M_free_list_link;
_S_start_free = (*)__p;
_S_end_free = _S_start_free + __i;
(_S_chunk_alloc(__size, __nobjs));
}
}
_S_end_free = ;
_S_start_free = (*)malloc_alloc::(__bytes_to_get);
}
_S_heap_size += __bytes_to_get;
_S_end_free = _S_start_free + __bytes_to_get;
(_S_chunk_alloc(__size, __nobjs));
}
}
< threads, inst>
*__default_alloc_template<threads, inst>::( *__p, __old_sz, __new_sz) {
*__result;
__copy_sz;
(__old_sz > ()_MAX_BYTES && __new_sz > ()_MAX_BYTES) {
((__p, __new_sz));
}
(_S_round_up(__old_sz) == _S_round_up(__new_sz)) (__p);
__result = (__new_sz);
__copy_sz = __new_sz > __old_sz ? __old_sz : __new_sz;
(__result, __p, __copy_sz);
(__p, __old_sz);
(__result);
}
以上便是第二级配置器的完整实现。
uninitialized_xx
STL 定义五个全局函数,作用于未初始化的空间上,前两个函数是 construct() 和 destroy(),剩下的三个就是 uninitialized_xx 类型函数,具体分为:uninitialized_copy(), uninitialized_fill(), uninitialized_fill_n()。
uninitialized_copy()
该函数接收三个参数,迭代器 first, last, result。first 和 last 指向输出的起始和结尾,result 指向输出端。
template<class _InputIter, class _ForwardIter>
inline _ForwardIter __uninitialized_copy_aux(_InputIter __first, _InputIter __last, _ForwardIter __result, __true_type) {
return copy(__first, __last, __result);
}
template<class _InputIter, class _ForwardIter>
_ForwardIter __uninitialized_copy_aux(_InputIter __first, _InputIter __last, _ForwardIter __result, __false_type) {
_ForwardIter __cur = __result;
__STL_TRY {
for (; __first != __last; ++__first, ++__cur)
_Construct(&*__cur, *__first);
return __cur;
}
__STL_UNWIND(_Destroy(__result, __cur));
}
template<class _InputIter, class _ForwardIter, class _Tp>
inline _ForwardIter __uninitialized_copy(_InputIter __first, _InputIter __last, _ForwardIter __result, _Tp *) {
typedef typename __type_traits<_Tp>::is_POD_type _Is_POD;
return __uninitialized_copy_aux(__first, __last, __result, _Is_POD());
}
template<class _InputIter, class _ForwardIter>
inline _ForwardIter uninitialized_copy(_InputIter __first, _InputIter __last, _ForwardIter __result) {
return __uninitialized_copy(__first, __last, __result, __VALUE_TYPE(__result));
}
{
(__result, __first, __last - __first);
__result + (__last - __first);
}
{
(__result, __first, () * (__last - __first));
__result + (__last - __first);
}
uninitialized_fill()
template<class _ForwardIter, class _Tp>
inline void __uninitialized_fill_aux(_ForwardIter __first, _ForwardIter __last, const _Tp &__x, __true_type) {
fill(__first, __last, __x);
}
template<class _ForwardIter, class _Tp>
void __uninitialized_fill_aux(_ForwardIter __first, _ForwardIter __last, const _Tp &__x, __false_type) {
_ForwardIter __cur = __first;
__STL_TRY {
for (; __cur != __last; ++__cur)
_Construct(&*__cur, __x);
}
__STL_UNWIND(_Destroy(__first, __cur));
}
template<class _ForwardIter, class _Tp, class _Tp1>
inline void __uninitialized_fill(_ForwardIter __first, _ForwardIter __last, const _Tp &__x, _Tp1 *) {
typedef typename __type_traits<_Tp1>::is_POD_type _Is_POD;
__uninitialized_fill_aux(__first, __last, __x, _Is_POD());
}
template<class _ForwardIter, class _Tp>
inline void uninitialized_fill(_ForwardIter __first, _ForwardIter __last, const _Tp &__x) {
__uninitialized_fill(__first, __last, __x, __VALUE_TYPE(__first));
}
uninitialized_fill_n()
template<class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter __uninitialized_fill_n_aux(_ForwardIter __first, _Size __n, const _Tp &__x, __true_type) {
return fill_n(__first, __n, __x);
}
template<class _ForwardIter, class _Size, class _Tp>
_ForwardIter __uninitialized_fill_n_aux(_ForwardIter __first, _Size __n, const _Tp &__x, __false_type) {
_ForwardIter __cur = __first;
__STL_TRY {
for (; __n > 0; --__n, ++__cur)
_Construct(&*__cur, __x);
return __cur;
}
__STL_UNWIND(_Destroy(__first, __cur));
}
template<class _ForwardIter, class _Size, class _Tp, class _Tp1>
inline _ForwardIter __uninitialized_fill_n(_ForwardIter __first, _Size __n, const _Tp &__x, _Tp1 *) {
typedef typename __type_traits<_Tp1>::is_POD_type _Is_POD;
return __uninitialized_fill_n_aux(__first, __n, __x, _Is_POD());
}
template<class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter uninitialized_fill_n(_ForwardIter __first, _Size __n, const _Tp &__x) {
return __uninitialized_fill_n(__first, __n, __x, __VALUE_TYPE(__first));
}
综上所述,uninitialized_*() 类别的函数执行流程如下:
- 在
uninitialized_*() 中执行 __uninitialized_*()。
- 在
__uninitialized_*() 中判断传入迭代器类型进行判断。
- 如果是 POD 则使用高阶函数 (特化
char*, wchar*,使用 memmove() 直接进行内存移动)。
- 如果非 POD 则使用循环 + constructor() 构造对象。