STL内存管理机制是否考虑到CACHE命中率的问题？

bluefire9213

小弟没看过STL源代码，知道STL算法很优化，但不知道其是否优化到考虑提升CACHE命中率问题的程度。

希望高人告知。谢谢！

SevenCat

建议把stl原代码先看一遍吧。

和编译器也相关。

whb9633

内存管理和cache命中完全两码事，天知道你程序下一步访问哪块内存呢.

bluefire9213

虽说无法预测程序下一步访问哪个地址，但我想应该不是说完全不可以做任何关于这方面的优化的，比如缩小链表的前驱后继链表结点之间的地址差。

结点： A      -> B     -> C     -> D     -> NULL
地址：1000 -> 5000-> 3000-> 4000 -> NULL

如果结点小，程序在一定顺便的情况下，会把结点内容相互交换，再更新结点的指针域改掉，可以减小CACHE不命中的情况。

结点： A      -> B     -> C     -> D      -> NULL
地址：1000 -> 3000-> 4000-> 5000 -> NULL

还有一种就是采用大结点方法，半顺序存储半链式存储，这个大结点的大小取什么值，太大了浪费空间，太小了效率优化又不够，适当的数值可以通过很多次实验来得出。

bluefire9213

当然，我举的只是简单的例子，为了证明在CACHE命中率方面，算法还是可以做一点优化的。如果STL算法大师在设计STL时考虑到了CACHE命中率的问题，他们做的优化肯定不止这点皮毛。

游戏战士

我觉得应该没有吧，CACHE命中率和具体代码关系是密切的

bluefire9213

是啊，不能说跟代码是完全两回事。

moremoretime

我一直不觉得STL快,基本上感觉慢.
只有为自己程序定做的,才能达到最高效率.

bluefire9213

有哪位高人读过STL源码的，望告知。

whb9633

楼主..根本就不可能预测下一步访问的地址，又怎么优化？因为内存的分配和回收是随机的，而且可能同一块地址被分配和释放多次，又怎么能“把linktable的地址放近一些”？SGI的stl用的是数组，不是真正意义上的链表。比如这样，初始化的时候分配了T[10]，然后连成假链表A->B->C->D->E...(A,B,C,D表示节点，B是A的下一个节点，以此论推之)。然后A,B,C，D被分配掉了，这时表头应该指向了E,然后C被原来分配的程序释放了，这时表头指向C，C的下一个节点指向了E...这就是东基于块的内存分配的基本样式，你能怎么优化？
SGI的源码应该很多人看过，我也看过,自己没看到也没听人说过做cache优化的......
内存管理真正的作用在于：1.提高内存利用率，减少内存碎片，2.提高小块内存分配的速度3.提供一些外围的内存检查和调试信息、leak报告等.