如何优化以下公共循环？

Question

我有密码

#include <iostream>
#include <vector>
#include <ctime>
using namespace std;

void foo(int n, double* a, double* b, double *c, double*d, double* e, double* f, double* g)
{
    for (int i = 0; i < n; ++i)
        a[i] = b[i] * a[i] + c[i] * (d[i] + e[i] + f[i] + g[i]);
}

int main()
{
    int m = 1001001;
    vector<double> a(m), b(m), c(m), d(m), f(m);

    clock_t start = std::clock();

    for (int i = 0; i < 1000; ++i)
        foo(1000000, &a[0], &b[0], &c[0], &d[0], &d[1], &f[0], &f[1000] );

    double duration = (std::clock() - start) / (double)CLOCKS_PER_SEC;
    cout << "Finished in " << duration << " seconds [CPU Clock] " << endl;
}

你能给我一个可行的例子来优化它以获得更好的性能吗？任何编译器都可以，比如 Intel c++ 编译器和 visual c++ 编译器。请推荐一个 CPU 性能好的人来做这样的工作。

Answer 1

我认为你应该使用多线程。更改 foo 以获取 fromIndex、toIndex，而不是 n 并在线程上分发向量。

void foo(int fromIndex, int toIndex, double* a, double* b, double *c, double*d, double* e, double* f, double* g)
{
    for (int i = fromIndex; i < toIndex; ++i)
        a[i] = b[i] * a[i] + c[i] * (d[i] + e[i] + f[i] + g[i]);
}

Answer 2

在 apple clang 上，我试过：

在参数上使用 __restict__ 使编译器相信没有别名。

结果：无变化

将计算分布在 foo()

结果：计算时间增加，从 ~3 秒增加到 ~18 秒！

使用#pragma omp parallel for

结果：编译器忽略了我并保留了原始解决方案。 ~3 秒。

设置命令行选项 -march=native 以允许 cpu 的全部魅力闪耀

结果：不同的汇编程序输出（应用了矢量化），但运行时间仍然保持不变，为 ~3s

初步结论：

此问题受内存访问限制，而不受 CPU 限制。

Answer 3

有问题的代码没有用。它使用未初始化的变量进行大量计算，然后忽略结果。编译器越来越聪明地解决这类问题并为此删除所有代码。因此，如果像这样的代码根本不需要任何时间，请不要感到惊讶。

在 C 中，您可以将指针声明为 "const double* restrict" 除了一个是 double* restrict，告诉编译器除了第一个指针之外的所有指针都指向在期间不会被修改的数据循环；这允许编译器进行矢量化。不幸的是，afaik 不是 C++ 功能。

如果这是你的真正问题，你只需交换内循环和外循环，并像这样删除循环不变量：

void foo(int iter, int n, double* a, double* b, double *c, double*d, double* e, double* f, double* g)
{
    for (int i = 0; i < n; ++i) {
        double xa = a [i];
        double xb = b [i];
        double xr = c[i] * (d[i] + e[i] + f[i] + g[i]);

        for (int j = 0; j < iter; ++j)
            xa = xb * xa + xr;

        a [i] = xa;
    }
}

您可能会并行执行四次迭代以避免延迟。

但在现实生活中，您会发现在每次调用中，您读取了大约 40MB，这远远超出了任何缓存。所以你受到 RAM 速度的限制。通常的解决方案是将工作分成更小的部分，例如一次 500 个元素，所以所有内容都适合 L1 缓存，然后对相同的数据执行 1000 次操作。

Answer 4

您可以尝试将向量预取到缓存行中，然后以 8 个为一组对它们进行操作（8 个双精度数将适合每个缓存行）。

确保在 x[i] 到 x[i+7] 上操作时，你正在预取 x[i+8] 到 x[i+15]。

这可能无济于事，因为您使用的加法和乘法速度太快，以至于您的 RAM 可能无法跟上。

如何优化以下公共循环？

How to optimize the following common loop?

c++

optimization

loops

multicore

vectorization