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




performance compiler-optimization (7)

CPU가 캐시 미스가 너무 많아서 (배열 데이터가 RAM 칩에서 나올 때까지 기다려야 만하는 곳) 때문입니다. CPU의 레벨 1 캐시 (L1), 레벨 2 캐시 (L2)의 크기를 초과하고 코드에 걸리는 시간을 계획하도록 배열의 크기를 지속적으로 조정하는 것은 흥미로울 것입니다 배열의 크기에 따라 실행합니다. 그래프는 직선과 같지 않아야합니다.

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을 보여줍니다.)


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

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

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

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

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

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

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

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

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

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

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

신청

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


두 번째 루프는 캐시 활동이 훨씬 적기 때문에 프로세서가 메모리 요구 사항을 따라 잡는 것이 더 쉽습니다.


이것에 대한 추가 분석을 통해, 나는 적어도 부분적으로 네 포인터의 데이터 정렬에 의한 것이라고 생각한다. 이로 인해 일정 수준의 캐시 뱅크 / 웨이 충돌이 발생합니다.

배열을 할당하는 방법을 정확히 추측했다면 페이지 줄에 정렬 될 가능성이 높습니다 .

즉, 각 루프의 모든 액세스는 동일한 캐시 방식으로 이루어집니다. 그러나 Intel 프로세서는 8-way 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;
}

벤치 마크 결과 :

편집 : 실제 코어 2 아키텍처 컴퓨터에서 결과 :

2 x 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은 주석에서 지적했듯이이 정렬로 인해로드 / 저장 유닛이나 캐시에 잘못된 앨리어싱 이 발생할 가능성이 매우 높습니다. 나는 이것에 대해 주위를 인터넷을 검색하고 실제로 인텔이 부분적인 주소 앨리어싱을 위한 하드웨어 카운터를 가지고 있음을 발견했다.

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

5 개 지역 - 설명

지역 1 :

이거 쉽지. 데이터 세트는 너무 작기 때문에 성능이 루프 및 분기와 같은 오버 헤드에 의해 좌우됩니다.

지역 2 :

여기서 데이터 크기가 증가하면 상대적 오버 헤드가 감소하고 성능이 "포화"됩니다. 두 개의 루프는 두 배의 루프와 브랜치 오버 헤드를 가지므로 더 느립니다.

정확히 무슨 일이 일어나고 있는지 확신 할 수 없습니다. Agner Fog가 캐시 뱅크 충돌을 언급하면서 정렬은 여전히 ​​영향을 미칩니다. (이 링크는 샌디 브릿지에 관한 것이지만 아이디어는 여전히 코어 2에 적용 가능해야합니다.)

지역 3 :

이 시점에서 데이터는 더 이상 L1 캐시에 들어 가지 않습니다. 따라서 성능은 L1 <-> L2 캐시 대역폭으로 제한됩니다.

지역 4 :

단일 루프의 성능 저하는 우리가 관찰하고있는 것입니다. 언급 한 바와 같이, 이것은 (대부분의 경우) 프로세서로드 / 저장 장치에서 거짓 앨리어싱을 야기하는 정렬 때문입니다.

그러나 잘못된 앨리어싱이 발생하려면 데이터 집합간에 충분히 큰 보폭이 있어야합니다. 이것이 지역 3에서는 보이지 않는 이유입니다.

지역 5 :

이 시점에서 캐시에는 아무 것도 없습니다. 따라서 메모리 대역폭에 묶여 있습니다.


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 바이트의 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] 캐시에서 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

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


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

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

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

루프 내에서 b[j] , d[j]InitToZero[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 초로 거의 동일합니다.


오래된 C ++ 및 최적화 일 수 있습니다. 내 컴퓨터에서 나는 거의 같은 속도를 얻었다.

하나의 루프 : 1.577ms 두 개의 루프 : 1.507ms

VS2015를 E5-1620 3.5Ghz 프로세서에서 16Gb 램과 함께 실행합니다.





vectorization