前言
关于STL内存管理,不仅仅限于他的做法,也不仅仅使用于STL,他的一些思想和优秀的做法值得我们每一个工程师去参考、借鉴,并在此基础上添加一些属于你的技术元素。考虑到现在在读的你没有使用过STL的容器,更不知道其内部构造,所以导致你对内存管理这件事云里雾里,其实这些都没关系,你可以花十五分钟去了解就足够了。作者计划写一些关于STL中,各种容器的底部支撑相关的文章,比如从简单的array(数组),vector(一种动态数组),list(采用双向链表),deque(双向队列),stack(底部支撑可以是list和deque),queue(底部支撑位deque),set(RB-tree),multiset(RB-tree),hash-set(hash-table)等等,作者相信网上也有许多关于这些技术的讲解,各位也可以先参考。作者认为,仅仅学习一些工具的使用对于有些工程师而言这就足够了,但是对于一个有追求的工程师而言,不仅仅要会用,也要会知道底层原理。今后慢慢的,这些相关的文章会慢慢发布(如果工作之余,还有时间的话,作者会慢慢整理出来的)。
OK,言归正常,回到我们自己的主题——STL内存管理(分配器),上一章讲过,STL自己写了一套一级分配器叫(allcator),但是这个第一级分配器基本上不用的,这一章我们讲的是关于STL的二级分配器,也是作者认为,非常棒的一种做法,如何棒呢?他对内存的使用,对申请的内存有较为偏执的使用,对内存有着最大化的利用,如今作者在工作时刚好也接触到这方面的业务,刚刚好对比着去分析。
同样的,我们这些内容也需要一些前置知识(你至少使用过STL里面得一种容器,你得熟悉模板,你得熟悉c++基本语法,你得知道一些在常用编译器下,由分配器分配的内存,其内存模型是怎么样的。)本部分分为以下三个部分:1,关于内存相关的知识。2,标准库二级分配器的做法。3,在此之上的一些反思。
1,内存
关于内存分配,大家在学习相关知识的时候,都学过:如果我们要new一个内存,如果我们不用的话,需要将其释放掉(delete),因为我们new的内存在heap上拿的,那么就需要自己手动释放,如果在stack上的拿的,不需要自己释放,在其生命周期结束时,自然其就归还了。当然我们还学过,如果我们是new一个数组空间大小,如果我们不用的话,就需要用数组的方式去释放
例如:
class apple{
apple (int a):app(a){}
private:
int app;
};
apple* p = new apple(3);
......一系列操作
delete p;
如果是:
apple* p = new apple[5];
........一系列操作
delete[] p;
那为什么要进行上述操作呢?为什么delete前面,一个加了[],一个不加呢?其实,我们调用new的时候(底层也是调用malloc),我们得到的内存其实并不是我们想的那么简单,我们简单来看一下调用new,我们得到的内存长什么样:
指针指向的那个位置才是我们真正得到的内存地址,他上面还会有一个header,(那个header其实更加的复杂,他其中一个功能就是记录这一块内存的大小,这个涉及到另一个话题(操作系统下的内存管理,与我们现在讲的STL内存管理方向不符,有时间的话,作者也会写一下操作系统内存管理))。我们每调用一次new,就会产生像上面的那样的内存,但每一次分配的内存,总是带着一额外的内存开销(header),可能一次两次,那种开销不算什么,但是如果上百万次的内存分配,那种开销其实是非常大的,那么我们来看一下,真正在STL中,他的二级分配器是如何解决这种额外开销的:
2,实现
enum {align = 8};//对齐
enum {max_size = 128};//小区块的最大长度
enum {n_free_list = max_size / align};//free_list最大长度
//第一参数代表是否是多线程,这个不在我们话题,有时间作者会慢慢讲解多线程的东西
template<bool threads,int ints>
class alloc_template{
private:
static size_t round_up(size_t size)
{
return (((size) + align -1) & ~(align-1));//将传入的size上调到8的倍数
}
private:
//联合体,这个是使用嵌入式指针的形式,关于什么是嵌入式指针,读者自行去查
union obj{
union obj *free_list_next;
}
private:
static obj *free_list[n_free_list] ={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
static size_t free_list_index(size_t bytes)
{
retrun (((bytes) + align-1)/align-1);
}
//返回一个大小为n的对象,并可能加入大小为你的其他区块到free_list
static void *refill(size_t n);
//内存池,配置nobjs个大小为size的区块
static char *chunk_alloc(size_t size,int &nobjs);
//内存池的首指针
static char * start_free = NULL;
//内存池的尾指针
static char * end_free = NULL;
public:
//内存分配
static void * allocate(size_t n);
//回收内存
static void deallocate(void *p,size_t n);
//重注内存
static void * reallocate(void *p,size_t old_size,size_t new_size);
};
//内存分配
template<bool threads , int ints>
static void * alloc_template<threads,ints>::allocate(size_t n)
{
obj** my_free_list = NULL;
obj* result;
if (n > (size_t)max_size)
{
//回到第一级分配器,第一章讲过
return allocate(n);
}
my_free_list = free_list + free_list_index(n);
result = *my_free_list;
if (NULL == result)
{
void *r = refill(round_up(n));
return r;
}
//调整free_list
*my_free_list = result -> free_list_next;
return (result);
}
//释放函数
template<bool threads , int ints>
static void alloc_template<threads,ints>::deallocate(void * p,size_t n)
{
obj *q = (obj*)p;
obj ** my_free_list = NULL:
if (n > (size_t)max_size)
{
//这里调用第一级的空间释放函数,但这里并没有写出来
/*
malloc_alloc::deallocate(p,n);
return;
*/
}
my_free_list = free_list + free_list_index(n);
q-> free_list_next = *my_free_list;
*my_free_list = q;
}
//重新填充
template<bool threads ,int ints>
void * alloc_template<threads,ints>::refill(size_t n)
{
int nobjs = 20;
char * chunk = chunk_alloc(n,nobjs);
obj **my_free_list = NULL;
obj *result = NULL;
obj *current = NULL;
obj *next = NULL;
int i;
if (1 == nobjs)
{
retrun (chunk);
}
my_free_list = free_list + free_list_index(n);
result = (obj*)chunk;
*my_free_list = next = (obj*)(chunk + n);
for (i = 1; ; i++)
{
current =next;
next = (obj*)((char*)next + n);
if (i == nobjs -1)
{
current ->free_list_next = NULL;
break;
}
else
{
current ->free_list_next =next;
}
}
return result;
}
//内存池的设计
template<bool threads ,int ints>
char * alloc_template<threads,ints>::chunk_alloc(size_t size,int & nobjs)
{
char *result = NULL;
size_t total_bytes = size * nobjs;
size_t bytes_left = end_free - start_free;//内存池还剩多少
//不够全部
if (bytes_left >=total_bytes)
{
result = start_free;
start_free += total_bytes;
return result;
}
else if (bytes_left >= size)//只够一个
{
nobjs = bytes_left/size;
total_bytes = size * nobjs;
result = start_free;
start_free += total_bytes;
return result;
}
else//一个也无法满足了
{
size_t bytes_to_get = 2 * total_bytes;//这里操作给出了一个追加量,但是这里省去了,因为我觉得没必要
//尝试让剩余内存还有利用价值
if (bytes_left > 0)
{
obj **my_free_list = free_list + free_list_index(bytes_left);
((obj*)start_free)->free_list_next = *my_free_list;
*my_free_list = (obj*)start_free;
}
}
//配置内存空间.看!!!这里居然调用malloc!!神奇吧!
//其实,这个这这里太正常不够了,我们几乎所以的内存管理,几乎都是建立在malloc之上的,也就是我们是踩在巨人的肩膀了干事
start_free = (char*)malloc(bytes_to_get);
if (NULL == start_free)
{
//开始在free_list中找空余的空间
int i;
obj **my_free_list = NULL;
obj *p = NULL;
for (i = size; i <= max_size; i += align)
{
my_free_list = free_list + free_list_index(i);
p = * my_free_list;
if (NULL != p)
{
*my_free_list = p->free_list_next;
start_free = (char*)p;
end_free = start_free + i;
//递归调用自己
retrun (chunk_alloc(size,nobjs));
}
}
//就连free_list中都没有空间可利用了
end_free = NULL;
//这里调用第一级分配器,第一章写过!这里调用的allocate是第一级的,不是上面那个其注意!!!!名字一样,那是我懒得改了!!!
start_free = (char*)allocate(bytes_to_get);
//这里本来有一个追加量的,但是我觉得没必要,多此一举,就没有写。
end_free = start_free + bytes_to_get;
return (chunk_alloc(size,nobjs));
}
}
3,反思
我们可以从上述看出,其实STL回收的内存,并没有归还给操作系统,而是一直在自己free_list链表中。那为什么我再标题二中说,STL中的内存分配少了额外的开销呢?其实关键在于那个嵌入式指针的设计上。简单来说,那个嵌入式指针,即可以当指针来用,也可以作为数据填充单元,闲时,当做指针,需要使用了,那个指针将会被覆盖,被当成数据单元来使用,这样,他就可以使用内存池,一下子分配一大堆内存,然后使用嵌入式指针将每一小区块链接起来,需要用到了,在分配出去。这样,不就省掉了那个header了嘛?但是缺点就是,没有将回收的内存归还给操作系统,而是在自己手中,这个其实是可以改进的。
到此呢,我们关于STL的内存管理就完结了,当然有不完善的地方,就是代码中没有写注释,不是不写,而是给读者有自己的思考过程,为什么那部分代码要那样写,这个需要读者自己去思考的,在思考过程中不妨去画个图,是自己能深入理解(可以结合上述我画的那个图,继续增删查改!!!)
网友评论