STL和内存管理技术

前段日子读了STL的源码，大师级的作品真是精致到让人喟叹。当然，有时候你在网上还是可以看到很多对STL的批评，例如，对编译器要求很高，很多时候出错了的话，打印出来的错误信息总是让人摸不着头脑的。这确实是比较头疼的一个问题，因为模板编程，编译的过程总是分为两个部分的，是先要找到相应的模板，然后才对模板进行具现化，有时候单纯从模板来看，似乎很完整，没有什么问题呀，可是一旦投入使用了，才发现找不到合适的具现化版本，于是又要搞特化了。某日在路上行走，突然想起爱情这个难题，突然想起具现化，突然觉得爱情就像是一个模板类，是想象，没有实现的时候，它看起来很完美，很丰富，可是爱情一旦具现化，它便成了独此一家的一个类，想象的空间本就狭窄了，倘若需求比较复杂，还须得有偏特化版本，不然就要出错。每个女人心目中的恋爱对象都是完美的，是那种选择性的完美，她爱的并不是那个实体，而是加诸于该实体上的想象。好了，不管你看没看懂，还是言归正传了。

STL的设计非常巧妙，组件间互取短长，形成了一个世界，这是这个世界里的组件：
1. containers（容器）：所谓容器，是指存放数据的地方，将数据以一定的方法组织存放。根据不同的组织方式，可以把容器分为顺序容器，如vector、deque、list，关联容器，如set、map。Container是一种class template。
2. algorithm（算法）：各种常用不常用的算法如sort、copy、search等等。algorithm是一种function template。
3. iterator（迭代器）：迭代器是算法和容器之前的胶合剂，算法作用于容器之上，但算法以迭代器作为形参。从实现上看，迭代器是一种将operator*，operator++，operator--，operator->等指针相关操作予以重载的class template。所以容器都带有自己的迭代器，因为只有容器设计者才知道如何遍历自己的元素。
4. functors（仿函数）：行为类似函数，可作为算法的某种策略。从实现的角度来看，仿函数是一种重载了operator()的class或class template，它常常是算法的一个输入，类似于一种策略。
5. adapters（适配器）：用来形容容器、迭代器或仿函数接口的东西，有时候上面那些组件的行为可能跟我们想要的约束不大一样，于是给它们包装一下，使它们遵守一定的行为。
6. allocator（配置器）：负责空间配置与管理。从实现的角度来看，配置器是一种实现了动态空间配置、管理、空间释放的class template。

STL中的空间配置器，使用了两层架构，一层用于分类大块内存，一层用于管理小块内存。大块内存基本上是用完了就返回给操作系统，而小块内存则由内存池管理。另外，我们知道当我们new一个对象的时候，不仅仅是给了它内存，同时还可能调用了构造函数对这块内存进行了初始化（假如它是用户自定义类型），当我们delete一个对象的时候，同样，也可能是先调用了析构函数，然后再把内存还回去。调用构造、析构函数是要付出代价的，可是对于基本类型如int、long这种Plain-Old-Data，根本就不存在这样的构造/析构函数，便没有必要为它花费这种心思了。因此，为了便于分开处理这两种情况，STL把new/delete的执行过程分开成了两部分，一部分放在<stl_construct>里，用于在必要的时候调用构造、析构函数，一部分放在<stl_alloc>里，用于策略性地分配内存，跟内存分配管理相关的，还有一个<stl_uninitialized>，针对多个对象的初始化、复制做了一定的优化（当然也是以是否为POD来区分）。

<stl_construct>里定义了一个construct和两个destroy，construct基本上就是一个placement new，在指定内存上调用构造函数，而destroy有两个版本，一个是只析构单独一个对象的，直接调用了对应的~T()版本，另一个版本用于析构一段范围内的对象，这样的话如果对象是POD类型的，还for[i,j)地去执行，就是一种无谓的浪费了，因此，这个destroy将根据数据类型，决定调用特定版本的__destroy，如果是POD类型，则什么都不做，如果不是POD类型，则for[i,j)地去调用~T()。这些类型判断都是在编译时就确定的（通过__type_traits<T>::has_trivial_destructor），因此并不影响运行时效率。另外你肯定会想，为什么针对destroy这番考虑，针对construct却没有呢？反正当时我就是这么想的，后来发现原来这些事情交给uninitialized_fill、uninitialized_copy和unintialized_fill_n去做了，因为对象的初始化可能是经由constructor，也可能是经由copy constructor去执行呀。这里面，**_copy可能在必要的时候直接使用memmove来执行。

然后就是那个大头，空间分配器了。<stl_alloc.h>内定义了两个template，一个是__malloc_alloc_template，这是sgi stl的一级配置器，它的allocate()直接使用malloc()而deallocate()直接使用free()，同时，它模拟C++的set_new_handler()处理内存不足的状况。第二个是__default_alloc_template，它维护了16个free list，每个list上集合着大小分别为8，16，24，...128大小的内存块。内存池以malloc()配置而得，如果内存不足，转调用第一级配置器，因为那里设置了内存不足的处理程序。如果请求的内存块大小大于128bytes，就转调用第一级配置器。另外定义了两个alloc，一个是debug_alloc，每次配置一块内存时，都会配置比需求多8byte的空间以存储空间大小，通过assert语句来检查会不会内存溢出。另一个是simple_alloc，定义了两个版本的allocate和deallocate，它们都只是单纯的转调用。sgi stl容器全都使用simple_alloc接口。free-list的节点巧妙地使用了一个union结构来管理链表：

union obj{
	union obj* free_list_link;	//当作为自由链表的一个结点时，存储其下一个节点的地址
	char client_date[1];		//当其作为返回值时，返回的正好是分配内存的首地址
}

每次配置器需要向系统要内存的时候，都不是按客户需求向系统申请的，而是一次性向系统要了比需求更多的内存，放在内存池里，有一个free_start和free_end指示剩余的空间（也就是说内存池剩余的空间都是连续的，因此每次重新向system heap要空间的时候，都会把原先内存池里没用完的空间分配给合适的free list。）当free-list中没有可用区块了的时候，会首先从内存池里要内存，同样，也不是以按客户需求要多少块的，而是一次可能会要上20块，如果内存池内空间允许的话，可能会得到20个特定大小的内存，如果内存池给不了那么多，那么就只好尽力给出；如果连一个都给不出，那么就要开始向系统即system heap要空间了。换算的标准是bytes_to_get=2*total_bytes+ROUND_UP(heap_size>>4)。这个时候使用的是malloc，如果没成功，就尝试着从大块一点的freelist那里要一个来还给内存池，如果还是不行，那么会调用第一级空间配置器的malloc::allocate，看看out-of-memory机制能做点什么不。

总结起来整个过程大概是这样的，假设我们向系统要x大小的内存，
（1）x大于128byte，用第一级配置器直接向系统malloc，至于不成功的处理，过程仿照new，通过set_new_handler来处理，直到成功返回相应大小的内存或者是抛出异常或者是干脆结束运行；
（2）x小于128byte，用第二级配置器向内存池相应的free_list要内存，如果该freelist上面没有空闲块了，
（2.1）从内存池里面要内存，差不多要的是<=20个相应freelist大小的块，如果要不到：
（2.2）从系统的heap里面要内存给到内存池，换算的标准是bytes_to_get=2*total_bytes+ROUND_UP(heap_size>>4)，这时使用的是系统的malloc，如果要不到：
（2.3）从比较大的freelist那里要内存到内存池，如果还是要不到：
（2.4）从系统的heap里面要内存给到内存池，换算标准跟2.2一样，但是这时候使用的是第一级配置器的allocate，主要是看看能不能通过out_of_memory机制得到一点内存。所以，freelist总是从内存池里要内存的，而内存池可能从freelist也可能从系统heap那里要内存。
sgi stl的alloc的主要开销就在于管理这些小内存，管理这些小内存的主要开销就在于，每次freelist上的内存块用完了，需要重新要空间，然后建立起这个list来。freelist上的内存，会一直保留着直到程序退出才还给系统。但这不会产生内存泄漏，一来是管理的都是小内存，二来是，占用的内存只会是整个程序运行过程中小内存占用量最大的那一刻所占用的内存。

SGI STL的alloc是一种内存管理机制，用于管理小内存块的分配，以减少内存碎片。后来我又看了另外一些内存管理机制（利用对象管理资源），包括智能指针的RAII，用于复杂但可能过程不是很久的算法内存管理AutoFreeAlloc，ScopeAlloc，以及boost中的pool跟object_pool。总的来说，内存管理的基本要求就是：不重不漏，既不重复delete，也不漏掉delete。
首先是智能指针，智能指针的基本思想是利用编译器在对象离开作用范围后自动调用析构函数来实现内存的自动释放，即通过对象来管理资源，把指针封装成一个对象，在其构造、析构、赋值函数中，实现对内存的管理。最简单的是auto_ptr，你把指针给了它，它就在析构的时候把指针指向的内存释放掉。可是我要把指针赋值给其他人怎么办？它说，哦，那没办法，被赋值的那个人接管了你的内存，你就退休指向NULL吧。这显然给指针的应用带来了相当大的不便，想想，在用裸指针时，用temp = head, head = head->next这样的状况是多么常见，用容器存放指针也是常有的事（存放到容器是一种赋值行为）。那就使用share_ptr吧。share_ptr中记录了一块内存的reference_count，在构造时其为一，在复制构造、赋值时修改reference_count，在析构时reference_count--，如果reference_count为0，那么就把内存给释放了。在多线程中，reference_count便成了一个竞争资源，因此可能会成为瓶颈。另外，所谓的这个“把内存给释放了”，其实也可能只是一种指定的操作，例如把它放到freelist去啊之类的，是可以自定义的。

接下来的内容我基本是从许式伟的博客（http://blog.csdn.net/xushiweizh/article/category/265099）看到的，因为AutoFreeAlloc和ScopeAlloc是他们团队做的内存管理库中的一部分。AutoFreeAlloc的基本思想可以用下图表示：

 
因此在一般情况下，使用AutoFreeAlloc为底层的NEW的开销就是对m_end的移动，或者重新开辟一块大内存进行管理，而这种NEW不需要DELETE，当算法结束的时候通过clear把AutoFreeAlloc管理的内存链表释放掉。

 

情况一：

情况二：

情况三：

 
ScopeAlloc跟AutoFreeAlloc的区别主要在于，AutoFreeAlloc是直接从系统申请的内存，用的是malloc/free，而ScopeAlloc是从内存池里申请的内存，用的是使用的内存池ProxyBlockPool::allocate/deallocate。

typedef AutoFreeAllocT<ProxyBlockPool> ScopeAlloc;
typedef AutoFreeAllocT<DefaultStaticAlloc> AutoFreeAlloc;

内存池
经典的内存池技术是一种用于分配大小相同的小对象的技术，它通常涉及两个常量：MemBlockSize和ItemSize，就是说，每次申请的内存大小固定为ItemSize，当池中没有空间的ItemSize块时，从系统heap中申请MemBlockSize大小的内存块，跟原先池中的大小块串在一起，而MemBlockSize的块中也要相应建立起一条freelist，因此，内存池还涉及另外两个指针变量：pFreeNodeHeader，指向freelist的头部，当需要一个对象时，从pFreeNodeHeader取下一个，当然，如果pFreeNodeHeader为空，说明没有空闲的块了；另一个为pMemBlockHeader，最后要把所有的内存释放时，从pMemBlockHeader处开始释放。
boost::pool对经典内存池的改进：
（1）MemBlockSize不再是固定的，而是采用了预测模型，第一次申请时，MemBlockSize=ItemSize*32，第二次为ItemSize*64等等，就像std::vector的增长模型。
（2）增加了ordered_free(void* p)。ordered_free与free的差别在于，free的时候，只是简单地把这个item放回freelist的头部，而ordered_free假设这些item是有一定的顺序的，因此返回item的时候会找到一个合适的位置放置item（指的是在链表中的位置）。
boost::object_pool支持手工释放内存和自动回收内存（并自动执行析构函数），从而保证当它离开作用范围后不会产生内存泄漏，为了判断block中的节点是否为free，要求其在获取、释放内存的时候必须使用ordered_malloc和ordered_free。这样子，当object_pool离开作用范围而调用析构函数~object_pool时，它遍历所有的内存块MemBlock，并遍历其中所有结点，如果该结点不出现在free_list中，那么它就是未被释放的，因此要执行该结点的析构函数，如果free跟malloc是有序的，我们就能在线性时间内完成自动释放。

STL中给我印象比较深的就是这个allocator，因此也才会额外去看了这么些内存管理的技术。其他的，印象比较深的就是里面一些精简的算法了。下次再讲~,~