为什么处理多个数据流比处理一个数据流慢？

Question

我正在测试读取多个数据流如何影响 CPU 的缓存性能。我正在使用以下代码对此进行基准测试。基准读取顺序存储在内存中的整数并顺序写回部分总和。从中读取的顺序块的数量是变化的。块中的整数以循环方式读取。

#include <iostream>
#include <vector>
#include <chrono>
using std::vector;
void test_with_split(int num_arrays) {
    int num_values = 100000000;
    // Fix up the number of values. The effect of this should be insignificant.
    num_values -= (num_values % num_arrays);
    int num_values_per_array = num_values / num_arrays;
    // Initialize data to process
    auto results = vector<int>(num_values);
    auto arrays = vector<vector<int>>(num_arrays);
    for (int i = 0; i < num_arrays; ++i) {
        arrays.emplace_back(num_values_per_array);
    }
    for (int i = 0; i < num_values; ++i) {
        arrays[i%num_arrays].emplace_back(i);
        results.emplace_back(0);
    }
    // Try to clear the cache
    const int size = 20*1024*1024; // Allocate 20M. Set much larger then L2
    char *c = (char *)malloc(size);
    for (int i = 0; i < 100; i++)
        for (int j = 0; j < size; j++)
            c[j] = i*j;
    free(c);
    auto start = std::chrono::high_resolution_clock::now();
    // Do the processing
    int sum = 0;
    for (int i = 0; i < num_values; ++i) {
        sum += arrays[i%num_arrays][i/num_arrays];
        results[i] = sum;
    }
    std::cout << "Time with " << num_arrays << " arrays: " << std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now() - start).count() << " ms\n";
}
int main() {
    int num_arrays = 1;
    while (true) {
        test_with_split(num_arrays++);
    }
}

以下是在 Intel Core 2 Quad CPU Q9550 @ 2.83GHz 上拆分 1-80 路的时序：

8 个流后不久速度的提升对我来说很有意义，因为处理器有一个 8 路关联 L1 缓存。 24 路关联 L2 高速缓存反过来解释了 24 个流的冲击。如果我得到与 Why is one loop so much slower than two loops? 中相同的效果，这些尤其成立，其中多个大分配总是以相同的关联集结束。为了进行比较，我在结束时包括了在一个大块中完成分配的时间。

但是，我并不完全理解从一个流到两个流的颠簸。我自己的猜测是它与预取到 L1 缓存有关。阅读 Intel 64 and IA-32 Architectures Optimization Reference Manual 似乎 L2 流预取器支持跟踪多达 32 个数据流，但没有为 L1 流预取器提供此类信息。 是 L1 预取器无法跟踪多个流，还是这里有其他问题？

背景

我正在对此进行调查，因为我想了解将游戏引擎中的实体组织为数组结构样式中的组件如何影响性能。目前看来，转换所需的数据包含两个组件而不是包含 8-10 个组件对于现代 CPUs 来说并不重要。但是，上面的测试表明，如果允许 "bottlenecking" 转换仅使用一个组件，有时避免将某些数据拆分为多个组件可能是有意义的，即使这意味着其他一些转换必须读取数据没兴趣。

在一个块中分配

这里是时间安排，如果不是分配多个数据块，只有一个以跨步方式分配和访问。这不会将碰撞从一个流更改为两个，但为了完整起见，我将其包括在内。

这里是修改后的代码：

void test_with_split(int num_arrays) {
    int num_values = 100000000;
    num_values -= (num_values % num_arrays);
    int num_values_per_array = num_values / num_arrays;

    // Initialize data to process
    auto results = vector<int>(num_values);
    auto array = vector<int>(num_values);
    for (int i = 0; i < num_values; ++i) {
        array.emplace_back(i);
        results.emplace_back(0);
    }

    // Try to clear the cache
    const int size = 20*1024*1024; // Allocate 20M. Set much larger then L2
    char *c = (char *)malloc(size);
    for (int i = 0; i < 100; i++)
        for (int j = 0; j < size; j++)
            c[j] = i*j;
    free(c);

    auto start = std::chrono::high_resolution_clock::now();
    // Do the processing
    int sum = 0;
    for (int i = 0; i < num_values; ++i) {
        sum += array[(i%num_arrays)*num_values_per_array+i/num_arrays];
        results[i] = sum;
    }
    std::cout << "Time with " << num_arrays << " arrays: " << std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now() - start).count() << " ms\n";
}

编辑 1

我确保 1 对 2 拆分差异不是由于编译器展开循环并以不同方式优化第一次迭代。使用 __attribute__ ((noinline)) 我确保工作函数没有内联到主函数中。我通过查看生成的程序集验证它没有发生。这些更改后的时间是相同的。

Answer 1

回答问题的主要部分：L1 预取器是否能够跟踪多个流？

没有。这实际上是因为 L1 缓存根本没有预取器。 L1 缓存不够大，无法冒险获取可能不会使用的数据。它会导致太多的驱逐，并对任何不以适合特定 L1 缓存预测方案的特定模式读取数据的软件产生不利影响。相反，L1 缓存已被 显式读取或写入的数据。 L1 缓存仅在您写入数据和重新读取最近访问过的数据时有用。

L1 缓存实现不是您的配置文件从 1X 到 2X 阵列深度的原因。在像您设置的那样进行流式读取时，L1 缓存对性能的影响很小或没有影响。您的大部分读取都直接来自 L2 缓存。在您使用嵌套向量的第一个示例中，一些读取可能是从 L1 中提取的（见下文）。

我猜你从 1X 到 2X 的提升与算法以及编译器如何优化它有很大关系。如果编译器知道 num_arrays 是一个等于 1 的常量，那么它会自动为您消除很多每次迭代的开销。

现在开始第二部分，关于为什么第二个版本更快？：

第二个版本速度更快的原因与其说是数据在物理内存中的排列方式，不如说是嵌套 std::vector<std::vector<int>> 类型所暗示的底层逻辑更改。

在嵌套（第一种）情况下，编译代码执行以下步骤：

访问顶级 std::vector class。 class 包含指向数据数组开头的指针。
必须从内存中加载该指针值。
将当前循环偏移量 [i%num_arrays] 添加到该指针。
访问嵌套的 std::vector class 数据。（可能命中 L1 缓存）
加载指向向量数据数组开头的指针。（可能命中 L1 缓存）
添加循环偏移量[i/num_arrays]
读取数据。终于！

（注意在大约 24 个流后，在步骤 #4 和 #5 中获得 L1 缓存命中的机会急剧减少，因为在循环的下一次迭代之前驱逐的可能性）

第二个版本，对比：

访问顶级 std::vector class.
加载指向向量数据数组开头的指针。
添加偏移量[(i%num_arrays)*num_values_per_array+i/num_arrays]
读取数据！

删除了一整套后台步骤。 offset 的计算稍微长一些，因为它需要额外乘以 num_values_per_array。但其他步骤足以弥补它。

为什么处理多个数据流比处理一个数据流慢？

Why is processing multiple streams of data slower than processing one?

c++

performance

caching

cpu

data-oriented-design

背景

在一个块中分配

编辑 1