集體或個人循環獲得最佳表現？

Question

假設我有N C中的相同大小的連續數組（或任何其他語言 - 我想這並不重要）。我想循環這些數組並對每個數組元素執行一些操作。由於所有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：不要成爲過早優化的受害者。如果你有一個你想要優化的項目，請分析你的代碼以找到瓶頸並專注於此！}