etc./StackOverFlow

32비트 루프 카운터를 64비트로 교체하면 Intel CPU에서 _mm_popcnt_u64로 미친 성능 편차가 발생합니다.

청렴결백한 만능 재주꾼 2022. 2. 27. 12:39
반응형

질문자 :gexicide


대규모 데이터 배열 popcount 하는 가장 빠른 방법을 찾고 있었습니다. 나는 매우 이상한 효과를 uint64_t . 루프 변수를 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번 수행합니다. 우리는 popcount에 대한 시간을 측정합니다. 대문자의 경우 내부 루프 변수는 unsigned 이고 소문자의 경우 내부 루프 변수는 uint64_t 입니다. 나는 이것이 차이가 없어야한다고 생각했지만 반대의 경우입니다.

(완전히 미친) 결과

다음과 같이 컴파일합니다(g++ 버전: Ubuntu 4.8.2-19ubuntu1).

 g++ -O3 -march=native -std=c++11 test.cpp -o test

test 1 실행한 Haswell Core i7-4770K CPU @ 3.50GHz의 결과입니다(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 로 떨어졌습니다. 따라서 non-constant를 상수 값으로 바꾸면 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를 출력할 수 있는 버전을 갖고 싶습니다. 내가 생각할 수있는 유일한 신뢰할 수있는 방법은이 경우 어셈블리를 복사하여 붙여넣고 인라인 어셈블리를 사용하는 것입니다. 이것이 내가 작은 변경에 미친 것처럼 보이는 컴파일러를 제거할 수 있는 유일한 방법입니다. 어떻게 생각하나요? 가장 성능이 좋은 코드를 안정적으로 얻을 수 있는 다른 방법이 있습니까?

분해

다음은 다양한 결과에 대한 분해입니다.

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% 차이를 만들 수 있습니다! 버퍼의 저장 유형조차도 크기 변수 앞에 static 키워드를 삽입한 것과 같이 큰 차이를 만들 수 있습니다! 앞으로 시스템 성능에 결정적인 매우 빡빡하고 핫 루프를 작성할 때 다양한 컴파일러에서 다양한 대안을 항상 테스트할 것입니다.

흥미로운 점은 이미 루프를 네 번 풀었지만 성능 차이가 여전히 너무 높다는 것입니다. 따라서 출시하더라도 여전히 주요 성능 편차에 부딪힐 수 있습니다. 꽤 흥미로운.



범인: 잘못된 데이터 종속성 (컴파일러도 이를 인식하지 못함)

Sandy/Ivy Bridge 및 Haswell 프로세서에서 명령:

 popcnt src, dest

dest 에 대한 종속성이 잘못된 것으로 보입니다. 명령어가 쓰기만 해도 명령어는 실행 전에 dest 이 잘못된 종속성은 (현재) Intel에서 정오표 HSD146(Haswell) 및 SKL029(Skylake)로 문서화했습니다.

lzcnt 및 tzcnt 대해 이 문제를 수정했습니다 .
Cannon Lake(및 Ice Lake)는 popcnt 대해 이 문제를 수정했습니다.
bsf / bsr 에는 실제 출력 종속성이 있습니다. 입력=0에 대해 출력이 수정되지 않았습니다. (그러나 내장 기능을 사용하면 이를 활용할 방법이 없습니다. AMD만 이를 문서화하고 컴파일러는 이를 노출하지 않습니다.)

(예, 이러한 명령은 모두 동일한 실행 단위에서 실행됩니다 ).

이 종속성은 단일 루프 반복에서 popcnt 루프 반복에 걸쳐 수행될 수 있으므로 프로세서가 다른 루프 반복을 병렬화하는 것이 불가능합니다.

unsigned 대 uint64_t 및 기타 조정은 문제에 직접적인 영향을 미치지 않습니다. 그러나 레지스터를 변수에 할당하는 레지스터 할당자에 영향을 줍니다.

귀하의 경우 속도는 레지스터 할당자가 수행하기로 결정한 것에 따라 (거짓) 종속성 체인에 걸린 직접적인 결과입니다.

  • popcnt /s에는 다음과 같은 체인이 있습니다. popcnt - add - popcnt - popcnt → 다음 반복
  • 15GB/s에는 다음과 같은 체인이 있습니다. popcnt - add - popcnt - add → 다음 반복
  • 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
  • 우분투 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.49272GB/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.8869GB/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 및 Intel 자체 ICC를 포함한 다른 공급업체의 주요 컴파일러는 아직 이를 인식하지 못하고 있습니다. 이 마이크로아키텍처 정오표는 이를 보완하는 코드를 내보내지 않습니다.)

CPU에 왜 그런 잘못된 종속성이 있습니까?

우리는 추측 할 수는 같은 실행 장치에서 실행 bsf / bsr 출력 의존성을해야합니까. ( POPCNT는 하드웨어에서 어떻게 구현됩니까? ). 이러한 지침에 대해 Intel은 입력=0에 대한 정수 결과를 "정의되지 않음"(ZF=1 사용)으로 문서화하지만 Intel 하드웨어는 실제로 이전 소프트웨어가 손상되지 않도록 더 강력한 보증을 제공합니다. 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

Mysticial

실험을 위해 동등한 C 프로그램을 코딩했으며 이 이상한 동작을 확인할 수 있습니다. 무엇보다, gcc (아마해야 64 비트 정수 믿고 size_t 사용하는 등 어쨌든이 ...), 더 좋을 uint_fast32_t 64 비트 UINT를 사용하는 GCC됩니다.

나는 어셈블리로 약간의 장난을 쳤다.
32비트 버전을 사용하고 프로그램의 내부 팝카운트 루프에서 모든 32비트 명령어/레지스터를 64비트 버전으로 교체하기만 하면 됩니다. 관찰: 코드는 32비트 버전만큼 빠릅니다!

프로그램의 다른 부분이 여전히 32비트 버전을 사용하기 때문에 변수의 크기가 실제로 64비트가 아니기 때문에 이것은 분명히 해킹이지만 내부 팝카운트 루프가 성능을 지배하는 한 좋은 시작입니다. .

그런 다음 프로그램의 32비트 버전에서 내부 루프 코드를 복사하여 최대 64비트로 해킹하고 레지스터를 만지작거리며 64비트 버전의 내부 루프를 대체했습니다. 이 코드는 32비트 버전만큼 빠르게 실행됩니다.

내 결론은 이것이 32비트 명령어의 실제 속도/대기 시간 이점이 아니라 컴파일러에 의한 잘못된 명령어 스케줄링이라는 것입니다.

(주의 사항: 조립품을 해킹했는데, 눈치채지 못한 채 무언가를 깨뜨릴 수 있었습니다. 저는 그렇게 생각하지 않습니다.)


EOF

정답은 아니지만 댓글로 결과를 올리면 읽기가 힘듭니다.

Mac Pro ( Westmere 6-Cores Xeon 3.33GHz)에서 이러한 결과를 얻었습니다. clang -O3 -msse4 -lstdc++ a.cpp -oa (-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; clang;

 unsigned 41950110000 0.623406 sec 16.8201 GB/s uint64_t 41950110000 0.623685 sec 16.8126 GB/s

나는 또한 시도했다:

  1. 테스트 순서를 반대로 하면 결과가 동일하므로 캐시 요소를 배제합니다.
  2. 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비트를 더 빠르게 만듭니다.

세 가지 요인이 함께 상충되는 것처럼 보이는 결과와 일치합니다.


Non-maskable Interrupt

신뢰할 수 있는 답변을 드릴 수는 없지만 가능한 원인에 대한 개요를 제공합니다. 이 참조 는 루프 본문의 지침에 대해 대기 시간과 처리량 사이에 3:1 비율이 있음을 매우 명확하게 보여줍니다. 또한 다중 디스패치의 효과를 보여줍니다. 최신 x86 프로세서에는 3개의 정수 단위가 있기 때문에 일반적으로 주기당 3개의 명령어를 발송하는 것이 가능합니다.

따라서 피크 파이프라인과 다중 디스패치 성능과 이러한 메커니즘의 실패 사이에는 성능이 6배입니다. x86 명령어 세트의 복잡성으로 인해 기발한 파손이 발생하기가 매우 쉽다는 것은 잘 알려져 있습니다. 위의 문서에 좋은 예가 있습니다.

64비트 오른쪽 시프트에 대한 Pentium 4 성능은 정말 좋지 않습니다. 64비트 왼쪽 시프트와 모든 32비트 시프트는 허용 가능한 성능을 갖습니다. ALU의 상위 32비트에서 하위 32비트로의 데이터 경로가 제대로 설계되지 않은 것으로 보입니다.

개인적으로 핫 루프가 4코어 칩(기억하는 경우 AMD)의 특정 코어에서 상당히 느리게 실행되는 이상한 경우에 부딪쳤습니다. 우리는 실제로 해당 코어를 끄면 맵 축소 계산에서 더 나은 성능을 얻었습니다.

여기서 내 추측은 정수 단위에 대한 경합입니다. popcnt , 루프 카운터 및 주소 계산은 모두 32비트 너비 카운터를 사용하여 최대 속도로 간신히 실행할 수 있지만 64비트 카운터는 경합 및 파이프라인 중단을 유발합니다. 루프 본문 실행당 총 약 12개의 주기, 다중 디스패치의 잠재적인 4개의 주기가 있기 때문에 단일 지연이 실행 시간에 2배만큼 합리적으로 영향을 미칠 수 있습니다.

정적 변수를 사용하여 유도된 변경은 명령어의 약간의 재정렬을 유발하는 것으로 추측되며, 이는 32비트 코드가 경합의 전환점에 있다는 또 다른 단서입니다.

나는이 엄격한 분석 아니라는 것을 알고,하지만 그럴듯한 설명이다.


Gene

인덱스 대신 포인터를 사용하여 Visual Studio 2013 Express 에서 이 작업을 시도했는데 프로세스 속도가 조금 빨라졌습니다. 주소 지정이 오프셋 + 레지스터 + (register<<3) 대신 오프셋 + 레지스터이기 때문이라고 생각합니다. 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 = 개수, rdi = 버퍼, 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

rcgldr

-funroll-loops -fprefetch-loop-arrays 를 GCC에 전달해 보셨습니까?

이러한 추가 최적화를 통해 다음과 같은 결과를 얻습니다.

 [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

Dangelov

감소 단계를 루프 외부로 이동해 보셨습니까? 지금 당장은 실제로 필요하지 않은 데이터 종속성이 있습니다.

노력하다:

 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];

또한 이상한 앨리어싱이 진행 중입니다. 엄격한 앨리어싱 규칙을 준수하는지 확실하지 않습니다.


Ben Voigt

TL;DR: __builtin 내장 함수를 사용하세요. 도움이 될 수 있습니다.

나는 gcc 4.8.4(그리고 gcc.godbolt.org의 4.7.3까지)가 동일한 어셈블리 명령어를 사용하는 __builtin_popcountll 잘못된 종속성 버그로 인해 예기치 않게 긴 루프 전달 종속성.

내 벤치마킹 코드에 대해 100% 확신할 수는 없지만 objdump 출력은 내 견해를 공유하는 것 같습니다. 다른 트릭( ++i vs i++ )을 사용하여 컴파일러가 movl 명령 없이 루프를 풀도록 합니다(이상한 동작, 말해야 함).

결과:

 Count: 20318230000 Elapsed: 0.411156 seconds Speed: 25.503118 GB/s

벤치마킹 코드:

 #include <stdint.h> #include <stddef.h> #include <time.h> #include <stdio.h> #include <stdlib.h> uint64_t builtin_popcnt(const uint64_t* buf, size_t len){ uint64_t cnt = 0; for(size_t i = 0; i < len; ++i){ cnt += __builtin_popcountll(buf[i]); } return cnt; } int main(int argc, char** argv){ if(argc != 2){ printf("Usage: %s <buffer size in MB>\n", argv[0]); return -1; } uint64_t size = atol(argv[1]) << 20; uint64_t* buffer = (uint64_t*)malloc((size/8)*sizeof(*buffer)); // Spoil copy-on-write memory allocation on *nix for (size_t i = 0; i < (size / 8); i++) { buffer[i] = random(); } uint64_t count = 0; clock_t tic = clock(); for(size_t i = 0; i < 10000; ++i){ count += builtin_popcnt(buffer, size/8); } clock_t toc = clock(); printf("Count: %lu\tElapsed: %f seconds\tSpeed: %f GB/s\n", count, (double)(toc - tic) / CLOCKS_PER_SEC, ((10000.0*size)/(((double)(toc - tic)*1e+9) / CLOCKS_PER_SEC))); return 0; }

컴파일 옵션:

 gcc --std=gnu99 -mpopcnt -O3 -funroll-loops -march=native bench.c -o bench

GCC 버전:

 gcc (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4

리눅스 커널 버전:

 3.19.0-58-generic

CPU 정보:

 processor : 0 vendor_id : GenuineIntel cpu family : 6 model : 70 model name : Intel(R) Core(TM) i7-4870HQ CPU @ 2.50 GHz stepping : 1 microcode : 0xf cpu MHz : 2494.226 cache size : 6144 KB physical id : 0 siblings : 1 core id : 0 cpu cores : 1 apicid : 0 initial apicid : 0 fpu : yes fpu_exception : yes cpuid level : 13 wp : yes flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ss ht syscall nx rdtscp lm constant_tsc nopl xtopology nonstop_tsc eagerfpu pni pclmulqdq ssse3 fma cx16 pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand hypervisor lahf_lm abm arat pln pts dtherm fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 invpcid xsaveopt bugs : bogomips : 4988.45 clflush size : 64 cache_alignment : 64 address sizes : 36 bits physical, 48 bits virtual power management:

assp1r1n3

이것은 답변이 아니라 2021년의 소수의 컴파일러에 대한 피드백입니다. Intel CoffeeLake 9900k에서.

Microsoft 컴파일러(VS2019), 도구 세트 v142:

 unsigned 209695540000 1.8322 sec 28.6152 GB/s uint64_t 209695540000 3.08764 sec 16.9802 GB/s

인텔 컴파일러 2021:

 unsigned 209695540000 1.70845 sec 30.688 GB/s uint64_t 209695540000 1.57956 sec 33.1921 GB/s

Mysticial의 답변에 따르면 Intel 컴파일러는 False Data Dependency를 인식하지만 Microsoft 컴파일러는 인식하지 못합니다.

인텔 컴파일러의 경우 /QxHost (호스트의 CPU 아키텍처 최적화) /Oi (내재 기능 활성화) 및 #include <nmmintrin.h> 대신 #include <immintrin.h> .

전체 컴파일 명령: /GS /W3 /QxHost /Gy /Zi /O2 /D "NDEBUG" /D "_CONSOLE" /D "_UNICODE" /D "UNICODE" /Qipo /Zc:forScope /Oi /MD /Fa"x64\Release\" /EHsc /nologo /Fo"x64\Release\" //fprofile-instr-use "x64\Release\" /Fp"x64\Release\Benchmark.pch" .

ICC에서 디컴파일된(IDA 7.5에 의한) 어셈블리:

 int __cdecl main(int argc, const char **argv, const char **envp) { int v6; // er13 _BYTE *v8; // rsi unsigned int v9; // edi unsigned __int64 i; // rbx unsigned __int64 v11; // rdi int v12; // ebp __int64 v13; // r14 __int64 v14; // rbx unsigned int v15; // eax unsigned __int64 v16; // rcx unsigned int v17; // eax unsigned __int64 v18; // rcx __int64 v19; // rdx unsigned int v20; // eax int result; // eax std::ostream *v23; // rbx char v24; // dl std::ostream *v33; // rbx std::ostream *v41; // rbx __int64 v42; // rdx unsigned int v43; // eax int v44; // ebp __int64 v45; // r14 __int64 v46; // rbx unsigned __int64 v47; // rax unsigned __int64 v48; // rax std::ostream *v50; // rdi char v51; // dl std::ostream *v58; // rdi std::ostream *v60; // rdi __int64 v61; // rdx unsigned int v62; // eax __asm { vmovdqa [rsp+98h+var_58], xmm8 vmovapd [rsp+98h+var_68], xmm7 vmovapd [rsp+98h+var_78], xmm6 } if ( argc == 2 ) { v6 = atol(argv[1]) << 20; _R15 = v6; v8 = operator new[](v6); if ( v6 ) { v9 = 1; for ( i = 0i64; i < v6; i = v9++ ) v8[i] = rand(); } v11 = (unsigned __int64)v6 >> 3; v12 = 0; v13 = Xtime_get_ticks_0(); v14 = 0i64; do { if ( v6 ) { v15 = 4; v16 = 0i64; do { v14 += __popcnt(*(_QWORD *)&v8[8 * v16]) + __popcnt(*(_QWORD *)&v8[8 * v15 - 24]) + __popcnt(*(_QWORD *)&v8[8 * v15 - 16]) + __popcnt(*(_QWORD *)&v8[8 * v15 - 8]); v16 = v15; v15 += 4; } while ( v11 > v16 ); v17 = 4; v18 = 0i64; do { v14 += __popcnt(*(_QWORD *)&v8[8 * v18]) + __popcnt(*(_QWORD *)&v8[8 * v17 - 24]) + __popcnt(*(_QWORD *)&v8[8 * v17 - 16]) + __popcnt(*(_QWORD *)&v8[8 * v17 - 8]); v18 = v17; v17 += 4; } while ( v11 > v18 ); } v12 += 2; } while ( v12 != 10000 ); _RBP = 100 * (Xtime_get_ticks_0() - v13); std::operator___std::char_traits_char___(std::cout, "unsigned\t"); v23 = (std::ostream *)std::ostream::operator<<(std::cout, v14); std::operator___std::char_traits_char____0(v23, v24); __asm { vmovq xmm0, rbp vmovdqa xmm8, cs:__xmm@00000000000000004530000043300000 vpunpckldq xmm0, xmm0, xmm8 vmovapd xmm7, cs:__xmm@45300000000000004330000000000000 vsubpd xmm0, xmm0, xmm7 vpermilpd xmm1, xmm0, 1 vaddsd xmm6, xmm1, xmm0 vdivsd xmm1, xmm6, cs:__real@41cdcd6500000000 } v33 = (std::ostream *)std::ostream::operator<<(v23); std::operator___std::char_traits_char___(v33, " sec \t"); __asm { vmovq xmm0, r15 vpunpckldq xmm0, xmm0, xmm8 vsubpd xmm0, xmm0, xmm7 vpermilpd xmm1, xmm0, 1 vaddsd xmm0, xmm1, xmm0 vmulsd xmm7, xmm0, cs:__real@40c3880000000000 vdivsd xmm1, xmm7, xmm6 } v41 = (std::ostream *)std::ostream::operator<<(v33); std::operator___std::char_traits_char___(v41, " GB/s"); LOBYTE(v42) = 10; v43 = std::ios::widen((char *)v41 + *(int *)(*(_QWORD *)v41 + 4i64), v42); std::ostream::put(v41, v43); std::ostream::flush(v41); v44 = 0; v45 = Xtime_get_ticks_0(); v46 = 0i64; do { if ( v6 ) { v47 = 0i64; do { v46 += __popcnt(*(_QWORD *)&v8[8 * v47]) + __popcnt(*(_QWORD *)&v8[8 * v47 + 8]) + __popcnt(*(_QWORD *)&v8[8 * v47 + 16]) + __popcnt(*(_QWORD *)&v8[8 * v47 + 24]); v47 += 4i64; } while ( v47 < v11 ); v48 = 0i64; do { v46 += __popcnt(*(_QWORD *)&v8[8 * v48]) + __popcnt(*(_QWORD *)&v8[8 * v48 + 8]) + __popcnt(*(_QWORD *)&v8[8 * v48 + 16]) + __popcnt(*(_QWORD *)&v8[8 * v48 + 24]); v48 += 4i64; } while ( v48 < v11 ); } v44 += 2; } while ( v44 != 10000 ); _RBP = 100 * (Xtime_get_ticks_0() - v45); std::operator___std::char_traits_char___(std::cout, "uint64_t\t"); v50 = (std::ostream *)std::ostream::operator<<(std::cout, v46); std::operator___std::char_traits_char____0(v50, v51); __asm { vmovq xmm0, rbp vpunpckldq xmm0, xmm0, cs:__xmm@00000000000000004530000043300000 vsubpd xmm0, xmm0, cs:__xmm@45300000000000004330000000000000 vpermilpd xmm1, xmm0, 1 vaddsd xmm6, xmm1, xmm0 vdivsd xmm1, xmm6, cs:__real@41cdcd6500000000 } v58 = (std::ostream *)std::ostream::operator<<(v50); std::operator___std::char_traits_char___(v58, " sec \t"); __asm { vdivsd xmm1, xmm7, xmm6 } v60 = (std::ostream *)std::ostream::operator<<(v58); std::operator___std::char_traits_char___(v60, " GB/s"); LOBYTE(v61) = 10; v62 = std::ios::widen((char *)v60 + *(int *)(*(_QWORD *)v60 + 4i64), v61); std::ostream::put(v60, v62); std::ostream::flush(v60); free(v8); result = 0; } else { std::operator___std::char_traits_char___(std::cerr, "usage: array_size in MB"); LOBYTE(v19) = 10; v20 = std::ios::widen((char *)&std::cerr + *((int *)std::cerr + 1), v19); std::ostream::put(std::cerr, v20); std::ostream::flush(std::cerr); result = -1; } __asm { vmovaps xmm6, [rsp+98h+var_78] vmovaps xmm7, [rsp+98h+var_68] vmovaps xmm8, [rsp+98h+var_58] } return result; }

그리고 메인 분해:

 .text:0140001000 .686p .text:0140001000 .mmx .text:0140001000 .model flat .text:0140001000 .text:0140001000 ; =========================================================================== .text:0140001000 .text:0140001000 ; Segment type: Pure code .text:0140001000 ; Segment permissions: Read/Execute .text:0140001000 _text segment para public 'CODE' use64 .text:0140001000 assume cs:_text .text:0140001000 ;org 140001000h .text:0140001000 assume es:nothing, ss:nothing, ds:_data, fs:nothing, gs:nothing .text:0140001000 .text:0140001000 ; =============== SUBROUTINE ======================================= .text:0140001000 .text:0140001000 .text:0140001000 ; int __cdecl main(int argc, const char **argv, const char **envp) .text:0140001000 main proc near ; CODE XREF: __scrt_common_main_seh+107↓p .text:0140001000 ; DATA XREF: .pdata:ExceptionDir↓o .text:0140001000 .text:0140001000 var_78 = xmmword ptr -78h .text:0140001000 var_68 = xmmword ptr -68h .text:0140001000 var_58 = xmmword ptr -58h .text:0140001000 .text:0140001000 push r15 .text:0140001002 push r14 .text:0140001004 push r13 .text:0140001006 push r12 .text:0140001008 push rsi .text:0140001009 push rdi .text:014000100A push rbp .text:014000100B push rbx .text:014000100C sub rsp, 58h .text:0140001010 vmovdqa [rsp+98h+var_58], xmm8 .text:0140001016 vmovapd [rsp+98h+var_68], xmm7 .text:014000101C vmovapd [rsp+98h+var_78], xmm6 .text:0140001022 cmp ecx, 2 .text:0140001025 jnz loc_14000113E .text:014000102B mov rcx, [rdx+8] ; String .text:014000102F call cs:__imp_atol .text:0140001035 mov r13d, eax .text:0140001038 shl r13d, 14h .text:014000103C movsxd r15, r13d .text:014000103F mov rcx, r15 ; size .text:0140001042 call ??_U@YAPEAX_K@Z ; operator new[](unsigned __int64) .text:0140001047 mov rsi, rax .text:014000104A test r15d, r15d .text:014000104D jz short loc_14000106E .text:014000104F mov edi, 1 .text:0140001054 xor ebx, ebx .text:0140001056 mov rbp, cs:__imp_rand .text:014000105D nop dword ptr [rax] .text:0140001060 .text:0140001060 loc_140001060: ; CODE XREF: main+6C↓j .text:0140001060 call rbp ; __imp_rand .text:0140001062 mov [rsi+rbx], al .text:0140001065 mov ebx, edi .text:0140001067 inc edi .text:0140001069 cmp rbx, r15 .text:014000106C jb short loc_140001060 .text:014000106E .text:014000106E loc_14000106E: ; CODE XREF: main+4D↑j .text:014000106E mov rdi, r15 .text:0140001071 shr rdi, 3 .text:0140001075 xor ebp, ebp .text:0140001077 call _Xtime_get_ticks_0 .text:014000107C mov r14, rax .text:014000107F xor ebx, ebx .text:0140001081 jmp short loc_14000109F .text:0140001081 ; --------------------------------------------------------------------------- .text:0140001083 align 10h .text:0140001090 .text:0140001090 loc_140001090: ; CODE XREF: main+A2↓j .text:0140001090 ; main+EC↓j ... .text:0140001090 add ebp, 2 .text:0140001093 cmp ebp, 2710h .text:0140001099 jz loc_140001184 .text:014000109F .text:014000109F loc_14000109F: ; CODE XREF: main+81↑j .text:014000109F test r13d, r13d .text:01400010A2 jz short loc_140001090 .text:01400010A4 mov eax, 4 .text:01400010A9 xor ecx, ecx .text:01400010AB nop dword ptr [rax+rax+00h] .text:01400010B0 .text:01400010B0 loc_1400010B0: ; CODE XREF: main+E7↓j .text:01400010B0 popcnt rcx, qword ptr [rsi+rcx*8] .text:01400010B6 add rcx, rbx .text:01400010B9 lea edx, [rax-3] .text:01400010BC popcnt rdx, qword ptr [rsi+rdx*8] .text:01400010C2 add rdx, rcx .text:01400010C5 lea ecx, [rax-2] .text:01400010C8 popcnt rcx, qword ptr [rsi+rcx*8] .text:01400010CE add rcx, rdx .text:01400010D1 lea edx, [rax-1] .text:01400010D4 xor ebx, ebx .text:01400010D6 popcnt rbx, qword ptr [rsi+rdx*8] .text:01400010DC add rbx, rcx .text:01400010DF mov ecx, eax .text:01400010E1 add eax, 4 .text:01400010E4 cmp rdi, rcx .text:01400010E7 ja short loc_1400010B0 .text:01400010E9 test r13d, r13d .text:01400010EC jz short loc_140001090 .text:01400010EE mov eax, 4 .text:01400010F3 xor ecx, ecx .text:01400010F5 db 2Eh .text:01400010F5 nop word ptr [rax+rax+00000000h] .text:01400010FF nop .text:0140001100 .text:0140001100 loc_140001100: ; CODE XREF: main+137↓j .text:0140001100 popcnt rcx, qword ptr [rsi+rcx*8] .text:0140001106 add rcx, rbx .text:0140001109 lea edx, [rax-3] .text:014000110C popcnt rdx, qword ptr [rsi+rdx*8] .text:0140001112 add rdx, rcx .text:0140001115 lea ecx, [rax-2] .text:0140001118 popcnt rcx, qword ptr [rsi+rcx*8] .text:014000111E add rcx, rdx .text:0140001121 lea edx, [rax-1] .text:0140001124 xor ebx, ebx .text:0140001126 popcnt rbx, qword ptr [rsi+rdx*8] .text:014000112C add rbx, rcx .text:014000112F mov ecx, eax .text:0140001131 add eax, 4 .text:0140001134 cmp rdi, rcx .text:0140001137 ja short loc_140001100 .text:0140001139 jmp loc_140001090 .text:014000113E ; --------------------------------------------------------------------------- .text:014000113E .text:014000113E loc_14000113E: ; CODE XREF: main+25↑j .text:014000113E mov rsi, cs:__imp_?cerr@std@@3V?$basic_ostream@DU?$char_traits@D@std@@@1@A ; std::ostream std::cerr .text:0140001145 lea rdx, aUsageArraySize ; "usage: array_size in MB" .text:014000114C mov rcx, rsi ; std::ostream * .text:014000114F call std__operator___std__char_traits_char___ .text:0140001154 mov rax, [rsi] .text:0140001157 movsxd rcx, dword ptr [rax+4] .text:014000115B add rcx, rsi .text:014000115E mov dl, 0Ah .text:0140001160 call cs:__imp_?widen@?$basic_ios@DU?$char_traits@D@std@@@std@@QEBADD@Z ; std::ios::widen(char) .text:0140001166 mov rcx, rsi .text:0140001169 mov edx, eax .text:014000116B call cs:__imp_?put@?$basic_ostream@DU?$char_traits@D@std@@@std@@QEAAAEAV12@D@Z ; std::ostream::put(char) .text:0140001171 mov rcx, rsi .text:0140001174 call cs:__imp_?flush@?$basic_ostream@DU?$char_traits@D@std@@@std@@QEAAAEAV12@XZ ; std::ostream::flush(void) .text:014000117A mov eax, 0FFFFFFFFh .text:014000117F jmp loc_1400013E2 .text:0140001184 ; --------------------------------------------------------------------------- .text:0140001184 .text:0140001184 loc_140001184: ; CODE XREF: main+99↑j .text:0140001184 call _Xtime_get_ticks_0 .text:0140001189 sub rax, r14 .text:014000118C imul rbp, rax, 64h ; 'd' .text:0140001190 mov r14, cs:__imp_?cout@std@@3V?$basic_ostream@DU?$char_traits@D@std@@@1@A ; std::ostream std::cout .text:0140001197 lea rdx, aUnsigned ; "unsigned\t" .text:014000119E mov rcx, r14 ; std::ostream * .text:01400011A1 call std__operator___std__char_traits_char___ .text:01400011A6 mov rcx, r14 .text:01400011A9 mov rdx, rbx .text:01400011AC call cs:__imp_??6?$basic_ostream@DU?$char_traits@D@std@@@std@@QEAAAEAV01@_K@Z ; std::ostream::operator<<(unsigned __int64) .text:01400011B2 mov rbx, rax .text:01400011B5 mov rcx, rax ; std::ostream * .text:01400011B8 call std__operator___std__char_traits_char____0 .text:01400011BD vmovq xmm0, rbp .text:01400011C2 vmovdqa xmm8, cs:__xmm@00000000000000004530000043300000 .text:01400011CA vpunpckldq xmm0, xmm0, xmm8 .text:01400011CF vmovapd xmm7, cs:__xmm@45300000000000004330000000000000 .text:01400011D7 vsubpd xmm0, xmm0, xmm7 .text:01400011DB vpermilpd xmm1, xmm0, 1 .text:01400011E1 vaddsd xmm6, xmm1, xmm0 .text:01400011E5 vdivsd xmm1, xmm6, cs:__real@41cdcd6500000000 .text:01400011ED mov r12, cs:__imp_??6?$basic_ostream@DU?$char_traits@D@std@@@std@@QEAAAEAV01@N@Z ; std::ostream::operator<<(double) .text:01400011F4 mov rcx, rbx .text:01400011F7 call r12 ; std::ostream::operator<<(double) ; std::ostream::operator<<(double) .text:01400011FA mov rbx, rax .text:01400011FD lea rdx, aSec ; " sec \t" .text:0140001204 mov rcx, rax ; std::ostream * .text:0140001207 call std__operator___std__char_traits_char___ .text:014000120C vmovq xmm0, r15 .text:0140001211 vpunpckldq xmm0, xmm0, xmm8 .text:0140001216 vsubpd xmm0, xmm0, xmm7 .text:014000121A vpermilpd xmm1, xmm0, 1 .text:0140001220 vaddsd xmm0, xmm1, xmm0 .text:0140001224 vmulsd xmm7, xmm0, cs:__real@40c3880000000000 .text:014000122C vdivsd xmm1, xmm7, xmm6 .text:0140001230 mov rcx, rbx .text:0140001233 call r12 ; std::ostream::operator<<(double) ; std::ostream::operator<<(double) .text:0140001236 mov rbx, rax .text:0140001239 lea rdx, aGbS ; " GB/s" .text:0140001240 mov rcx, rax ; std::ostream * .text:0140001243 call std__operator___std__char_traits_char___ .text:0140001248 mov rax, [rbx] .text:014000124B movsxd rcx, dword ptr [rax+4] .text:014000124F add rcx, rbx .text:0140001252 mov dl, 0Ah .text:0140001254 call cs:__imp_?widen@?$basic_ios@DU?$char_traits@D@std@@@std@@QEBADD@Z ; std::ios::widen(char) .text:014000125A mov rcx, rbx .text:014000125D mov edx, eax .text:014000125F call cs:__imp_?put@?$basic_ostream@DU?$char_traits@D@std@@@std@@QEAAAEAV12@D@Z ; std::ostream::put(char) .text:0140001265 mov rcx, rbx .text:0140001268 call cs:__imp_?flush@?$basic_ostream@DU?$char_traits@D@std@@@std@@QEAAAEAV12@XZ ; std::ostream::flush(void) .text:014000126E xor ebp, ebp .text:0140001270 call _Xtime_get_ticks_0 .text:0140001275 mov r14, rax .text:0140001278 xor ebx, ebx .text:014000127A jmp short loc_14000128F .text:014000127A ; --------------------------------------------------------------------------- .text:014000127C align 20h .text:0140001280 .text:0140001280 loc_140001280: ; CODE XREF: main+292↓j .text:0140001280 ; main+2DB↓j ... .text:0140001280 add ebp, 2 .text:0140001283 cmp ebp, 2710h .text:0140001289 jz loc_14000131D .text:014000128F .text:014000128F loc_14000128F: ; CODE XREF: main+27A↑j .text:014000128F test r13d, r13d .text:0140001292 jz short loc_140001280 .text:0140001294 xor eax, eax .text:0140001296 db 2Eh .text:0140001296 nop word ptr [rax+rax+00000000h] .text:01400012A0 .text:01400012A0 loc_1400012A0: ; CODE XREF: main+2D6↓j .text:01400012A0 xor ecx, ecx .text:01400012A2 popcnt rcx, qword ptr [rsi+rax*8] .text:01400012A8 add rcx, rbx .text:01400012AB xor edx, edx .text:01400012AD popcnt rdx, qword ptr [rsi+rax*8+8] .text:01400012B4 add rdx, rcx .text:01400012B7 xor ecx, ecx .text:01400012B9 popcnt rcx, qword ptr [rsi+rax*8+10h] .text:01400012C0 add rcx, rdx .text:01400012C3 xor ebx, ebx .text:01400012C5 popcnt rbx, qword ptr [rsi+rax*8+18h] .text:01400012CC add rbx, rcx .text:01400012CF add rax, 4 .text:01400012D3 cmp rax, rdi .text:01400012D6 jb short loc_1400012A0 .text:01400012D8 test r13d, r13d .text:01400012DB jz short loc_140001280 .text:01400012DD xor eax, eax .text:01400012DF nop .text:01400012E0 .text:01400012E0 loc_1400012E0: ; CODE XREF: main+316↓j .text:01400012E0 xor ecx, ecx .text:01400012E2 popcnt rcx, qword ptr [rsi+rax*8] .text:01400012E8 add rcx, rbx .text:01400012EB xor edx, edx .text:01400012ED popcnt rdx, qword ptr [rsi+rax*8+8] .text:01400012F4 add rdx, rcx .text:01400012F7 xor ecx, ecx .text:01400012F9 popcnt rcx, qword ptr [rsi+rax*8+10h] .text:0140001300 add rcx, rdx .text:0140001303 xor ebx, ebx .text:0140001305 popcnt rbx, qword ptr [rsi+rax*8+18h] .text:014000130C add rbx, rcx .text:014000130F add rax, 4 .text:0140001313 cmp rax, rdi .text:0140001316 jb short loc_1400012E0 .text:0140001318 jmp loc_140001280 .text:014000131D ; --------------------------------------------------------------------------- .text:014000131D .text:014000131D loc_14000131D: ; CODE XREF: main+289↑j .text:014000131D call _Xtime_get_ticks_0 .text:0140001322 sub rax, r14 .text:0140001325 imul rbp, rax, 64h ; 'd' .text:0140001329 mov rdi, cs:__imp_?cout@std@@3V?$basic_ostream@DU?$char_traits@D@std@@@1@A ; std::ostream std::cout .text:0140001330 lea rdx, aUint64T ; "uint64_t\t" .text:0140001337 mov rcx, rdi ; std::ostream * .text:014000133A call std__operator___std__char_traits_char___ .text:014000133F mov rcx, rdi .text:0140001342 mov rdx, rbx .text:0140001345 call cs:__imp_??6?$basic_ostream@DU?$char_traits@D@std@@@std@@QEAAAEAV01@_K@Z ; std::ostream::operator<<(unsigned __int64) .text:014000134B mov rdi, rax .text:014000134E mov rcx, rax ; std::ostream * .text:0140001351 call std__operator___std__char_traits_char____0 .text:0140001356 vmovq xmm0, rbp .text:014000135B vpunpckldq xmm0, xmm0, cs:__xmm@00000000000000004530000043300000 .text:0140001363 vsubpd xmm0, xmm0, cs:__xmm@45300000000000004330000000000000 .text:014000136B vpermilpd xmm1, xmm0, 1 .text:0140001371 vaddsd xmm6, xmm1, xmm0 .text:0140001375 vdivsd xmm1, xmm6, cs:__real@41cdcd6500000000 .text:014000137D mov rcx, rdi .text:0140001380 call r12 ; std::ostream::operator<<(double) ; std::ostream::operator<<(double) .text:0140001383 mov rdi, rax .text:0140001386 lea rdx, aSec ; " sec \t" .text:014000138D mov rcx, rax ; std::ostream * .text:0140001390 call std__operator___std__char_traits_char___ .text:0140001395 vdivsd xmm1, xmm7, xmm6 .text:0140001399 mov rcx, rdi .text:014000139C call r12 ; std::ostream::operator<<(double) ; std::ostream::operator<<(double) .text:014000139F mov rdi, rax .text:01400013A2 lea rdx, aGbS ; " GB/s" .text:01400013A9 mov rcx, rax ; std::ostream * .text:01400013AC call std__operator___std__char_traits_char___ .text:01400013B1 mov rax, [rdi] .text:01400013B4 movsxd rcx, dword ptr [rax+4] .text:01400013B8 add rcx, rdi .text:01400013BB mov dl, 0Ah .text:01400013BD call cs:__imp_?widen@?$basic_ios@DU?$char_traits@D@std@@@std@@QEBADD@Z ; std::ios::widen(char) .text:01400013C3 mov rcx, rdi .text:01400013C6 mov edx, eax .text:01400013C8 call cs:__imp_?put@?$basic_ostream@DU?$char_traits@D@std@@@std@@QEAAAEAV12@D@Z ; std::ostream::put(char) .text:01400013CE mov rcx, rdi .text:01400013D1 call cs:__imp_?flush@?$basic_ostream@DU?$char_traits@D@std@@@std@@QEAAAEAV12@XZ ; std::ostream::flush(void) .text:01400013D7 mov rcx, rsi ; Block .text:01400013DA call cs:__imp_free .text:01400013E0 xor eax, eax .text:01400013E2 .text:01400013E2 loc_1400013E2: ; CODE XREF: main+17F↑j .text:01400013E2 vmovaps xmm6, [rsp+98h+var_78] .text:01400013E8 vmovaps xmm7, [rsp+98h+var_68] .text:01400013EE vmovaps xmm8, [rsp+98h+var_58] .text:01400013F4 add rsp, 58h .text:01400013F8 pop rbx .text:01400013F9 pop rbp .text:01400013FA pop rdi .text:01400013FB pop rsi .text:01400013FC pop r12 .text:01400013FE pop r13 .text:0140001400 pop r14 .text:0140001402 pop r15 .text:0140001404 retn .text:0140001404 main endp

Coffee Lake 사양 업데이트 "POPCNT 명령을 실행하는 데 예상보다 오래 걸릴 수 있습니다".


Soleil

우선 최고 성능을 추정해 보십시오. https://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf를 검토하십시오. , 특히 부록 C.

귀하의 경우 POPCNT 명령에 대기 시간 = 3 클럭 및 처리량 = 1 클럭이 있음을 보여주는 테이블 C-10입니다. 처리량은 클록 단위로 최대 속도를 보여줍니다(가능한 최상의 대역폭 수를 얻으려면 코어 주파수와 popcnt64의 경우 8바이트를 곱함).

이제 컴파일러가 수행한 작업을 검사하고 루프에 있는 다른 모든 명령어의 처리량을 요약합니다. 이것은 생성된 코드에 대한 최상의 추정치를 제공합니다.

마지막으로 루프의 명령 간의 데이터 종속성을 살펴보십시오. 처리량 대신 지연 시간이 많이 소요되므로 데이터 흐름 체인에서 단일 반복 명령을 분할하고 전체 지연 시간을 계산한 다음 순진하게 최대값을 선택합니다. 데이터 흐름 종속성을 고려하여 대략적인 추정치를 제공합니다.

그러나 귀하의 경우 올바른 방법으로 코드를 작성하면 이러한 모든 복잡성이 제거됩니다. 동일한 count 변수에 누적하는 대신 다른 변수(예: count0, count1, ... count8)에 누적하고 끝에 합산합니다. 또는 count[8]의 배열을 만들고 해당 요소에 누적할 수도 있습니다. 아마도 벡터화되어 훨씬 더 나은 처리량을 얻을 수 있습니다.

추신 및 1초 동안 벤치마크를 실행하지 마십시오. 먼저 코어를 워밍업한 다음 루프를 최소 10초 이상 100초 동안 실행하십시오. 그렇지 않으면 하드웨어에서 전원 관리 펌웨어 및 DVFS 구현을 테스트하게 됩니다. :)

PPS 벤치마크가 실제로 실행되어야 하는 시간에 대한 끝없는 토론을 들었습니다. 가장 똑똑한 사람들은 심지어 10초가 11초나 12초가 아니라 왜 10초인지 묻기도 합니다. 이론적으로는 이것이 재미있다는 것을 인정해야 합니다. 실제로는 벤치마크를 연속으로 백 번 실행하고 편차를 기록하기만 하면 됩니다. 재밌된다. 대부분의 사람들은 소스를 변경하고 그 후에 정확히 한 번 벤치를 실행하여 새로운 성능 기록을 캡처합니다. 옳은 일을 하십시오.

아직 확신이 서지 않습니까? assp1r1n3 ( https://stackoverflow.com/a/37026212/9706746 )의 벤치마크의 위의 C 버전을 사용하고 재시도 루프에서 10000 대신 100을 시도하십시오.

내 7960X는 RETRY=100을 보여줍니다.

개수: 203182300 경과: 0.008385초 속도: 12.505379GB/s

개수: 203182300 경과: 0.011063초 속도: 9.478225GB/s

개수: 203182300 경과: 0.011188초 속도: 9.372327GB/s

개수: 203182300 경과: 0.010393초 속도: 10.089252GB/s

개수: 203182300 경과: 0.009076초 속도: 11.553283GB/s

RETRY=10000:

개수: 20318230000 경과 시간: 0.661791초 속도: 15.844519GB/s

개수: 20318230000 경과: 0.665422초 속도: 15.758060GB/s

개수: 20318230000 경과 시간: 0.660983초 속도: 15.863888GB/s

개수: 20318230000 경과 시간: 0.665337초 속도: 15.760073GB/s

개수: 20318230000 경과: 0.662138초 속도: 15.836215GB/s

PPPS 마지막으로 "수락된 답변" 및 기타 미스터리에 대해 ;-)

assp1r1n3의 대답을 사용합시다. 그는 2.5Ghz 코어를 가지고 있습니다. POPCNT는 1개의 클럭을 처리하고 그의 코드는 64비트 popcnt를 사용하고 있습니다. 따라서 수학은 그의 설정에 대해 2.5Ghz * 1 클럭 * 8바이트 = 20GB/s입니다. 그는 25Gb/s를 보고 있는데, 이는 아마도 약 3Ghz로의 터보 부스트 때문일 것입니다.

따라서 ark.intel.com으로 이동하여 i7-4870HQ를 찾으십시오. https://ark.intel.com/products/83504/Intel-Core-i7-4870HQ-Processor-6M-Cache-up-to-3-70 -GHz-?q=i7-4870HQ

해당 코어는 최대 3.7Ghz까지 실행할 수 있으며 하드웨어의 경우 실제 최대 속도는 29.6GB/s입니다. 그렇다면 또 다른 4GB/s는 어디에 있습니까? 아마도 각 반복 내에서 루프 논리 및 기타 주변 코드에 소비되었을 것입니다.

이제 이 잘못된 종속성 은 어디에 있습니까? 하드웨어는 거의 최고 속도로 실행됩니다. 어쩌면 내 수학이 좋지 않을 수도 있습니다. 때때로 발생합니다. :)

PPPPPS 여전히 HW 정오표를 제안하는 사람들이 범인이므로 제안에 따라 인라인 asm 예제를 만들었습니다. 아래를 참조하십시오.

내 7960X에서 첫 번째 버전(cnt0에 대한 단일 출력 포함)은 11MB/s로 실행되고 두 번째 버전(cnt0, cnt1, cnt2 및 cnt3에 대한 출력 포함)은 33MB/s로 실행됩니다. 그리고 하나는 말할 수 있습니다 - 짜잔! 출력 의존성입니다.

좋아, 어쩌면 내가 말한 요점은 이와 같은 코드를 작성하는 것이 의미가 없으며 출력 종속성 문제가 아니라 멍청한 코드 생성이라는 것입니다. 우리는 하드웨어를 테스트하는 것이 아니라 최대 성능을 발휘할 수 있는 코드를 작성하고 있습니다. HW OOO가 이러한 "출력 종속성"의 이름을 바꾸고 숨길 것이라고 예상할 수 있지만, 젠장, 올바른 일을 올바르게 하면 어떤 신비에도 직면하지 않을 것입니다.

 uint64_t builtin_popcnt1a(const uint64_t* buf, size_t len) { uint64_t cnt0, cnt1, cnt2, cnt3; cnt0 = cnt1 = cnt2 = cnt3 = 0; uint64_t val = buf[0]; #if 0 __asm__ __volatile__ ( "1:\n\t" "popcnt %2, %1\n\t" "popcnt %2, %1\n\t" "popcnt %2, %1\n\t" "popcnt %2, %1\n\t" "subq $4, %0\n\t" "jnz 1b\n\t" : "+q" (len), "=q" (cnt0) : "q" (val) : ); #else __asm__ __volatile__ ( "1:\n\t" "popcnt %5, %1\n\t" "popcnt %5, %2\n\t" "popcnt %5, %3\n\t" "popcnt %5, %4\n\t" "subq $4, %0\n\t" "jnz 1b\n\t" : "+q" (len), "=q" (cnt0), "=q" (cnt1), "=q" (cnt2), "=q" (cnt3) : "q" (val) : ); #endif return cnt0; }

Kovalex

좋아, 나는 OP가 기존 질문에서 해결되지 않은 것으로 보이는 하위 질문 중 하나에 대한 작은 답변을 제공하고 싶습니다. 경고, 나는 테스트나 코드 생성 또는 분해를 하지 않았으며 다른 사람들이 설명할 수 있는 생각을 공유하고 싶었습니다.

static 이 성능을 변경하는 이유는 무엇입니까?

문제의 줄: uint64_t size = atol(argv[1])<<20;

짧은 답변

size 에 액세스하기 위해 생성된 어셈블리를 살펴보고 비정적 버전과 관련된 포인터 간접 참조의 추가 단계가 있는지 확인합니다.

긴 답변

static 선언 여부에 관계없이 변수의 복사본은 하나만 있고 크기가 변경되지 않기 때문에 차이점은 코드에서 변수가 사용되는 위치와 함께 변수를 백업하는 데 사용되는 메모리의 위치라는 이론입니다. 더 아래로.

자, 명백하게 시작하기 위해 함수의 모든 지역 변수(매개변수와 함께)에는 저장소로 사용하기 위해 스택에 공간이 제공된다는 것을 기억하십시오. 이제 분명히 main()의 스택 프레임은 정리되지 않고 한 번만 생성됩니다. 좋아, 그것을 static 만드는 것은 어떻습니까? 글쎄, 이 경우 컴파일러는 프로세스의 전역 데이터 공간에서 공간을 예약한다는 것을 알고 있으므로 스택 프레임을 제거하여 위치를 지울 수 없습니다. 하지만 여전히 위치가 하나뿐이므로 차이점은 무엇입니까? 스택의 메모리 위치가 참조되는 방식과 관련이 있다고 생각합니다.

컴파일러가 기호 테이블을 생성할 때 크기 등과 같은 관련 속성과 함께 레이블에 대한 항목을 만듭니다. 메모리에 적절한 공간을 예약해야 한다는 것을 알고 있지만 실제로는 나중에 어느 정도 그 위치를 선택하지 않습니다. 활성 분석을 수행한 후 처리하고 할당을 등록할 수 있습니다. 그러면 링커는 최종 어셈블리 코드에 대해 기계어에 제공할 주소를 어떻게 알 수 있습니까? 최종 위치를 알고 있거나 해당 위치에 도착하는 방법을 알고 있습니다. 스택을 사용하면 스택 프레임에 대한 포인터와 프레임에 대한 오프셋을 기반으로 한 위치를 참조하는 것이 매우 간단합니다. 이는 기본적으로 링커가 런타임 전에 스택 프레임의 위치를 알 수 없기 때문입니다.


Kelly S. French

출처 : http:www.stackoverflow.com/questions/25078285/replacing-a-32-bit-loop-counter-with-64-bit-introduces-crazy-performance-deviati

반응형

'etc. > StackOverFlow' 카테고리의 다른 글

Docker 컨테이너의 셸에 어떻게 들어가나요?  (0) 2022.02.27
C#에서 const와 readonly의 차이점은 무엇입니까?  (0) 2022.02.27
고방사성 환경에서 사용하기 위한 애플리케이션 컴파일  (0) 2022.02.27
두 목록을 사전으로 어떻게 변환합니까?  (0) 2022.02.24
jQuery를 사용하여 요소의 ID를 어떻게 얻을 수 있습니까?  (0) 2022.02.24

'etc./StackOverFlow'의 다른글

  • 현재글32비트 루프 카운터를 64비트로 교체하면 Intel CPU에서 _mm_popcnt_u64로 미친 성능 편차가 발생합니다.

관련글

댓글

티스토리툴바