异想天开

What's the true meaning of light, Could you tell me why

STL内存管理

日期:2014-07-02 18:15:38
  
最后更新日期:2014-07-02 18:20:10
【技术文章,非码农勿入】
系统环境:
[code lang="cpp"]
[root@localhost data]# uname -r
2.6.32-431.1.2.0.1.el6.x86_64
[root@localhost data]# gcc -v
使用内建 specs。
目标:x86_64-redhat-linux
线程模型:posix
gcc 版本 4.4.7 20120313 (Red Hat 4.4.7-4) (GCC)
[/code]
文章主要内容主要来自stl的手册关于memory的叙述以及针对内存部分的gdb调试,所有论述仅适用于当前版本gcc,因为不是学术研究,所以不选最新的,也不选很旧的,而选择与实际环境相同的STL源码,STL源码在gcc的一个子目录。 一.STL内存设计概述
STL的内存分配器(allocator)有两种类型,一种是不带缓冲的,相当于直接封装malloc/free,另外一种是有缓冲的内存池实现。通过查手册,系统上面用到的STL版本有8种内存分配器:
1.new_allocator -浅封装new/delete
2.malloc_allocator -浅封装malloc和free
3.array_allocator -通过全局或借用std::tr1::array objects内存分配方式分配内存
4.debug_allocator -可以调试的内存分配器
5.throw_allocator -Includes memory tracking and marking abilities as well as hooks for throwing exceptions at configurable intervals (including random, all, none).
6.__pool_alloc 内存池分配器
7.__mt_alloc -A high-performance fixed-size allocator with exponentially-increasing allocations
8.bitmap_allocator -A high-performance allocator that uses a bit-map to keep track of the used and unused memory location
上诉这么多内存分配器,笔者测试过的带缓冲的就__pool_alloc,因为适用环境并不适合这些内存分配器,所以实际环境没有使用它们,而是往后会介绍google的tcmalloc(thread cache malloc)。
二.__pool_alloc(内存池分配器)实现概要
包含如下头文件:
[code lang="cpp"]
#include <ext/pool_allocator.h>
[/code]
写一个这样的函数:
[code lang="cpp"]
void testvector()
{
typedef std::basic_string<char, std::char_traits<char>, __gnu_cxx::__pool_alloc<char> > pstring
vector<pstring,__gnu_cxx::__pool_alloc<pstring> > vec;
for(int i=0;i<10;++i){
pstring tmp="vecotr";
vec.push_back(tmp);
}
typedef vector<pstring,__gnu_cxx::__pool_alloc<pstring> >::iterator Iter ;
for(Iter iter=vec.begin();iter!=vec.end();++iter){
cout<<*iter<<endl;
}
}
[/code]
安装了C++的调试信息,就跟踪进入__pool_alloc,查看其实现。__pool_alloc实现不复杂,主要由结构为邻接链表的free_list缓冲小内存块,小内存按8的倍数对齐申请,最大到_S_max_bytes=16*8,即free_list包含8,16,32,...,_S_max_bytes。其策略如下:
申请
1.大内存(判断申请的size是否大于_S_max_bytes),直接调用::operator new申请;
2.小内存用free_list的缓冲块。
释放
1.大内存释放,直接调用::operator delete释放。
2.小内存cache到free_list链上。
内部实现:
__pool_alloc_base 基类
[code lang="cpp"]
class __pool_alloc_base
{
protected:

enum { _S_align = 8 };
enum { _S_max_bytes = 128 };
enum { _S_free_list_size = (size_t)_S_max_bytes / (size_t)_S_align };

union _Obj
{
union _Obj* _M_free_list_link;
char _M_client_data[1]; // The client sees this.
};
// _S_free_list 在基类里面,共用一个
static _Obj* volatile _S_free_list[_S_free_list_size];
// Chunk allocation state.
static char* _S_start_free;
static char* _S_end_free;
static size_t _S_heap_size;

size_t
_M_round_up(size_t __bytes)
{ return ((__bytes + (size_t)_S_align - 1) & ~((size_t)_S_align - 1)); }

_Obj* volatile*
_M_get_free_list(size_t __bytes);

__mutex&
_M_get_mutex();

// Returns an object of size __n, and optionally adds to size __n
// free list.
void* _M_refill(size_t __n);

// Allocates a chunk for nobjs of size size. nobjs may be reduced
// if it is inconvenient to allocate the requested number.
char*
_M_allocate_chunk(size_t __n, int& __nobjs);
};
[/code]
模板构造类:
[code lang="cpp"]
template<typename _Tp>
class __pool_alloc : private __pool_alloc_base
{
private:
static _Atomic_word _S_force_new; //该变量根据环境变量决定是否强制调用new来申请内存

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;
...
void destroy(pointer __p) { __p->~_Tp(); }
pointer allocate(size_type __n, const void* = 0);
void deallocate(pointer __p, size_type __n);
};
[/code]

三.STL的string,vector和map,list容器的内存管理
容器涉及内存部分在两个地方:a.容器自身数据结构消耗的内存;b.容器中的元素内存。string也可以看成为容器。
1.vector
当使用push_back之类的操作插入数据时,若vector容量不足时,vector会按照2倍于当前size来调整。所以一开始可以确定vector大小情况最好调用reserve函数一次分配。
2.map和list
这类链式数据结构的容器自身的节点内存直接调用自身的alloctor分配内存,删除节点时,调用alloctor来释放内存,cache不cache由alloctor来决定。而容器内的元素的内存,则由元素的alloctor来管理。