為什麼單獨循環中的元素加法比組合循環中的要快得多？

假設<code>a1 ，

b1

，

c1

和

d1

指向堆記憶體，而我的數字代碼具有以下核心循環。

const int n = 100000;

for (int j = 0; j < n; j++) {
    a1[j] += b1[j];
    c1[j] += d1[j];
}
           

此循環通過另一個外部

for

循環執行了10,000次。 為了加快速度，我将代碼更改為：

for (int j = 0; j < n; j++) {
    a1[j] += b1[j];
}

for (int j = 0; j < n; j++) {
    c1[j] += d1[j];
}
           

在具有完全優化功能的MS Visual C ++ 10.0上編譯，并在Intel Core 2 Duo（x64）上為32位啟用了SSE2 ，第一個示例花費5.5秒，而雙循環示例僅花費1.9秒。 我的問題是：（請參閱底部的我改寫的問題）

PS：我不确定，這是否有幫助：

第一個循環的反彙編基本上是這樣的（在整個程式中此塊重複了大約五次）：

movsd       xmm0,mmword ptr [edx+18h]
addsd       xmm0,mmword ptr [ecx+20h]
movsd       mmword ptr [ecx+20h],xmm0
movsd       xmm0,mmword ptr [esi+10h]
addsd       xmm0,mmword ptr [eax+30h]
movsd       mmword ptr [eax+30h],xmm0
movsd       xmm0,mmword ptr [edx+20h]
addsd       xmm0,mmword ptr [ecx+28h]
movsd       mmword ptr [ecx+28h],xmm0
movsd       xmm0,mmword ptr [esi+18h]
addsd       xmm0,mmword ptr [eax+38h]
           

雙循環示例的每個循環都會生成此代碼（以下塊重複大約三遍）：

addsd       xmm0,mmword ptr [eax+28h]
movsd       mmword ptr [eax+28h],xmm0
movsd       xmm0,mmword ptr [ecx+20h]
addsd       xmm0,mmword ptr [eax+30h]
movsd       mmword ptr [eax+30h],xmm0
movsd       xmm0,mmword ptr [ecx+28h]
addsd       xmm0,mmword ptr [eax+38h]
movsd       mmword ptr [eax+38h],xmm0
movsd       xmm0,mmword ptr [ecx+30h]
addsd       xmm0,mmword ptr [eax+40h]
movsd       mmword ptr [eax+40h],xmm0
           

事實證明這個問題無關緊要，因為行為嚴重取決于陣列（n）的大小和CPU緩存。 是以，如果有進一步的興趣，我重新提出一個問題：

您能否對導緻不同緩存行為的細節提供深入的了解，如下圖的五個區域所示？

通過為這些CPU提供類似的圖形來指出CPU /緩存體系結構之間的差異也可能很有趣。

PPS：這是完整的代碼。 它使用TBB

Tick_Count

獲得更高分辨率的時序，可以通過不定義

TBB_TIMING

宏來禁用它：

#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>

//#define TBB_TIMING

#ifdef TBB_TIMING   
#include <tbb/tick_count.h>
using tbb::tick_count;
#else
#include <time.h>
#endif

using namespace std;

//#define preallocate_memory new_cont

enum { new_cont, new_sep };

double *a1, *b1, *c1, *d1;


void allo(int cont, int n)
{
    switch(cont) {
      case new_cont:
        a1 = new double[n*4];
        b1 = a1 + n;
        c1 = b1 + n;
        d1 = c1 + n;
        break;
      case new_sep:
        a1 = new double[n];
        b1 = new double[n];
        c1 = new double[n];
        d1 = new double[n];
        break;
    }

    for (int i = 0; i < n; i++) {
        a1[i] = 1.0;
        d1[i] = 1.0;
        c1[i] = 1.0;
        b1[i] = 1.0;
    }
}

void ff(int cont)
{
    switch(cont){
      case new_sep:
        delete[] b1;
        delete[] c1;
        delete[] d1;
      case new_cont:
        delete[] a1;
    }
}

double plain(int n, int m, int cont, int loops)
{
#ifndef preallocate_memory
    allo(cont,n);
#endif

#ifdef TBB_TIMING   
    tick_count t0 = tick_count::now();
#else
    clock_t start = clock();
#endif

    if (loops == 1) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++){
                a1[j] += b1[j];
                c1[j] += d1[j];
            }
        }
    } else {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                a1[j] += b1[j];
            }
            for (int j = 0; j < n; j++) {
                c1[j] += d1[j];
            }
        }
    }
    double ret;

#ifdef TBB_TIMING   
    tick_count t1 = tick_count::now();
    ret = 2.0*double(n)*double(m)/(t1-t0).seconds();
#else
    clock_t end = clock();
    ret = 2.0*double(n)*double(m)/(double)(end - start) *double(CLOCKS_PER_SEC);
#endif

#ifndef preallocate_memory
    ff(cont);
#endif

    return ret;
}


void main()
{   
    freopen("C:\\test.csv", "w", stdout);

    char *s = " ";

    string na[2] ={"new_cont", "new_sep"};

    cout << "n";

    for (int j = 0; j < 2; j++)
        for (int i = 1; i <= 2; i++)
#ifdef preallocate_memory
            cout << s << i << "_loops_" << na[preallocate_memory];
#else
            cout << s << i << "_loops_" << na[j];
#endif

    cout << endl;

    long long nmax = 1000000;

#ifdef preallocate_memory
    allo(preallocate_memory, nmax);
#endif

    for (long long n = 1L; n < nmax; n = max(n+1, long long(n*1.2)))
    {
        const long long m = 10000000/n;
        cout << n;

        for (int j = 0; j < 2; j++)
            for (int i = 1; i <= 2; i++)
                cout << s << plain(n, m, j, i);
        cout << endl;
    }
}
           

（它顯示

n

不同值的FLOP / s。）

#1樓

第一個循環交替寫入每個變量。 第二個和第三個隻使元素大小發生很小的變化。

嘗試用相隔20厘米的鋼筆和紙書寫兩條20條交叉的平行線。 嘗試先完成一條，然後再完成另一行，然後通過在每行中交替寫一個十字來嘗試另一次。

#2樓

我無法複制此處讨論的結果。

我不知道應該歸咎于糟糕的基準測試代碼還是什麼，但是使用下面的代碼，這兩種方法在我的機器上的相差不到10％，并且一個循環通常僅比兩個循環快一點-如您所願期望。

使用八個循環，數組大小從2 ^ 16到2 ^ 24。 我小心地初始化了源數組，是以

+=

配置設定沒有要求FPU添加解釋為double的記憶體垃圾。

我

InitToZero[j]

了各種方案，例如将

b[j]

，

d[j]

的指派配置設定給

InitToZero[j]

到循環内，還使用

+= b[j] = 1

和

+= d[j] = 1

，結果相當一緻。

如您所料，使用

InitToZero[j]

在循環内初始化

b

和

d

使組合方法具有優勢，因為它們是在配置設定給

a

和

c

之前背對背完成的，但仍在10％以内。 去搞清楚。

硬體是Dell XPS 8500，具有第三代Core i7 @ 3.4 GHz和8 GB記憶體。 對于2 ^ 16到2 ^ 24，使用八個循環，累積時間分别為44.987和40.965。 完全優化的Visual C ++ 2010。

PS：我更改了循環以減少到零，并且組合方法略快。 撓我的頭。 注意新的數組大小和循環計數。

// MemBufferMystery.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <cmath>
#include <string>
#include <time.h>

#define  dbl    double
#define  MAX_ARRAY_SZ    262145    //16777216    // AKA (2^24)
#define  STEP_SZ           1024    //   65536    // AKA (2^16)

int _tmain(int argc, _TCHAR* argv[]) {
    long i, j, ArraySz = 0,  LoopKnt = 1024;
    time_t start, Cumulative_Combined = 0, Cumulative_Separate = 0;
    dbl *a = NULL, *b = NULL, *c = NULL, *d = NULL, *InitToOnes = NULL;

    a = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    b = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    c = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    d = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    InitToOnes = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    // Initialize array to 1.0 second.
    for(j = 0; j< MAX_ARRAY_SZ; j++) {
        InitToOnes[j] = 1.0;
    }

    // Increase size of arrays and time
    for(ArraySz = STEP_SZ; ArraySz<MAX_ARRAY_SZ; ArraySz += STEP_SZ) {
        a = (dbl *)realloc(a, ArraySz * sizeof(dbl));
        b = (dbl *)realloc(b, ArraySz * sizeof(dbl));
        c = (dbl *)realloc(c, ArraySz * sizeof(dbl));
        d = (dbl *)realloc(d, ArraySz * sizeof(dbl));
        // Outside the timing loop, initialize
        // b and d arrays to 1.0 sec for consistent += performance.
        memcpy((void *)b, (void *)InitToOnes, ArraySz * sizeof(dbl));
        memcpy((void *)d, (void *)InitToOnes, ArraySz * sizeof(dbl));

        start = clock();
        for(i = LoopKnt; i; i--) {
            for(j = ArraySz; j; j--) {
                a[j] += b[j];
                c[j] += d[j];
            }
        }
        Cumulative_Combined += (clock()-start);
        printf("\n %6i miliseconds for combined array sizes %i and %i loops",
                (int)(clock()-start), ArraySz, LoopKnt);
        start = clock();
        for(i = LoopKnt; i; i--) {
            for(j = ArraySz; j; j--) {
                a[j] += b[j];
            }
            for(j = ArraySz; j; j--) {
                c[j] += d[j];
            }
        }
        Cumulative_Separate += (clock()-start);
        printf("\n %6i miliseconds for separate array sizes %i and %i loops \n",
                (int)(clock()-start), ArraySz, LoopKnt);
    }
    printf("\n Cumulative combined array processing took %10.3f seconds",
            (dbl)(Cumulative_Combined/(dbl)CLOCKS_PER_SEC));
    printf("\n Cumulative seperate array processing took %10.3f seconds",
        (dbl)(Cumulative_Separate/(dbl)CLOCKS_PER_SEC));
    getchar();

    free(a); free(b); free(c); free(d); free(InitToOnes);
    return 0;
}
           

我不确定為什麼決定MFLOPS是一個相關名額。 盡管我的想法是專注于記憶體通路，是以我嘗試将浮點計算時間減至最少。 我離開了

+=

，但是我不确定為什麼。

沒有計算的直接配置設定将更幹淨地測試記憶體通路時間，并且将建立一個統一的測試，而與循環計數無關。 也許我錯過了談話中的某些内容，但值得三思。 如果加号不包括在配置設定中，則累積時間幾乎相同，每個為31秒。

#3樓

原始問題

為什麼一個循環比兩個循環要慢得多？

結論：

情況1是一個經典的插值問題，碰巧是一個效率低下的問題。 我還認為，這就是許多機器體系結構和開發人員最終建構和設計具有執行多線程應用程式以及并行程式設計能力的多核系統的主要原因之一。

從這種方法來看待它，而不涉及硬體，作業系統和編譯器如何一起工作以進行堆配置設定，這涉及使用RAM，緩存，頁面檔案等。 這些算法基礎上的數學方法向我們展示了這兩種方法中哪種更好。 我們可以用一個比喻，其中一個

Boss

或

Summation

，将代表一個

For Loop

有勞工來往于

A

＆

B

，我們可以很容易地看到， 第2種情況是至少1/2，快，如果不是有點超過案例1由于行駛所需的距離與勞工之間的時間差。 這個數學運算幾乎與基準時間以及彙編指令中的差異幾乎完美地吻合。

現在，我将在下面開始解釋所有這些工作方式。

評估問題

OP的代碼：

const int n=100000;

for(int j=0;j<n;j++){
    a1[j] += b1[j];
    c1[j] += d1[j];
}
           

和

for(int j=0;j<n;j++){
    a1[j] += b1[j];
}
for(int j=0;j<n;j++){
    c1[j] += d1[j];
}
           

考慮

考慮到OP最初關于for循環的2個變體的問題，以及他對緩存行為的修正問題，以及許多其他出色的答案和有用的注釋； 我想通過對這種情況和問題采取不同的方法來嘗試做一些不同的事情。

該方法

考慮到這兩個循環以及有關緩存和頁面歸檔的所有讨論，我想采用另一種方法從不同的角度來看待這一點。 一種不涉及緩存和頁面檔案，也不涉及執行配置設定記憶體的方法，實際上，這種方法甚至根本不涉及實際的硬體或軟體。

觀點

在看了一段時間的代碼之後，很明顯的是問題出在哪裡，問題是由什麼産生的。 讓我們将其分解為一個算法問題，并從使用數學符号的角度來看待它，然後對數學問題和算法進行類比。

我們所知道的

我們知道他的循環将運作100,000次。 我們還知道

a1

，

b1

，

c1

和

d1

是64位體系結構上的指針。 在32位計算機上的C ++中，所有指針均為4個位元組，而在64位計算機上，它們的大小為8個位元組，因為指針的長度是固定的。 我們知道在兩種情況下都需要配置設定32個位元組。 唯一的差別是我們在每次疊代中配置設定32位元組或2組2-8位元組，在第二種情況下，我們為兩個獨立循環的每次疊代配置設定16個位元組。 是以，兩個循環的總配置設定仍然等于32個位元組。 有了這些資訊，讓我們繼續展示它的一般數學，算法和類比。 我們确實知道在兩種情況下必須執行同一組或一組操作的次數。 我們确實知道在兩種情況下都需要配置設定的記憶體量。 我們可以估計，兩種情況之間配置設定的總體工作量将大緻相同。

我們不知道的

除非我們設定計數器并進行基準測試，否則我們不知道每種情況需要花費多長時間。 但是，基準問題已經包含在原始問題以及一些答案和評論中，并且我們可以看到兩者之間存在顯着差異，這就是該問題針對該問題的全部原因以及對它的回答。首先。

讓我們調查一下

很明顯，許多人已經通過檢視堆配置設定，基準測試，檢視RAM，高速緩存和頁面檔案來做到這一點。 還包括檢視特定的資料點和特定的疊代索引，關于此特定問題的各種讨論使許多人開始質疑與此相關的其他問題。 那麼，我們如何開始使用數學算法并對其進行類推來研究這個問題呢？ 我們首先提出幾個斷言！ 然後，我們從那裡建構算法。

我們的斷言：

• 我們将循環及其疊代設為從1開始到100000結束的求和，而不是像在循環中那樣從0開始，因為我們不必擔心記憶體尋址的0索引方案，因為我們隻關心算法本身。
• 在這兩種情況下，我們都有4個函數可以使用，有2個函數調用，每個函數調用都需要進行2個操作。 是以，我們将這些函數設定為

  F1()

  ，

  F2()

  ，

  f(a)

  ，

  f(b)

  ，

  f(c)

  和

  f(d)

  。

算法：

第一種情況： -隻有一個求和，但有兩個獨立的函數調用。

Sum n=1 : [1,100000] = F1(), F2();
                       F1() = { f(a) = f(a) + f(b); }
                       F2() = { f(c) = f(c) + f(d);  }
           

第二種情況： -兩個求和，但每個求和都有自己的函數調用。

Sum1 n=1 : [1,100000] = F1();
                        F1() = { f(a) = f(a) + f(b); }

Sum2 n=1 : [1,100000] = F1();
                        F1() = { f(c) = f(c) + f(d); }
           

如果您發現

F2()

僅存在于

Sum1

和

Sum2

都隻包含

F1()

Sum

中。 當我們開始得出結論，第二種算法正在發生某種優化時，這也将在以後顯而易見。

通過第一種情況的疊代

Sum

調用

f(a)

将添加到其自身

f(b)

然後調用

f(c)

進行相同的操作，但每進行

100000 iterations

将

f(d)

添加到自身。 在第二種情況下，我們有

Sum1

和

Sum2

，它們的行為相同，就好像它們是同一函數連續被調用兩次一樣。 在這種情況下，我們可以将

Sum1

和

Sum2

視為普通舊的

Sum

，在這種情況下，

Sum

看起來像這樣：

Sum n=1 : [1,100000] { f(a) = f(a) + f(b); }

Sum n=1 : [1,100000] { f(a) = f(a) + f(b); }

現在這個樣子的優化，我們可以隻考慮它是相同的功能。

類推總結

在第二種情況下，由于兩個for循環具有相同的确切簽名，是以幾乎看起來好像是在進行優化，但這不是真正的問題。 問題不是兩種情況下

f(a)

，

f(b)

，

f(c)

和

f(d)

所做的工作，而兩者之間的比較是求和的距離差異在兩種情況下都必須旅行，這給您時間執行帶來了不同。

可以将

For Loops

看作是進行疊代的

Summations

，是将兩個人

A

和

B

下達指令的

Boss

，他們的工作分别是給

C

和

D

求肉，并從他們那裡拿走一些包裝并傳回。 以此類推，for循環或求和疊代以及條件檢查本身實際上并不代表

Boss

。 這裡真正代表

Boss

的不是直接來自實際的數學算法，而是來自例程或子例程，方法，函數，翻譯單元等中

Scope

和

Code Block

的實際概念。第一種算法具有一個範圍，其中第二算法具有2個連續範圍。

在每個呼叫單的第一種情況下，

Boss

轉到

A

發出訂單，而

A

轉到取回

B's

包裹，然後

Boss

轉到

C

發出指令以進行相同的操作，并在每次疊代中從

D

接收包裹。

在第二種情況下，

Boss

直接與

A

一起去取回

B's

包裹，直到收到所有包裹為止。 然後，

Boss

與

C

一起完成擷取

D's

所有程式包的操作。

由于我們正在使用8位元組指針并處理堆配置設定，是以我們在這裡考慮此問題。 讓我們說，

Boss

是從100英尺

A

和

A

從500英尺

C

。 由于執行的順序，我們不必擔心

Boss

最初與

C

的距離。 在這兩種情況下，

Boss

最初都從

A

出發，然後到達

B

這個比喻并不是說這個距離是準确的。 這隻是一個用例場景，展示了算法的工作原理。 在許多情況下，當進行堆配置設定以及使用緩存和頁面檔案時，位址位置之間的距離差異可能不會有太大變化，或者取決于資料類型和數組大小的性質，它們之間的差異可能非常明顯。

測試案例：

第一種情況：在第一次疊代中，

Boss

首先必須走100英尺才能将訂單單交給

A

而

A

掉下來然後做他的事情，但是随後

Boss

不得不向

C

走500英尺才能給他單單。 然後，在下一次疊代中，

Boss

之後的所有其他疊代必須在兩者之間來回500英尺。

第二種情況：

The Boss

在第一次疊代中必須走100英尺才能到達

A

，但是之後他已經在那裡并且隻等

A

回來直到所有單子都裝滿。 然後，

Boss

必須在第一次疊代中向

C

行駛500英尺，因為自從與

A

一起工作後立即調用此

Boss( Summation, For Loop )

之後

Boss( Summation, For Loop )

C

距離

A

500英尺，然後像他對

A

一樣等待直到所有

C's

訂單單已完成。

行駛距離的差異

const n = 100000
distTraveledOfFirst = (100 + 500) + ((n-1)*(500 + 500); 
// Simplify
distTraveledOfFirst = 600 + (99999*100);
distTraveledOfFirst = 600 + 9999900;
distTraveledOfFirst =  10000500;
// Distance Traveled On First Algorithm = 10,000,500ft

distTraveledOfSecond = 100 + 500 = 600;
// Distance Traveled On Second Algorithm = 600ft;    
           

任意值的比較

我們可以很容易地看到600遠遠少于1000萬。 現在這是不精确的，因為我們不知道每次疊代中每次調用哪個RAM或哪個Cache或Page File的距離之間的實際差異是由于許多其他看不見的變量引起的，但這僅僅是評估要注意的情況，并嘗試從最壞的情況來看。

是以，根據這些數字，似乎算法一應該比算法二慢99％； 但是，這僅是算法

The Boss's

部分或職責，它并沒有考慮實際的從業人員

A

，

B

，

C

和

D

以及他們在Loop的每次疊代中必須執行的操作。 是以，老闆的工作僅占完成工作總數的15-40％。 是以，通過勞工完成的大部分工作對将速度差異率保持在50％到70％之間有較大的影響。

觀察結果： - 兩種算法之間的差異

在這種情況下，這是工作過程的結構，它确實表明案例2比具有部分相似的函數聲明和定義的局部優化更為有效，其中僅變量名不同。 而且我們還看到， 情況1所經過的總距離比情況2中的要遠得多，我們可以認為該距離在兩種算法之間經過了時間因子 。 案例1比案例2有更多的工作要做。 在兩個案例之間顯示的

ASM

證據中也可以看到這一點。 即使已經對這些案例進行了說明，這也不能說明在案例1中老闆必須等待

A

＆

C

都傳回，然後才能在下一次疊代中再次傳回

A

，如果

A

或

B

花費的時間很長，那麼

Boss

和其他勞工也都閑着閑着，這也沒有考慮到這一事實。 在案例2中 ，隻有一個閑置的人是

Boss

直到勞工回來為止。 是以，即使這也會對算法産生影響。

OP修訂的問題

編輯：問題被證明是不相關的，因為行為嚴重取決于數組（n）和CPU緩存的大小。 是以，如果有進一步的興趣，我重新提出一個問題：

您能否對導緻不同緩存行為的細節提供深入的了解，如下圖的五個區域所示？

通過為這些CPU提供類似的圖形來指出CPU /緩存體系結構之間的差異也可能很有趣。

關于這些問題

正如我毫無疑問地證明的那樣，甚至在涉及硬體和軟體之前就存在一個潛在的問題。 現在，關于記憶體和緩存以及頁面檔案等的管理，它們都可以在以下系統之間的內建系統中一起工作：

The Architecture

{硬體，固件，某些嵌入式驅動程式，核心和ASM指令集}，

The OS

{檔案以及記憶體管理系統，驅動程式和系統資料庫}，

The Compiler

{源代碼的翻譯單元和優化}，甚至

Source Code

本身及其獨特算法集； 與第二個算法相比，我們甚至已經将其應用于具有任意

Architecture

，

OS

和

Programmable Language

任何計算機之前，已經知道第一個算法中存在瓶頸。 是以，在涉及現代計算機的内在要素之前已經存在一個問題。

最終結果

然而; 并不是說這些新問題并不重要，因為它們本身是重要的，而且它們畢竟會發揮作用。 它們确實會影響程式和整體性能，這在許多給出答案和/或評論的圖表和評估中很明顯。 如果您注意

Boss

和兩個勞工

A

和

B

的類比，他們不得不分别從

C

和

D

那裡取回包裹，并考慮這兩個算法的數學符号，您會發現，甚至沒有計算機

Case 2

比

Case 1

快60％，當您在将這些算法應用于源代碼，通過OS進行編譯，優化和執行以在給定硬體上執行操作後檢視圖形和圖表時，您甚至會看到一點點這些算法之間的差異會導緻更多的降級。

現在，如果“資料”集很小，那麼乍一看似乎并沒有那麼差，但是由于

Case 1

比

Case 2

慢

60 - 70%

我們可以将此函數的增長看成是時間執行的差異：

DeltaTimeDifference approximately = Loop1(time) - Loop2(time)
//where 
Loop1(time) = Loop2(time) + (Loop2(time)*[0.6,0.7]) // approximately
// So when we substitute this back into the difference equation we end up with 
DeltaTimeDifference approximately = (Loop2(time) + (Loop2(time)*[0.6,0.7])) - Loop2(time)
// And finally we can simplify this to
DeltaTimeDifference approximately = [0.6,0.7]*(Loop2(time)
           

這個近似值是算法和機器操作（包括軟體優化和機器指令）這兩個循環之間的平均差。 是以，當資料集線性增長時，兩者之間的時間差也将增加。 算法1的取數比算法2的取數多，這在

Boss

第一次疊代後每次疊代都必須在

A

和

C

之間最大距離來回移動而算法2

Boss

必須一次又一次到達

A

時明顯可見。有

A

他不得不從去當行駛的最大距離隻有一次

A

到

C

。

是以，試圖讓

Boss

集中精力做兩件事，而不是專注于連續的類似任務，這會讓他在一天結束前很生氣，因為他不得不旅行和工作兩倍。 是以，不要讓您的老闆陷入插補的瓶頸，因為老闆的配偶和子女不會對此感到困惑，是以不會失去局面。

#4樓

可能是舊的C ++和優化。 在我的計算機上，我獲得了幾乎相同的速度：

一圈：1.577毫秒

兩個循環：1.507毫秒

我在具有16 GB RAM的E5-1620 3.5 GHz處理器上運作Visual Studio 2015。

#5樓

第二個循環涉及較少的緩存活動，是以處理器可以更輕松地滿足記憶體需求。

#6樓

這不是因為代碼不同，而是由于緩存：RAM的速度比CPU寄存器慢，并且CPU内有一個緩存，以避免每次變量更改時都寫入RAM。 但是緩存不像RAM那樣大，是以它僅映射其中的一小部分。

第一個代碼修改遠處的存儲器位址，使它們在每個循環中交替出現，是以需要不斷使緩存無效。

第二個代碼不交替：它僅在相鄰位址上流兩次。 這使得所有作業都在高速緩存中完成，僅在第二個循環開始後才使該作業無效。

#7樓

這是因為CPU沒有太多的高速緩存未命中（必須等待陣列資料來自RAM晶片）。 您将不斷調整數組的大小，使其超過CPU的1級緩存 （L1）和2級緩存 （L2）的大小，并繪制代碼花費的時間，這将很有趣。對數組的大小執行。 該圖不應是您期望的直線。

#8樓

經過對此的進一步分析，我認為這（至少部分地）是由四個指針的資料對齊引起的。 這将導緻某種程度的緩存庫/方式沖突。

如果我猜對了如何配置設定數組，則它們很可能與page line對齊 。

這意味着您在每個循環中的所有通路都将使用相同的緩存方式。 但是，一段時間以來，英特爾處理器已經具有8路L1緩存關聯性。 但實際上，性能并不完全相同。 通路4路仍然比說2路慢。

編輯：實際上，它的确看起來像您是分别配置設定所有數組。 通常，當請求如此大的配置設定時，配置設定器會從OS請求新頁面。 是以，很有可能大配置設定将出現在與頁面邊界相同的偏移量處。

這是測試代碼：

int main(){
    const int n = 100000;

#ifdef ALLOCATE_SEPERATE
    double *a1 = (double*)malloc(n * sizeof(double));
    double *b1 = (double*)malloc(n * sizeof(double));
    double *c1 = (double*)malloc(n * sizeof(double));
    double *d1 = (double*)malloc(n * sizeof(double));
#else
    double *a1 = (double*)malloc(n * sizeof(double) * 4);
    double *b1 = a1 + n;
    double *c1 = b1 + n;
    double *d1 = c1 + n;
#endif

    //  Zero the data to prevent any chance of denormals.
    memset(a1,0,n * sizeof(double));
    memset(b1,0,n * sizeof(double));
    memset(c1,0,n * sizeof(double));
    memset(d1,0,n * sizeof(double));

    //  Print the addresses
    cout << a1 << endl;
    cout << b1 << endl;
    cout << c1 << endl;
    cout << d1 << endl;

    clock_t start = clock();

    int c = 0;
    while (c++ < 10000){

#if ONE_LOOP
        for(int j=0;j<n;j++){
            a1[j] += b1[j];
            c1[j] += d1[j];
        }
#else
        for(int j=0;j<n;j++){
            a1[j] += b1[j];
        }
        for(int j=0;j<n;j++){
            c1[j] += d1[j];
        }
#endif

    }

    clock_t end = clock();
    cout << "seconds = " << (double)(end - start) / CLOCKS_PER_SEC << endl;

    system("pause");
    return 0;
}
           

基準結果：

編輯：在實際的 Core 2體系結構機器上的結果：

2個Intel Xeon X5482 Harpertown @ 3.2 GHz：

#define ALLOCATE_SEPERATE
#define ONE_LOOP
00600020
006D0020
007A0020
00870020
seconds = 6.206

#define ALLOCATE_SEPERATE
//#define ONE_LOOP
005E0020
006B0020
00780020
00850020
seconds = 2.116

//#define ALLOCATE_SEPERATE
#define ONE_LOOP
00570020
00633520
006F6A20
007B9F20
seconds = 1.894

//#define ALLOCATE_SEPERATE
//#define ONE_LOOP
008C0020
00983520
00A46A20
00B09F20
seconds = 1.993
           

觀察結果：

• 一圈為6.206秒 ， 兩圈為2.116秒 。 這樣可以準确地再現OP的結果。
• 在前兩個測試中，分别配置設定數組。 您會注意到它們相對于頁面都具有相同的對齊方式。
• 在後兩個測試中，将數組打包在一起以破壞對齊方式。 在這裡，您會注意到兩個循環都更快。 此外，第二（雙）循環現在比通常期望的要慢。

正如@Stephen Cannon在評論中指出的那樣，這種對齊很有可能導緻加載/存儲單元或緩存中出現錯誤的混疊 。 我在Google上搜尋了一下，發現Intel實際上有一個硬體計數器，用于部分位址别名停頓：

http://software.intel.com/sites/products/documentation/doclib/stdxe/2013/~amplifierxe/pmw_dp/events/partial_address_alias.html

5個地區-說明

區域1：

這很容易。 資料集是如此之小，以緻于性能受循環和分支之類的開銷所支配。

區域2：

在這裡，随着資料大小的增加，相對開銷的數量減少，性能“飽和”。 在這裡，兩個循環比較慢，因為它的循環和分支開銷是其兩倍。

我不确定這到底是怎麼回事...對齊仍然可以發揮作用，因為Agner Fog提到了緩存庫沖突 。 （該連結是關于Sandy Bridge的，但該想法仍應适用于Core2。）

區域3：

此時，資料不再适合L1緩存。 是以，性能受L1 <-> L2緩存帶寬的限制。

區域4：

我們正在觀察單循環中的性能下降。 并且如前所述，這是由于對齊（最有可能）導緻處理器加載/存儲單元中的假混疊停頓。

但是，為了使假混疊發生，資料集之間必須有足夠大的跨度。 這就是為什麼您在區域3中看不到它的原因。

區域5：

在這一點上，沒有什麼适合緩存。 是以，您受記憶體帶寬的束縛。

#9樓

好的，正确的答案肯定與CPU緩存有關。 但是使用cache參數可能非常困難，尤其是在沒有資料的情況下。

有很多答案，引起了很多讨論，但讓我們面對現實：緩存問題可能非常複雜，而且不是一維的。 它們在很大程度上取決于資料的大小，是以我的問題是不公平的：事實證明這是在緩存圖中非常有趣的一點。

@Mysticial的回答使很多人（包括我）信服，可能是因為它是唯一一個似乎依賴事實的人，但這隻是事實的一個“資料點”。

這就是為什麼我将他的測試（使用連續配置設定與單獨配置設定）和@James'Answer的建議結合在一起的原因。

下圖顯示，根據所使用的确切場景和參數，可以将大多數答案，尤其是對問題和答案的大多數評論視為​​完全錯誤或正确。

請注意，我最初的問題是n = 100.000 。 這一點（偶然）表現出特殊的行為：

1. 它在一個和兩個循環版本之間的差異最大（幾乎是三分之一）
2. 這是唯一的一環（即具有連續配置設定）優于兩環版本的地方。 （這完全使Mysticial的答案成為可能。）

使用初始化資料的結果：

使用未初始化資料的結果（這是Mysticial測試的結果）：

這是一個難以解釋的資料：初始化資料，該資料隻配置設定一次，并在以下每個具有不同向量大小的測試用例中重新使用：

提案

應該要求有關堆棧溢出的所有與低級别性能相關的問題，以提供有關整個高速緩存相關資料大小範圍的MFLOPS資訊！ 浪費每個人思考答案的時間，尤其是在沒有這些資訊的情況下與他人讨論答案。

#10樓

假設您在一台機器上工作，而

n

隻是一個正确的值，因為它隻能一次将兩個陣列儲存在記憶體中，但是通過磁盤緩存可用的總記憶體仍然足以容納全部四個。

假設一個簡單的LIFO緩存政策，此代碼：

for(int j=0;j<n;j++){
    a[j] += b[j];
}
for(int j=0;j<n;j++){
    c[j] += d[j];
}
           

首先會導緻

a

和

b

加載到RAM中，然後完全在RAM中處理。 當第二個循環開始時，然後将

c

和

d

從磁盤加載到RAM中并進行操作。

另一個循環

for(int j=0;j<n;j++){
    a[j] += b[j];
    c[j] += d[j];
}
           

每次循環都會分頁出兩個數組，并分頁到另外兩個。 這顯然要慢得多 。

您可能沒有在測試中看到磁盤緩存，但是可能看到了其他某種形式的緩存的副作用。

這裡似乎有些混亂/誤解，是以我将嘗試通過一個例子進行詳細說明。

假設

n = 2

，我們正在處理位元組。 是以，在我的情況下，我們隻有4個位元組的RAM ，而其餘​​的記憶體則顯着變慢（例如，通路時間增加了100倍）。

假設一個相當愚蠢的緩存政策是如果該位元組不在緩存中，則将其放在那裡并在我們處于緩存狀态時也擷取下一個位元組，您将獲得類似以下的情況：

• 用
• 緩存

  a[0]

  和

  a[1]

  然後緩存

  b[0]

  和

  b[1]

  并在緩存中設定

  a[0] = a[0] + b[0]

  -現在緩存中有四個位元組，

  a[0], a[1]

  和

  b[0], b[1]

  。 費用= 100 + 100。
• 在緩存中設定

  a[1] = a[1] + b[1]

  。 費用= 1 + 1。
• 重複

  c

  和

  d

  。
• 總費用=

  (100 + 100 + 1 + 1) * 2 = 404

• 用
• 緩存

  a[0]

  和

  a[1]

  然後緩存

  b[0]

  和

  b[1]

  并在緩存中設定

  a[0] = a[0] + b[0]

  -現在緩存中有四個位元組，

  a[0], a[1]

  和

  b[0], b[1]

  。 費用= 100 + 100。
• 從緩存和緩存

  c[0]

  和

  c[1]

  彈出

  a[0], a[1], b[0], b[1]

  ，然後彈出

  d[0]

  和

  d[1]

  并設定

  c[0] = c[0] + d[0]

  緩存中的

  c[0] = c[0] + d[0]

  。 費用= 100 + 100。
• 我懷疑您開始看到我要去的地方。
• 總費用=

  (100 + 100 + 100 + 100) * 2 = 800

這是一個經典的緩存崩潰情況。