pair<double,double> 的数组如何比两个双 C++ 数组快 2 倍

Question

#include <iostream>
#include <chrono>
#include <random>
#include <time.h>
using namespace std;

typedef pair<double,double> pd;
#define x first
#define y second
#define cell(i,j,w) ((i)*(w) + (j))

class MyTimer
{
private:
    std::chrono::time_point<std::chrono::steady_clock> starter;
    std::chrono::time_point<std::chrono::steady_clock> ender;

public:
    void startCounter() {
        starter = std::chrono::steady_clock::now();
    }

    long long getCounter() {
        ender = std::chrono::steady_clock::now();
        return std::chrono::duration_cast<std::chrono::milliseconds>(ender - starter).count();
    }
};
        
int main()
{
    const int n = 5000;
    int* value1 = new int[(n + 1) * (n + 1)];
    int* value2 = new int[(n + 1) * (n + 1)];
    double* a = new double[(n + 1) * (n + 1)];
    double* b = new double[(n + 1) * (n + 1)];
    pd* packed = new pd[(n + 1) * (n + 1)];
    MyTimer timer;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            value1[cell(i, j, n + 1)] = rand() % 5000;
            value2[cell(i, j, n + 1)] = rand() % 5000;
        }

    for (int i = 1; i <= n; i++) {
        a[cell(i, 0, n + 1)] = 0;
        a[cell(0, i, n + 1)] = 0;
        b[cell(i, 0, n + 1)] = 0;
        b[cell(0, i, n + 1)] = 0;
        packed[cell(i, 0, n + 1)] = pd(0, 0);
        packed[cell(0, i, n + 1)] = pd(0, 0);
    }

    for (int tt=1; tt<=5; tt++)
    {
        timer.startCounter();
        for (int i=1; i<=n; i++)
            for (int j = 1; j <= n; j++) {
                // packed[i][j] = packed[i-1][j] + packed[i][j-1] - packed[i-1][j-1] + value1[i][j]
                packed[cell(i, j, n + 1)].x = packed[cell(i - 1, j, n + 1)].x + packed[cell(i, j - 1, n + 1)].x - packed[cell(i - 1, j - 1, n + 1)].x + value1[cell(i, j, n + 1)];
                packed[cell(i, j, n + 1)].y = packed[cell(i - 1, j, n + 1)].y + packed[cell(i, j - 1, n + 1)].y - packed[cell(i - 1, j - 1, n + 1)].y + value1[cell(i, j, n + 1)] * value1[cell(i, j, n + 1)];
            }
        cout << "Time packed  = " << timer.getCounter() << "\n";

        timer.startCounter();
        for (int i=1; i<=n; i++)
            for (int j = 1; j <= n; j++) {
                // a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + value2[i][j];
                // b[i][j] = b[i-1][j] + b[i][j-1] - b[i-1][j-1] + value2[i][j] * value2[i][j];
                a[cell(i, j, n + 1)] = a[cell(i - 1, j, n + 1)] + a[cell(i, j - 1, n + 1)] - a[cell(i - 1, j - 1, n + 1)] + value2[cell(i, j, n + 1)];
                b[cell(i, j, n + 1)] = b[cell(i - 1, j, n + 1)] + b[cell(i, j - 1, n + 1)] - b[cell(i - 1, j - 1, n + 1)] + value2[cell(i, j, n + 1)] * value2[cell(i, j, n + 1)];
            }
        cout << "Time separate = " << timer.getCounter() << "\n\n";
    }

    delete[] value1;
    delete[] value2;
    delete[] a;
    delete[] b;
    delete[] packed;
}

所以我正在计算二维前缀 table（总面积 Table）。我注意到标题中的属性。

当使用命令行或Visual Studio发布模式使用 CUDA nvcc 编译器（带 -O2）时，结果快 2 倍（单独需要 200 毫秒，打包需要100 毫秒）第一个运行，但在随后的运行中只快 25%（这是因为 value2[] 在第一个循环之后被缓存）。在我的计算步骤更多的实际程序中（计算 SAT 只是第 1 步），它总是快 2 倍，因为 value1[] 和 value2[] 肯定已从缓存中逐出。

我知道打包数组更快，因为现代英特尔 CPU 一次将 32-64 字节读入缓存 。因此，通过将两个数组打包在一起，它可以 在 1 个主存储器 (RAM) 访问而不是 2 中读取两个数据。但是为什么加速比这么高？除了内存访问，CPU 仍然必须在每个循环中执行 6 次加法、2 次减法和 1 次乘法。将内存访问减半的 2 倍加速是 100% 的效率提升（阿姆达尔定律），与那些 add/mult 操作 没有一样存在。怎么可能？

我确定它与 CPU 流水线有关，但无法解释得更透彻。谁能根据指令 latency/memory 访问 latency/assembly 进一步解释这一点？谢谢。

该代码不使用任何 GPU，因此任何其他好的编译器应该提供与 nvcc 相同的 2 倍加速。在 g++ 9.3.0 (g++ file.cpp -O2 -std=c++11 -o file.exe) 上，它也是 2 倍加速。 CPU 是英特尔 i7-7700

我运行这个程序 here and here2 带有命令行参数 -O2 -std=c++11，它还显示了 1.5-2 倍的加速。 使用 n = 3000，再大也不会运行（毕竟免费的 VM 服务）。所以不只是我的电脑

Answer 1

答案在于不同级别内存的访问延迟，从 L1 缓存 -> 主内存 (RAM)。

L1 缓存中的数据需要~~5 个周期才能访问，而来自 RAM 的数据需要 50-100 个周期。同时，add/sub/mult 操作需要 3-5 个周期。

因此，性能的主要限制因素是主内存访问。所以通过将主内存请求的数量减少一半，性能几乎翻倍

pair<double,double> 的数组如何比两个双 C++ 数组快 2 倍

How is array of pair<double,double> 2 times faster than two arrays of double C++

c++

caching

memory

cpu-registers

cpu-cache