集体或个人循环以获得最佳性能？

Question

假设我在 C 中有 N 个相同大小的连续数组(或任何其他语言 - 我想这无关紧要)。我想遍历这些数组并对每个数组元素执行一些操作。这可以通过单个循环来实现，因为所有 N 数组的大小都相同。但是，由于计算机内存的工作方式，对每个数组执行单独的循环会更快吗？

具体来说，假设 N 非常大，可能有几十亿，这使得每个数组的大小都有好几千兆字节。此外，数组实际上是 3D 的，这意味着一个完整的“数组循环”实际上是三个嵌套循环。从三个循环变量计算数组指针的算法的复杂性与对数组元素的实际操作的复杂性相当，这就是为什么我害怕添加不必要的循环。

“显而易见”的答案是只编写两个程序，看看哪个在我的特定情况下表现最好。然而，我想听到一些关于如何判断这种情况的更深思熟虑的论点/指南，因为它超出了我自己的编程直觉。

Answer 1

我最初的直觉是每个数组一个循环会更好，因为数据局部性将有助于缓存。

将所有数组放在一个循环中会污染缓存(当处理第一个数组时，缓存将(部分)填充该数组的某些元素，但在下一行代码中，您将需要数据第二个数组和缓存将无法提供帮助)。

两种情况下的理论复杂度保持不变。

---

但是，这取决于您拥有的数组数量(我现在不是说连续的)。必须一次又一次地从头开始循环可以超过每次循环一个数组的方法可以提供的缓存加速，如下所示:

Georgioss-MacBook-Pro:~ gsamaras$ cat bigloop.c
#include <stdio.h>
#include <sys/time.h>
#include <time.h>

#define N 100000

typedef struct timeval wallclock_t;
void wallclock_mark(wallclock_t *const tptr);
double wallclock_since(wallclock_t *const tptr);

// gcc -Wall -O3 bigloop.c -o bigloop
int main(void)
{
    int a[N], b[N], c[N], d[N], e[N], i;

    wallclock_t  t;
    double  s;

    wallclock_mark(&t);
    for(i = 0; i < N; ++i)
    {
        a[i] = i * 10 + (i - 2);
        b[i] = i * 9 + (i - 3);
        c[i] = i * 8 + (i - 1);
        d[i] = i * 11 + (i - 5);
        e[i] = i * 5 + (i - 0);
    }
    s = wallclock_since(&t);
    printf("Populating took %.9f seconds wall clock time.\n", s);

    wallclock_mark(&t);
    for(i = 0; i < N; ++i)
    {
        a[i] = e[i] + (i - 1);
        b[i] = d[i] + (i + 3);
        c[i] = a[i] - (i + 2);
        d[i] = b[i] + (i - 2);
        e[i] = a[i] + (i - 4);
    }
    s = wallclock_since(&t);
    printf("Load/write took %.9f seconds wall clock time.\n", s);

    return 0;
}

#include <stdio.h>
#include <sys/time.h>
#include <time.h>

#define N 100000

typedef struct timeval wallclock_t;
void wallclock_mark(wallclock_t *const tptr);
double wallclock_since(wallclock_t *const tptr);

int main(void)
{
    int a[N], b[N], c[N], d[N], e[N], i;

    wallclock_t  t;
    double  s;

    wallclock_mark(&t);
    for(i = 0; i < N; ++i)
        a[i] = i * 10 + (i - 2);
    for(i = 0; i < N; ++i)
        b[i] = i * 9 + (i - 3);
    for(i = 0; i < N; ++i)
        c[i] = i * 8 + (i - 1);
    for(i = 0; i < N; ++i)
        d[i] = i * 11 + (i - 5);
    for(i = 0; i < N; ++i)
        e[i] = i * 5 + (i - 0);
    s = wallclock_since(&t);
    printf("Populating took %.9f seconds wall clock time.\n", s);

    wallclock_mark(&t);
    for(i = 0; i < N; ++i)
        a[i] = e[i] + (i - 1);
    for(i = 0; i < N; ++i)
        b[i] = d[i] + (i + 3);
    for(i = 0; i < N; ++i)
        c[i] = a[i] - (i + 2);
    for(i = 0; i < N; ++i)
        d[i] = b[i] + (i - 2);
    for(i = 0; i < N; ++i)
        e[i] = a[i] + (i - 4);
    s = wallclock_since(&t);
    printf("Load/write took %.9f seconds wall clock time.\n", s);

    return 0;
}

我遗漏了时间测量代码，我有 here .结果是:

Georgioss-MacBook-Pro:~ gsamaras$ ./bigloop 
Populating took 0.000581000 seconds wall clock time.
Load/write took 0.000178000 seconds wall clock time.
Georgioss-MacBook-Pro:~ gsamaras$ ./loop
Populating took 0.001092000 seconds wall clock time.
Load/write took 0.000285000 seconds wall clock time.

在填充数组时，您可以在其中看到一个循环中的所有数组获得一个数量级的加速。此外，处理它们的速度也更快!

---

所以，如果我是你，我会实现这两种方法并衡量时间! =)

_{PS:不要成为过早优化的牺牲品。如果您有想要优化的项目，请分析您的代码以找到瓶颈并专注于此!}