[C++] 32 비트 루프 카운트 변수를 64 비트로 대체하면 성능이 크게 저하됩니다.


Answers

실험 할만한 C 프로그램을 작성했는데, 이상한 행동을 확인할 수 있습니다. 게다가 gccuint_fast32_t 를 사용하면 gcc가 64 비트 단위를 사용하기 때문에 64 비트 정수 (아마도 size_t 어쨌든 ...이어야 함)가 더 좋다고 uint_fast32_t 있습니다.

나는 어셈블리로 주변을 조금 비웃었다.
간단히 32 비트 버전을 가져 와서 모든 32 비트 명령어 / 레지스터를 프로그램의 내부 popcount 루프에있는 64 비트 버전으로 대체하십시오. 관찰 : 코드는 32 비트 버전만큼 빠릅니다!

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

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

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

(경고 : 나는 어셈블리를 해킹하고,주의를 기울이지 않고 무언가를 망가 뜨릴 수 있었다. 나는 그렇게 생각하지 않는다.)

Question

나는 대량의 데이터를 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 를 읽는 크기 인 x 메가 바이트 인 임의의 데이터 버퍼를 만듭니다. 그런 다음 버퍼를 반복하고 x86 popcount 내장 버전을 사용하여 popcount를 수행합니다. 보다 정확한 결과를 얻으려면 10,000 번 팝콘을 사용하십시오. 우리는 팝 카운트의 시간을 측정합니다. 대문자에서 내부 루프 변수는 unsigneduint64_t , 소문자에서 내부 루프 변수는 uint64_t 입니다. 나는 이것이 별 차이가 없어야한다고 생각했지만 반대의 경우가 있습니다.

(절대적으로 미친) 결과

나는 이것을 이렇게 컴파일한다 (g ++ 버전 : 우분투 4.8.2-19ubuntu1).

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

다음은 test 1 (1MB의 랜덤 데이터)을 실행중인 Haswell Core i7-4770K CPU @ 3.50GHz의 결과입니다.

  • 서명되지 않은 41959360000 0.401554 초 26.113GB / 초
  • uint64_t 41959360000 0.759822 초 13.8003 GB / 초

보시다시피, uint64_t 버전의 처리량은 unsigned 버전의 절반입니다 ! 문제는 다른 어셈블리가 생성되지만 그 이유는 무엇입니까? 먼저 컴파일러 버그를 생각 했으므로 clang++ (우분투 Clang 버전 3.4-1ubuntu3)을 시도했습니다.

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

결과 : test 1

  • 서명되지 않은 41959360000 0.398293 초 26.3267GB / 초
  • uint64_t 41959360000 0.680954 초 15.3986GB / 초

따라서 거의 동일한 결과이며 여전히 이상합니다. 그러나 지금 그것은 매우 이상하게된다. 입력에서 읽은 버퍼 크기를 상수 1 바꿉니다. 그래서 바꿉니다.

uint64_t size = atol(argv[1]) << 20;

uint64_t size = 1 << 20;

따라서 컴파일러는 컴파일 타임에 버퍼 크기를 알 수 있습니다. 어쩌면 최적화를 추가 할 수 있습니다! 다음은 g++ 의 숫자입니다.

  • 서명되지 않은 41959360000 0.509156 초 20.5944 GB / 초
  • uint64_t 41959360000 0.508673 초 20.6139GB / 초

자, 두 버전 모두 똑같이 빠릅니다. 그러나, unsigned 도 더 천천히있어 ! 26 에서 20 GB/s 로 떨어짐으로써 비 상수 값을 일정 값으로 대체하면 비 최적 화가 발생 합니다. 진지하게, 나는 여기에 무슨 일이 일어나는지 전혀 모른다! 그러나 이제는 새로운 버전으로 clang++clang++ 하기 위해 :

  • 서명되지 않은 41959360000 0.677009 초 15.4884GB / 초
  • uint64_t 41959360000 0.676909 초 15.4906GB / 초

무엇을 기다립니다? 이제 두 버전 모두 15GB / s의 속도가 느려졌습니다 . 따라서 상수 값으로 비 상수를 대체하면 Clang의 경우 모두 느린 코드가됩니다.

나는 Ivy Bridge CPU로 동료에게 내 벤치 마크를 컴파일 해달라고 요청했다. 그는 비슷한 결과를 얻었으므로 Haswell이되지는 않습니다. 두 개의 컴파일러가 이상한 결과를 생성하기 때문에 컴파일러 버그가 아닌 것 같습니다. 여기에는 AMD CPU가 없으므로 인텔에서만 테스트 할 수 있습니다.

더 광기 야, 제발!

첫 번째 예제 ( atol(argv[1]) 있는 예제)를 가져 와서 변수 앞에 static 넣으십시오.

static uint64_t size=atol(argv[1])<<20;

g ++의 결과는 다음과 같습니다.

  • 서명되지 않은 41959360000 0.396728 초 26.4306GB / 초
  • uint64_t 41959360000 0.509484 초 20.5811GB / s

그래, 또 다른 대안 . 우리는 여전히 u32 와 함께 u64 / s의 빠른 속도를 가지고 있지만, 우리는 u64 / s에서 20GB / s 버전까지 u64 를 얻을 수 u64 ! 제 동료의 PC에서, u64 버전은 u32 버전보다 훨씬 빨라져서 가장 빠른 결과를 u64 . 안타깝게도, 이것은 g++ 에서만 작동하며, clang++static 에 대해서는 신경 쓰지 않습니다.

내 질문

이 결과를 설명해 주시겠습니까? 특히:

  • u32u64 의 차이점은 무엇입니까?
  • 정수가 아닌 정수를 상수 버퍼 크기로 대체하면 어떻게 최적의 코드를 트리거 할 수 있습니까?
  • static 키워드를 삽입하면 u64 루프가 더 빨리 수행됩니다. 동료 컴퓨터의 원본 코드보다 훨씬 빠릅니다!

나는 최적화가 까다로운 영역이라는 것을 알고 있지만, 그러한 작은 변화가 실행 시간의 100 % 차이 를 가져올 수 있다고 생각하지 못했습니다. 버퍼 크기와 같은 작은 요소는 결과를 완전히 혼합 할 수 있습니다. 물론, 저는 항상 26 GB / s를 팝콘 할 수있는 버전을 원합니다. 내가 신뢰할 수있는 유일한 방법은이 경우 어셈블리를 복사하여 붙여 넣고 인라인 어셈블리를 사용하는 것입니다. 이것은 내가 작은 변화에 화를내는 것처럼 보이는 컴파일러를 제거 할 수있는 유일한 방법이다. 어떻게 생각해? 대부분의 성능으로 코드를 안정적으로 얻을 수있는 또 다른 방법이 있습니까?

해체

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

g ++ / u32 / non-const 에서 26 GB / s 버전 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 0x400af8

g ++ / u64 / non-const 에서 13 GB / s 버전 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 0x400c00

clang 의 15 GB / s 버전 ++ / 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 0x400e50

g ++ / u32 및 u64 / const 에서 20 GB / s 버전 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 0x400a68

clang 의 15 GB / s 버전 ++ / 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

흥미롭게도 가장 빠른 (26 GB / s) 버전도 가장 오래되었습니다! 그것은 lea 를 사용하는 유일한 솔루션 인 것 같습니다. 어떤 버전은 점프하기 위해 jb 를 사용하고, 다른 버전은 점프를 사용합니다. 그러나 그것과는 별개로 모든 버전이 비교 될 수 있습니다. 100 % 성능 차이가 어디에서 유래했는지는 모르겠지만 어셈블리를 해독하는 데 너무 능숙하지 않습니다. 가장 느린 (13 GB / s) 버전도 매우 짧고 좋습니다. 아무도 이것을 설명 할 수 있습니까?

교훈

이 질문에 대한 답이 무엇이든간에; 나는 정말 뜨거운 루프에서 모든 세부 사항이 중요 할 수 있다는 것을 배웠습니다. 핫 코드와 관련이없는 세부 사항까지도 알 수 있습니다 . 루프 변수에 어떤 유형을 사용할 지 생각해 본 적이 없지만 이러한 사소한 변화가 100 % 차이를 만들 수 있음을 알 수 있습니다. 버퍼의 저장 유형조차도 크기 변수 앞에 static 키워드를 삽입하여 보았을 때 큰 차이를 만들 수 있습니다! 미래에는 필자가 시스템 성능에 결정적인 타이트하고 뜨거운 루프를 작성할 때 다양한 컴파일러에서 다양한 대안을 테스트 할 것입니다.

흥미로운 점은 이미 루프를 4 번 풀어 봤지만 성능 차이가 여전히 높다는 것입니다. 따라서 언 롤하더라도 주요 성능 편차로 여전히 공격을받을 수 있습니다. 꽤 흥미로운.




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 = 카운트, 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



저는 권위있는 대답을 줄 수는 없지만, 가능한 원인에 대한 개요를 제공합니다. 이 참고 자료 는 루프 본문의 명령어에 대해 대기 시간과 처리량간에 3 : 1 비율이 있음을 분명히 보여줍니다. 또한 다중 발송의 효과를 보여줍니다. 최신 x86 프로세서에는 3 개의 정수 단위가 있기 때문에 일반적으로 사이클 당 3 개의 명령어를 디스패치 할 수 있습니다.

피크 파이프 라인과 다중 디스패치 성능 및 이러한 메커니즘의 실패 사이에는 성능면에서 6 배가됩니다. x86 명령어 세트의 복잡성으로 인해 기발한 파손이 발생하기 쉽습니다. 위의 문서에는 훌륭한 예제가 있습니다.

64 비트 오른쪽 교대에 대한 Pentium 4 성능은 정말 좋지 않습니다. 64 비트 왼쪽 쉬프트뿐만 아니라 모든 32 비트 쉬프트도 만족스러운 성능을 제공합니다. ALU의 상위 32 비트에서 하위 32 비트까지의 데이터 경로가 잘 설계되지 않은 것처럼 보입니다.

개인적으로 핫 루프가 4 코어 칩 (AMD가 기억한다면)의 특정 코어에서 상당히 느리게 실행되는 이상한 경우가 발생했습니다. 이 코어를 끄면 map-reduce 계산에서 성능이 향상되었습니다.

여기에 내 추측은 정수 단위에 대한 논쟁입니다 : popcnt , 루프 카운터 및 주소 계산은 모두 32 비트 와이드 카운터로 전체 속도로 겨우 실행될 수 있지만 64 비트 카운터는 경쟁 및 파이프 라인 정지를 초래합니다. 루프 바디 실행 당 다중 디스패치로 인해 약 12 ​​사이클의 총 4 사이클이 가능하기 때문에 단일 실속은 2의 요인으로 실행 시간에 합리적으로 영향을 줄 수 있습니다.

필자가 추측하고있는 정적 변수를 사용하여 유도 된 변경 사항은 지침의 사소한 순서 변경을 야기하며 32 비트 코드가 경합을위한 일정한 시점에 있다는 또 다른 단서입니다.

나는 이것이 엄격한 분석이 아니라는 것을 안다. 그러나 그럴듯한 설명이다.




TL; DR : __builtin 내장 함수를 대신 사용하십시오.

gcc.godbolt.org에서 gcc 4.8.4 (및 g7.godbolt.org 에서조차 4.7.3)까지도 동일한 어셈블리 명령어를 사용하지만 false 종속성 버그가없는 __builtin_popcountll 을 사용하여 최적의 코드를 생성 할 수있었습니다.

나는 내 벤치마킹 코드를 100 % 확신하지는 못했지만, objdump 출력은 내 의견을 공유하는 것 같다. 난 다른 트릭을 ( ++ii++ ) 어떤 movl 명령 (이상한 행동, 나는 말을해야한다)없이 컴파일러 unroll 루프를 만들 수 있습니다.

결과 :

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:



Links