首页 > STL源码剖析 > STL笔记之空间配置器

STL笔记之空间配置器

最近看了看侯捷的《STL源码剖析》,打算看完之后写写笔记,毕竟很多东西看起来看懂了,却并不一定能够将其描述清楚,说到底还是没有彻底弄明白,最近博客也基本不怎么写了,所以还是决定写一写,这也算是写博客的乐趣之一吧。这一系列笔记,更主要是写给自己看的:)

1. 初探allocator
其实像我这样的一般人几乎接触不到allocator这种东西,因为这个模板参数是有默认值的,普通用户完全不需要和他打交道。但观察一下allocator这个东西的设计思路,还是可以学到不少东西。先从一个简单的allocator源代码看起:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#ifndef _JJALLOC_
#define _JJALLOC_
 
#include <new>
#include <cstddef>
#include <cstdlib>
#include <climits>
#include <iostream>
 
namespace JJ
{
    // 使用operator new分配空间
    template<class T>
    inline T* _allocate(ptrdiff_t size, T*)
    {
        std::set_new_handler(0);
        T *tmp = (T*)(::operator new((size_t)(size * sizeof(T))));
        if (tmp == 0)
        {
            std::cerr << "out of memory" << std::endl;
            exit(1);
        }
        return tmp;
    }
    // 使用operator delete回收空间
    template<class T>
    inline void _deallocate(T* buffer)
    {
        ::operator delete(buffer);
    }
    // 在指定内存上构造一个对象
    template<class T1, class T2>
    inline void _construct(T1* p, const T2& value)
    {
        // placement new
        new (p) T1(value);
    }
    // 析构一个对象
    template<class T>
    inline void _destroy(T* ptr)
    {
        ptr->~T();
    }
    // 遵循allocator的标准定义相关结构
    template<class T>
    class allocator
    {
    public:
        typedef T           value_type;
        typedef T*          pointer;
        typedef const T*    const_pointer;
        typedef T&          reference;
        typedef const T&    const_reference;
        typedef size_t      size_type;
        typedef ptrdiff_t   difference_type;
 
        template<class U>
        struct rebind
        {
            typedef allocator<U> other;
        };
 
        pointer allocate(size_type n, const void* hint=0)
        {
            return _allocate((difference_type)n, (pointer)0);
        }
 
        void deallocate(pointer p, size_type n)
        {
            _deallocate(p);
        }
 
        void construct(pointer p, const T& value)
        {
            _construct(p, value);
        }
 
        void destroy(pointer p)
        {
            _destroy(p);
        }
 
        pointer address(reference x)
        {
            return (pointer)&x;
        }
 
        const_pointer const_address(const_reference x)
        {
            return (const_pointer)&x;
        }
 
        size_type max_size() const
        {
            return size_type(UINT_MAX/sizeof(T));
        }
    };
}
 
#endif

上面的代码之中的几个点:
1. set_new_handler
set_new_handler的函数原型如下:

typedef void (*new_handler)();
new_handler set_new_handler (new_handler new_p) throw();

使用set_new_handler可以设置一个函数new_p,当使用new/operator new分配内存失败时,new_p将被调用。new_p将尝试使得更多内存空间可用,以使得接下来的内存分配操作能够成功。如果new_p指向NULL(默认就是NULL),那么将会抛出bad_alloc异常,这也是为什么我们默认使用new失败的时候将会抛出bad_alloc异常的原因;

2. 几个new/delete操作
我们使用的new叫做new operator,包括两个步骤,一是调用operator new来分配指定大小的内存空间,然后调用构造函数;所以如果只是进行空间分配操作,那么使用operator new就可以了,就好比C的malloc函数;如果已经分配好了空间,想在上面构造一个对象,那么可以使用placement new,上面的_construct函数里面调用的就是placement new;

3. 如何使用这个allocator?
定义vector时有一个模板参数用于指定allocator,如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include "jjalloc.h"
#include <vector>
#include <iostream>
using namespace std;
 
int main(int argc, char **argv)
{
    int ia[5] = {0, 1, 2, 3, 4};
    unsigned int i;
    vector<int, JJ::allocator<int> > iv(ia, ia+5);
    for (i = 0; i < iv.size(); ++i)
    {
        cout << iv[i] << " ";
    }
    cout << endl;
 
    return 0;
}

2. 构造与析构
在stl_construct.h中定义了构造和析构的相关函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
// 调用placement new,根据__value在__p上构造一个对象
template <class _T1, class _T2>
inline void _Construct(_T1* __p, const _T2& __value) {
  new ((void*) __p) _T1(__value);
}
 
// 调用placement new在__p上构造一个对象,使用默认构造函数
template <class _T1>
inline void _Construct(_T1* __p) {
  new ((void*) __p) _T1();
}
 
// 析构一个对象
template <class _Tp>
inline void _Destroy(_Tp* __pointer) {
  __pointer->~_Tp();
}
 
// 析构迭代器__first和__last之间的对象,实际上通过destroy函数,调用了对应的析构函数
template <class _ForwardIterator>
void
__destroy_aux(_ForwardIterator __first, _ForwardIterator __last, __false_type)
{
  for ( ; __first != __last; ++__first)
    destroy(&*__first);
}
 
// __destroy_aux重载函数,这里是对于trivial析构函数,不进行任何处理,提高效率
template <class _ForwardIterator> 
inline void __destroy_aux(_ForwardIterator, _ForwardIterator, __true_type) {}
 
// 根据__type_traits萃取出类型_Tp的析构函数是否是trivial的,编译器根据类型自动选择对应的__destroy_aux
template <class _ForwardIterator, class _Tp>
inline void 
__destroy(_ForwardIterator __first, _ForwardIterator __last, _Tp*)
{
  typedef typename __type_traits<_Tp>::has_trivial_destructor
          _Trivial_destructor;
  __destroy_aux(__first, __last, _Trivial_destructor());
}
 
template <class _ForwardIterator>
inline void _Destroy(_ForwardIterator __first, _ForwardIterator __last) {
  __destroy(__first, __last, __VALUE_TYPE(__first));
}
 
inline void _Destroy(char*, char*) {}
inline void _Destroy(int*, int*) {}
inline void _Destroy(long*, long*) {}
inline void _Destroy(float*, float*) {}
inline void _Destroy(double*, double*) {}
#ifdef __STL_HAS_WCHAR_T
inline void _Destroy(wchar_t*, wchar_t*) {}
#endif /* __STL_HAS_WCHAR_T */
 
// --------------------------------------------------
// Old names from the HP STL.
 
template <class _T1, class _T2>
inline void construct(_T1* __p, const _T2& __value) {
  _Construct(__p, __value);
}
 
template <class _T1>
inline void construct(_T1* __p) {
  _Construct(__p);
}
 
template <class _Tp>
inline void destroy(_Tp* __pointer) {
  _Destroy(__pointer);
}
 
template <class _ForwardIterator>
inline void destroy(_ForwardIterator __first, _ForwardIterator __last) {
  _Destroy(__first, __last);
}
 
__STL_END_NAMESPACE

这里值得一提的主要是析构部分使用的一些技巧。首先解释一下所谓的trivial destructor,值得就是调用不调用都无所谓的析构函数,那么处于效率方面的考虑,在这样的情况下肯定选择什么都不做(如果进行十万百万次这样的函数调用,是不是就白白浪费了大好的时光了?)而且这里是在编译器就通过函数的重载来决定是否要调用析构函数。

具体是通过__type_traits来萃取出类型是否具有trivial destructor的,这里在后面的文章会提到这些细节。现在所要了解的就是通过__type_traits可以萃取出类型的destructor特性(trivial or non-trivial),然后通过函数重载来决定具体进行什么样的操作。

The implicitly-declared destructor for class T is trivial if all of the following is true:
  The destructor is not virtual (that is, the base class destructor is not virtual)
  All direct base classes have trivial destructors
  All non-static data members of class type (or array of class type) have trivial destructors
A trivial destructor is a destructor that performs no action. Objects with trivial destructors 
don't require a delete-expression and may be disposed of by simply deallocating their storage. 
All data types compatible with the C language (POD types) are trivially destructible.

3. 两级空间配置器
SGI STL提供两级空间配置器,第一级空间配置器使用malloc/free函数,当分配的空间大小超过128 bytes的时候使用第一级空间配置器;第二级空间配置器使用了内存池技术,当分配的空间大小小雨128 bytes的时候,将使用第二级空间配置器。

大量分配小块的内存空间会带来问题:一是从运行库的堆管理器中取得的内存(比如通过malloc获得的内存),会有一部分空间用于存储管理信息,用于管理各个内存块,这样内存的使用率就降低了;二是过多的小块内存会带来内存碎片问题;采用合适的内存池技术可以避免这些问题。

SGI STL的第二级内存配置器维护了一个free-list数组,分别用于管理8,16,24,32,40,48,56,64,72,80,88,96,104,112,120,128 bytes的小额区块,free-list的节点结构如下:

union obj
{
    union obj* free_list_link;
    char client_data[1];
};

这里使用union结构,是为了节省空间,也就是说,当节点位于free-list时,通过free_list_link指向下一块内存,而当节点取出来分配给用户使用的时候,整个节点的内存空间对于用户而言都是可用的,这样在用户看来,就完全意识不到free_list_link的存在,可以使用整块的内存了。

在分配内存时,会将大小向上调整为8的倍数,因为free-list中的节点大小全是8的倍数。

    enum {_ALIGN = 8};
    enum {_MAX_BYTES = 128};
    enum {_NFREELISTS = 16}; // _MAX_BYTES/_ALIGN
  // 将待分配的空间大小向上调整为8的倍数
  static size_t
  _S_round_up(size_t __bytes) 
    { return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1)); }
 
__PRIVATE:
  union _Obj {
        union _Obj* _M_free_list_link;
        char _M_client_data[1];    /* The client sees this.        */
  };
private:
  // 定义free_list数组
  static _Obj* __STL_VOLATILE _S_free_list[_NFREELISTS]; 
  // 根据空间大小取得free_list数组的对应下标
  static  size_t _S_freelist_index(size_t __bytes) {
        return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1);
  }

空间的分配:就是从对应的free-list节点链表中取出一个节点返回给用户,当然,如果没有可用的节点的话就要通过refill来分配新的节点了,后面会有描述:

  static void* allocate(size_t __n)
  {
    void* __ret = 0;
    // 如果大于128 bytes,则使用第一级空间配置器
    if (__n > (size_t) _MAX_BYTES) {
      __ret = malloc_alloc::allocate(__n);
    }
    else {
      // 通过大小取得free-list数组下标,随后取得对应节点的指针
      // 相当于&_S_free_list[_S_freelist_index(__n)]
      _Obj* __STL_VOLATILE* __my_free_list
          = _S_free_list + _S_freelist_index(__n);
      _Obj* __RESTRICT __result = *__my_free_list;
      // 如果没有可用的节点,则通过_S_refill分配新的节点
      if (__result == 0)
        __ret = _S_refill(_S_round_up(__n));
      else {
        // 将当前节点移除,并当做结果返回给用户使用
        *__my_free_list = __result -> _M_free_list_link;
        __ret = __result;
      }
    }
 
    return __ret;
  };

从free-list中摘取节点返回给用户使用的示意图如下:(配图来自《STL源码剖析》一书)
从free-list中摘取节点分配给用户使用
而空间的回收,则是把内存重新加入到free-list对应的节点链表上去。

那么,当对应的free-list链表中没有可用节点的时候,refill进行了怎样的操作呢?默认操作时通过_S_chunk_alloc从内存池中取得20个新的节点添加到free-list链表中,当然,内存池中的内存不够用也是会出现的情况之一,这时候能分多少就分多少节点,再万一内存池一个节点都提供不了了,那就内存池需要新增空间了,如果失败,再抛出bad_alloc异常。

template <bool __threads, int __inst>
void*
__default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
{
    int __nobjs = 20;
    // 通过内存池分配内存,第二个参数为传引用方式
    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);
    // 如果分配了不止一个节点,那么多余的我们要放到free-list里面去
    __my_free_list = _S_free_list + _S_freelist_index(__n);
 
    /* Build free list in chunk */
      __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) {
            // 最后一个节点的_M_free_list_link指针指向NULL,并跳出循环
            __current_obj -> _M_free_list_link = 0;
            break;
        } else {
            __current_obj -> _M_free_list_link = __next_obj;
        }
      }
    return(__result);
}

4. 内存池
通过_S_chunk_alloc,从内存池中分配空间给free-list:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
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;
 
    // 如果剩余大小满足要求,那么直接操作对应的指针即可
    if (__bytes_left >= __total_bytes) {
        __result = _S_start_free;
        _S_start_free += __total_bytes;
        return(__result);
    }
    // 剩余大小不够,但是至少还能分配一个节点
    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);
    }
    // 一个节点的空间都不够了
    else {
        // 新申请的空间为2倍大小
        size_t __bytes_to_get = 
	  2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
        // Try to make use of the left-over piece.
        // 如果还有剩余的空间,加入对应的free-list节点的链表
        if (__bytes_left > 0) {
            _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 = (char*)malloc(__bytes_to_get);
        // 如果操作失败
        if (0 == _S_start_free) {
            size_t __i;
            _Obj* __STL_VOLATILE* __my_free_list;
            _Obj* __p;
            // Try to make do with what we have.  That can't
            // hurt.  We do not try smaller requests, since that tends
            // to result in disaster on multi-process machines.
            // 看看free-list数组中,是否有更大尺寸的可用节点
            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;
                // 如果有可用节点则摘一个下来给内存池使用
                if (0 != __p) {
                    *__my_free_list = __p -> _M_free_list_link;
                    _S_start_free = (char*)__p;
                    _S_end_free = _S_start_free + __i;
                    // 递归调用自身,修正__nobjs
                    return(_S_chunk_alloc(__size, __nobjs));
                    // Any leftover piece will eventually make it to the
                    // right free list.
                }
            }
            // 如果没有可用节点,则只能指望第一级空间配置器了
            _S_end_free = 0;	// In case of exception.
            _S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);
            // This should either throw an
            // exception or remedy the situation.  Thus we assume it
            // succeeded.
        }
        _S_heap_size += __bytes_to_get;
        _S_end_free = _S_start_free + __bytes_to_get;
        // 递归调用自身,修正__nobjs
        return(_S_chunk_alloc(__size, __nobjs));
    }
}

_S_chunk_alloc的流程总结如下:
1. 内存池有足够大小的空间,则分配申请的空间;
2. 内存池没有足够大小的空间,但是至少还能分配一个节点的空间,则能分多少分多少;
3. 内存池一个节点都腾不出来了,向系统的heap申请2倍于要求大小的空间,在此之间,如果内存池剩余有空间,则放到free-list中去;
4. 如果向heap申请空间失败,那么只能看free-list中更大的节点是否有可用空间了,有则用之,同时递归调用自身修正__nobjs;
5. 如果free-list也没有可用节点了,那么转向第一级空间配置器申请空间;
6. 再不行,第一级空间配置器就要抛出bad_alloc异常了;

注意如果有需求的话,内存池中会不断的通过malloc申请新的内存,最后内存池所拥有的内存也会越来越大,当然最后进程结束的时候,这些内存都会由操作系统收回。

5. 内存基本处理工具
STL提供了五个全局函数用于处理空间,分别为:
1. construct 用于构造;
2. destroy 用于析构;
3. uninitialized_copy(first, last, result) 将[first,last)范围内的对象复制到result处;
4. uninitiated_fill(first, last, X) 将[first,last)范围内的内存用对象X的副本填充;
5. uninitiated_fill_n(first, n, X) 将first开始的n个连续的内存空间用X的副本填充;

前面提到对于destroy的实现,如果对象的析构函数是trivial的,那么什么都不用做,同样的,对于uninitialized_copy和uninitiated_fill / uninitiated_fill_n,如果对象时POD类型,那么可以直接通过复制内存的方式来实现,对于普通的POD类型,通过上层的copy函数来实现复制填充,对于char*/wchar_t*,则提供对应的特化版本,通过memmove实现(和memcpy相比,memmove支持重叠内存操作);如果不是POD类型,那么就只能通过construct实现了。

关于POD类型:

可见,POD类类型就是指class、struct、union,且不具有用户定义的构造函数、析构函数、拷贝算子、赋值算子;不具有继承关系,
因此没有基类;不具有虚函数,所以就没有虚表;非静态数据成员没有私有或保护属性的、没有引用类型的、没有非POD类类型的
(即嵌套类都必须是POD)、没有指针到成员类型的(因为这个类型内含了this指针)。

简单的说直接的内存复制操作对POD类型没有影响,比如用memset进行初始化,但这对于非POD类型是不可行的,比如存在虚函数的情况下。

判断一个类型是否是POD类型,也是通过__type_traits萃取出来的。

 
// POD类型,通过高层的copy实现
template <class _InputIter, class _ForwardIter>
inline _ForwardIter 
__uninitialized_copy_aux(_InputIter __first, _InputIter __last,
                         _ForwardIter __result,
                         __true_type)
{
  return copy(__first, __last, __result);
}
 
// 非POD类型,通过调用_Construct进行构造对象
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));
}
 
// 中间函数,通过__type_traits<_Tp>::is_POD_type萃取出POD类型
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));
}
 
// char* 特化版本
inline char* uninitialized_copy(const char* __first, const char* __last,
                                char* __result) {
  memmove(__result, __first, __last - __first);
  return __result + (__last - __first);
}
 
// wchar_t* 特化版本
inline wchar_t* 
uninitialized_copy(const wchar_t* __first, const wchar_t* __last,
                   wchar_t* __result)
{
  memmove(__result, __first, sizeof(wchar_t) * (__last - __first));
  return __result + (__last - __first);
}

具体的实现方法的选择示意图如下:

uninitiated_copy实现版本选择

uninitiated_copy实现版本选择

参考
std::set_new_handler http://www.cplusplus.com/reference/new/set_new_handler/
trivial destructor http://en.cppreference.com/w/cpp/language/destructor
POD http://zh.wikipedia.org/wiki/POD_(%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1)


觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> STL笔记之空间配置器
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



  1. ydc
    2014年11月26日21:17 | #1

    博主,你这关于STL文章 请问能不能转载。。

    [回复]

    代码疯子 回复:

    @ydc, 可以的,这也是自己看书的时候做的一些笔记,非商业用途欢迎转载,转载还请保留出处,谢谢

    [回复]

  1. 本文目前尚无任何 trackbacks 和 pingbacks.