c++ - 為什麼在單獨的循環中元素添加比在組合循環中快得多?




performance compiler-optimization (7)

原始問題

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

結論:

案例1是一個經典的插值問題,恰好是一個低效的問題。 我還認為這是為什麼許多機器架構和開發人員最終構建和設計具有多線程應用程序以及並行編程能力的多核系統的主要原因之一。

從這種方法看它,而不涉及硬件,操作系統和編譯器如何協同工作以進行涉及使用RAM,緩存,頁面文件等的堆分配; 作為這些算法基礎的數學證明了這兩者中的哪一個是更好的解決方案。 我們可以使用一個類比,其中一個BossSummation代表一個必須在工人AB之間旅行的For Loop ,我們可以很容易地看到案例2至少是1/2 ,如果不是比案例1多一點,由於旅行所需距離的差異和工人之間的時間差異。 這個數學幾乎完全符合Bench Mark Times以及裝配說明中的差異。

我現在開始解釋下面的所有這些是如何工作的。

評估問題

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循環的兩個變體的原始問題以及他對緩存行為的修正問題以及許多其他優秀答案和有用的評論; 我想通過對這種情況和問題採取不同的方法來嘗試做一些與眾不同的事情。

該方法

考慮到兩個循環以及關於緩存和頁面歸檔的所有討論,我想採用另一種方​​法來從不同的角度來看待這個問題。 一個不涉及緩存和頁面文件,也不涉及分配內存的執行,實際上這種方法甚至根本不涉及實際的硬件或軟件。

透視

在查看代碼一段時間之後,很明顯問題是什麼以及產生什麼。 讓我們將其分解為一個算法問題,並從使用數學符號的角度來看待它,然後對數學問題和算法進行類比。

我們所知道的

我們知道他的循環將運行100,000次。 我們也知道a1b1c1d1是64位架構的指針。在32位機器上的C ++中,所有指針都是4個字節,而在64位機器上,它們的大小是8個字節,因為指針具有固定長度。我們知道在兩種情況下我們都有32個字節可供分配。唯一的區別是我們在每次迭代時分配32個字節或2個2-8字節集合,在第二種情況下,我們為每個獨立循環的每次迭代分配16個字節。因此,兩個循環在總分配中仍然等於32個字節。有了這些信息,我們繼續展示它的一般數學,算法和類比。我們知道在兩種情況下必須執行相同集合或操作組的次數。我們知道在兩種情況下都需要分配的內存量。我們可以評估兩種情況之間分配的總體工作量大致相同。

我們不知道的

我們不知道每個案件需要多長時間,除非我們設置一個櫃檯並進行基準測試。然而,基準分數已經包含在原始問題和一些答案和評論中,我們可以看到兩者之間存在顯著差異,這就是這個問題對這個問題的整體推理以及對它的回答。首先。

我們來調查吧

很明顯,許多人已經通過查看堆分配,基準測試,查看RAM,緩存和頁面文件來完成此操作。還包括了特定的數據點和特定的迭代索引,關於這個特定問題的各種對話讓很多人開始質疑其他相關的事情。那麼我們如何通過使用數學算法並對其進行類比來開始研究這個問題呢?我們首先做幾個斷言!然後我們從那裡構建我們的算法。

我們的斷言:

  • 我們將讓循環及其迭代成為一個從1開始並以100000結束而不是從循環開始的Summation,因為我們不需要擔心內存尋址的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()只存在於Sum兩者Sum1Sum2僅包含的位置F1()。當我們開始斷定第二種算法發生了某種優化時,這也將在後面明顯。

通過第一個案例Sum調用的迭代f(a)將添加到它自己,f(b)然後它調用f(c)將執行相同但f(d)為每個調用添加自身100000 iterations。在第二種情況下,我們有Sum1Sum2並且兩者的行為相同,就好像它們是連續兩次調用的相同函數一樣。在這種情況下,我們可以把Sum1Sum2作為只是普通的老Sum地方Sum在這種情況下是這樣的:Sum n=1 : [1,100000] { f(a) = f(a) + f(b); }現在這看起來像一個優化,我們可以只考慮它是相同的功能。

類比摘要

根據我們在第二種情況下看到的情況,它幾乎看起來好像存在優化,因為兩個for循環具有相同的精確簽名,但這不是真正的問題。這個問題是不是正在做的工作f(a)f(b)f(c)f(d)在這兩種情況下,以及兩者之間的比較是在求和在這兩種情況下,讓你在執行時間的不同行駛的距離差。

的認為For Loops作為是Summations,做迭代作為一個Boss被發號施令兩個人AB與他們的工作是肉CD分別拿起從他們一些包並返回它。在這裡類比,for循環或求和迭代和條件檢查本身實際上並不代表Boss。什麼實際上代表了Boss這裡是無法直接從實際的數學算法,但是從實際的概念ScopeCode Block的例程或子例程,方法,功能,翻譯單元等內的第一算法具有1範圍,其中第二算法具有2連續範圍。

在每個調用單上的第一種情況下,Boss轉到A並給出訂單然後A去獲取B's包然後Boss轉到C並給出命令以執行相同的操作並從D每次迭代接收包。

在第二種情況下,Boss直接A用於去獲取B's包,直到收到所有包。然後Boss工作與C獲取所有D's包相同。

由於我們正在使用8字節指針並處理堆分配,所以我們在這裡考慮這個問題。讓我們說Boss距離AA是100英尺,距離是500英尺C。由於執行的順序,我們不需要擔心Boss最初的距離C。在這兩種情況下,Boss最初從A第一次到第二次旅行B。這個類比並不是說這個距離是準確的;它只是一個使用測試用例場景來顯示算法的工作原理。在許多情況下,在進行堆分配並使用緩存和頁面文件時,地址位置之間的這些距離在差異上可能不會有太大變化,或者它們可能非常顯著地取決於數據類型的性質和數組大小。

測試用例:

第一種情況:在第一次迭代時,Boss必須首先走100英尺才能讓訂單滑到AA離開並完成他的工作,但隨後Boss必須行駛500英尺C才能給他訂單。然後在下一次迭代和每次其他迭代之後,Boss必須在兩者之間來回500英尺。

第二種情況: The Boss在第一次迭代時必須行進100英尺A,但在此之後他已經在那裡並等待A回到所有滑倒。然後Boss必須在第一次迭代時行進500英尺C因為C距離500英尺,A因為這Boss( Summation, For Loop )是在工作之後立即調用A,然後就像他一樣等待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部分或算法的責任,它不佔實際工作者ABC,和D他們必須在每迴路的每個迭代做什麼。所以老闆的工作只佔工作總量的15-40%。因此,通過工人完成的大部分工作對將速度差異的比率保持在約50-70%有輕微的影響

觀察: - 兩種算法之間的差異

在這種情況下,它是正在完成工作的過程的結構,它確實表明案例2從具有類似函數聲明和定義的部分優化兩者中更有效,其中它只是名稱不同的變量。我們還看到案例1中的總行進距離比案例2中的距離遠得多,我們可以認為這個距離在兩個算法之間傳遞了我們的時間因子案例1案例2做了大量工作。這也是在證據中看到的ASM兩個案例之間都顯示出來。即使已經說了這些情況是什麼,它也不會考慮的事實,案例1的老闆將不得不等待兩個AC找回之前,他可以回到A對下一次迭代一次也沒有按不能說明如果A或者B是否需要很長時間,那麼Boss其他工人和其他工人也在閒置等待。在案例2中,唯一一個閒置的是Boss工人回來之前。所以即使這對算法也有影響。

OPs修訂問題

編輯:問題證明是無關緊要的,因為行為嚴重依賴於數組(n)和CPU緩存的大小。因此,如果有進一步的興趣,我重新提出這個問題:

您能否提供一些有關導致不同緩存行為的詳細信息,如下圖中的五個區域所示?

通過為這些CPU提供類似的圖表,指出CPU /緩存架構之間的差異也可能是有趣的。

關於這些問題

正如我毫無疑問地證明的那樣,即使在涉及硬件和軟件之前也存在潛在的問題。現在關於內存和緩存以及頁面文件等的管理,它們在以下各項系統之間協同工作:The Architecture{硬件,固件,一些嵌入式驅動程序,內核和ASM指令集},The OS{文件和內存管理系統,驅動程序和註冊表},The Compiler{源代碼的翻譯單元和優化},甚至Source Code自身及其獨特的算法集;我們已經可以看到,有是第一種算法中發生的事情之前,我們甚至可以與任意適用於任何機器的瓶頸ArchitectureOSProgrammable Language與第二種算法相比。因此在涉及現代計算機的內在函數之前就已存在問題。

結局結果

然而; 並不是說這些新問題不重要,因為它們本身就是,而且它們確實起了作用。它們確實會對程序和整體績效產生影響,這一點可以從許多給出答案和/或評論的圖表和評估中看出來。如果你留意的類比Boss和兩名工人AB誰過的去,並從中檢索包CD分別與考慮問題的兩種算法的數學符號,你可以看到,如果沒有計算機,甚至參與Case 2大約為60%比...快Case 1 當您將這些算法應用於源代碼後查看圖形和圖表,通過操作系統進行編譯和優化並執行以在給定硬件上執行操作時,您甚至會看到這些算法之間的差異稍微降低。

現在,如果“數據”組是相當小的,它可能看起來不差的都壞在第一,但因為Case 1是約60 - 70%慢於Case 2我們可以看看這個函數的增長是在執行時間的不同條件是:

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不得不來回之間的最大距離AC對於第一次迭代後,每一次迭代,而算法2 Boss輾轉去A一次,然後正在做用後A,他不得不前往從A去往的最大距離只有一次C

所以試著把Boss注意力集中在同時做兩件相似的事情並且來回擺弄他們而不是專注於類似的連續任務,這將使他在一天結束時非常生氣,因為他必須旅行和工作兩倍。因此,讓老闆陷入內插瓶頸,因為老闆的配偶和孩子不會欣賞它,因此不會失去這種情況的範圍。

假設a1b1c1d1指向堆內存,我的數字代碼具有以下核心循環。

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。)


我不能複制這裡討論的結果。

我不知道糟糕的基準代碼是否應該受到責備,或者是什麼,但是這兩種方法在我的機器上使用下面的代碼在10%之內,並且一個循環通常只比兩個快一點 - 就像你一樣期望。

陣列大小範圍從2 ^ 16到2 ^ 24,使用八個循環。 我小心地初始化了源數組,所以+=賦值並沒有要求FPU添加被解釋為double的內存垃圾。

我玩了各種方案,例如將b[j]d[j]InitToZero[j]放在循環內的InitToZero[j] ,並使用+= b[j] = 1+= d[j] = 1 ,我得到了相當一致的結果。

正如您所料,使用InitToZero[j]在循環內初始化bd使得組合方法具有優勢,因為它們在分配給ac之前背靠背地完成,但仍然在10%之內。 去搞清楚。

硬件是戴爾XPS 8500,具有第3代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秒。


好的,正確的答案肯定要對CPU緩存做一些事情。 但是使用緩存參數可能非常困難,尤其是沒有數據。

有許多答案,導致了很多討論,但讓我們面對現實:緩存問題可能非常複雜,並不是一維的。 它們在很大程度上取決於數據的大小,所以我的問題是不公平的:事實證明它在緩存圖中非常有趣。

@Mysticial的回答讓很多人(包括我)相信,可能是因為它是唯一一個似乎依賴於事實的人,但它只是事實的一個“數據點”。

這就是為什麼我結合他的測試(使用連續分配和單獨分配)和@James答案的建議。

下圖顯示,根據所使用的確切方案和參數,大多數答案,特別是對問題和答案的大多數評論可以被認為是完全錯誤或真實的。

請注意,我的初始問題是在n = 100.000 。 這一點(偶然)表現出特殊的行為:

  1. 它在一個和兩個循環版本之間存在最大的差異(幾乎是三分之一)

  2. 這是唯一的一點,其中一個循環(即連續分配)勝過雙循環版本。 (這使得Mysticial的答案成為可能。)

使用初始化數據的結果:

使用未初始化數據的結果(這是Mysticial測試的):

這是一個難以解釋的問題:初始化數據,分配一次並重複用於以下每個不同矢量大小的測試用例:

提案

應該要求上的每個低級性能相關問題為整個緩存相關數據大小提供MFLOPS信息! 浪費每個人的時間來思考答案,特別是在沒有這些信息的情況下與他人討論答案。


想像一下,你正在使用一台機器,其中n只是正確的值,它只能在內存中同時保存兩個陣列,但是通過磁盤緩存可用的總內存仍足以容納所有四個。

假設一個簡單的LIFO緩存策略,這段代碼:

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

首先會導致ab被加載到RAM中,然後完全在RAM中工作。 當第二個循環開始時, cd將從磁盤加載到RAM中並進行操作。

另一個循環

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

每次循環時 ,它會在其他兩個數組中分頁出兩個數組和頁面。 這顯然會慢得多。

您可能沒有在測試中看到磁盤緩存,但您可能會看到其他形式的緩存的副作用。

這裡似乎有一點混亂/誤解,所以我將嘗試用一個例子來詳細說明。

n = 2 ,我們正在使用字節。 因此,在我的場景中,我們只有4個字節的RAM ,其餘的內存明顯變慢(比如說訪問時間長100倍)。

假設一個相當愚蠢的緩存策略, 如果該字節不在緩存中,把它放在那裡並獲得以下字節,當我們在它時你會得到這樣的場景:

  • for(int j=0;j<n;j++){
     a[j] += b[j];
    }
    for(int j=0;j<n;j++){
     c[j] += d[j];
    }
    
  • 緩存a[0]a[1]然後b[0]b[1]並在緩存中設置a[0] = a[0] + b[0] - 緩存中現在有4個字節, a[0], a[1]b[0], b[1] 。 成本= 100 + 100。

  • 在緩存中設置a[1] = a[1] + b[1] 。 成本= 1 + 1。
  • 重複cd
  • 總費用= (100 + 100 + 1 + 1) * 2 = 404

  • for(int j=0;j<n;j++){
     a[j] += b[j];
     c[j] += d[j];
    }
    
  • 緩存a[0]a[1]然後b[0]b[1]並在緩存中設置a[0] = a[0] + b[0] - 緩存中現在有4個字節, a[0], a[1]b[0], b[1] 。 成本= 100 + 100。

  • 從緩存和緩存c[0]c[1]彈出a[0], a[1], b[0], b[1] c[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

這是一個經典的緩存捶打場景。


第二個循環涉及更少的緩存活動,因此處理器更容易滿足內存需求。


這不是因為代碼不同,而是因為緩存:RAM比CPU寄存器慢,CPU內部有緩存,以避免每次變量更改時寫入RAM。 但是緩存並不像RAM那麼大,因此,它只映射了一小部分。

第一個代碼修改在每個循環中交替它們的遠程存儲器地址,因此需要連續地使高速緩存無效。

第二個代碼不會交替:它只是在相鄰地址上流動兩次。 這使得所有作業都在緩存中完成,僅在第二個循環開始後使其無效。


它可能是舊的C ++和優化。在我的電腦上,我獲得了幾乎相同的速度:

一個循環:1.577毫秒

兩個循環:1.507毫秒

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







vectorization