[c++] 분리 된 루프에서 결합 된 루프보다 요소 별 추가가 훨씬 빠른 이유는 무엇입니까?


Answers

OK, 올바른 대답은 분명히 CPU 캐시에서 무엇인가해야합니다. 그러나 캐시 인수를 사용하는 것은 특히 데이터가 없으면 매우 어려울 수 있습니다.

많은 해답을 얻었으나 많은 논의가 있었지만 문제에 직면 해 보겠습니다. 캐시 문제는 매우 복잡하고 일차원이 아닙니다. 그들은 데이터의 크기에 크게 의존하므로 제 질문은 불공평합니다. 그것은 캐시 그래프에서 매우 흥미로운 점으로 밝혀졌습니다.

@ 미스터리의 대답은 사실을 의지하는 유일한 사람 이었기 때문에 (나를 포함하여) 많은 사람들을 납득 시켰지만 진실의 유일한 "데이터 포인트"였습니다.

그래서 나는 그의 테스트 (연속 대 분리 할당을 사용)와 @James 'Answer의 조언을 결합했다.

아래 그래프는 대부분의 답변과 특히 질문과 답변에 대한 의견의 대다수가 정확한 시나리오 또는 사용 된 매개 변수에 따라 완전히 틀렸다고 간주 할 수 있음을 보여줍니다.

나의 초기 질문은 n = 100.000 이었다. 이 점 (사고로)은 특별한 행동을 보입니다.

  1. 그것은 하나와 두 개의 loop'ed 버전 (거의 세 요소) 사이에 가장 큰 불일치를 가지고 있습니다.

  2. 그것은 유일한 루프이며, 하나의 루프 (즉, 연속적인 할당)는 2 루프 버전보다 우수합니다. (이것은 Mysticial의 대답을 가능하게했다.)

초기화 된 데이터를 사용한 결과 :

초기화되지 않은 데이터를 사용한 결과 (이것은 미스테리가 테스트 한 것입니다) :

그리고 이것은 설명하기 어려운 것입니다 : 한 번 할당되고 다른 벡터 크기의 다음 테스트 케이스마다 다시 사용되는 초기화 된 데이터 :

신청

스택 오버플로에 대한 모든 저수준 성능 관련 질문은 캐시 관련 데이터 크기의 전체 범위에 대해 MFLOPS 정보를 제공해야합니다. 답변을 생각하고 특히이 정보없이 다른 사람들과 토론하는 것은 모두의 시간 낭비입니다.

Question

a1 , b1 , c1d1 이 힙 메모리를 가리키고 숫자 코드가 다음 코어 루프를 가지고 있다고 가정합니다.

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.0Intel Core 2 Duo (x64)에서 32 비트 용 SSE2 사용하도록 컴파일 된 첫 번째 예제는 5.5 초, 이중 루프 예제는 1.9 초 밖에 걸리지 않습니다. 제 질문은 : (하단에있는 내 구절을 참고하십시오)

추신 :이게 도움이되는지 확실하지 않습니다.

첫 번째 루프에 대한 디스 어셈블리는 기본적으로 다음과 같습니다 (이 블록은 전체 프로그램에서 약 5 번 반복됨).

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]

이중 루프 예제의 각 루프는이 코드를 생성합니다 (다음 블록은 약 3 번 반복됩니다).

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 캐시의 크기에 따라 달라집니다 관련성이없는 것으로 판명. 그래서 더 많은 관심이 있다면, 나는 그 질문에 대해 다음과 같이 표현한다.

다음 그래프의 5 개 영역에서 설명한 것처럼 다른 캐시 동작을 발생시키는 세부 사항에 대한 확실한 통찰력을 제공 할 수 있습니까?

또한 이러한 CPU에 대해 유사한 그래프를 제공하여 CPU / 캐시 아키텍처 간의 차이점을 지적하는 것도 흥미로울 수 있습니다.

조달청 : 여기에 전체 코드가 있습니다. 더 높은 해상도 타이밍을 위해 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을 보여줍니다.)




첫 번째 루프는 각 변수의 쓰기를 번갈아 수행합니다. 두 번째와 세 번째 요소는 요소 크기의 작은 점프 만 만듭니다.

펜과 종이가 20cm 떨어져있는 20 개의 십자가로 된 두 개의 평행선을 작성해보십시오. 한 번 끝내고 다른 줄을 끝내고 각 줄에 십자 기호를 번갈아 써서 다른 시간을 시도하십시오.




여기서 논의 된 결과를 재현 할 수는 없습니다.

가난한 벤치 마크 코드가 탓일 것인가, 아니면 무엇인지는 모르겠지만, 두 코드가 내 컴퓨터에서 다음 코드를 사용하여 서로 10 % 이내이고 한 루프는 일반적으로 두 개보다 약간 빠릅니다. 배고 있다.

어레이 크기는 8 개의 루프를 사용하여 2 ^ 16에서 2 ^ 24까지였습니다. 소스 배열을 초기화 할 때는 += 할당이 FPU 에 double로 해석되는 메모리 가비지를 추가하도록 요청하지 않도록주의해야했습니다.

루프 내에서 b[j] , d[j]InitToZero[j] 에 지정하고 += b[j] = 1+= d[j] = 1 를 사용하여 다양한 방법으로 연주했습니다 += d[j] = 1 , 그리고 나는 상당히 일관된 결과를 얻었다.

예상대로, InitToZero[j] 사용하여 루프 내부에서 bd 초기화하면 ac 대한 할당 전에 연속적으로 수행되었지만 여전히 10 % 이내 인 경우 결합 된 접근 방식이 유리하게 작용합니다. 그림을 이동.

하드웨어는 3 세대 Core i7 @ 3.4GHz 및 8GB 메모리가있는 Dell XPS 8500 입니다. 2 ^ 16에서 2 ^ 24의 경우 8 개의 루프를 사용하여 누적 시간은 각각 44.987과 40.965입니다. 완전히 최적화 된 Visual C ++ 2010.

추신 : 루프 수를 0으로 낮추었습니다. 결합 된 방법은 약간 빨랐습니다. 내 머리를 긁적. 새로운 배열 사이징 및 루프 카운트에 주목하십시오.

// 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 초로 거의 동일합니다.




n 이 적당한 값을 가진 컴퓨터에서 작업하는 경우 한 번에 두 개의 배열을 메모리에 저장할 수 있지만 디스크 캐싱을 통해 사용할 수있는 전체 메모리가 여전히 4 개를 모두 보유 할만큼 충분하다고 가정 해보십시오.

간단한 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 바이트의 캐쉬를 가지며 나머지 메모리는 상당히 느립니다 (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] 캐시에서 a[0] = a[0] + b[0] 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] 캐시에서 a[0] = a[0] + b[0] a[0], a[1]b[0], b[1] . 비용 = 100 + 100.

  • a[0], a[1], b[0], b[1] 을 캐시 및 캐시 c[0]c[1] 로부터 추출하고 d[0]d[1] 캐시에서 c[0] = c[0] + d[0] . 비용 = 100 + 100.
  • 나는 네가 어디로 가는지보기 시작하고 있다고 생각한다.
  • 총 비용 = (100 + 100 + 100 + 100) * 2 = 800

이것은 전형적인 캐시 스 래시 시나리오입니다.




Related