SGI空间配置器

标准配置器

SGI定义有一个符合标准的配置器std::allocator，但这个配置器并没有对内存分配做任何优化，只是对::operator new 和 ::operator delete 做 一 层 薄 薄 的 包 装 而 已。SGI并没有使用这个配置器，也不建议我们使用。

特殊配置器std::alloc

std::alloc是一个特殊的配置器，并不符合标准规范，如STL规范规定配置器必须拥有名为 construct() 和 destroy() 的两个成员函数，但std::alloc就没有这两个函数。
但SGI真正使用的配置器就是std::alloc,SGI STL每个容器都指定std::alloc为其默认配置器。

template <class T, class Alloc = alloc> // 使用 alloc 为配置器
class vector { ... };

new和delete表达式：

平时我们new一个类的时候如：

Complex* pc = new Complex(1,2);

编译器会转为：

Complex *pc;
try{
      void*  mem = operator new(sizeof(Complex));   //(1)
      pc = static_cast<Complex*>(mem);
      pc->Complex::Complex(1,2);       //(2)
}
catch(std::bad_alloc){}

就是把表达式new分为两个操作，(1)调用operator new函数配置内存；(2)调用类的构造函数。

//编译器内部
pc->~Complex();   //(1)
operator delete(pc); //(2)

调用delete表达式也一样，(1)调用类析构函数；(2)调用operator delete函数释放内存。
std::alloc配置器把这两个阶段的操作区分开来，内存配置动作由alloc:allocate() 负责，内存释放动作由 alloc::deallocate() 负责；对象建构动作由 ::construct() 负责，对象解构动作由 ::destroy() 负责。且这几个函数分别位于两个文件中：

#include <stl_alloc.h>  // 负责内存空间的配置与释放
#include <stl_construct.h>   // 负责对象内容的建构与解构

负责构造和析构的两个函数 construct() 和 destroy()

construct()：

#include <new.h> // 欲使用 placement new ，需先含入此檔
template <class T1, class T2>
inline void construct(T1* p, const T2& value) {
     new (p) T1(value);
     /*new (p) T1(value):
    上面已经说过，new表达式在编译器内被分成两个阶段操作，这里也一样，会被分成：
    T1*pc;
    void*  mem = operator new(sizeof(T1),p);   //(1)
    pc = static_cast<T1*>(mem);
    pc->Complex::Complex(1,2);       //(2)
    
    //operator new什么都没做，只是返回传入的指针
    void* operator new(size_t size,void* start){
            return start;
    }
    所以new (p) T1(value)；相当于只是调用了T1的构造函数
  */
}

destroy()

destroy有两个版本：

// 以下是 destroy() 第一版本，接受参数。
template <class T>
inline void destroy(T* pointer) {
        pointer->~T();  // 唤起 dtor ~T()
}
// 以下是 destroy() 第二版本，接受两个迭代器。此函式设法找出元素的数值型别，
// 进而利用 __type_traits<> 求取最适当措施。
template <class ForwardIterator>
inline void destroy(ForwardIterator first, ForwardIterator last) {
      __destroy(first, last, value_type(first));
}

第二个版本关联的函数：

// 判断元素的数值型别（ value type ）是否有 trivial destructor
template <class ForwardIterator, class T>
inline void __destroy(ForwardIterator first, ForwardIterator last, T*)
{
       typedef typename __type_traits<T>::has_trivial_destructor trivial_destructor;
       __destroy_aux(first, last, trivial_destructor());
}
// 如果元素的数值型别（ value type ）有 non-trivial destructor…
template <class ForwardIterator>
inline void
__destroy_aux(ForwardIterator first, ForwardIterator last, __false_type) {
      for ( ; first < last; ++first)
          destroy(&*first);
}
// 如果元素的数值型别（ value type ）有 trivial destructor…
template <class ForwardIterator>
inline void __destroy_aux(ForwardIterator, ForwardIterator, __true_type) {}

// 以下是 destroy() 第二版本针对迭代器为 char* 和 wchar_t* 的特化版
inline void destroy(char*, char*) {}
inline void destroy(wchar_t*, wchar_t*) {}

destroy示意图.png

第二个版本泛化的会去判断对象的析构函数释放是否是trivial destructor，如果是就什么都不做（也就是不调用对象的析构函数，对untrivial destructor的最终做的也只是调用对象析构函数），如果不是就一个个调用对象析构函数。析构函数的作用就是释放其对象中手动分配的内存，如果析构函数中没有释放内存的操作，那么调不调用析构函数都无所谓，当然平时写程序不提倡这么做，养成好习惯。所以在destroy()中，如果对象析构函数是trivial destructor（如基本内置类型），则析构函数内就没有释放内存操作，就什么都不用做，若是untrivial destructor，说明析构函数内有可能有释放内存操作，就必须一个个调用析构函数，否则会内存泄露。

空间配置和释放

内存管理1.png

C++中，分配器(allocator)、new、new[]等内存配置操作最终都是经过malloc和free来完成内存的配置和释放。
SGI采用了双层级配置器，第一级直接使用malloc()和free(),第二级则根据需要配置的大小决定，如果需要配置区块超过128bytes时，调用第一级配置器配置（在下面源码中可以看到），如果不超过128bytes，为了避免太多小区块造成内存碎片和减少额外负担（去除cookie，减少浪费内存），采用复杂的memory pool的管理方式。

static void * allocate(size_t n)
{
        // .........
        // 大于 128 就呼叫第一级配置器
        if (n > (size_t) __MAX_BYTES)
            return(malloc_alloc::allocate(n));
            /*malloc_alloc::allocate就是调用malloc:
            static void * allocate(size_t n)
            {
                  void *result = malloc(n);
                  if (0 == result) result = oom_malloc(n);
                  return result;
             }
            */
       }
      // .........
}

simple_alloc

为了让配置器接口符合STL规格（ std::alloc 并不接受任何 template 型别参数），SGI还为sdt::alloc包装一个接口：

template<class T, class Alloc>
class simple_alloc {
public:
    static T *allocate(size_t n)
    {
        return 0 == n ? 0 : (T*)Alloc::allocate(n * sizeof(T));
    }
    static T *allocate(void)
    {
        return (T*)Alloc::allocate(sizeof(T));
    }
    static void deallocate(T *p, size_t n)
    {
        if (0 != n) Alloc::deallocate(p, n * sizeof(T));
    }
    static void deallocate(T *p)
    {
        Alloc::deallocate(p, sizeof(T));
    }
}; 

std::alloc接收的参数是bytes，一次配置和释放多少个字节，包装后的simple_alloc接收的参数是元素的个数，一次配置和释放多少个元素。
SGI STL容器都使用simple_alloc这个接口。如：

template <class T, class Alloc = alloc> // 预设使用 alloc 为配置器
class vector {
protected:
    // 专属之空间配置器，每次配置一个元素大小
    typedef simple_alloc<value_type, Alloc> data_allocator;
    void deallocate() {
        if (...)
            data_allocator::deallocate(start, end_of_storage - start);
    }
    ...
};