缓存友好的离线随机读取

Question

考虑一下 C++ 中的这个函数：

void foo(uint32_t *a1, uint32_t *a2, uint32_t *b1, uint32_t *b2, uint32_t *o) {
    while (b1 != b2) {
        // assert(0 <= *b1 && *b1 < a2 - a1)
        *o++ = a1[*b1++];
    }
}

其目的应该足够明确。不幸的是，b1包含随机数据并垃圾缓存，成为foo我的程序的瓶颈。无论如何我可以优化它吗？

这是一个 SSCCE，应该类似于我的实际代码：

#include <iostream>
#include <chrono>
#include <algorithm>
#include <numeric>

namespace {
    void foo(uint32_t *a1, uint32_t *a2, uint32_t *b1, uint32_t *b2, uint32_t *o) {
        while (b1 != b2) {
            // assert(0 <= *b1 && *b1 < a2 - a1)
            *o++ = a1[*b1++];
        }
    }

    constexpr unsigned max_n = 1 << 24, max_q = 1 << 24;
    uint32_t data[max_n], index[max_q], result[max_q];
}

int main() {
    uint32_t seed = 0;
    auto rng = [&seed]() { return seed = seed * 9301 + 49297; };
    std::generate_n(data, max_n, rng);
    std::generate_n(index, max_q, [rng]() { return rng() % max_n; });

    auto t1 = std::chrono::high_resolution_clock::now();
    foo(data, data + max_n, index, index + max_q, result);
    auto t2 = std::chrono::high_resolution_clock::now();
    std::cout << std::chrono::duration<double>(t2 - t1).count() << std::endl;

    uint32_t hash = 0;
    for (unsigned i = 0; i < max_q; i++)
        hash += result[i] ^ (i << 8) ^ i;
    std::cout << hash << std::endl;
}

这不是通过已知索引重新调整的缓存友好的数组复制，聚集，分散，它询问随机写入并假设b是排列。

Answer 1

首先我们看一下上面代码的实际性能：

$ sudo perf stat ./offline-read
0.123023
1451229184

 Performance counter stats for './offline-read':

        184.661547      task-clock (msec)         #    0.997 CPUs utilized          
                 3      context-switches          #    0.016 K/sec                  
                 0      cpu-migrations            #    0.000 K/sec                  
               717      page-faults               #    0.004 M/sec                  
       623,638,834      cycles                    #    3.377 GHz                    
       419,309,952      instructions              #    0.67  insn per cycle         
        70,803,672      branches                  #  383.424 M/sec                  
            16,895      branch-misses             #    0.02% of all branches        

       0.185129552 seconds time elapsed

我们得到的 IPC 为 0.67，这可能几乎完全是由于 DRAM ⁵的加载缺失造成的。我们来确认一下：

sudo ../pmu-tools/ocperf.py stat -e cycles,LLC-load-misses,cycle_activity.stalls_l3_miss ./offline-read
perf stat -e cycles,LLC-load-misses,cpu/event=0xa3,umask=0x6,cmask=6,name=cycle_activity_stalls_l3_miss/ ./offline-read
0.123979
1451229184

 Performance counter stats for './offline-read':

       622,661,371      cycles                                                      
        16,114,063      LLC-load-misses                                             
       368,395,404      cycle_activity_stalls_l3_miss                                   

       0.184045411 seconds time elapsed

因此，62 万个周期中约有 37 万个周期因未命中的未命中而直接停滞。事实上，以这种方式停滞的周期部分foo()要高得多，接近 90%，因为perf还要测量初始化和accumulate代码，这需要大约三分之一的运行时间（但没有明显的 L3 缺失）。

这并不意外，因为我们知道随机读取模式的a1[*b1++]局部性基本上为零。事实上， 的数量LLC-load-misses是 1600 万次¹，几乎完全对应于 的 1600 万次随机读取a1。²

如果我们假设 100%foo()花费在等待内存访问上，我们就可以了解每次未命中的总成本：0.123 sec / 16,114,063 misses == 7.63 ns/miss。在我的机器上，最好情况下内存延迟约为 60 ns，因此每次未命中少于 8 ns 意味着我们已经提取了大量内存级并行性 (MLP)：大约 8 次未命中必须重叠并插入-平均飞行来实现这一点（甚至完全忽略来自流负载b1和流写入的额外流量o）。

所以我认为没有太多的调整可以应用到简单的循环来做得更好。不过，有两种可能性：

• 如果您的平台支持，则用于写入的非临时存储o。这将消除RFO对普通存储隐含的读取。这应该是一场直接的胜利，因为o再也不会被阅读（在定时部分内！）。

• 软件预取。仔细调整a1or的预取b1可能会有所帮助。然而，影响将相当有限，因为如上所述，我们已经接近 MLP 的极限。b1此外，我们预计硬件预取器可以几乎完美地预取线性读取。随机读取a1似乎可以进行预取，但实际上，循环中的 ILP 通过乱序处理（至少在像最近的 x86 这样的大型 OoO 处理器上）导致足够的 MLP。

  在评论中，用户 harold 已经提到他尝试过预取，但效果很小。

因此，由于简单的调整不太可能产生太多成果，因此您只能改变循环。一种“明显”的转换是对索引进行排序b1（以及索引元素的原始位置），然后按a1排序顺序进行读取。这将读取a1从完全随机转变为几乎³线性，但现在写入都是随机的，这也好不到哪儿去。

排序然后取消排序

a1关键问题是在控制下的读取b1是随机的，而且a1很大，基本上每次读取都会丢失到 DRAM。我们可以通过排序来解决这个问题b1，然后读取a1以获得排列的结果。现在您需要“取消排列”结果a1以获得最终顺序的结果，这只是另一种排序，这次是在“输出索引”上。

这是一个使用给定输入数组a、索引数组b和输出数组的工作示例o，以及i每个元素的（隐式）位置：

  i =   0   1   2   3
  a = [00, 10, 20, 30]
  b = [ 3,  1,  0,  1]
  o = [30, 10, 00, 10] (desired result)

首先，对 array 进行排序b，将原始数组位置i作为辅助数据（或者您可能会将其视为排序元组(b[0], 0), (b[1], 1), ...），这将为您提供排序后的b数组b'和排序后的索引列表i'，如下所示：

  i' = [ 2, 1, 3, 0]
  b' = [ 0, 1, 1, 3]

现在您可以在 的控制下o'读取排列后的结果数组。此读取严格按顺序递增，并且应该能够以接近的速度运行。事实上，您也许能够利用宽连续 SIMD 读取和一些洗牌来执行多次读取和一次，并将 4 字节元素移动到正确的位置（复制一些元素并跳过其他元素）：ab'memcpy

  a  = [00, 10, 20, 30]
  b' = [ 0,  1,  1,  3]
  o' = [00, 10, 10, 30]

最后，从概念上讲，您只需对排列后的索引进行排序即可将其反排列为o'get ：oo'i'

  i' = [ 2,  1,  3,  0]
  o' = [00, 10, 10, 30]
  i  = [ 0,  1,  2,  3]
  o  = [30, 10, 00, 10]

完成的！

现在，这是该技术最简单的想法，并且不是特别适合缓存（每个遍在概念上迭代一个或多个 2^26 字节数组），但它至少完全使用它读取的每个缓存行（与原始循环不同）它只从缓存行中读取单个元素，这就是为什么即使数据只占用 100 万个缓存行，也会有 1600 万次未命中！）。所有读取或多或少都是线性的，因此硬件预取将有很大帮助。

您获得多少加速可能取决于您如何实现排序：它们需要快速且对缓存敏感。几乎可以肯定，某种类型的缓存感知基数排序效果最好。

以下是有关进一步改进这一点的一些注意事项：

优化排序量

您实际上不需要完全排序b。您只想对其进行“足够”排序，以便a在 的控制下的后续读取b'或多或少是线性的。例如，一个缓存行中有 16 个元素，因此您根本不需要根据最后 4 位进行排序：无论如何都会读取相同的缓存行线性序列。您还可以对更少的位进行排序：例如，如果您忽略了 5 个最低有效位，您将以“几乎线性”的方式读取缓存行，有时会从完美的线性模式中交换两个缓存行，例如：0, 1, 3, 2, 5, 4, 6, 7。在这里，您仍然可以充分利用 L1 缓存（对缓存行的后续读取始终会命中），并且我怀疑这样的模式仍然可以很好地预取，如果没有，您始终可以通过软件预取来帮助它。

您可以在您的系统上测试忽略位数的最佳值。忽略位有两个好处：

• 基数搜索中要做的工作更少，要么是需要更少的传递，要么是在一个或多个传递中需要更少的存储桶（这有助于缓存）。
• 在最后一步中“撤消”排列可能需要做更少的工作：如果通过检查原始索引数组来撤消b，忽略位意味着您在撤消搜索时可以获得相同的节省。

缓存阻止工作

上面的描述将所有内容展示在几个连续的、不相交的传递中，每个传递都作用于整个数据集。在实践中，您可能希望将它们交错以获得更好的缓存行为。例如，假设您使用 MSD radix-256 排序，您可能会执行第一遍，将数据排序到 256 个桶中，每个桶大约有 256K 个元素。

a然后，您可以只完成第一个（或前几个）存储桶的排序，然后根据 的结果块继续读取 ，而不是执行完整的第二遍b'。您可以保证该块是连续的（即最终排序序列的后缀），因此您不会放弃读取中的任何局部性，并且您的读取通常会被缓存。您也可以执行第一遍解排列，o'因为 的块o'在缓存中也很热（也许您可以将后两个阶段合并到一个循环中）。

智能解排列

o'优化的一个领域是如何准确地实现 的反排列。在上面的描述中，我们假设一些索引数组i最初具有与[0, 1, 2, ..., max_q]一起排序的值b。从概念上讲，这就是它的工作原理，但您可能不需要i立即具体化并将其分类为辅助数据。例如，在基数排序的第一遍中， 的值i是隐式已知的（因为您正在迭代数据），因此可以免费计算⁴并在第一遍期间写出，而无需每个都按排序顺序出现。

可能还有比维护完整索引更有效的方法来执行“取消排序”操作。例如，原始未排序b数组在概念上具有执行取消排序所需的所有信息，但我很清楚如何使用它来有效地取消排序。

是不是更快一点？

那么这实际上会比简单的方法更快吗？这在很大程度上取决于实现细节，尤其是包括实现排序的效率。在我的硬件上，最简单的方法是每秒处理大约 1.4 亿个元素。缓存感知基数排序的在线描述似乎从 200 到 6 亿个元素/秒不等，并且由于您需要其中两个元素，因此如果您相信这些数字，那么大幅加速的机会似乎有限。另一方面，这些数字来自较旧的硬件，并且用于稍微更一般的搜索（例如，对于密钥的所有 32 位，而我们可能能够使用少至 16 位）。

只有仔细实现才能决定是否可行，而可行性还取决于硬件。例如，在无法支持尽可能多的 MLP 的硬件上，排序-不排序方法变得相对更有利。

最佳方法还取决于max_n和的相对值max_q。例如，如果max_n >> max_q，那么即使采用最佳排序，读取也将是“稀疏”的，因此朴素方法会更好。另一方面，如果max_n << max_q，则相同的索引通常会被读取多次，因此排序方法将具有良好的读取局部性，排序步骤本身将具有更好的局部性，并且可以进行显式处理重复读取的进一步优化。

多核

从问题中尚不清楚您是否有兴趣并行化它。天真的解决方案foo()已经承认“直接”并行化，您只需将a和b数组划分为每个线程的相同大小的块，这似乎提供了完美的加速。不幸的是，您可能会发现比线性扩展更糟糕，因为您将遇到内存控制器中的资源争用以及在套接字上的所有核心之间共享的相关非核心/非核心资源。因此，当您添加更多核心⁶时，尚不清楚将纯并行随机读取加载到内存时可以获得多少吞吐量。

对于基数排序版本，大多数瓶颈（存储吞吐量、总指令吞吐量）都在核心中，因此我希望它能够通过额外的核心进行合理扩展。正如 Peter 在评论中提到的，如果您使用超线程，排序可能具有核心本地 L1 和 L2 缓存中良好局部性的额外好处，有效地让每个兄弟线程使用整个缓存，而不是将有效容量削减一半。当然，这涉及仔细管理线程关联性，以便同级线程实际使用附近的数据，而不仅仅是让调度程序执行它所做的任何事情。

¹您可能会问为什么LLC-load-misses不说 32 或 4800 万个，因为我们还必须读取 的所有 1600 万个元素b1，然后accumulate()调用读取 的所有元素result。答案是只计算L3 中实际LLC-load-misses未命中的需求未命中。其他提到的读取模式是完全线性的，因此预取器总是会在需要之前将行带入 L3。根据 perf 使用的定义，这些不算作“LLC 未命中”。

²您可能想知道我如何知道加载未命中全部来自a1in的读取foo：我只是使用perf record和perf mem来确认未命中来自预期的汇编指令。

³ 几乎线性，因为b1不是所有索引的排列，所以原则上可以存在跳过索引和重复索引。然而，在缓存行级别，每个缓存行很可能会按顺序读取，因为每个元素都有大约 63% 的机会被包含，并且一个缓存行有 16 个 4 字节元素，因此只有任何给定的缓存有零个元素的可能性约为千万分之一。因此，在缓存行级别工作的预取将工作得很好。

⁴这里我的意思是，值的计算是免费的或几乎免费的，但当然写入仍然需要付费。然而，这仍然比“预先实现”方法好得多，“预先实现”方法首先创建需要写入的i数组，然后再次需要另一次写入以在第一个基数排序过程中对其进行排序。隐式物化仅发生第二次写入。[0, 1, 2, ...]max_qmax_q

⁵事实上，实际定时部分的IPCfoo()要低得多：根据我的计算，约为0.15。整个流程上报的IPC是该定时段的IPC和前后的初始化和累加代码的平均，其IPC要高得多。

⁶值得注意的是，这与依赖负载延迟限制工作流程的扩展方式不同：正在进行随机读取的负载，但只能有一个负载正在进行，因为每个负载都依赖于最后一个负载的结果，因此可以很好地扩展到多个核心，因为负载的串行性质不会使用许多下游资源（但从概念上讲，即使在单个核心上，也可以通过更改核心循环以并行处理多个相关负载流来加速此类负载）。