排序与 Cache Miss

最近学完了 CSE 6220 这门课,补完了一些基础理论知识。这门课有6个 lab work,最后一个 Cache-Oblivious Sorting 有些意思,记录一点我的思考。

理论背景

问题的讨论基于经典的快-慢两层存储器的机器模型:

  • 处理器连接一个容量为 $Z$ 的快速存储器,和一个容量几乎无穷的低速存储器;
  • 处理器使用数据之前,数据必须先从低速存储器调入快速存储器,每次读入大小为 $L$ 的数据;
  • 假定快速存储器使用最优的替换策略。

在 CPU-RAM 中,快速存储器对应各级 data cache,低速存储器对应 RAM,Cache Line 大小对应 $L$;在 RAM-Disk 中,快速存储器对应 RAM,低速存储器对应 HDD/SSD。

常用的基于二路分治策略的排序算法如快速排序和二路归并排序都是 Cache-Oblivious 的,即可以利用分治法来适应各种大小的 cache。然而,它们对 cache 的利用并不好。这一点初看有点难以接受,因为快排和二路归并的访问都具有局部性,即它们都是依次比较相邻的数据,这样一次 load 进来的 cache line 中的元素都会被用到。问题出在哪里呢?

问题出在分治递归树的高度上。如果我们把二路归并改成 $K$ 路归并,那么每一层计算的时候,仍然需要读入全部 $N$ 个元素,但是递归树的高度从 $ log_2(N) $ 减小到了 $ log_K(N) $ 。因此在理论上,我们只要保证进行 $K$ 路归并时所需的数据都在 cache 中,即可最大化 cache 利用效率。

实验结果

我写了一个手动调节 $K$ 值的 $K$ 路归并排序,在递归划分到小于指定元素的时候直接使用 stdlib 的快排(对,一点都不 Cache-Oblivious,需要手动计算参数)。测试平台是 Xeon E5-2620v2 @ 2.1GHz, 1600MHz DDR3, CentOS 7.2 x86, GCC 4.8.5。Xeon E5-2620v2 每个核心有 32KB L1 data cache,cache line size 为 64B,因此我取了 $K = 128, l = 16$ 这一组参数,$l$ 为读入的 buffer 数组大小。

课程提供的测试方法是关掉 GCC 的优化参数来编译,使用 perf 工具来统计 10 次运行中 L1 data cache miss 数量。排序对象为 8Byte 大小的 long long。测试结果如下:

n qsort time k-way time qsort L1 miss k-way L1 miss k-way/qsort time k-way/qsort L1 miss
8388608 3.09 3.73 6224667 4107852 1.206 0.660
16777217 6.25 7.64 10662456 6244378 1.222 0.586
33554432 12.80 15.22 19258644 11381176 1.189 0.590

课程设置实际上需要我们实现一个 funnel sort,在我看来 funnel sort 只不是两层 multi-way merge sort,操作还更繁琐一些。Brodal 2008 年关于 funnel sort 的论文给出的实现,funnel sort 比 std::sort() 要慢一点,课程资料里也说 funnel sort 的参考实现比 C stdlib 的 qsort 要慢两倍多。我的实现比 qsort 慢了 20% 左右,看起来是正常的。L1 data cache miss 的数据我没有在其他地方找到,课程资料里说他们的参考实现在只有 16KB L1 data cache 的 AMD CPU 上的 k-way/qsort L1 miss 分别是 0.931, 0.809 和 0.723,这个跨了硬件平台,也不太好直接对比。

虽然 k-way merge sort 的 L1 miss 要更少,但是耗费的时间却更多,我认为可能的原因包括:

  • merge sort 需要额外的内存辅助空间和内存拷贝操作带来额外的开销;
  • 多路归并时维护的小根堆和读入缓冲区的额外操作带来常数倍额外操作;
  • 排序算法的性能瓶颈不在 cache 上(CPU 分治预测失败清空流水线的代价比从 L2 或者 L3 取数据更大)。

出于好奇,我使用 -O3 重新编译了程序并进行了测试:

n qsort time k-way time qsort L1 miss k-way L1 miss k-way/qsort time k-way/qsort L1 miss
8388608 2.32 2.15 10927067 4004436 0.925 0.336
16777217 4.62 4.38 18362595 6122074 0.948 0.333
33554432 9.35 8.78 18987204 10529204 0.939 0.555

这个结果就相当有趣了。无论是 stdlib 的 qsort 还是我的实现,速度都提高了 50% 甚至更多。与没有 -O 的时候相比,qsort 的 L1 miss 在 $n = 2^{23}, 2^{24}$ 时显著增大了,而速度也显著提升了。我不知道这里面具体发生了什么,但是这说明 cache miss 和性能并不总是负相关。我的实现的 L1 miss 几乎没有什么变化,大概是我的代码的访存行为和编译器优化后的代码的访存行为没有太大区别。