下面将结合关键源码分析C++STL（SGI版）的内存配置器设计思路。既然关键词是“思想”，关键点就呼之欲出了。一、allocator简介我看的源码是SGI公司的版本，也是看的最清楚的版本，各种名字也最容易看懂。Allocator有人称之为空间配置器，因为空间不一定是内存，也可以是磁盘或者其他辅助存储介质。我说的内存配置是指分配器。C++标准规定了allocator的一些必要接口，各个厂商都实现了。SGI的版本不同，也与标准规范不同，命名为alloc而不是allocator，并且不接受任何参数。假设你在程序中显式写出分配器，你不能这样写：vector>iv;//如果你写错了，你必须这样写：vectoriv//Okay虽然SGISTL不符合规范，但我们使用它似乎很自然。这是因为我们默认使用时空配置器，不需要自己指定。比如STL中vector的声明如下：注：下面的代码我基本都是用截图来解释，因为我觉得比粘贴代码更清晰（有颜色对比）。2、源代码文件简要介绍STL标准规定：STL的allocator定义在文件中，主要包括一些头文件。我们主要讲两个：负责内存空间的配置和Release；负责对象内容的构造和销毁3.构造和销毁工具：construct()和destroy()先说简单的文件。这部分不涉及任何思路，但是有一个版本的destroy()要仔细看。(1)构造工具：construct()construct()只有一个版本：这里使用placementnewexpression（定位new表达式），其作用是p指向的内存类型为T1，用值值。(2)销毁工具destroy()有几个版本：第一个版本：这个显示析构函数调用的方法大家应该也很熟悉了。第二版：第二版有话要说。调用层次是这样的：destroy->__destroy->__destroy_aux，__destroy_aux最后调用的是第一个版本的destroy。这个版本的destroy将一对迭代器作为参数并销毁迭代器指向的范围内的元素。在解释这个过程之前，先简单说一下trivial_destructor。如果用户没有定义析构函数，而是用编译器综合了它，那么说明这个析构函数基本没有用（但默认会调用），称为trivialdestructor。那么，如果一对迭代器指向的元素都是平凡的析构函数，就没有必要浪费时间依次为每个对象执行它的析构函数，只需要依靠编译器的行为。这是效率的提高。这是STL分配器优化的一个要点。首先使用value_type()获取迭代器指向的对象的类型，然后使用__type_traits判断对象的析构函数是否为trivial_destructor。如果是__true_type，什么都不做，否则循环调用最新版本的destroy()。第三个版本：这是迭代器char*和wchar_t*的专用版本。看到它们的函数体都是空的，你应该猜到不需要进行破坏操作了。4、内存的申请和销毁，负责std::alloc内存的申请和销毁。SGI在这一点上的设计理念是：(1)从系统堆中申请空间。(2)考虑多线程状态。(3)考虑内存不足时的应急策略。(4)考虑“小块”过多可能造成的内存碎片问题。其实我主要想说的是（3）和（4）的设计策略，尤其是内存池的思想。std::alloc的整体设计思路是：SGI设计了一个二级配置器，一级配置器直接使用malloc和free；二级配置器根据情况采取不同的策略：当配置块超过128bytes，认为“足够大”时，调用顶层配置器进行处理；当配置块小于128bytes时，被认为是“太小”，为了减少额外的负担，采用了内存池（memorypool）的处理方式，而不是使用高级配置器中的。1.顶层内存配置器分析顶层配置器的主要功能有：allocatememory,deallocatereleasememory,reallocatereallocatememory等(1)allocate直接调用C函数malloc，如果内存不能满足需求，调用oom_malloc函数。原来这是自己实现的handler函数，为什么要自己实现呢？因为不使用operatornew配置的内存，所以不能使用C++new-handler机制。这个机制其实讲的很多，如果你不了解它的用途或者自己怎么实现的话，建议你看看《Effective C++》，或者看看我在《Effective C++》上的笔记。我在这里主要不是要分析语法方面。(2)deallocate代码应该放在上面，并且应该清楚。(3)reallocate这里还是调用C的realloc函数，调用失败则调用oom_realloc函数。可见oom_realloc也是一个处理函数。基本上顶层的内存配置器都解释的很清楚了。这里还有一点：一方面，由于历史原因，SGI使用malloc而不是operatornew来配置内存，另一方面，C++没有提供realloc函数。导致SGI无法直接使用C++的set_new_handler()，只能自己模拟一个。如何模拟set_new_handler有特定的模式。#p#二、二级内存配置器分析二级内存配置器增加了一些机制来避免小块过多导致的内存碎片。小块带来的不仅仅是内存碎片，额外的配置负担也是个大问题。额外的负担永远无法避免。毕竟系统是靠多出来的空间来管理内存的，但是block越小，多出来的负担所占的比例就越大，自然就更加浪费了。二级内存配置器的总体思路是：（1）如果请求的block超过128bytes，则交给一级内存配置器处理。(2)如果请求的块小于或等于128bytes，则使用内存池进行管理。具体来说：二级内存配置器会将任意一个小块的内存需求增加到8的倍数，维护16个free-list，每个管理大小为8,16,24,32,40,48,56，64、72、80、88、96、104、112、120、128字节的小块。free-lists中的节点结构如下：（这个union我已经注释了）注：union的这个用法也叫“灵活数组”成员。本质上，这是与小端存储相关的技巧。(1)allocate二级内存配置器__default_alloc_template的内存分配接口是allocate函数。我用红框标注了关键部分。FREELIST_INDEX(n)函数根据n的值返回16个free-lists中合适的list的下标。再看看ROUND_UP(n)。我觉得这个函数写得很巧妙。它将字节值调整为8字节的倍数。理解这个函数，可以先给几个字节值，看看返回值是什么，自然就明白了。refill()函数非常好用，下面介绍一下。(2)deallocate()首先判断块的大小，如果大于128字节则调用顶层配置器，否则根据需要返回的字节大小判断应该返回哪个freelist被回收，然后freelist回收。(3)refill()函数非常重要，单独介绍。当空闲列表中没有可用的块时，调用此函数为空闲列表重新填充部分空间。新空间从内存池中获取（由chunk_alloc完成）。默认情况下，获取20个新块。如果内存池空间不足，获取的新块数可能会少于20个。图中两个红框是值得注意的两点。一旦从内存池中获取到内存块，就给调用者一个，还得再找一个合适的freelist来“穿”。(4)内存池函数chunk_alloc()内存池已经被用来提供freelist。下面是这个函数的截图。第一个分支：检查内存池中的容量是否足够，如果足够就拿走。第二个分支：内存池不够20个block，但是大于等于1个block的长度，剩下的给出来。此时，内存池为空。第三个分支：如果内存池连一个对应的block都不能提供，比如需要32个字节，但是只有8个字节可用。这时候最好的办法就是把这8个字节链接到对应的块上。使用空闲列表。不出所料，此时内存池也是空的。第四个分支：内存池为空，所以内存池求助于runtimeheap，而heap没有那么多空间，所以查看16个freelist中有哪些block没有被使用，将这些加入内存水池。第五分支：是的，heap什么也做不了，内存池直接调用top-levelconfigurator，因为top-levelconfigurator有new-handler机制，可能有机会释放其他内存在这里使用调用它。如果可以，那就成功了；否则，将抛出错误分配异常。总结：如果有人问我对STL内存配置的看法。我可能会这样说：C++STL在两个级别上配置内存。具体来说：第一层负责管理大块内存，必须保证类似new-handler的机制；第二层负责管理小块内存。为了更好的管理内存碎片，建立了16个链表，每个链表“穿”了一块固定大小的内存。这16个链表（0到15）“消耗”的内存是8,16,24...128的倍数关系。当需要内存时，从“合适的”链表中取出。如果“适合”的链表内存不够，就从内存池中拿。如果内存池不够用，就从运行时堆中取出。如果堆也溢出了，就交给顶层配置器吧，因为它有new-handler机制。
