질문 : 32 비트 루프 카운터를 64 비트로 대체하면 Intel CPU에서 _mm_popcnt_u64의 성능 편차가 발생합니다.
대규모 데이터 배열 popcount 하는 가장 빠른 방법을 찾고있었습니다. 매우 이상한 효과가 발생했습니다. 루프 변수를 unsigned 에서 uint64_t 로 변경하면 내 PC에서 성능이 50 % 저하되었습니다.
#include <iostream>
#include <chrono>
#include <x86intrin.h>
int main(int argc, char* argv[]) {
using namespace std;
if (argc != 2) {
cerr << "usage: array_size in MB" << endl;
return -1;
}
uint64_t size = atol(argv[1])<<20;
uint64_t* buffer = new uint64_t[size/8];
char* charbuffer = reinterpret_cast<char*>(buffer);
for (unsigned i=0; i<size; ++i)
charbuffer[i] = rand()%256;
uint64_t count,duration;
chrono::time_point<chrono::system_clock> startP,endP;
{
startP = chrono::system_clock::now();
count = 0;
for( unsigned k = 0; k < 10000; k++){
// Tight unrolled loop with unsigned
for (unsigned i=0; i<size/8; i+=4) {
count += _mm_popcnt_u64(buffer[i]);
count += _mm_popcnt_u64(buffer[i+1]);
count += _mm_popcnt_u64(buffer[i+2]);
count += _mm_popcnt_u64(buffer[i+3]);
}
}
endP = chrono::system_clock::now();
duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
cout << "unsigned\t" << count << '\t' << (duration/1.0E9) << " sec \t"
<< (10000.0*size)/(duration) << " GB/s" << endl;
}
{
startP = chrono::system_clock::now();
count=0;
for( unsigned k = 0; k < 10000; k++){
// Tight unrolled loop with uint64_t
for (uint64_t i=0;i<size/8;i+=4) {
count += _mm_popcnt_u64(buffer[i]);
count += _mm_popcnt_u64(buffer[i+1]);
count += _mm_popcnt_u64(buffer[i+2]);
count += _mm_popcnt_u64(buffer[i+3]);
}
}
endP = chrono::system_clock::now();
duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
cout << "uint64_t\t" << count << '\t' << (duration/1.0E9) << " sec \t"
<< (10000.0*size)/(duration) << " GB/s" << endl;
}
free(charbuffer);
}보시다시피, 임의의 데이터 버퍼를 생성합니다. 크기는 x 메가 바이트이며 여기서 x 는 명령 줄에서 읽습니다. 그 후 버퍼를 반복하고 x86 popcount 내장 함수의 펼쳐진 버전을 사용하여 popcount를 수행합니다. 보다 정확한 결과를 얻으려면 popcount를 10,000 번 수행합니다. 팝 카운트의 시간을 측정합니다. 대문자의 경우 내부 루프 변수는 unsigned 이고, 소문자의 경우 내부 루프 변수는 uint64_t 입니다. 차이가 없어야한다고 생각했지만 그 반대입니다.
다음과 같이 컴파일합니다 (g ++ 버전 : Ubuntu 4.8.2-19ubuntu1).
g++ -O3 -march=native -std=c++11 test.cpp -o test다음은 내 Haswell Core i7-4770K CPU @ 3.50GHz에서 test 1 실행 한 결과입니다 (1MB 임의 데이터).
- 서명되지 않음 41959360000 0.401554 초 26.113GB / s
- uint64_t 41959360000 0.759822 초 13.8003GB / s
uint64_t 버전의 처리량은 unsigned 버전의 절반에 불과합니다! 문제는 다른 어셈블리가 생성되는 것 같지만 그 이유는 무엇입니까? 먼저 컴파일러 버그를 생각했기 때문에 clang++ (Ubuntu Clang 버전 3.4-1ubuntu3)을 시도했습니다.
clang++ -O3 -march=native -std=c++11 teest.cpp -o test결과 : test 1
- 서명되지 않음 41959360000 0.398293 초 26.3267GB / s
- uint64_t 41959360000 0.680954 초 15.3986GB / s
따라서 거의 동일한 결과이며 여전히 이상합니다. 그러나 이제는 매우 이상해집니다. 입력에서 읽은 버퍼 크기를 상수 1 로 대체하므로 다음과 같이 변경합니다.
uint64_t size = atol(argv[1]) << 20;...에
uint64_t size = 1 << 20;따라서 컴파일러는 이제 컴파일 타임에 버퍼 크기를 알고 있습니다. 아마도 몇 가지 최적화를 추가 할 수 있습니다! g++ 의 숫자입니다.
- 서명되지 않음 41959360000 0.509156 초 20.5944GB / s
- uint64_t 41959360000 0.508673 초 20.6139GB / s
이제 두 버전 모두 똑같이 빠릅니다. 그러나 unsigned 는 더 느려졌습니다 ! 그것으로부터 떨어 26 에 20 GB/s 따라서 deoptimization에 일정한 값을 리드하여 일정하지 않은 대체. 진지하게, 나는 여기서 무슨 일이 일어나고 있는지 전혀 모른다! 그러나 이제 새 버전 clang++
- 서명되지 않음 41959360000 0.677009 초 15.4884GB / s
- uint64_t 41959360000 0.676909 초 15.4906GB / s
무엇을 기다립니다? 이제 두 버전 모두 느린 속도 인 15GB / s로 떨어졌습니다. 따라서 상수가 아닌 값을 상수 값으로 대체하면 두 경우 모두 Clang!
Ivy Bridge CPU를 사용하는 동료에게 벤치 마크를 컴파일 해달라고 요청했습니다. 그는 비슷한 결과를 얻었으므로 Haswell이 아닌 것 같습니다. 두 개의 컴파일러가 여기서 이상한 결과를 생성하기 때문에 컴파일러 버그가 아닌 것 같습니다. 여기에는 AMD CPU가 없으므로 Intel에서만 테스트 할 수 있습니다.
첫 번째 예제 ( atol(argv[1]) 있는 예제)를 사용하고 변수 앞에 static
static uint64_t size=atol(argv[1])<<20;다음은 g ++의 결과입니다.
- 서명되지 않음 41959360000 0.396728 초 26.4306GB / s
- uint64_t 41959360000 0.509484 초 20.5811GB / s
예, 또 다른 대안 . u32 u64 / s를 가지고 있지만, 우리는 적어도 13GB / s에서 20GB / s 버전까지 u64를 얻을 수있었습니다! 동료의 PC에서 u64 u32 버전보다 훨씬 빨라져 가장 빠른 결과를 얻었습니다. g++ 에서만 작동하며 clang++ static 을 신경 쓰지 않는 것 같습니다.
이 결과를 설명 할 수 있습니까? 특히:
u32와u64사이에 어떻게 그런 차이가있을 수 있습니까?- 상수가 아닌 것을 일정한 버퍼 크기로 대체하면 어떻게 덜 최적의 코드를 트리거 할 수 있습니까?
static키워드를 삽입u64루프를 더 빠르게 만들 수 있습니까? 동료 컴퓨터의 원래 코드보다 훨씬 빠릅니다!
최적화가 까다로운 영역이라는 것을 알고 있지만 이러한 작은 변경이 실행 시간에 100 % 차이 를 가져올 수 있고 일정한 버퍼 크기와 같은 작은 요소가 다시 결과를 완전히 혼합 할 수 있다고는 생각하지 못했습니다. 물론, 저는 항상 26GB / s를 팝 카운트 할 수있는 버전을 원합니다. 내가 생각할 수있는 유일한 방법은이 경우에 어셈블리를 복사하여 붙여넣고 인라인 어셈블리를 사용하는 것입니다. 이것이 내가 작은 변화에 미친 것처럼 보이는 컴파일러를 제거 할 수있는 유일한 방법입니다. 어떻게 생각해? 성능이 가장 뛰어난 코드를 안정적으로 얻을 수있는 또 다른 방법이 있습니까?
다양한 결과에 대한 분해는 다음과 같습니다.
26 GB/s version from g++ / u32 / non-const bufsize:
0x400af8:
lea 0x1(%rdx),%eax
popcnt (%rbx,%rax,8),%r9
lea 0x2(%rdx),%edi
popcnt (%rbx,%rcx,8),%rax
lea 0x3(%rdx),%esi
add %r9,%rax
popcnt (%rbx,%rdi,8),%rcx
add $0x4,%edx
add %rcx,%rax
popcnt (%rbx,%rsi,8),%rcx
add %rcx,%rax
mov %edx,%ecx
add %rax,%r14
cmp %rbp,%rcx
jb 0x400af813 GB/s version from g++ / u64 / non-const bufsize:
0x400c00:
popcnt 0x8(%rbx,%rdx,8),%rcx
popcnt (%rbx,%rdx,8),%rax
add %rcx,%rax
popcnt 0x10(%rbx,%rdx,8),%rcx
add %rcx,%rax
popcnt 0x18(%rbx,%rdx,8),%rcx
add $0x4,%rdx
add %rcx,%rax
add %rax,%r12
cmp %rbp,%rdx
jb 0x400c0015 GB/s version from clang++ / u64 / non-const bufsize:
0x400e50:
popcnt (%r15,%rcx,8),%rdx
add %rbx,%rdx
popcnt 0x8(%r15,%rcx,8),%rsi
add %rdx,%rsi
popcnt 0x10(%r15,%rcx,8),%rdx
add %rsi,%rdx
popcnt 0x18(%r15,%rcx,8),%rbx
add %rdx,%rbx
add $0x4,%rcx
cmp %rbp,%rcx
jb 0x400e5020 GB/s version from g++ / u32&u64 / const bufsize:
0x400a68:
popcnt (%rbx,%rdx,1),%rax
popcnt 0x8(%rbx,%rdx,1),%rcx
add %rax,%rcx
popcnt 0x10(%rbx,%rdx,1),%rax
add %rax,%rcx
popcnt 0x18(%rbx,%rdx,1),%rsi
add $0x20,%rdx
add %rsi,%rcx
add %rcx,%rbp
cmp $0x100000,%rdx
jne 0x400a6815 GB/s version from clang++ / u32&u64 / const bufsize:
0x400dd0:
popcnt (%r14,%rcx,8),%rdx
add %rbx,%rdx
popcnt 0x8(%r14,%rcx,8),%rsi
add %rdx,%rsi
popcnt 0x10(%r14,%rcx,8),%rdx
add %rsi,%rdx
popcnt 0x18(%r14,%rcx,8),%rbx
add %rdx,%rbx
add $0x4,%rcx
cmp $0x20000,%rcx
jb 0x400dd0흥미롭게도 가장 빠른 (26GB / s) 버전도 가장 길다! lea 를 사용하는 유일한 솔루션 인 것 같습니다. 일부 버전은 점프에 jb jne 사용합니다. 그러나 그 외에는 모든 버전이 비슷해 보입니다. 100 % 성능 차이가 어디에서 시작될 수 있는지는 알 수 없지만 어셈블리를 해독하는 데 너무 능숙하지 않습니다. 가장 느린 (13GB / s) 버전은 매우 짧고보기에도 좋습니다. 누구든지 이것을 설명 할 수 있습니까?
이 질문에 대한 답이 무엇이든 상관 없습니다. 나는 정말로 핫 루프에서 모든 세부 사항이 중요 할 수 있다는 것을 배웠습니다. 심지어 핫 코드와 관련이없는 것처럼 보이는 세부 사항도 중요합니다. 루프 변수에 어떤 유형을 사용할지 생각해 본 적이 없지만, 이러한 사소한 변경은 100 % 차이를 만들 수 있습니다! 크기 변수 앞에 static 키워드를 삽입하여 보았 듯이 버퍼의 저장 유형조차도 큰 차이를 만들 수 있습니다! 앞으로는 시스템 성능에 중요한 매우 타이트하고 핫 루프를 작성할 때 항상 다양한 컴파일러에서 다양한 대안을 테스트 할 것입니다.
흥미로운 점은 이미 루프를 4 번 풀었지만 성능 차이가 여전히 높다는 것입니다. 따라서 펼친 경우에도 주요 성능 편차에 의해 타격을받을 수 있습니다. 꽤 흥미로운.
답변
범인 : 잘못된 데이터 종속성 (컴파일러는이를 인식하지 못함)
Sandy / Ivy Bridge 및 Haswell 프로세서에서 지침 :
popcnt src, destdest 에 잘못된 종속성이있는 것 같습니다. 명령어는 쓰기 만하더라도 실행하기 전에 dest 이 잘못된 종속성은 (현재) 인텔에서 정오표 HSD146 (Haswell) 및 SKL029 (Skylake)로 문서화되었습니다.
Skylake는 lzcnt 및 tzcnt 대해 이것을 수정했습니다.
Cannon Lake (및 Ice Lake)는 popcnt 대해 이것을 수정했습니다.bsf / bsr 은 진정한 출력 의존성을 가지고 있습니다 : 입력 = 0에 대해 수정되지 않은 출력. (그러나 내장 함수로이를 활용할 수있는 방법 은 없습니다. AMD만이이를 문서화하고 컴파일러는이를 노출하지 않습니다.)
(예, 이러한 명령어는 모두 동일한 실행 단위에서 실행 됩니다.)
이 종속성은 단일 루프 반복에서 popcnt 유지하는 것이 아닙니다. 루프 반복을 수행 할 수 있으므로 프로세서가 다른 루프 반복을 병렬화 할 수 없습니다.
unsigned vs. uint64_t 및 기타 조정은 문제에 직접적인 영향을주지 않습니다. 그러나 그들은 레지스터를 변수에 할당하는 레지스터 할당 자에 영향을 미칩니다.
귀하의 경우 속도는 레지스터 할당자가 수행하기로 결정한 것에 따라 (거짓) 종속성 체인에 붙어있는 직접적인 결과입니다.
popcnt/ s에는 체인이 있습니다 : popcnt-add-popcnt-popcnt→ 다음 반복- 15GB / s에는 체인이 있습니다 :
popcntaddpopcntadd→ 다음 반복 - 20GB / s에는 체인이 있습니다 :
popcnt-popcnt→ 다음 반복 popcnt/ s에는 체인이 있습니다 : popcnt-popcnt→ 다음 반복
20GB / s와 26GB / s의 차이는 간접 주소 지정의 사소한 아티팩트 인 것 같습니다. 어느 쪽이든 프로세서는이 속도에 도달하면 다른 병목 현상을 일으키기 시작합니다.
이를 테스트하기 위해 인라인 어셈블리를 사용하여 컴파일러를 우회하고 원하는 어셈블리를 정확하게 얻었습니다. 또한 count 변수를 분할하여 벤치 마크를 망칠 수있는 다른 모든 종속성을 깨뜨 렸습니다.
결과는 다음과 같습니다.
Sandy Bridge Xeon @ 3.5GHz : (전체 테스트 코드는 하단에서 찾을 수 있음)
- GCC 4.6.3 :
g++ popcnt.cpp -std=c++0x -O3 -save-temps -march=native - Ubuntu 12
다른 레지스터 : 18.6195GB / s
.L4:
movq (%rbx,%rax,8), %r8
movq 8(%rbx,%rax,8), %r9
movq 16(%rbx,%rax,8), %r10
movq 24(%rbx,%rax,8), %r11
addq $4, %rax
popcnt %r8, %r8
add %r8, %rdx
popcnt %r9, %r9
add %r9, %rcx
popcnt %r10, %r10
add %r10, %rdi
popcnt %r11, %r11
add %r11, %rsi
cmpq $131072, %rax
jne .L4동일한 레지스터 : 8.49272 GB / s
.L9:
movq (%rbx,%rdx,8), %r9
movq 8(%rbx,%rdx,8), %r10
movq 16(%rbx,%rdx,8), %r11
movq 24(%rbx,%rdx,8), %rbp
addq $4, %rdx
# This time reuse "rax" for all the popcnts.
popcnt %r9, %rax
add %rax, %rcx
popcnt %r10, %rax
add %rax, %rsi
popcnt %r11, %rax
add %rax, %r8
popcnt %rbp, %rax
add %rax, %rdi
cmpq $131072, %rdx
jne .L9끊어진 체인이있는 동일한 레지스터 : 17.8869 GB / s
.L14:
movq (%rbx,%rdx,8), %r9
movq 8(%rbx,%rdx,8), %r10
movq 16(%rbx,%rdx,8), %r11
movq 24(%rbx,%rdx,8), %rbp
addq $4, %rdx
# Reuse "rax" for all the popcnts.
xor %rax, %rax # Break the cross-iteration dependency by zeroing "rax".
popcnt %r9, %rax
add %rax, %rcx
popcnt %r10, %rax
add %rax, %rsi
popcnt %r11, %rax
add %rax, %r8
popcnt %rbp, %rax
add %rax, %rdi
cmpq $131072, %rdx
jne .L14그렇다면 컴파일러에 무슨 문제가 있습니까?
popcnt 가 그러한 잘못된 종속성을 가지고 있다는 것을 인식하지 못하는 것 같습니다. 그럼에도 불구하고 이러한 잘못된 종속성은 드문 일이 아닙니다. 컴파일러가 인식하는지 여부는 단지 문제입니다.
popcnt 는 정확히 가장 많이 사용되는 명령어가 아닙니다. 따라서 주요 컴파일러가 이와 같은 것을 놓칠 수 있다는 것은 놀라운 일이 아닙니다. 또한이 문제를 언급하는 문서는 어디에도없는 것으로 보입니다. 인텔이 공개하지 않으면 누군가 우연히 발견 할 때까지 아무도 알 수 없습니다.
( 업데이트 : 버전 4.9.2 부터 GCC는 이러한 잘못된 종속성을 인식하고 최적화가 활성화 될 때이를 보상하기위한 코드를 생성합니다. Clang, MSVC 및 인텔 자체 ICC를 포함한 다른 공급 업체의 주요 컴파일러는 아직이를 인식하지 못합니다. 이 마이크로 아키텍처 정오표는이를 보완하는 코드를 생성하지 않습니다.)
CPU에 잘못된 종속성이있는 이유는 무엇입니까?
우리는 추측 할 수는 같은 실행 장치에서 실행 bsf / bsr 출력 의존성을해야합니까. ( POPCNT는 하드웨어에서 어떻게 구현됩니까? ). 이러한 지침에 대해 인텔은 input = 0에 대한 정수 결과를 "정의되지 않음"(ZF = 1 사용)으로 문서화하지만 인텔 하드웨어는 실제로 오래된 소프트웨어가 손상되지 않도록 더 강력한 보증을 제공합니다. 수정되지 않은 출력입니다. AMD는이 동작을 문서화합니다.
아마도이 실행 단위에 대해 일부 uop을 출력에 의존하도록 만드는 것은 다소 불편했을 것입니다.
AMD 프로세서에는 이러한 잘못된 종속성이없는 것으로 보입니다.
전체 테스트 코드는 다음과 같습니다.
#include <iostream>
#include <chrono>
#include <x86intrin.h>
int main(int argc, char* argv[]) {
using namespace std;
uint64_t size=1<<20;
uint64_t* buffer = new uint64_t[size/8];
char* charbuffer=reinterpret_cast<char*>(buffer);
for (unsigned i=0;i<size;++i) charbuffer[i]=rand()%256;
uint64_t count,duration;
chrono::time_point<chrono::system_clock> startP,endP;
{
uint64_t c0 = 0;
uint64_t c1 = 0;
uint64_t c2 = 0;
uint64_t c3 = 0;
startP = chrono::system_clock::now();
for( unsigned k = 0; k < 10000; k++){
for (uint64_t i=0;i<size/8;i+=4) {
uint64_t r0 = buffer[i + 0];
uint64_t r1 = buffer[i + 1];
uint64_t r2 = buffer[i + 2];
uint64_t r3 = buffer[i + 3];
__asm__(
"popcnt %4, %4 \n\t"
"add %4, %0 \n\t"
"popcnt %5, %5 \n\t"
"add %5, %1 \n\t"
"popcnt %6, %6 \n\t"
"add %6, %2 \n\t"
"popcnt %7, %7 \n\t"
"add %7, %3 \n\t"
: "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
: "r" (r0), "r" (r1), "r" (r2), "r" (r3)
);
}
}
count = c0 + c1 + c2 + c3;
endP = chrono::system_clock::now();
duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
cout << "No Chain\t" << count << '\t' << (duration/1.0E9) << " sec \t"
<< (10000.0*size)/(duration) << " GB/s" << endl;
}
{
uint64_t c0 = 0;
uint64_t c1 = 0;
uint64_t c2 = 0;
uint64_t c3 = 0;
startP = chrono::system_clock::now();
for( unsigned k = 0; k < 10000; k++){
for (uint64_t i=0;i<size/8;i+=4) {
uint64_t r0 = buffer[i + 0];
uint64_t r1 = buffer[i + 1];
uint64_t r2 = buffer[i + 2];
uint64_t r3 = buffer[i + 3];
__asm__(
"popcnt %4, %%rax \n\t"
"add %%rax, %0 \n\t"
"popcnt %5, %%rax \n\t"
"add %%rax, %1 \n\t"
"popcnt %6, %%rax \n\t"
"add %%rax, %2 \n\t"
"popcnt %7, %%rax \n\t"
"add %%rax, %3 \n\t"
: "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
: "r" (r0), "r" (r1), "r" (r2), "r" (r3)
: "rax"
);
}
}
count = c0 + c1 + c2 + c3;
endP = chrono::system_clock::now();
duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
cout << "Chain 4 \t" << count << '\t' << (duration/1.0E9) << " sec \t"
<< (10000.0*size)/(duration) << " GB/s" << endl;
}
{
uint64_t c0 = 0;
uint64_t c1 = 0;
uint64_t c2 = 0;
uint64_t c3 = 0;
startP = chrono::system_clock::now();
for( unsigned k = 0; k < 10000; k++){
for (uint64_t i=0;i<size/8;i+=4) {
uint64_t r0 = buffer[i + 0];
uint64_t r1 = buffer[i + 1];
uint64_t r2 = buffer[i + 2];
uint64_t r3 = buffer[i + 3];
__asm__(
"xor %%rax, %%rax \n\t" // <--- Break the chain.
"popcnt %4, %%rax \n\t"
"add %%rax, %0 \n\t"
"popcnt %5, %%rax \n\t"
"add %%rax, %1 \n\t"
"popcnt %6, %%rax \n\t"
"add %%rax, %2 \n\t"
"popcnt %7, %%rax \n\t"
"add %%rax, %3 \n\t"
: "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
: "r" (r0), "r" (r1), "r" (r2), "r" (r3)
: "rax"
);
}
}
count = c0 + c1 + c2 + c3;
endP = chrono::system_clock::now();
duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
cout << "Broken Chain\t" << count << '\t' << (duration/1.0E9) << " sec \t"
<< (10000.0*size)/(duration) << " GB/s" << endl;
}
free(charbuffer);
}똑같이 흥미로운 벤치 마크는 http://pastebin.com/kbzgL8si에서 찾을 수 있습니다.
이 벤치 마크는 (거짓) 종속성 체인에있는 popcnt
False Chain 0: 41959360000 0.57748 sec 18.1578 GB/s
False Chain 1: 41959360000 0.585398 sec 17.9122 GB/s
False Chain 2: 41959360000 0.645483 sec 16.2448 GB/s
False Chain 3: 41959360000 0.929718 sec 11.2784 GB/s
False Chain 4: 41959360000 1.23572 sec 8.48557 GB/s출처 : https://stackoverflow.com/questions/25078285/replacing-a-32-bit-loop-counter-with-64-bit-introduces-crazy-performance-deviati
'프로그래밍 언어 > C++' 카테고리의 다른 글
| C ++에서 다른 생성자 (생성자 체인)에서 생성자를 호출 하는 방법 (0) | 2021.07.07 |
|---|---|
| 이 프로그램이 세 개의 C ++ 컴파일러에서 잘못 거부 된 이유 (0) | 2021.07.07 |
| POSIX를 사용하여 C ++에서 명령을 실행하고 명령의 출력을 얻는 방법 (0) | 2021.07.06 |
| new를 사용하여 C ++에서 2차원 배열을 선언하는 방법 (0) | 2021.07.06 |
| __name__ == “__main__”: 하면 어떻게 될까? (0) | 2021.07.02 |