std :: map标准分配器性能与块分配器

Question

我读过一本关于STL容器的标准分配器,如std :: list,std :: set,std :: multi_set,std :: map,e std :: multi_map,可以用更高性能的代替块分配器.

块分配器具有更高的性能,低碎片和高效的数据缓存.

我在网上发现FSBAllocator声称比标准更快. http://warp.povusers.org/FSBAllocator/

我已经尝试使用std :: map并且发现它看起来确实更快,但我的问题是如何使STL实现比特定分配器慢得多,并且除了标准之外,另一个分配器的缺点是什么？便携性和稳健性？我的代码必须在各种体系结构(win32,osx,linux)上编译.有人有这种固定大小的块分配器的经验吗？

Answer 1

块分配器对空闲存储/堆执行一次大的分配,然后在内部将此内存拆分为块.这里的一个缺点是它会直接分配这个块(需要很大,并且通常是在每个用例的基础上指定用户),所以即使你没有全部使用它,那个内存也会被占用.其次,标准内存分配器建立在new/delete之上,而new/delete通常建立在malloc/free之上.虽然我不记得malloc/free是否保证在所有情况下都是线程安全的,但它通常是.

但最后,为什么块分配器工作得如此之好的原因是因为它们具有标准分配器不存在的信息,并且它们不需要涵盖非常广泛的用例.例如,如果你这样做std::map< int, int >()并且它分配了1mb你可能会生气,但如果你这样做,std::map< int, int, std::less< int >, block_alloc< 1024 * 1024 > >()你会期待它.标准分配器不以块为单位分配,它们通过new请求新内存,而new依次没有上下文.它获得任意大小的内存请求,需要找到要返回的连续字节数.大多数实现所做的是它们具有一组存储区域,它们保持不同的倍数(例如,4个字节的区域或多或少可能保证存在,因为对4个字节的请求非常常见).如果请求不是偶数,那么返回一个好的块会变得更加困难而不会浪费空间并导致碎片化.如果你希望它接近恒定时间,低碎片,线程安全等,基本上很难做任意大小的内存管理.

该升压池分配器文档有一个良好的块分配器如何工作的一些好的信息.