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




performance compiler-optimization (7)

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


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


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