为什么被修改后的std::vector遍历速度比未修改的std::vector慢？

核心原因和std::vector本身的遍历速度无关，本质是CPU缓存的空间局部性失效、TLB（地址翻译快表）命中率暴跌导致的内存访问开销大幅上升，具体过程如下：

• 初始分配字符串阶段：你在循环中连续调用new分配2400万个字符串，初始堆状态没有内存碎片的情况下，这些字符串的虚拟内存地址是近乎连续排布的，vector里相邻位置的指针指向的字符串在物理内存上也挨在一起。
• 第一次遍历阶段：你按照vector的初始顺序（也就是字符串的内存分配顺序）依次访问每个字符串，访问顺序和内存排布顺序完全匹配，完美符合CPU缓存的空间局部性要求：CPU硬件预取器会自动将后续要访问的内存提前加载到高速缓存中，同时TLB的命中率接近100%，几乎没有额外的内存访问开销，所以速度极快。
• 排序后第二次遍历阶段：std::sort会按照字符串的字典序重排vector中存储的指针顺序，这个顺序和字符串原本的内存分配顺序完全无关。此时遍历vector时，每次访问的字符串内存地址是随机跳变的，空间局部性完全失效：
  • CPU预取器无法预测下一次要访问的内存地址，不能提前加载数据到缓存，绝大多数访问都会触发Cache Miss，需要从主存读取数据，而主存的访问延迟是L1高速缓存的100倍以上
  • 随机跳变的地址大概率落在不同的内存页上，TLB命中率大幅下降，虚拟地址转物理地址的翻译开销也会急剧增加

如果省略std::sort调用，第二次遍历的指针顺序和第一次完全一致，而且第一次遍历已经把所有字符串数据加载到了缓存中，第二次直接读缓存自然速度和第一次差不多。换成std::random_shuffle也会变慢的原因同理：只要打乱了vector中指针的顺序，破坏了访问顺序和内存排布的一致性，就会出现同样的现象。

内容的提问来源于stack exchange，提问作者Renol P. H.