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를 10,000 번 수행합니다. 우리는 popcount의 시간을 측정합니다. 대문자 인 경우 내부 루프 변수는 unsigned이고, 소문자 인 경우 내부 루프 변수는 uint64_t입니다. 나는 이것이 아무런 차이가 없어야한다고 생각했지만 그 반대의 경우입니다.
(절대적으로 미친) 결과
나는 이것을 다음과 같이 컴파일한다 (g ++ 버전 : Ubuntu 4.8.2-19ubuntu1) :
g++ -O3 -march=native -std=c++11 test.cpp -o test다음은 3.50GHz에서 실행중인 Haswell Core i7-4770K CPU 의 결과입니다 test 1(따라서 1MB의 임의 데이터).
- 부호없는 41959360000 0.401554 초 26.113 GB / s
- uint64_t 41959360000 0.759822 초 13.8003 GB / 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.3267 GB / s
- uint64_t 41959360000 0.680954 초 15.3986 GB / s
따라서 거의 같은 결과이며 여전히 이상합니다. 그러나 이제는 매우 이상해집니다. 입력에서 읽은 버퍼 크기를 constant로 1바꾸므로 다음과 같이 변경합니다.
uint64_t size = atol(argv[1]) << 20;에
uint64_t size = 1 << 20;따라서 컴파일러는 이제 컴파일 타임에 버퍼 크기를 알고 있습니다. 아마도 최적화를 추가 할 수 있습니다! 다음은 숫자입니다 g++.
- 부호없는 41959360000 0.509156 초 20.5944 GB / s
- uint64_t 41959360000 0.508673 초 20.6139 GB / s
이제 두 버전 모두 똑같이 빠릅니다. 그러나, unsigned 더 느려 ! 그것으로부터 떨어 26에 20 GB/s따라서 (A)에 일정한 값의 리드가 일정하지 않은 대체 deoptimization . 진지하게, 나는 여기서 무슨 일이 일어나고 있는지 전혀 모른다! 그러나 이제 clang++새 버전으로 :
- 부호없는 41959360000 0.677009 초 15.4884 GB / s
- uint64_t 41959360000 0.676909 초 15.4906 GB / s
무엇을 기다립니다? 이제 두 버전 모두 15GB / s 의 느린 수로 떨어졌습니다 . 따라서 상수가 아닌 상수를 바꾸면 Clang의 두 경우 모두 코드가 느려질 수 있습니다 !
Ivy Bridge CPU를 사용 하는 동료에게 벤치 마크를 컴파일 하도록 요청했습니다 . 그는 비슷한 결과를 얻었으므로 Haswell이 아닌 것 같습니다. 두 개의 컴파일러가 여기에서 이상한 결과를 생성하기 때문에 컴파일러 버그가 아닌 것 같습니다. 여기에는 AMD CPU가 없으므로 인텔에서만 테스트 할 수 있습니다.
더 많은 광기, 제발!
첫 번째 예제 (로 된 예제)를 가져 와서 변수 앞에 atol(argv[1])a static를 넣으십시오 .
static uint64_t size=atol(argv[1])<<20;다음은 g ++의 결과입니다.
- 부호없는 41959360000 0.396728 초 26.4306 GB / s
- uint64_t 41959360000 0.509484 초 20.5811 GB / s
예, 또 다른 대안 입니다. 우리는 여전히 26GB / s의 빠른 속도를 유지 u32하지만 u64최소한 13GB / s에서 20GB / s 버전으로 업그레이드했습니다! 동료의 PC에서 u64버전이 버전보다 훨씬 빨라져서 u32가장 빠른 결과를 얻었습니다. 슬프게도이 기능은에만 효과가 있으며 g++, clang++신경 쓰지 않는 것 같습니다 static.
내 질문
이 결과를 설명 할 수 있습니까? 특히:
- 어떻게 간의 이러한 차이가있을 수 있습니다
u32와u64? - 불변 상수를 일정한 버퍼 크기로 바꾸면 어떻게 최적의 코드가 트리거 되지 않습니까?
static키워드를 삽입 하면u64루프가 더 빨라집니다. 동료 컴퓨터의 원래 코드보다 훨씬 빠릅니다!
나는 최적화가 까다로운 영역이라는 것을 알고 있지만 그런 작은 변화로 인해 실행 시간 이 100 % 차이 를 낼 수 있으며 일정한 버퍼 크기와 같은 작은 요소가 다시 결과를 완전히 혼합 할 수 있다고 생각하지 않았습니다 . 물론, 나는 항상 26GB / s를 차지할 수있는 버전을 원합니다. 내가 생각할 수있는 유일한 확실한 방법은이 경우에 어셈블리를 복사하여 붙여 넣고 인라인 어셈블리를 사용하는 것입니다. 이것은 작은 변화에 화를 낸 것처럼 보이는 컴파일러를 제거 할 수있는 유일한 방법입니다. 어떻게 생각해? 대부분의 성능으로 코드를 안정적으로 얻는 다른 방법이 있습니까?
분해
다양한 결과에 대한 분해는 다음과 같습니다.
g ++ / u32 / non-const bufsize의 26GB / s 버전 :
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 0x400af8
g ++ / u64 / non-const bufsize의 13GB / s 버전 :
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 0x400c00
clang ++ / u64 / non-const bufsize 의 15GB / s 버전 :
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 0x400e50
g ++ / u32 & u64 / const bufsize 의 20GB / s 버전 :
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 0x400a68
clang ++ / u32 & u64 / const bufsize 의 15GB / s 버전 :
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 % 차이를 만들 수 있습니다 ! staticsize 변수 앞에 키워드를 삽입하면 버퍼의 스토리지 유형조차도 큰 차이를 만들 수 있습니다 ! 앞으로 시스템 성능에 중요한 빡빡하고 핫한 루프를 작성할 때 다양한 컴파일러에서 다양한 대안을 테스트 할 것입니다.
흥미로운 점은 이미 루프를 네 번 풀었지만 성능 차이가 여전히 높다는 것입니다. 따라서 롤을 풀더라도 주요 성능 편차로 인해 여전히 타격을받을 수 있습니다. 꽤 흥미로운.
답변
Culprit : False Data Dependency (컴파일러도 인식하지 못함)
Sandy / Ivy Bridge 및 Haswell 프로세서에서 다음 명령을 수행하십시오.
popcnt src, dest대상 레지스터에 대한 종속성이 잘못된 것으로 보입니다 dest. 명령은 명령에만 쓰지만 dest실행 전에 준비가 될 때까지 기다립니다 . 이 잘못된 종속성은 Intel에서 정오표 HSD146 (Haswell) 및 SKL029 (Skylake) 로 문서화했습니다.
Skylake가 lzcnt및에 대해이 문제를 해결했습니다tzcnt .
캐논 레이크 (및 아이스 레이크)가이 문제를 해결했습니다 popcnt.
bsf/ bsr실제 출력 종속성이 있습니다 : input = 0에 대해 수정되지 않은 출력. (그러나 내장 함수를 사용하는 방법 은 없습니다. AMD 문서 만 해당하며 컴파일러는이를 공개하지 않습니다.)
(예, 이러한 명령어는 모두 동일한 실행 단위에서 실행됩니다 ).
이 의존성은 popcnt단일 루프 반복에서 4 초를 유지하지 않습니다 . 루프 반복을 수행 할 수 있으므로 프로세서가 다른 루프 반복을 병렬화 할 수 없습니다.
unsigned대 uint64_t및 기타 비틀기 직접 문제에 영향을 미치지 않습니다. 그러나 레지스터를 변수에 할당하는 레지스터 할당 자에 영향을줍니다.
귀하의 경우, 속도는 레지스터 할당자가 수행하기로 결정한 것에 따라 (거짓) 종속성 체인에 붙어있는 것의 직접적인 결과입니다.
- 13기가바이트 / s는 체인을 가지고 :
popcnt–add–popcnt–popcnt→ 다음 반복 - 15기가바이트 / s는 체인을 가지고 :
popcnt–add–popcnt–add→ 다음 반복 - 20GB / s에는 체인이 있습니다
popcnt.-popcnt→ 다음 반복 - 26GB / s에는 체인이 있습니다
popcnt.-popcnt→ 다음 반복
20GB / s와 26GB / s의 차이는 간접 주소 지정의 사소한 것으로 보입니다. 어느 쪽이든,이 속도에 도달하면 프로세서가 다른 병목 현상을 시작합니다.
이것을 테스트하기 위해 인라인 어셈블리를 사용하여 컴파일러를 무시하고 원하는 어셈블리를 정확하게 얻었습니다. 또한 count변수를 분할 하여 벤치 마크에 혼란을 줄 수있는 다른 모든 종속성을 해제했습니다.
결과는 다음과 같습니다.
Sandy Bridge Xeon @ 3.5 GHz : (전체 테스트 코드는 하단에 있습니다)
- GCC 4.6.3 :
g++ popcnt.cpp -std=c++0x -O3 -save-temps -march=native - 우분투 12
다른 레지스터 : 18.6195 GB / 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
그렇다면 컴파일러에 어떤 문제가 있습니까?
GCC 나 Visual Studio 모두 popcnt그러한 잘못된 종속성 이 있음을 인식하지 못하는 것 같습니다 . 그럼에도 불구하고 이러한 잘못된 의존성은 드문 일이 아닙니다. 컴파일러가 인식하고 있는지 여부는 문제입니다.
popcnt정확히 가장 많이 사용되는 명령은 아닙니다. 따라서 주요 컴파일러가 이와 같은 것을 놓칠 수 있다는 것은 놀라운 일이 아닙니다. 이 문제를 언급 한 문서는 어디에도 없습니다. 인텔이 공개하지 않으면 누군가 외부에 우연히 들어 오기 전까지는 아무도 외부에서 알 수 없습니다.
( 업데이트 : 버전 4.9.2 부터 GCC는 이러한 잘못된 종속성을 인식하고 최적화가 활성화 될 때이를 보상하는 코드를 생성합니다. Clang, MSVC 및 인텔 자체 ICC를 포함한 다른 공급 업체의 주요 컴파일러는 아직 인식하지 못하고 있습니다. 이 미세 아키텍처 정오표는이를 보완하는 코드를 생성하지 않습니다.)
CPU가 왜 이러한 잘못된 종속성을 가지고 있습니까?
우리는 추측 할 수는 같은 실행 장치에서 실행 bsf/ 수행 출력 의존성을 가지고있다. ( 하드웨어에서 POPCNT는 어떻게 구현됩니까? ). 이러한 지침에 대해 인텔은 input = 0의 정수 결과를 “정의되지 않은”(ZF = 1)로 기록하지만 인텔 하드웨어는 실제로 오래된 소프트웨어 (출력 수정되지 않은)를 깨뜨리지 않도록 더 강력하게 보장합니다. AMD는 이러한 행동을 기록합니다.bsr
아마도이 실행 장치에 대한 일부 uops를 출력에 의존하게 만드는 것은 다소 불편했지만 다른 것은 그렇지 않았습니다.
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
답변
실험을 위해 동등한 C 프로그램을 코딩 했으며이 이상한 행동을 확인할 수 있습니다. 또한 gcc가 64 비트 uint를 사용하기 때문에 64 gcc비트 정수 (아마도 어쩌면 size_t…)가 더 좋을 것이라고 생각합니다 uint_fast32_t.
어셈블리와 관련하여 약간의 문제
가 발생했습니다. 32 비트 버전을 가져 와서 모든 32 비트 명령 / 레지스터를 프로그램의 내부 popcount-loop에서 64 비트 버전으로 바꾸십시오. 관찰 : 코드는 32 비트 버전만큼 빠릅니다!
프로그램의 다른 부분이 여전히 32 비트 버전을 사용하기 때문에 변수의 크기가 실제로 64 비트가 아니기 때문에 이것은 분명히 해킹입니다. 그러나 내부 popcount-loop가 성능을 지배하는 한 좋은 시작입니다. .
그런 다음 32 비트 버전의 프로그램에서 내부 루프 코드를 복사하여 64 비트 버전으로 해킹했으며 64 비트 버전의 내부 루프를 대체하기 위해 레지스터로 조정했습니다. 이 코드는 32 비트 버전만큼 빠르게 실행됩니다.
내 결론은 이것이 32 비트 명령어의 실제 속도 / 대기 시간 이점이 아니라 컴파일러의 잘못된 명령어 스케줄링이라는 것입니다.
(주의 : 나는 어셈블리를 해킹했다.
답변
이것은 대답이 아니지만 결과를 주석에 넣으면 읽기가 어렵습니다.
Mac Pro ( Westmere 6-Cores Xeon 3.33 GHz)로 이러한 결과를 얻습니다 . 나는 그것을 컴파일했다 clang -O3 -msse4 -lstdc++ a.cpp -o a(-O2는 같은 결과를 얻는다).
씨름하다 uint64_t size=atol(argv[1])<<20;
unsigned 41950110000 0.811198 sec 12.9263 GB/s
uint64_t 41950110000 0.622884 sec 16.8342 GB/s
씨름하다 uint64_t size=1<<20;
unsigned 41950110000 0.623406 sec 16.8201 GB/s
uint64_t 41950110000 0.623685 sec 16.8126 GB/s
나는 또한 시도했다 :
- 테스트 순서를 반대로하면 결과는 동일하므로 캐시 팩터를 배제합니다.
- 이
for역으로 문을 :for (uint64_t i=size/8;i>0;i-=4). 이것은 동일한 결과를 제공하며 컴파일이 예상대로 반복마다 8 씩 크기를 나눌 수 없을 정도로 똑똑하다는 것을 증명합니다.
여기 내 거친 추측이 있습니다.
속도 계수는 세 부분으로 나뉩니다.
-
코드 캐시 :
uint64_t버전의 코드 크기는 크지 만 Xeon CPU에는 영향을 미치지 않습니다. 이로 인해 64 비트 버전이 느려집니다. -
사용 된 지침. 루프 수뿐만 아니라 두 버전에서 32 비트 및 64 비트 인덱스로 버퍼에 액세스합니다. 64 비트 오프셋으로 포인터에 액세스하면 전용 64 비트 레지스터 및 주소 지정이 필요하지만 32 비트 오프셋에 즉시 사용할 수 있습니다. 이로 인해 32 비트 버전이 더 빨라질 수 있습니다.
-
명령어는 64 비트 컴파일 (즉, 프리 페치)에서만 생성됩니다. 이를 통해 64 비트가 더 빨라집니다.
이 세 가지 요소는 서로 상충되는 결과와 일치합니다.
답변
나는 정답을 줄 수는 없지만 가능한 원인에 대한 개요를 제공합니다. 이 참조 는 루프 본문의 명령어에 대해 대기 시간과 처리량 사이에 3 : 1의 비율이 있음을 분명히 보여줍니다. 또한 다중 디스패치의 효과를 보여줍니다. 최신 x86 프로세서에는 3 개의 정수 단위가 제공되므로 일반적으로주기 당 3 개의 명령어를 디스패치 할 수 있습니다.
따라서 최대 파이프 라인과 여러 디스패치 성능과 이러한 메커니즘의 실패 사이에 성능의 요소는 6 배입니다. x86 명령어 세트의 복잡성으로 인해 기발한 파손이 발생하기 쉽다는 것은 잘 알려져 있습니다. 위의 문서는 훌륭한 예입니다.
64 비트 오른쪽 시프트에 대한 Pentium 4 성능은 실제로 열악합니다. 64 비트 왼쪽 시프트 및 모든 32 비트 시프트는 허용 가능한 성능을 갖습니다. ALU의 상위 32 비트에서 하위 32 비트로의 데이터 경로가 제대로 설계되지 않은 것 같습니다.
나는 개인적으로 핫 루프가 4 코어 칩의 특정 코어에서 느리게 실행되는 이상한 경우에 부딪쳤다. 실제로 코어를 끄면 맵 감소 계산에서 성능이 향상되었습니다.
여기에 정수 단위에 대한 경합이 있습니다. popcnt, 루프 카운터 및 주소 계산은 32 비트 너비 카운터에서 최대 속도로 거의 실행될 수 없지만 64 비트 카운터는 경합 및 파이프 라인 중단을 유발합니다. 루프 바디 실행 당 여러 디스패치가있는 총 12 개의 사이클, 잠재적으로 4 개의 사이클 만 있기 때문에 단일 스톨은 실행 시간에 2의 영향을 줄 수 있습니다.
정적 변수를 사용하여 유도 된 변경 사항은 명령의 약간의 재정렬을 유발한다고 추측합니다 .32 비트 코드가 경합의 전환점에 있다는 또 다른 단서입니다.
나는이 엄격한 분석 아니라는 것을 알고 있지만, 그것은 이다 그럴듯한 설명.
답변
Visual Studio 2013 Express 에서 색인 대신 포인터를 사용하여 시도해 보았습니다.이 색인은 프로세스를 약간 가속화했습니다. 주소 지정이 offset + register + (register << 3) 대신 offset + register이기 때문에 이것이 의심됩니다. C ++ 코드.
uint64_t* bfrend = buffer+(size/8);
uint64_t* bfrptr;
// ...
{
startP = chrono::system_clock::now();
count = 0;
for (unsigned k = 0; k < 10000; k++){
// Tight unrolled loop with uint64_t
for (bfrptr = buffer; bfrptr < bfrend;){
count += __popcnt64(*bfrptr++);
count += __popcnt64(*bfrptr++);
count += __popcnt64(*bfrptr++);
count += __popcnt64(*bfrptr++);
}
}
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;
}어셈블리 코드 : r10 = bfrptr, r15 = bfrend, rsi = count, rdi = buffer, r13 = k :
$LL5@main:
mov r10, rdi
cmp rdi, r15
jae SHORT $LN4@main
npad 4
$LL2@main:
mov rax, QWORD PTR [r10+24]
mov rcx, QWORD PTR [r10+16]
mov r8, QWORD PTR [r10+8]
mov r9, QWORD PTR [r10]
popcnt rdx, rax
popcnt rax, rcx
add rdx, rax
popcnt rax, r8
add r10, 32
add rdx, rax
popcnt rax, r9
add rsi, rax
add rsi, rdx
cmp r10, r15
jb SHORT $LL2@main
$LN4@main:
dec r13
jne SHORT $LL5@main답변
-funroll-loops -fprefetch-loop-arraysGCC로 전달해 보셨습니까 ?
이러한 추가 최적화로 다음과 같은 결과를 얻습니다.
[1829] /tmp/so_25078285 $ cat /proc/cpuinfo |grep CPU|head -n1
model name : Intel(R) Core(TM) i3-3225 CPU @ 3.30GHz
[1829] /tmp/so_25078285 $ g++ --version|head -n1
g++ (Ubuntu/Linaro 4.7.3-1ubuntu1) 4.7.3
[1829] /tmp/so_25078285 $ g++ -O3 -march=native -std=c++11 test.cpp -o test_o3
[1829] /tmp/so_25078285 $ g++ -O3 -march=native -funroll-loops -fprefetch-loop-arrays -std=c++11 test.cpp -o test_o3_unroll_loops__and__prefetch_loop_arrays
[1829] /tmp/so_25078285 $ ./test_o3 1
unsigned 41959360000 0.595 sec 17.6231 GB/s
uint64_t 41959360000 0.898626 sec 11.6687 GB/s
[1829] /tmp/so_25078285 $ ./test_o3_unroll_loops__and__prefetch_loop_arrays 1
unsigned 41959360000 0.618222 sec 16.9612 GB/s
uint64_t 41959360000 0.407304 sec 25.7443 GB/s답변
루프 밖으로 축소 단계를 이동해 보셨습니까? 지금은 실제로 필요하지 않은 데이터 종속성이 있습니다.
시험:
uint64_t subset_counts[4] = {};
for( unsigned k = 0; k < 10000; k++){
// Tight unrolled loop with unsigned
unsigned i=0;
while (i < size/8) {
subset_counts[0] += _mm_popcnt_u64(buffer[i]);
subset_counts[1] += _mm_popcnt_u64(buffer[i+1]);
subset_counts[2] += _mm_popcnt_u64(buffer[i+2]);
subset_counts[3] += _mm_popcnt_u64(buffer[i+3]);
i += 4;
}
}
count = subset_counts[0] + subset_counts[1] + subset_counts[2] + subset_counts[3];엄격한 앨리어싱 규칙을 준수하는지 확실하지 않은 이상한 앨리어싱도 진행 중입니다.