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 번 풀어 봤지만 성능 차이가 여전히 높다는 것입니다. 따라서 언 롤하더라도 주요 성능 편차로 여전히 공격을받을 수 있습니다. 꽤 흥미로운.