https://code.i-harness.com/ko-kr/q/17eaa0d


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

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

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

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

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

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


Question

optimizing software in c++

나는 대량의 데이터를 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 번 팝콘을 사용하십시오. 우리는 팝 카운트의 시간을 측정합니다. 대문자에서 내부 루프 변수는 unsigned 가 uint64_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 / s
  • 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 와 함께 26 GB / s의 빠른 속도를 가지고 있지만, 우리는 13 GB / s에서 20 GB / s 버전까지 u64 를 얻을 수 u64 ! 제 동료의 PC에서, u64 버전은 u32 버전보다 훨씬 빨라져서 가장 빠른 결과를 u64 . 안타깝게도, 이것은 g++ 에서만 작동하며, clang++ 은 static 에 대해서는 신경 쓰지 않습니다.

내 질문

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

  • u32 와 u64 의 차이점은 무엇입니까?
  • 어떻게 정수가 아닌 정수를 상수 버퍼 크기로 대체하면 최적화되지 않은 코드가 발생 합니까?
  • 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 를 사용하고, 다른 버전은 jne 사용합니다. 그러나 그것과는 별개로 모든 버전이 비교 될 수 있습니다. 100 % 성능 차이가 어디에서 유래했는지는 모르겠지만 어셈블리를 해독하는 데 너무 능숙하지 않습니다. 가장 느린 (13 GB / s) 버전도 매우 짧고 좋습니다. 아무도 이것을 설명 할 수 있습니까?

교훈

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

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




저는 권위있는 대답을 줄 수는 없지만, 가능한 원인에 대한 개요를 제공합니다. 이 참고 자료 는 루프 본문의 명령어에 대해 대기 시간과 처리량간에 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 비트 코드가 경합을위한 일정한 시점에 있다는 또 다른 단서입니다.

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




-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



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

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

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

결과 :

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: