为什么遍历比在两个排序的std :: list上合并更耗时？

Question

令我非常惊讶的是,遍历需要花费更多时间而不是合并两个排序std::list大约12%的结果.由于可以将合并视为连续元素比较并将其实现,因此列表拼接和迭代器遍历两个分开的已排序链接列表.因此,遍历不应该比通过它们合并慢,特别是当两个列表足够大时,因为迭代元素的比率增加.

然而,结果似乎与我的想法不符,这就是我测试上面的想法的方式:

std::list<int> list1, list2;

for (int cnt = 0; cnt < 1 << 22; cnt++)
    list1.push_back(rand());
for (int cnt = 0; cnt < 1 << 23; cnt++)
    list2.push_back(rand());

list1.sort();
list2.sort();

auto start = std::chrono::system_clock::now();  // C++ wall clock

// Choose either one option below
list1.merge(list2);         // Option 1
for (auto num : list1);     // Option 2
for (auto num : list2);     // Option 2

std::chrono::duration<double> diff = std::chrono::system_clock::now() - start;
std::cout << std::setprecision(9) << "\n       "
          << diff.count() << " seconds (measured)" << std::endl;  // show elapsed time

PS.icc足够聪明,可以消除选项2.尝试sum += num;打印出来sum.

这是以下输出perf:(测量时间保持不变,不使用perf)

选项1:合并

       0.904575206 seconds (measured)

 Performance counter stats for './option-1-merge':

    33,395,981,671      cpu-cycles
       149,371,004      cache-misses              #   49.807 % of all cacherefs
       299,898,436      cache-references
    24,254,303,068      cycle-activity.stalls-ldm-pending    

       7.678166480 seconds time elapsed

选项2:遍历

       1.01401903 seconds (measured)

 Performance counter stats for './option-2-traverse':

    33,844,645,296      cpu-cycles
       138,723,898      cache-misses             #   48.714 % of all cacherefs
       284,770,796      cache-references
    25,141,751,107      cycle-activity.stalls-ldm-pending

       7.806018949 seconds time elapsed

由于这些链接列表中可怕的空间位置的属性.缓存未命中是导致CPU停滞并占用大部分CPU资源的主要原因.奇怪的是,选项2比选项1具有更少的缓存未命中,但它具有更高的CPU停顿和CPU周期来完成其任务.是什么让这种异常发生？

Answer 1

如您所知，记忆占用了您所有的时间。

缓存未命中很糟糕，但停顿也很糟糕。

从这篇论文：

具有不规则内存访问模式的应用程序（例如，在遍历链表或树时解引用指针链）可能无法生成足够的并发未完成请求来充分利用数据路径。然而，此类应用显然也受到内存访问性能的限制。因此，考虑带宽利用率不足以检测所有与内存相关的性能问题。

基本上，随机移动指针可能无法使内存带宽饱和。

通过等待下一个指针被加载的位置，每个迭代上的紧密循环都会被阻塞。如果它不在缓存中，CPU 将无能为力——它会停止运行。

组合的紧密循环/合并尝试将两个页面加载到缓存中。当一个正在加载时，有时cpu 会先于另一个。

您测量的结果是，合并比裸浪费的双迭代具有更少的停顿。

或者换句话说，

24,254,303,068      cycle-activity.stalls-ldm-pending 

是一个大数且小于：

25,141,751,107      cycle-activity.stalls-ldm-pending

我很惊讶这足以产生 10% 的差异，但这就是为什么性能是关于测量的。