站在巨人的肩膀上剖析STL空间配置器

2017-08-02 14:04 阅读 874 次 评论 0 条

STL的运用角度而言,它是不需要介绍的,但是作为一名C++Coder,剖析并熟练使用它是非常有必要的。今天我不是在造轮子,而是站在它的肩膀上探索空间配置器的设计原理和实现细节。与其说它是一个C++的标准库,不如称之为一门艺术。

STL六大组件之间的关系

面对扮演轮子角色的这些STL组件,不论是为了重温数据结构和算法,或是为了扮演轮子角色,或是想要进一步扩张别人的轮子,都可因此获得深厚扎实的基础,天下大事,必作于细。

① 空间配置器(allocator)

是一种管理空间的机制,进行空间的分配与回收,之所以不叫它内存配置器,是因为空间不一定是内存,空间也可以是磁盘或其他辅助存储介质。

② 迭代器(iterator)

提供一种方法,使之能够依序巡访某个聚合物(容器)所含的各个元素,而又无需暴露该聚合物的内部表达方式。你可以认为它是算法与数据容器的粘合剂,将两者有机的统一起来。

③ 容器(container)

任何特定的数据结构都是为了实现某种特定的算法,STL则将运用最广泛的一些数据结构实现出来。它是STL的核心之一,几乎所有的组件都围绕容器展开,比如:迭代器提供访问方式,空间配置器提供容器的空间分配,算法对容器中的数据进行处理,仿函数伪算法提供具体的策略,类型萃取实现对自定义类型、内置类型的提取。

④ 类型萃取(typetraits)

它是基于范型编程的内部类型解析,通过typename可以获取迭代器内部类型。它依靠的是模板的特化,模板的特化又分为全特化与偏特化,对于编译器来说,如果你对某一功能有更好的实现,那么就应该使用你的特化版本。

⑤ 仿函数(functors)

在C语言中,它是一种类似于函数指针的可回调机制,用于算法中的决策处理。在C++重它使得一个类看上去像一个函数,提供在类中重载operator(),这个类就有了类似于函数的行为。

⑥ 适配器(adapters)

将一个类的接口转换为另一个类的接口,使得原本因接口不兼容而不能合作的类可以一起运作。比如STL中的stack、queue,通过deque双端队列适配实现,map、set通过RBTree适配实现。

下图较好的说明了STL六大组件之间的关系:

当然,面对PJ、SGI、HP等众多版本的STL而言,我所要剖析的是易读性最强的SGI版本。而今天只谈空间配置器,嗯,更加准确的说应该称为内存配置器,,SGI对此的设计哲学是:

STL产生空间配置器的原因?

1、小块内存带来的内存碎片问题

当然这里指的是外碎片,由于频繁分配、释放小块内存,导致堆中空闲的内存总量虽然足够,但是这些空闲的内存块都不连续,导致任何一个单独空间的内存都无法满足这一要求。

内碎片:是由于内存对齐、访问效率而产生的,也是空间配置器的历史遗留问题。比如操作系统的分页机制。默认一页是4K,如果用户申请了100字节,依旧会分配4K字节,未使用的空间就构成了内碎片。

下图模拟了一个内碎片与外碎片的产生原因:

2、小块内存频繁申请释放带来的性能问题

额外负担是永远无法避免的,毕竟系统要靠这多出来的空间管理内存,但是空间越小,额外负担所占的比例越大,越显得浪费,如下图所示:

频繁向系统申请内存会引起性能上的消耗,毕竟寻找空闲内存块也是需要时间的。此外,依据计算机的局部性原理,当你申请了某一大小的内存块时,很可能接下来又要申请同样大小的内存,这在B树与B树的变种也应用很多。

STL一级空间配置器

在STL中,默认如果分配的内存大于128字节,则认为是大块内存,调用一级空间配置器向系统申请内存。当然,这是STL十几年前的标准,你可以把这道分水岭调节的更适合。

一级空间配置器的内存申请、释放只是简单了封装了malloc()和free()。但是,很重要的一点是,一级空间配置器实现了类似于C++ new-handler机制,它不能直接运用C++new-handler机制,因为它并非使用::operator new来配置内存。

所谓的C++ new-handler机制是,你可以要求系统在内存配置需求无法满足时,调用一个你所指定的函数。也就是万一内存开辟失败,在抛出异常之前,会先调用由客户端指定的处理例程,没错,这一切都是由客户自己设定。在SGI第一次空间配置器的allacate()和realloc()都是在调用malloc()和realloc()不成功后,改调用oom_malloc()和oom_realloc(),而后两者都存在内循环,如果客户设定的处理例程足够失败,就陷入了死循环的危险。

一级空间配置器流程图:

STL二级空间配置器

第二级空间配置器才是空间配置器的精华所在,当申请的内存小于128字节时,就调用二级。它的巧妙就在于使用狭义内存池+自由链表的形式来避免小块内存带来的碎片化,如下图所示:

每次配置一大块内存,并维护与之对应的自由链表,下次若在有相同的需求,则直接可以在自由链表中取,释放时链接在自由链表中。为了方便管理,二级空间配置器会主动将任何小额区块的内存需求上调至8的倍数,并维护16个free_list:它的结构如下:

使用union结构的好处在于避免了维护链表而需要额外的指针,因为union的第一个字段就可试之为指针,指向第一块内存。

我先对几个重要的函数进行介绍,然后在放出二级配置器的流程图:

✔ 空间配置函数Allocate()

此函数首先判断内存块大小,大于128字节就调用第一级空间配置器,小于128字节就检查对应的free_list,如果free_list之内有可用的内存块,就直接拿来使用,否则将内存块上调至8的倍数,调用Refilll()来填充free_list。

✔ 空间释放函数Deallocate()

该函数首先判断内存块的大小,大于128字节就调用一级配置器,小于128字节就找到对应的free_list,利用头插法将内存块挂接在对应位置。

✔ 重新填充函数Refill()

当free_list中没有可用内存块时,就调用refill()为free_list重新填充空间,新的空间将取自内存池,由ChunkAlloc完成,缺省取得20个新内存块,但有些时候并不能如愿以偿。

✔ 填充free_list函数ChunkAlloc()

ChunkAlloc()从内存池中取空间给free_list使用,但是存在下述三种情况:

上述第三步又衍生出两种情况:

上述第二步又衍生出两种情况:

上述第二步又衍生出两种情况:

二级空间配置器的流程图:

源代码见GitHub:STL 空间配置器 

STL空间配置器的遗留问题

⑴ 二级空间配置器从头到尾都没有看到它释放内存,究竟是否释放,何时释放?

首先应该明确一点,二级配置器并没有将申请的空间释放,而是将它们挂在了自由链表上。空间配置器的所有方法,成员都是静态的,那么它们就存放在静态区,因此释放的时机也必定是程序结束时。

⑵ 自由链表释放空间的连续性问题

真正在程序中就归还空间的只有自由链表中的未使用值,由于用户申请空间、释放空间顺序的不可控性,这些空间并不一定是连续的,而释放空间必须保证其连续性。保证连续的方案可以是:跟踪分配释放过程、记录节点信息,释放时,仅释放连续的大块空间。

⑶ 二级空间配置器的效率问题

二级配置器虽然解决了外碎片的问题,但同时也造成了内存片。加入用户频繁的申请char类型的空间,而配置器默认对其到8的倍数,那么剩下的7/8的空间就会浪费。

如果用户频繁申请8字节的空间,甚至将堆中的可用空间全部挂在了自由链表的第一个节点,这时如果申请一个16字节的内存,也会失败。这也是二级配置器的弊端所在,设置一个释放内存的函数是很有必要的。

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:站在巨人的肩膀上剖析STL空间配置器 | 术与道的分享
分类:编程素养 标签:, , ,
1024do.com导航_术与道导航平台

发表评论


表情