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

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路关联L1缓存,因此8个流后不久的速度提升对我来说很有意义.24路关联L2缓存反过来解释了24个流的颠簸.如果我得到的效果与为什么一个循环比两个循环慢得多,那么这些特别有用？,多个大分配总是在同一个关联集中.比较我在一个大块中完成分配时的结束时间.

但是,我不完全理解从一个流到两个流的颠簸.我自己的猜测是它与预取到L1缓存有关.阅读英特尔64和IA-32架构优化参考手册,L2流式预取器似乎支持跟踪多达32个数据流,但没有为L1流式预取器提供此类信息.L1预取器是否无法跟踪多个流,或者此处还有其他内容？

背景

我正在研究这个问题,因为我想了解游戏引擎中的组织实体作为数组结构样式中的组件如何影响性能.现在看来,转换所需的数据分为两个组件而不是8-10个组件,这对于现代CPU来说并不重要.但是,上面的测试表明,如果允许"瓶颈"转换仅使用一个组件,有时可能有必要避免将某些数据拆分为多个组件,即使这意味着某些其他转换必须读取数据不感兴趣.

分配到一个区块

以下是如果改为分配多个数据块,则只有一个以分步方式分配和访问的时序.这不会将碰撞从一个流改变为两个,但为了完整起见,我已将其包括在内.

以下是修改后的代码:

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 vs 2分裂差异不是由于编译器展开循环并以不同方式优化第一次迭代.使用__attribute__ ((noinline))我确保工作功能没有内联到主函数中.我通过查看生成的程序集验证了它没有发生.这些改变后的时间是一样的.

Answer 1

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

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

L1 缓存实现并不是您的配置文件从 1 倍阵列深度增加到 2 倍阵列深度的原因。在像您所设置的那样进行流式读取时，L1 缓存对性能影响很小或根本不影响。大多数读取直接来自二级缓存。在您使用嵌套向量的第一个示例中，某些数量的读取可能是从 L1 中提取的（见下文）。

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

现在来说第二部分，为什么第二个版本更快？：

第二个版本更快的原因并不在于数据在物理内存中的排列方式，而在于嵌套类型隐含的底层逻辑变化std::vector<std::vector<int>>。

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

1. 访问顶级std::vector类。此类包含指向数据数组开头的指针。
2. 该指针值必须从内存加载。
3. 将当前循环偏移添加[i%num_arrays]到该指针。
4. 访问嵌套std::vector类数据。（可能是 L1 缓存命中）
5. 加载指向向量数据数组开头的指针。（可能是 L1 缓存命中）
6. 添加循环偏移[i/num_arrays]
7. 读取数据。最后！

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

相比之下，第二个版本：

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

一整套底层步骤被移除。偏移量的计算稍微长一些，因为它需要额外乘以num_values_per_array。但其他步骤足以弥补这一点。