为何在此场景下std::array<int,10>比std::vector<int>(10)更快？

问题场景 #

给定N个不同的数（N∈[3,1000000]，数值范围[0,18446744073709551616)），统计输入中可通过重排另一个数的数字得到的数的总数。实现代码中，使用std::vector<std::array<int, 10>> lut(n)时执行时间为550-600ms，改为std::vector<std::vector<int>> lut(n, std::vector<int>(10))后执行时间骤升至1050-1150ms，两者均涉及堆分配，为何前者性能更优？

核心原因拆解 #

• 内存连续性带来的缓存效率提升
  std::array<int,10>是固定大小的聚合类型，存入vector时，每个array的10个int直接嵌入到vector的连续内存块中。整个vector<array<int,10>>的存储空间完全连续，CPU缓存可以一次性加载大量相邻数据，大幅减少缓存 miss 概率，统计数字频率、排序、比较等操作都能高效利用缓存。
  而vector<vector<int>>是嵌套结构：外层vector存储指向内层vector堆内存的指针，每个内层vector的10个int都在独立的小堆块里。数据碎片化严重，CPU缓存无法有效利用，每次访问元素都可能触发缓存失效，读写效率暴跌。

• 堆分配次数的巨大差异
  vector<array<int,10>>只需要1次堆分配：为整个vector申请一块能容纳n个array<int,10>的连续内存即可。
  而vector<vector<int>>需要n+1次堆分配：外层vector占1次，每个内层vector还要单独申请自己的内存块。大量小内存分配会触发更多系统调用（如malloc/free），同时加剧内存碎片，带来显著的内存管理开销。

• 排序与比较操作的效率差距
  排序过程中需要频繁比较和交换元素：

  • 对于array<int,10>，比较是直接对连续的10个int进行批量内存比对，交换也是一次性移动40字节（假设int为4字节）的连续块，操作极快。
  • 对于vector<int>，比较时需先检查大小（此处虽均为10，但仍有额外逻辑），再逐个访问分散在堆中的元素；交换仅交换指针，但后续访问元素仍需跳转到独立堆块，缓存命中率极低，拖慢整个排序流程。

• 初始化开销的累积
  vector<array<int,10>>初始化时，可通过批量内存操作完成所有元素的清零（或默认初始化）；而每个vector<int>(10)都要单独初始化自己的堆内存，重复的小内存初始化操作累积起来，也会增加不少执行时间。

内容的提问来源于stack exchange，提问作者Petar Ivanov