STL (C++)-内存分配器(Allocator)在用于STL容器上的性能

项目合作 项目合作 主题:1030 回复:2135

STL (C++)-内存分配器(Allocator)在用于STL容器上的性能

偏爱自由 发布于 2017-05-10 字数 299 浏览 1458 回复 3

STL中使用ScopeAlloc 和 AutoFreeAlloc作为分配器的区别, 如果把他们用在 vector,map这些容器上哪个性能更高? 为什么?

我想问 哪个 分配器的效率高,不是哪个容器效率高。 vector 是线性,map 是红黑树,所以vector上查找效率比map 低. 我现在使用的是map, 想知道在使用map的时候,哪个分配器效率更高?

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

支持 Markdown 语法,需要帮助?

评论(3

瑾兮 2017-09-12 3 楼

std::vector, std::deque, std::stack(其实也是std::deque)等。这几个容器并不需要一个特别的Allocator,普通的new/delete足矣。

std::map使用ScopeAlloc或者AutoFreeAlloc后,性能有显著提高。而ScopeAlloc与AutoFreeAlloc在该容器存在大量内存分配时区别不显著。另外,由于内存池技术的作用,ScopeAlloc在Share同一个BlockPool后,性能略有改善

在单个Allocator仅申请少量内存时,AutoFreeAlloc性能最差,new/delete次之,ScopeAlloc最好。

在单个Allocator申请大量的小块内存时,AutoFreeAlloc性能最好,ScopeAlloc次之(但和AutoFreeAlloc很接近,差异不显著),new/delete最差。

生成一个新的AutoFreeAlloc实例是一个比较费时的操作,其用户应注意做好内存管理的规划。而生成一个ScopeAlloc实例的开销很小,你甚至可以哪怕为生成每一个对象都去生成一个ScopeAlloc都没有关系(当然我们并不建议你这样做)。

AutoFreeAlloc有较强的局限性,仅仅适用于有限的场合(局部的复杂算法);而ScopeAlloc是通用型的Allocator,基本在任何情况下,你都可通过使用ScopeAlloc来进行内存管理,以获得良好的性能回报。

参考:http://cplusplus.wikidot.com/cn:allocators-performance-comparison

灵芸 2017-09-03 2 楼

用在map上性能应该会更好点,vector的存储本身是线性的,换用什么样的分配器影响不大,map的内存结构可调整型比较大。

偏爱自由 2017-08-03 1 楼

1.就cpluscplus.wikidot.com的描述来看,ScopeAlloc仅仅是模板类AutoFreeAlloc的typedef,根据不同的编译选项自动选择最佳的多线程策略,即为AutoFreeAlloc使用不同的内存池。因此,从这一点上说,ScopeAlloc是AutoFreeAlloc的一个特例。因此,和你用什么容器无关。

2.AutoFreeAlloc有其天生的缺陷,它破坏了std::allocator要求该同一类型allocator的所有实例都等价的要求。此外,它也不能有效影响到容器元素所使用的Allocator类型,例如不能控制vector<string>中的string类型使用何种Allocator实例。这是无法透过vector来控制的,即使你企图通过直接使用basic_string去指定allocator也不行,因为无法从外部传一个预制的allocator对象给vector的元素,这是std::allocator要求的所有实例等价性被破坏带来的后果。
彻底的解决的方案在C++11的标准库中,使用scoped_allocator_adaptor.这个模板类可以分别指定各个层次的allocator(当然也可以公用),且标准库也做了相应修改一保证使用同一个allocator的实例,至此,“同一类型所有allocator实例等价”的要求也不再需要了。

3.你的“vector上查找效率比map低”的观点是错误的。对一个一般的序列来说,将之插入map要比插入vector,然后排序慢的多。尽管两者都是NlogN的复杂度。在一个已序的vector上做二分查找(通过lower_bound/upper_bound函数)也要比map上的find/lower_bound/upper_bound快得多。原因也是很显然的,vector具有内存局部性,更紧凑,cache更友好。