질문자 :Johannes Gerer
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]; }
Intel Core 2 Duo(x64)에서 32비트에 대해 전체 최적화 및 SSE2가 활성화된 MS Visual C++ 10.0 에서 컴파일된 첫 번째 예제는 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]
이중 루프 예제의 각 루프는 다음 코드를 생성합니다(다음 블록은 약 세 번 반복됨).
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/캐시 아키텍처 간의 차이점을 지적하는 것도 흥미로울 수 있습니다.
PPS: 전체 코드는 다음과 같습니다. TBB_TIMING 매크로를 정의하지 않음으로써 비활성화할 수 있는 더 높은 해상도 타이밍을 위해 TBB Tick_Count 를 사용합니다.
#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를 보여줍니다.)
이에 대한 추가 분석을 통해 나는 이것이 (적어도 부분적으로) 4개 포인터의 데이터 정렬로 인해 발생했다고 생각합니다. 이것은 어느 정도의 캐시 뱅크/웨이 충돌을 일으킬 것입니다.
배열을 할당하는 방법을 올바르게 추측했다면 페이지 행에 정렬될 가능성이 높습니다 .
이것은 각 루프의 모든 액세스가 동일한 캐시 방식에 속한다는 것을 의미합니다. 그러나 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; }
벤치마크 결과:
편집: 실제 Core 2 아키텍처 시스템에 대한 결과:
2 x Intel Xeon X5482 Harpertown @ 3.2GHz:
#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이 주석에서 지적했듯이 이 정렬로 인해 로드/저장 장치 또는 캐시에서 잘못된 앨리어싱이 발생할 가능성이 매우 높습니다. 나는 이것에 대해 주위를 둘러 보았고 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에 대한 것이지만 아이디어는 여전히 Core 2에 적용되어야 합니다.)
지역 3:
이 시점에서 데이터는 더 이상 L1 캐시에 맞지 않습니다. 따라서 성능은 L1 <-> L2 캐시 대역폭에 의해 제한됩니다.
지역 4:
단일 루프의 성능 저하가 우리가 관찰하고 있는 것입니다. 그리고 언급한 바와 같이 이는 (대부분) 프로세서 로드/저장 장치에서 잘못된 앨리어싱 지연을 일으키는 정렬 때문입니다.
그러나 잘못된 앨리어싱이 발생하려면 데이터 세트 간에 충분한 보폭이 있어야 합니다. 이것이 지역 3에서 이것을 볼 수 없는 이유입니다.
지역 5:
이 시점에서 캐시에 맞는 것은 없습니다. 그래서 당신은 메모리 대역폭에 묶여 있습니다.
좋아요, 정답은 확실히 CPU 캐시와 관련이 있습니다. 그러나 특히 데이터가 없으면 캐시 인수를 사용하는 것이 매우 어려울 수 있습니다.
많은 토론으로 이어진 많은 답변이 있지만 직시합시다. 캐시 문제는 매우 복잡할 수 있고 일차원적이지 않습니다. 그것들은 데이터의 크기에 크게 의존하므로 내 질문은 불공평했습니다. 캐시 그래프에서 매우 흥미로운 지점에 있다는 것이 밝혀졌습니다.
@Mysticial의 대답은 많은 사람들(저를 포함하여)을 확신시켰습니다. 아마도 그것이 사실에 의존하는 것처럼 보였던 유일한 사람이었기 때문일 것입니다. 그러나 그것은 진실의 하나의 "데이터 포인트"에 불과했습니다.
이것이 내가 그의 테스트(연속 할당과 별도 할당 사용)와 @James의 Answer의 조언을 결합한 이유입니다.
아래 그래프는 대부분의 답변, 특히 질문과 답변에 대한 대부분의 댓글이 사용된 정확한 시나리오와 매개변수에 따라 완전히 틀리거나 사실로 간주될 수 있음을 보여줍니다.
내 초기 질문은 n = 100.000에 있었습니다. 이 지점은 (우연히) 특별한 동작을 나타냅니다.
1루프 버전과 2루프 버전 사이에 가장 큰 불일치가 있습니다(거의 3배).
단일 루프(즉, 연속 할당 포함)가 이중 루프 버전을 능가하는 유일한 지점입니다. (이것은 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]; }
첫 번째 원인이 와 a b RAM에로드하고 다음 RAM에 완전히 작업 할. 두 번째 루프가 시작되면 c 와 d 가 디스크에서 RAM으로 로드되고 작동됩니다.
다른 루프
for(int j=0;j<n;j++){ a[j] += b[j]; c[j] += d[j]; }
루프를 돌 때마다 두 개의 배열을 페이징하고 다른 두 개의 배열을 페이징합니다. 이것은 분명히 훨씬 느릴 것입니다.
테스트에서 디스크 캐싱이 표시되지 않을 수 있지만 다른 형태의 캐싱의 부작용이 나타날 수 있습니다.
여기에 약간의 혼동/오해가 있는 것 같아서 예를 들어 조금 더 자세히 설명하겠습니다.
n = 2 라고 말하면 우리는 바이트로 작업하고 있습니다. 제 시나리오에서는 RAM이 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] 을 설정합니다. 이제 캐시에 4바이트가 있습니다. 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
와 함께
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] 을 꺼낸 다음 d[0] 및 d[1] 을 꺼내고 c[0] = c[0] + d[0] 캐시에 있습니다. 비용 = 100 + 100. - 나는 당신이 내가 어디로 가고 있는지보기 시작했다고 생각합니다.
- 총 비용 =
(100 + 100 + 100 + 100) * 2 = 800
이것은 전형적인 캐시 스래시 시나리오입니다.
다른 코드 때문이 아니라 캐싱 때문입니다. RAM은 CPU 레지스터보다 느리고 캐시 메모리는 변수가 변경될 때마다 RAM을 쓰는 것을 피하기 위해 CPU 내부에 있습니다. 그러나 캐시는 RAM만큼 크지 않으므로 일부만 매핑합니다.
첫 번째 코드는 원격 메모리 주소를 각 루프에서 교대로 수정하므로 캐시를 계속해서 무효화해야 합니다.
두 번째 코드는 교대하지 않습니다. 단지 인접한 주소로 두 번 흐릅니다. 이렇게 하면 모든 작업이 캐시에서 완료되고 두 번째 루프가 시작된 후에만 이를 무효화합니다.
여기서 논의된 결과를 복제할 수 없습니다.
열악한 벤치마크 코드가 원인인지 아니면 무엇 때문인지 모르겠지만 두 가지 방법은 다음 코드를 사용하는 내 컴퓨터에서 서로 10% 이내이며 하나의 루프는 일반적으로 두 개보다 약간 빠릅니다. 예상하다.
배열 크기의 범위는 2^16에서 2^24이며 8개의 루프를 사용합니다. += 할당이 FPU 에 이중으로 해석되는 메모리 가비지를 추가하도록 요청하지 않도록 소스 배열을 초기화하는 데 주의했습니다.
루프 내부 b[j] , d[j] 를 InitToZero[j] += b[j] = 1 및 += d[j] = 1 를 사용하는 것과 같은 다양한 계획을 가지고 놀았습니다. += d[j] = 1 , 상당히 일관된 결과를 얻었습니다.
예상할 수 있듯이 InitToZero[j] 사용하여 루프 내에서 b 및 d 초기화하면 결합된 접근 방식이 이점을 얻었습니다. a 및 c 할당하기 전에 연속적으로 수행되었지만 여전히 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초로 거의 동일합니다.
CPU에 캐시 미스가 많지 않기 때문입니다(어레이 데이터가 RAM 칩에서 올 때까지 기다려야 하는 곳). CPU의 레벨 1 캐시 (L1), 다음으로 레벨 2 캐시 (L2)의 크기를 초과하고 코드에 소요된 시간을 표시하도록 어레이의 크기를 지속적으로 조정하는 것은 흥미로울 것입니다. 배열의 크기에 대해 실행합니다. 그래프는 예상대로 직선이 아니어야 합니다.
첫 번째 루프는 각 변수에 쓰기를 번갈아 수행합니다. 두 번째와 세 번째는 요소 크기의 작은 점프만 합니다.
20cm 간격으로 펜과 종이를 사용하여 20개의 십자로 된 두 개의 평행선을 써 보십시오. 한 줄을 끝내고 다른 줄을 끝내고 각 줄에 교대로 십자가를 써서 다시 시도하십시오.
원래 질문
하나의 루프가 두 개의 루프보다 훨씬 느린 이유는 무엇입니까?
결론:
사례 1 은 비효율적인 보간 문제입니다. 또한 이것이 많은 기계 아키텍처와 개발자가 병렬 프로그래밍뿐만 아니라 다중 스레드 응용 프로그램을 수행할 수 있는 다중 코어 시스템을 구축 및 설계하게 된 주요 이유 중 하나라고 생각합니다.
하드웨어 , OS 및 컴파일러가 함께 작동하여 RAM, 캐시, 페이지 파일 등의 작업과 관련된 힙 할당을 수행하는 방법을 포함하지 않고 이러한 종류의 접근 방식에서 살펴봅니다. 이러한 알고리즘의 기초가 되는 수학은 이 두 가지 중 어느 것이 더 나은 솔루션인지 보여줍니다.
Boss 가 A 와 B 사이를 이동해야 하는 For Loop Summation 인 유추를 사용할 수 있습니다.
우리는 쉽게 사례 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]; }
고려
for 루프의 두 가지 변형에 대한 OP의 원래 질문과 다른 많은 훌륭한 답변 및 유용한 주석과 함께 캐시 동작에 대한 수정된 질문을 고려합니다. 저는 이 상황과 문제에 대해 다른 접근 방식을 취함으로써 여기서 다른 것을 시도하고 싶습니다.
접근
두 개의 루프와 캐시 및 페이지 파일링에 대한 모든 논의를 고려할 때 저는 이것을 다른 관점에서 보는 다른 접근 방식을 취하고 싶습니다. 캐시 및 페이지 파일이나 메모리 할당 실행을 포함하지 않는 방법은 사실 이 접근 방식은 실제 하드웨어나 소프트웨어와 전혀 관련이 없습니다.
관점
잠시 동안 코드를 살펴본 후 문제가 무엇이며 문제를 생성하는 것이 무엇인지 매우 분명해졌습니다. 이것을 알고리즘 문제로 분해하고 수학 표기법을 사용하는 관점에서 살펴본 다음 수학 문제와 알고리즘에 유추를 적용해 보겠습니다.
우리가 알고 있는 것
우리는 이 루프가 100,000번 실행된다는 것을 알고 있습니다. 우리는 또한 a1 , b1 , c1 & d1 이 64비트 아키텍처에 대한 포인터라는 것을 알고 있습니다. 32비트 시스템의 C++ 내에서 모든 포인터는 4바이트이고 64비트 시스템에서는 포인터의 길이가 고정되어 있으므로 크기가 8바이트입니다.
두 경우 모두에 할당할 32바이트가 있다는 것을 알고 있습니다. 유일한 차이점은 각 반복에서 32바이트 또는 2-8바이트의 두 세트를 할당한다는 것입니다. 두 번째 경우에는 두 독립 루프 모두에 대해 각 반복에 대해 16바이트를 할당합니다.
두 루프는 여전히 총 할당에서 32바이트와 같습니다. 이 정보를 가지고 이제 일반적인 수학, 알고리즘 및 이러한 개념의 유추를 보여 드리겠습니다.
우리는 두 경우 모두에서 동일한 작업 세트 또는 그룹이 수행되어야 하는 횟수를 알고 있습니다. 두 경우 모두 할당해야 하는 메모리의 양을 알고 있습니다. 두 경우 간의 할당의 전체 작업 부하가 거의 동일하다고 평가할 수 있습니다.
우리가 모르는 것
카운터를 설정하고 벤치마크 테스트를 실행하지 않는 한 각 경우에 얼마나 걸릴지 모릅니다. 그러나 벤치마크는 원래 질문과 일부 답변 및 의견에도 이미 포함되어 있습니다. 그리고 우리는 둘 사이의 상당한 차이를 볼 수 있으며 이것이 이 문제에 대한 이 제안에 대한 전체 추론입니다.
조사하자
많은 사람들이 힙 할당, 벤치마크 테스트, RAM, 캐시 및 페이지 파일을 살펴봄으로써 이미 이 작업을 수행했음이 분명합니다. 특정 데이터 포인트와 특정 반복 지수를 살펴보는 것도 포함되었으며 이 특정 문제에 대한 다양한 대화를 통해 많은 사람들이 이에 대해 다른 관련 질문을 하기 시작했습니다. 수학적 알고리즘을 사용하고 이에 대한 유추를 적용하여 이 문제를 어떻게 보기 시작합니까? 우리는 몇 가지 주장을 하는 것으로 시작합니다! 그런 다음 거기에서 알고리즘을 구축합니다.
우리의 주장:
- 우리는 루프와 그 반복이 루프에서처럼 0으로 시작하는 대신 1에서 시작하여 100000에서 끝나는 합이 되도록 할 것입니다. 알고리즘 자체.
- 두 경우 모두 작업할 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() 는 Case1 Sum 에만 존재하고 F1() Case1 Sum 과 Case2 Sum1 Sum2 모두에 포함되어 있습니다. 이것은 나중에 두 번째 알고리즘 내에서 최적화가 일어나고 있다는 결론을 내리기 시작할 때 분명해질 것입니다.
첫 번째 경우를 통해 반복 Sum 호출 f(a) 그 자체를 추가하는 것 f(b) 다음 호출 f(c) 동일한 기능을 수행하지만, 추가한다 f(d) 각각 그 자체 100000 반복. 두 번째 경우에는 Sum1 과 Sum2 가 모두 동일한 함수가 연속으로 두 번 호출되는 것처럼 동일하게 작동합니다.
Sum1 과 Sum2 를 평범한 오래된 Sum 으로 취급할 수 있습니다. 이 경우 Sum 은 다음과 같습니다. Sum n=1 : [1,100000] { f(a) = f(a) + f(b); } 이제 이것은 동일한 기능으로 간주할 수 있는 최적화처럼 보입니다.
유추를 통한 요약
두 번째 경우에서 보았듯이 두 for 루프가 정확히 동일한 서명을 가지고 있기 때문에 최적화가 있는 것처럼 보이지만 이것은 실제 문제가 아닙니다. f(a) , f(b) , f(c) 및 f(d) 가 수행하는 작업이 아닙니다. 두 경우 모두와 둘 사이의 비교에서 실행 시간의 차이를 제공하는 것은 각 경우에 Summation이 이동해야 하는 거리의 차이입니다.
for 루프 를 반복을 수행 하는 합계 A & B 에게 명령을 내리는 Boss 생각하고 그들의 작업은 C & D 수행하고 그들로부터 일부 패키지를 선택하고 반환하는 것입니다. 이 비유에서 for 루프 또는 합산 반복 및 조건 검사 자체는 실제로 Boss 나타내지 않습니다. Boss 나타내는 것은 실제 수학적 알고리즘에서 직접 나온 것이 아니라 Scope 및 Code Block 의 실제 개념에서 나온 것입니다. 첫 번째 알고리즘에는 두 번째 알고리즘이 두 개 있는 하나의 범위가 있습니다. 연속 범위.
각 호출 슬립의 첫 번째 케이스 내에서 Boss 로 이동 과 순서를 제공하고 A A 가져 꺼집니다 B's 다음 패키지를 Boss 로 이동 C 와에서 패키지를 동일한 작업을 수행하고받을 수있는 명령을 제공 D 각 반복에.
두 번째 경우 Boss A 와 직접 작업하여 모든 패키지가 수신될 때까지 B's 패키지를 가져옵니다. 그런 다음 Boss C 와 함께 D's 패키지를 가져오기 위해 동일한 작업을 수행합니다.
우리는 8바이트 포인터로 작업하고 힙 할당을 처리하므로 다음 문제를 고려해 보겠습니다. Boss A 에서 100피트이고 A C 에서 500피트라고 가정해 보겠습니다. 우리는 실행 순서 때문에 Boss 가 처음에 C 에서 얼마나 멀리 떨어져 있는지에 대해 걱정할 필요가 없습니다. 두 경우 모두 Boss 처음에 A 에서 B 합니다. 이 비유는 이 거리가 정확하다고 말하는 것이 아닙니다. 알고리즘의 작동을 보여주는 유용한 테스트 케이스 시나리오일 뿐입니다.
힙 할당을 수행하고 캐시 및 페이지 파일로 작업할 때 대부분의 경우 이러한 주소 위치 간의 거리는 데이터 유형 및 어레이 크기의 특성에 따라 크게 달라지지 않거나 크게 다를 수 있습니다.
테스트 사례:
첫 번째 경우: 첫 번째 반복에서 Boss A 에게 오더 슬립을 주기 위해 100피트를 이동해야 하고 A 는 가서 자신의 일을 하지만 Boss 는 그에게 오더 슬립을 주기 C 까지 500피트를 이동해야 합니다. 그런 다음 다음 반복과 Boss 이후의 다른 모든 반복에서 두 사람 사이에서 500피트를 왔다갔다 해야 합니다.
두 번째 경우: Boss A 까지 100피트를 이동해야 하지만 그 후에는 이미 거기에 있고 모든 슬립이 채워질 때까지 A 그런 다음 Boss 에 첫 번째 반복에 500피트를 여행하는 C 때문에 C 500 피트 . A Boss( Summation, For Loop ) A 와 작업한 직후에 호출되기 때문에 C's 모든 주문 슬립이 완료될 때까지 A 와 마찬가지로 그곳에서 기다리기만 하면 됩니다.
이동 거리의 차이
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의 주소 또는 캐시 또는 페이지 파일 간의 실제 거리 차이를 알지 못하기 때문입니다. 이는 최악의 시나리오에서 인식하고 바라보는 상황에 대한 평가일 뿐입니다.
이 숫자에서 알고리즘 1 은 알고리즘 2 보다 99% 느려야 하는 것처럼 거의 나타납니다. 그러나 이것은 Boss's 부분 또는 책임일 뿐이며 실제 작업자 A , B , C 및 D 와 루프의 각 반복에서 수행해야 하는 작업을 설명하지 않습니다. 따라서 상사의 업무는 수행되는 전체 업무의 약 15~40%만 차지합니다. 워커를 통해 하는 대부분의 작업은 속도 차이 비율을 약 50-70%로 유지하는 데 약간 더 큰 영향을 미칩니다.
관찰: - 두 알고리즘의 차이점
이 상황에서 수행되는 작업의 프로세스 구조입니다. Case 2 는 유사한 함수 선언을 갖는 부분 최적화와 이름과 이동 거리가 다른 변수만 있는 정의에서 더 효율적임을 보여줍니다.
또한 사례 1 에서 이동한 총 거리는 사례 2 에서보다 훨씬 더 멀다는 것을 알 수 있으며 이 거리가 두 알고리즘 사이 의 시간 계수 를 이동한 것으로 간주할 수 있습니다. 사례 1 은 사례 2 보다 해야 할 일이 훨씬 더 많습니다.
이것은 두 경우 모두에 표시된 조립 지침의 증거에서 관찰할 수 있습니다. 이러한 경우에 대해 이미 언급된 것과 함께 이것은 사례 1 에서 보스가 각 반복에 대해 A 다시 돌아갈 수 있기 전에 A 와 C 가 모두 돌아올 때까지 기다려야 한다는 사실을 설명하지 않습니다. A 또는 B 가 매우 오랜 시간이 걸리는 경우 Boss 와 다른 작업자가 모두 실행되기를 기다리며 유휴 상태라는 사실을 고려하지 않습니다.
사례 2 에서 유휴 상태인 유일한 사람은 작업자가 돌아올 때까지 Boss 따라서 이것조차도 알고리즘에 영향을 미칩니다.
OP의 수정된 질문
편집: 동작은 어레이(n) 및 CPU 캐시의 크기에 따라 크게 달라지므로 질문은 관련성이 없는 것으로 나타났습니다. 따라서 더 많은 관심이 있다면 질문을 다시 말하겠습니다.
다음 그래프의 5개 영역에서 설명하는 것처럼 다양한 캐시 동작으로 이어지는 세부 사항에 대한 확실한 통찰력을 제공할 수 있습니까?
이러한 CPU에 대해 유사한 그래프를 제공하여 CPU/캐시 아키텍처 간의 차이점을 지적하는 것도 흥미로울 수 있습니다.
이러한 질문에 대해
내가 의심의 여지 없이 증명했듯이 하드웨어와 소프트웨어가 관련되기 전에도 근본적인 문제가 있습니다.
이제 다음 사이의 통합 시스템 세트에서 함께 작동하는 페이지 파일 등과 함께 메모리 및 캐싱 관리에 대해 설명합니다.
- 아키텍처 (하드웨어, 펌웨어, 일부 임베디드 드라이버, 커널 및 어셈블리 명령어 세트).
- OS (파일 및 메모리 관리 시스템, 드라이버 및 레지스트리).
- 컴파일러 (번역 단위 및 소스 코드 최적화).
- 그리고 고유한 알고리즘 집합이 있는 소스 코드 자체도 포함됩니다.
우리는 두 번째 알고리즘과 비교하여 임의의 아키텍처 , OS 및 프로그래밍 가능한 언어를 가진 모든 기계에 적용하기 전에 첫 번째 알고리즘 내에서 병목 현상이 발생하고 있음을 이미 알 수 있습니다. 현대 컴퓨터의 본질을 포함하기 전에 이미 문제가 있었습니다.
최종 결과
하지만; 이러한 새로운 질문이 중요하지 않다는 것은 그 자체로 중요하지 않으며 결국 역할을 하기 때문입니다. 그것들은 절차와 전반적인 성능에 영향을 미치며, 이는 답변 및/또는 의견을 제시한 많은 사람들의 다양한 그래프와 평가에서 분명합니다.
C & D 각각 패키지를 가져와야 했던 Boss 와 두 작업자 A & B 의 비유에 주의를 기울이고 문제의 두 알고리즘의 수학적 표기법을 고려한다면; 컴퓨터 하드웨어 및 소프트웨어의 개입 없이 볼 수 있습니다. Case 2 는 Case 1 보다 60% 빠릅니다.
이러한 알고리즘을 일부 소스 코드에 적용하고, 컴파일, 최적화 및 OS를 통해 실행하여 주어진 하드웨어에서 작업을 수행한 후 그래프와 차트를 보면 차이점 사이에 약간 더 열화가 있음을 알 수 있습니다. 이러한 알고리즘에서.
Data 세트가 상당히 작은 경우 처음에는 그렇게 나쁜 차이로 보이지 않을 수 있습니다. 그러나 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 사이의 최대 거리를 앞뒤로 이동해야 Boss A 한 번 이동해야 하고 완료 후에는 완료되어야 합니다. A A 에서 C 갈 때 한 번만 최대 거리를 이동해야 합니다.
상사가 비슷한 연속 작업에 집중하는 대신 한 번에 두 가지 유사한 일에 집중하고 앞뒤로 저글링하도록 하면 두 배의 여행과 일을 해야 했기 때문에 하루가 끝날 때까지 Boss 그러므로 상사의 배우자와 자녀가 이를 고맙게 여기지 않는다고 해서 상사가 보간된 병목 현상에 빠지게 함으로써 상황의 범위를 잃지 마십시오.
수정: 소프트웨어 엔지니어링 설계 원칙
-- 반복 for 루프 내에서 로컬 스택 과 힙 할당 계산의 차이점과 사용법, 효율성 및 효율성의 차이 --
위에서 제안한 수학적 알고리즘은 주로 힙에 할당된 데이터에 대한 연산을 수행하는 루프에 적용됩니다.
- 연속 스택 작업:
- 루프가 스택 프레임 내에 있는 단일 코드 블록 또는 범위 내에서 로컬로 데이터에 대한 작업을 수행하는 경우에도 여전히 적용되지만 메모리 위치는 일반적으로 순차적이고 이동 거리 또는 실행 시간의 차이가 훨씬 더 가깝습니다. 거의 무시할 수 있습니다. 힙 내에서 할당이 수행되지 않기 때문에 메모리가 흩어지지 않고 램을 통해 메모리를 가져오지 않습니다. 메모리는 일반적으로 순차적이며 스택 프레임 및 스택 포인터에 상대적입니다.
- 스택에서 연속 작업이 수행될 때 최신 프로세서 는 반복적인 값과 주소를 캐시하여 이러한 값을 로컬 캐시 레지스터 내에 유지합니다. 여기에서 작동 또는 지시의 시간은 나노초 정도입니다.
- 연속 힙 할당 작업:
- 힙 할당을 적용하기 시작하고 프로세서가 연속 호출에서 메모리 주소를 가져와야 할 때 CPU, 버스 컨트롤러 및 RAM 모듈의 아키텍처에 따라 작업 또는 실행 시간은 마이크로에서 밀리초. 캐시된 스택 작업과 비교할 때 상당히 느립니다.
- CPU는 RAM에서 메모리 주소를 가져와야 하며 일반적으로 시스템 버스 전체의 모든 것이 CPU 자체 내의 내부 데이터 경로나 데이터 버스에 비해 느립니다.
따라서 힙에 있어야 하는 데이터로 작업하고 루프에서 데이터를 탐색할 때 각 데이터 세트와 해당 알고리즘을 자체 단일 루프 내에 유지하는 것이 더 효율적입니다. 힙에 있는 서로 다른 데이터 세트의 여러 작업을 단일 루프에 넣어 연속 루프를 제외하려고 시도하는 것과 비교하여 더 나은 최적화를 얻을 수 있습니다.
스택에 있는 데이터는 자주 캐시되기 때문에 이 작업을 수행해도 되지만 메모리 주소를 반복할 때마다 쿼리해야 하는 데이터의 경우에는 그렇지 않습니다.
여기에서 소프트웨어 엔지니어링 및 소프트웨어 아키텍처 설계가 시작됩니다. 데이터를 구성하는 방법, 데이터를 캐시할 때, 데이터를 힙에 할당할 때, 알고리즘을 설계하고 구현하는 방법, 호출할 때와 위치를 아는 능력입니다.
동일한 데이터 세트에 관련된 동일한 알고리즘이 있을 수 있지만, O(n) 힙으로 작업할 때 알고리즘.
내가 수년에 걸쳐 알아차린 것에서, 많은 사람들이 이 사실을 고려하지 않습니다. 그들은 특정 데이터 세트에서 작동하는 하나의 알고리즘을 설계하는 경향이 있으며 데이터 세트가 스택에 로컬로 캐시되거나 힙에 할당되었는지 여부에 관계없이 이를 사용합니다.
진정한 최적화를 원한다면 코드 중복처럼 보일 수 있지만 일반화하려면 동일한 알고리즘의 두 가지 변형을 갖는 것이 더 효율적일 것입니다. 하나는 스택 작업용이고 다른 하나는 반복 루프에서 수행되는 힙 작업용입니다!
다음은 의사 예입니다. 두 개의 간단한 구조체, 하나의 알고리즘.
struct A { int data; A() : data{0}{} A(int a) : data{a}{} }; struct B { int data; B() : data{0}{} A(int b) : data{b}{} } template<typename T> void Foo( T& t ) { // Do something with t } // Some looping operation: first stack then heap. // Stack data: A dataSetA[10] = {}; B dataSetB[10] = {}; // For stack operations this is okay and efficient for (int i = 0; i < 10; i++ ) { Foo(dataSetA[i]); Foo(dataSetB[i]); } // If the above two were on the heap then performing // the same algorithm to both within the same loop // will create that bottleneck A* dataSetA = new [] A(); B* dataSetB = new [] B(); for ( int i = 0; i < 10; i++ ) { Foo(dataSetA[i]); // dataSetA is on the heap here Foo(dataSetB[i]); // dataSetB is on the heap here } // this will be inefficient. // To improve the efficiency above, put them into separate loops... for (int i = 0; i < 10; i++ ) { Foo(dataSetA[i]); } for (int i = 0; i < 10; i++ ) { Foo(dataSetB[i]); } // This will be much more efficient than above. // The code isn't perfect syntax, it's only psuedo code // to illustrate a point.
이것은 스택 변형 대 힙 변형에 대한 별도의 구현을 통해 언급한 것입니다. 알고리즘 자체는 그다지 중요하지 않습니다. 그 작업에서 사용할 루핑 구조입니다.
오래된 C++ 및 최적화일 수 있습니다. 내 컴퓨터에서 거의 동일한 속도를 얻었습니다.
루프 1개: 1.577ms
2개의 루프: 1.507ms
16GB RAM이 장착된 E5-1620 3.5GHz 프로세서에서 Visual Studio 2015를 실행합니다.
출처 : http:www.stackoverflow.com/questions/8547778/why-are-elementwise-additions-much-faster-in-separate-loops-than-in-a-combined-l