프로그래밍 언어/C++

Collatz 추측을 테스트하기위한 C ++ 코드가 손으로 작성한 어셈블리보다 빠르게 실행되는 이유

Rateye 2021. 7. 23. 11:34
728x90
반응형
질문 : Collatz 추측을 테스트하기위한 C ++ 코드가 손으로 작성한 어셈블리보다 빠르게 실행되는 이유는 무엇입니까?

이 두 가지 솔루션을 Project Euler Q14 , 어셈블리 및 C ++로 작성했습니다. 그들은 Collatz 추측 을 테스트하기 위해 동일한 무차별 대입 접근 방식을 구현합니다. 조립 솔루션은 다음과 같이 조립되었습니다.

nasm -felf64 p14.asm && gcc p14.o -o p14

C ++는 다음과 같이 컴파일되었습니다.

g++ p14.cpp -o p14

어셈블리, p14.asm :

section .data
    fmt db "%d", 10, 0

global main
extern printf

section .text

main:
    mov rcx, 1000000
    xor rdi, rdi        ; max i
    xor rsi, rsi        ; i

l1:
    dec rcx
    xor r10, r10        ; count
    mov rax, rcx

l2:
    test rax, 1
    jpe even

    mov rbx, 3
    mul rbx
    inc rax
    jmp c1

even:
    mov rbx, 2
    xor rdx, rdx
    div rbx

c1:
    inc r10
    cmp rax, 1
    jne l2

    cmp rdi, r10
    cmovl rdi, r10
    cmovl rsi, rcx

    cmp rcx, 2
    jne l1

    mov rdi, fmt
    xor rax, rax
    call printf
    ret

C ++, p14.cpp :

#include <iostream>

int sequence(long n) {
    int count = 1;
    while (n != 1) {
        if (n % 2 == 0)
            n /= 2;
        else
            n = 3*n + 1;
        ++count;
    }
    return count;
}

int main() {
    int max = 0, maxi;
    for (int i = 999999; i > 0; --i) {
        int s = sequence(i);
        if (s > max) {
            max = s;
            maxi = i;
        }
    }
    std::cout << maxi << std::endl;
}

속도와 모든 것을 향상시키기위한 컴파일러 최적화에 대해 알고 있지만 어셈블리 솔루션을 더 최적화하는 방법은 많지 않습니다 (수학적이 아니라 프로그래밍 방식으로 말함).

C ++ 코드는 용어마다 모듈러스를 사용하고 다른 용어마다 나누기를 사용하는 반면 어셈블리 코드는 다른 용어마다 하나의 나누기 만 사용합니다.

그러나 어셈블리는 C ++ 솔루션보다 평균 1 초 더 오래 걸립니다. 왜 이런거야? 나는 주로 호기심에서 묻는다.

내 시스템 : 1.4GHz Intel Celeron 2955U (Haswell 마이크로 아키텍처)의 64 비트 Linux.

반응형
답변

64 비트 DIV 명령어가 2로 나누는 좋은 방법이라고 생각한다면 컴파일러의 asm 출력이 -O0 (빠른 컴파일, 추가 최적화 없음, 메모리에 저장 / 다시로드)을 사용해도 손으로 작성한 코드를 능가하는 것은 당연합니다. 디버거가 변수를 수정할 수 있도록 모든 C 문 전후).

효율적인 asm을 작성하는 방법을 배우려면 Agner Fog의 최적화 어셈블리 가이드 를 참조하십시오. 또한 특정 CPU에 대한 특정 세부 정보에 대한 지침 테이블과 마이크로 아키텍처 가이드도 있습니다. 더 많은 perf 링크 태그 위키를 참조하십시오.

손으로 작성한 asm으로 컴파일러를이기는 것에 대한 더 일반적인 질문을 참조하십시오. 인라인 어셈블리 언어가 네이티브 C ++ 코드보다 느립니까? . TL : DR : 네가 잘못하면 예 (이 질문처럼).

특히 효율적으로 컴파일 할 수있는 C ++를 작성하려는 경우 일반적으로 컴파일러가 작업을 수행하도록하는 것이 좋습니다. 또한 컴파일 된 언어보다 어셈블리가 더 빠릅니까? . 답변 중 하나는 다양한 C 컴파일러가 멋진 트릭으로 정말 간단한 함수를 최적화하는 방법을 보여주는 이 깔끔한 슬라이드에 대한 링크입니다. Matt Godbolt의 CppCon2017은“ 최근 내 컴파일러가 나를 위해 무엇을 했는가? Unbolting the Compiler 's Lid ”도 비슷한 맥락입니다.

even:
    mov rbx, 2
    xor rdx, rdx
    div rbx

Intel Haswell에서 div r64 는 36 uops이며 대기 시간은 32-96 사이클 이고 처리량은 21-74 사이클 당 1입니다. (RBX를 설정하고 RDX를 0으로 설정하는 데 2 개의 uop이 추가되지만 순서가 잘못된 실행은이를 조기에 실행할 수 있습니다.) DIV와 같은 높은 uop 카운트 명령어는 마이크로 코딩되어 프런트 엔드 병목 현상이 발생할 수도 있습니다. 이 경우 지연은 루프 전달 종속성 체인의 일부이기 때문에 가장 관련성이 높은 요소입니다.

shr rax, 1 은 동일한 unsigned division을 수행합니다. 1 uop이고 1c 지연 시간 이며 클럭주기 당 2 개를 실행할 수 있습니다.

비교를 위해 32 비트 분할이 더 빠르지 만 교대에 비해 여전히 끔찍합니다. idiv r32 는 Haswell에서 9 uops, 22-29c 지연 시간 및 8-11c 처리량 당 하나입니다.

-O0 asm 출력 ( Godbolt 컴파일러 탐색기 )에서 볼 수 있듯이 시프트 명령어 만 사용합니다 . clang -O0 은 64 비트 IDIV를 두 번 사용하더라도 생각대로 순진하게 컴파일됩니다. (최적화 할 때 컴파일러는 소스가 동일한 피연산자로 분할 및 모듈러스를 수행 할 때 IDIV의 출력을 모두 사용합니다 (IDIV를 전혀 사용하는 경우))

GCC에는 완전히 순진한 모드가 없습니다. 항상 GIMPLE을 통해 변환되므로 일부 "최적화"를 비활성화 할 수 없습니다 . 여기에는 상수로 나누기를 인식하고 시프트 (2의 거듭 제곱) 또는 고정 소수점 곱셈 역 (2의 거듭 제곱이 아님)을 사용하여 IDIV를 방지하는 div_by_13 됩니다 (위의 godbolt 링크에서 div_by_13 참조).

gcc -Os (크기 최적화) 는 2의 거듭 제곱이 아닌 나눗셈에 IDIV를 사용합니다.

컴파일러 지원

(이 경우 요약 : uint64_t n 사용)

우선, 최적화 된 컴파일러 출력을 보는 것이 흥미 롭습니다. ( -O3 ). -O0 속도는 기본적으로 의미가 없습니다.

asm 출력을보십시오 (Godbolt에서 또는 GCC / clang 어셈블리 출력에서 "노이즈"를 제거하는 방법? 참조 ). 컴파일러가 처음에 최적의 코드를 만들지 못하는 경우 : 컴파일러가 더 나은 코드를 만들도록 안내하는 방식으로 C / C ++ 소스를 작성하는 것이 일반적으로 가장 좋은 방법 입니다. asm을 알아야하고 무엇이 효율적인지 알아야하지만이 지식을 간접적으로 적용합니다. 컴파일러는 또한 좋은 아이디어 소스입니다. 때로는 clang이 멋진 일을 할 수 있으며 gcc를 손으로 잡고 같은 일을 할 수 있습니다. 이 답변 과 아래 @Veedrac의 코드에서 풀리지 않은 루프로 수행 한 작업을 참조하십시오.)

이 접근 방식은 이식 가능하며 20 년 후에는 미래의 일부 컴파일러가 새로운 ISA 확장 또는 자동 벡터화를 사용하여 향후 하드웨어 (x86 여부에 관계없이)에서 효율적인 것으로 컴파일 할 수 있습니다. 15 년 전 손으로 쓴 x86-64 asm은 일반적으로 Skylake에 맞게 최적으로 조정되지 않았습니다. 예를 들어 비교 및 분기 매크로 융합은 당시에는 존재하지 않았습니다. 하나의 마이크로 아키텍처에 대해 수작업으로 제작 된 asm에 현재 최적 인 것은 현재 및 미래의 다른 CPU에 최적이 아닐 수 있습니다. @johnfound의 답변에 대한 의견은 이 코드에 큰 영향을 미치는 AMD Bulldozer와 Intel Haswell의 주요 차이점에 대해 설명합니다. 그러나 이론적으로 g++ -O3 -march=bdver3 및 g++ -O3 -march=skylake 는 올바른 작업을 수행합니다. (또는 -march=native .) 또는 -mtune=... 은 다른 CPU가 지원하지 않을 수있는 명령을 사용하지 않고 조정합니다.

내 느낌은 현재 CPU에 적합한 asm으로 컴파일러를 안내하는 것이 향후 컴파일러에 문제가되지 않아야한다는 것입니다. 코드를 변환하는 방법을 찾는 데 현재 컴파일러보다 낫고 미래의 CPU에서 작동하는 방법을 찾을 수 있기를 바랍니다. 그럼에도 불구하고 미래의 x86은 아마도 현재 x86에서 좋은 것에 대해 끔찍하지 않을 것이며, 미래의 컴파일러는 C 소스에서 데이터 이동과 같은 것을 구현하는 동안 asm 관련 함정을 피할 것입니다.

손으로 쓴 asm은 옵티 마이저를위한 블랙 박스이므로 인라인이 입력을 컴파일 시간 상수로 만들 때 상수 전파가 작동하지 않습니다. 다른 최적화도 영향을받습니다. asm을 사용하기 전에 https://gcc.gnu.org/wiki/DontUseInlineAsm 을 읽으십시오. (그리고 MSVC 스타일의 인라인 asm을 피하십시오 : 입력 / 출력은 오버 헤드를 추가하는 메모리를 거쳐야합니다.)

이 경우 : n 은 서명 된 유형을 가지며 gcc는 올바른 반올림을 제공하는 SAR / SHR / ADD 시퀀스를 사용합니다. (음수 입력의 경우 IDIV 및 산술 시프트 "반올림"이 다릅니다. SAR insn set ref 수동 입력 참조 ). n 이 음수가 될 수 없음을 증명하려고 시도했지만 실패한 경우 IDK. 서명 된 오버플로는 정의되지 않은 동작이므로 가능해야합니다.)

uint64_t n 사용해야하므로 SHR 만 가능합니다. long 이 32 비트 (예 : x86-64 Windows) 인 시스템에 이식 할 수 있습니다.

BTW, gcc의 최적화 된 asm 출력은 꽤 좋아 보입니다 ( unsigned long n ) main() 으로 인라인되는 내부 루프는 다음을 수행합니다.

 # from gcc5.4 -O3  plus my comments

 # edx= count=1
 # rax= uint64_t n

.L9:                   # do{
    lea    rcx, [rax+1+rax*2]   # rcx = 3*n + 1
    mov    rdi, rax
    shr    rdi         # rdi = n>>1;
    test   al, 1       # set flags based on n%2 (aka n&1)
    mov    rax, rcx
    cmove  rax, rdi    # n= (n%2) ? 3*n+1 : n/2;
    add    edx, 1      # ++count;
    cmp    rax, 1
    jne   .L9          #}while(n!=1)

  cmp/branch to update max and maxi, and then do the next n

내부 루프는 분기가 없으며 루프 전달 종속성 체인의 중요 경로는 다음과 같습니다.

  • 3 성분 LEA (3 사이클)
  • cmov (Haswell에서 2주기, Broadwell 이상에서 1c).

총 : 반복 당 5주기, 지연 시간 병목 현상 . 비 순차적 실행은 이것과 병행하여 다른 모든 것을 처리합니다 (이론상 : 실제로 5c / iter에서 실행되는지 확인하기 위해 성능 카운터로 테스트하지 않았습니다).

cmov 의 FLAGS 입력 (TEST에서 생성)은 RAX 입력 (LEA-> MOV에서)보다 생성 속도가 빠르기 때문에 중요한 경로에 있지 않습니다.

마찬가지로 CMOV의 RDI 입력을 생성하는 MOV-> SHR은 LEA보다 빠르기 때문에 중요 경로를 벗어납니다. IvyBridge 이상의 MOV는 지연 시간이 없습니다 (등록-이름 변경시 처리됨). (여전히 uop과 파이프 라인의 슬롯이 필요하므로 무료가 아니며 지연 시간이 0입니다). LEA dep 체인의 추가 MOV는 다른 CPU의 병목 현상의 일부입니다.

cmp / jne은 또한 중요 경로의 일부가 아닙니다. 제어 종속성은 중요 경로에 대한 데이터 종속성과 달리 분기 예측 + 예측 실행으로 처리되기 때문에 루프 전달되지 않습니다.

컴파일러 잡기

GCC는 여기서 꽤 잘했습니다. add edx, 1 을 inc edx 를 사용하여 하나의 코드 바이트를 절약 할 수 있습니다. 왜냐하면 아무도 부분 플래그 수정 명령에 대한 P4와 그 거짓 종속성에 관심이 없기 때문입니다.

또한 모든 MOV 명령을 저장할 수 있으며 TEST : SHR은 CF = 비트를 시프트 아웃하도록 설정하므로 test / cmovz 대신 cmovc 를 사용할 수 있습니다.

 ### Hand-optimized version of what gcc does
.L9:                       #do{
    lea     rcx, [rax+1+rax*2] # rcx = 3*n + 1
    shr     rax, 1         # n>>=1;    CF = n&1 = n%2
    cmovc   rax, rcx       # n= (n&1) ? 3*n+1 : n/2;
    inc     edx            # ++count;
    cmp     rax, 1
    jne     .L9            #}while(n!=1)

또 다른 영리한 트릭에 대해서는 @johnfound의 답변을 참조하십시오 : SHR의 플래그 결과를 분기하고 CMOV에 사용하여 CMP를 제거하십시오 .n이 1 (또는 0) 인 경우에만 0으로 시작하십시오. (재미있는 사실 : Nehalem 또는 이전 버전에서 count! = 1을 사용하는 SHR은 플래그 결과를 읽으면 중단을 일으 킵니다 . 이것이 그들이 단일 uop으로 만든 방법입니다.하지만, shift-by-1 특수 인코딩은 괜찮습니다.)

MOV를 피하는 것은 Haswell의 지연 시간에 전혀 도움이되지 않습니다 ( x86의 MOV가 정말로 "무료"일 수 있습니까? 왜 이것을 전혀 재현 할 수 없습니까? ). Intel pre-IvB와 같은 CPU 및 MOV가 지연 시간이없는 AMD Bulldozer 제품군에서 크게 도움이됩니다. 컴파일러의 낭비되는 MOV 명령어는 중요 경로에 영향을줍니다. BD의 복잡한 LEA 및 CMOV는 모두 더 낮은 지연 시간 (각각 2c 및 1c)이므로 지연 시간의 더 큰 부분입니다. 또한 두 개의 정수 ALU 파이프 만 있기 때문에 처리량 병목 현상이 문제가됩니다. AMD CPU의 타이밍 결과가있는 @johnfound의 답변을 참조하십시오.

Haswell에서도이 버전은 중요하지 않은 uop가 중요 경로에있는 하나에서 실행 포트를 훔쳐 실행 포트를 1주기 지연시키는 간헐적 인 지연을 방지함으로써 약간의 도움이 될 수 있습니다. (이를 리소스 충돌이라고합니다). n 값을 병렬로 수행 할 때 도움이 될 수 있습니다 (아래 참조).

LEA의 지연 시간은 Intel SnB 제품군 CPU 의 주소 지정 모드에 따라 다릅니다. 3 개의 구성 요소에 대해 3c ( [base+idx+const] , 두 개의 개별 추가가 필요함), 2 개 이하의 구성 요소 (하나의 추가)가있는 1c 만 있습니다. 일부 CPU (예 : Core2)는 단일주기에서 3- 구성 요소 LEA를 수행하지만 SnB 제품군은 그렇지 않습니다. 더 나쁜 것은 Intel SnB 제품군이 지연 시간을 표준화하므로 2c uops가 없습니다 . 그렇지 않으면 3 개 구성 요소 LEA가 Bulldozer와 같이 2c에 불과합니다. (3 구성 요소 LEA는 AMD에서도 느립니다.

따라서 lea rcx, [rax + rax*2] / inc rcx 는 Haswell과 같은 Intel SnB 제품군 CPU에서 lea rcx, [rax + rax*2 + 1] 보다 빠른 2c 지연 시간입니다. BD에서는 손익분기 점, Core2에서는 더 나쁩니다. 추가 uop 비용이 들지만 일반적으로 1c 대기 시간을 절약하는 데는 가치가 없지만 대기 시간은 여기서 주요 병목이며 Haswell은 추가 uop 처리량을 처리 할 수있는 충분한 파이프 라인을 가지고 있습니다.

gcc, icc 또는 clang (godbolt에서)은 항상 AND 또는 TEST를 사용하는 SHR의 CF 출력을 사용하지 않았습니다 . 어리석은 컴파일러. : P 그들은 복잡한 기계의 훌륭한 조각이지만 영리한 인간은 종종 소규모 문제에서 그들을 이길 수 있습니다. (물론 생각하는 데 수천에서 수백만 배 더 오래 걸립니다! 컴파일러는 모든 가능한 작업 방법을 찾기 위해 철저한 알고리즘을 사용하지 않습니다. 많은 인라인 코드를 최적화 할 때 너무 오래 걸리기 때문입니다. 그들은 또한 대상 마이크로 아키텍처에서 파이프 라인을 모델링하지 않습니다. 적어도 IACA 또는 기타 정적 분석 도구와 동일한 세부 사항은 아닙니다. 일부 휴리스틱 만 사용합니다.)

간단한 루프 언 롤링은 도움이되지 않습니다 . 이 루프는 루프 오버 헤드 / 처리량이 아닌 루프 전달 종속성 체인의 지연 시간에 병목 현상이 발생합니다. 이것은 CPU가 두 스레드의 명령을 인터리브 할 시간이 많기 때문에 하이퍼 스레딩 (또는 다른 종류의 SMT)에서 잘 수행된다는 것을 의미합니다. main 에서 루프를 병렬화하는 것을 의미 n 값의 범위를 확인하고 결과적으로 한 쌍의 정수를 생성 할 수 있기 때문에 괜찮습니다.

단일 스레드 내에서 손으로 인터리빙하는 것도 가능할 수 있습니다 . 한 쌍의 숫자에 대한 시퀀스를 병렬로 계산할 수 있습니다. 각 숫자는 몇 개의 레지스터 만 사용하고 모두 동일한 max / maxi 업데이트 할 수 있기 때문입니다. 이것은 더 많은 명령어 수준의 병렬성을 생성합니다.

n 값의 다른 쌍을 얻기 전에 n 값이 1 도달 할 때까지 기다릴 것인지, 아니면 종료 조건에 도달 한 하나에 대한 레지스터를 건드리지 않고 새로운 시작점을 얻을 것인지를 결정하는 것입니다. 다른 순서. 아마도 각 체인이 유용한 데이터에서 작동하도록 유지하는 것이 가장 좋습니다. 그렇지 않으면 조건부로 카운터를 증가시켜야합니다.

n 1 도달하지 않은 벡터 요소에 대한 카운터를 조건부로 증가시키기 위해 SSE 압축 비교 항목으로 이것을 수행 할 수도 있습니다. 그런 다음 SIMD 조건부 증가 구현의 더 긴 대기 시간을 숨기려면 n 값의 더 많은 벡터를 공중에 유지해야합니다. 256b 벡터 (4x uint64_t 있습니다.

1 "sticky"를 감지하는 가장 좋은 전략은 카운터를 증가시키기 위해 추가하는 all-one의 벡터를 마스킹하는 것입니다. 1 을 본 후 증분 벡터는 0을 가지며 + = 0은 작동하지 않습니다.

# starting with YMM0 = [ n_d, n_c, n_b, n_a ]  (64-bit elements)
# ymm4 = _mm256_set1_epi64x(1):  increment vector
# ymm5 = all-zeros:  count vector

.inner_loop:
    vpaddq    ymm1, ymm0, xmm0
    vpaddq    ymm1, ymm1, xmm0
    vpaddq    ymm1, ymm1, set1_epi64(1)     # ymm1= 3*n + 1.  Maybe could do this more efficiently?

    vprllq    ymm3, ymm0, 63                # shift bit 1 to the sign bit

    vpsrlq    ymm0, ymm0, 1                 # n /= 2

    # FP blend between integer insns may cost extra bypass latency, but integer blends don't have 1 bit controlling a whole qword.
    vpblendvpd ymm0, ymm0, ymm1, ymm3       # variable blend controlled by the sign bit of each 64-bit element.  I might have the source operands backwards, I always have to look this up.

    # ymm0 = updated n  in each element.

    vpcmpeqq ymm1, ymm0, set1_epi64(1)
    vpandn   ymm4, ymm1, ymm4         # zero out elements of ymm4 where the compare was true

    vpaddq   ymm5, ymm5, ymm4         # count++ in elements where n has never been == 1

    vptest   ymm4, ymm4
    jnz  .inner_loop
    # Fall through when all the n values have reached 1 at some point, and our increment vector is all-zero

    vextracti128 ymm0, ymm5, 1
    vpmaxq .... crap this doesn't exist
    # Actually just delay doing a horizontal max until the very very end.  But you need some way to record max and maxi.

손으로 작성한 asm 대신 내장 함수를 사용하여 이를 구현할 수 있으며 구현해야합니다.

알고리즘/구현 개선:

보다 효율적인 asm으로 동일한 로직을 구현하는 것 외에도 로직을 단순화하거나 중복 작업을 피할 수있는 방법을 찾으십시오. 예를 들어 시퀀스의 공통 엔딩을 감지하기 위해 메모합니다. 또는 더 나은 방법은 한 번에 8 개의 후행 비트를 확인하는 것입니다 (gnasher의 대답).

@EOF는 tzcnt (또는 bsf )를 사용하여 한 단계에서 n/=2 반복을 수행 할 수 있음을 지적합니다. 아마도 SIMD 벡터화보다 낫습니다. SSE 또는 AVX 명령은이를 수행 할 수 없습니다. 그래도 다른 정수 레지스터에서 병렬로 n 을 수행하는 것과 여전히 호환됩니다.

따라서 루프는 다음과 같습니다.

goto loop_entry;  // C++ structured like the asm, for illustration only
do {
   n = n*3 + 1;
  loop_entry:
   shift = _tzcnt_u64(n);
   n >>= shift;
   count += shift;
} while(n != 1);

이렇게하면 반복 횟수가 크게 줄어들 수 있지만 BMI2가없는 Intel SnB 제품군 CPU에서는 가변 카운트 시프트가 느립니다. 3 uops, 2c 지연. (count = 0은 플래그가 수정되지 않았 음을 의미하므로 FLAGS에 대한 입력 종속성이 있습니다.이를 데이터 종속성으로 처리하고 uop에 2 개의 입력 만있을 수 있기 때문에 여러 uop을 사용합니다 (어쨌든 사전 HSW / BDW)). 이것은 사람들이 x86의 미친 CISC 디자인에 대해 불평하는 종류입니다. ISA가 오늘날 처음부터 설계되었을 때보 다 x86 CPU를 느리게 만듭니다. 거의 비슷한 방식으로도 말입니다. (즉, 이것은 속도 / 전력 비용이 드는 "x86 세금"의 일부입니다.) SHRX / SHLX / SARX (BMI2)는 큰 승리입니다 (1 uop / 1c 대기 시간).

또한 tzcnt (Haswell 이상에서는 3c)를 중요 경로에 배치하므로 루프 전달 종속성 체인의 총 대기 시간이 크게 늘어납니다. n>>1 보유하는 레지스터를 준비 할 필요가 없습니다. @Veedrac의 답변은 여러 반복에 대해 tzcnt / shift를 연기함으로써이 모든 것을 극복하며 이는 매우 효과적입니다 (아래 참조).

n 은 그 시점에서 절대 0이 될 수 없기 때문에 BSF 또는 TZCNT를 서로 바꿔서 안전하게 사용할 수 있습니다. TZCNT의 기계 코드는 BMI1을 지원하지 않는 CPU에서 BSF로 디코딩됩니다. (의미없는 접두사는 무시되므로 REP BSF는 BSF로 실행됩니다).

TZCNT는이를 지원하는 AMD CPU에서 BSF보다 훨씬 더 나은 성능을 발휘하므로 입력이 출력이 아닌 0 인 경우 ZF를 설정하는 데 신경 쓰지 않더라도 REP BSF -mno-bmi 와 함께 __builtin_ctzll 을 사용할 때이를 수행합니다.

그들은 Intel CPU에서 똑같이 수행하므로 그게 중요한 경우 바이트를 저장하십시오. Intel (Skylake 이전)의 TZCNT는 BSF와 마찬가지로 쓰기 전용 출력 피연산자에 대한 거짓 의존성을 가지고있어 입력 = 0 인 BSF가 대상을 수정되지 않은 상태로 남겨 두는 문서화되지 않은 동작을 지원합니다. 따라서 Skylake에 대해서만 최적화하지 않는 한이 문제를 해결해야하므로 추가 REP 바이트에서 얻을 수있는 것이 없습니다. (인텔은 종종 x86 ISA 매뉴얼이 요구하는 것 이상으로 나아가서는 안되는 것에 의존하거나 소급 적으로 허용되지 않는 널리 사용되는 코드를 깨뜨리는 것을 방지합니다. 예를 들어 Windows 9x는 TLB 항목에 대한 추측 성 프리 페치가 없다고 가정 합니다. 인텔이 TLB 관리 규칙을 업데이트하기 전에 코드가 작성되었을 때.)

어쨌든 Haswell의 LZCNT / TZCNT는 POPCNT와 동일한 false dep를 가지고 있습니다. 이 Q & A를 참조하세요. 이것이 @Veedrac의 코드에 대한 gcc의 asm 출력에서 dst = src를 사용하지 않을 때 TZCNT의 대상으로 사용하려는 레지스터에서 xor-zeroing으로 dep 체인을 끊는 것을 볼 수있는 이유입니다. TZCNT / LZCNT / POPCNT는 목적지를 정의되지 않거나 수정하지 않은 상태로 두지 않기 때문에 Intel CPU의 출력에 대한 이러한 잘못된 종속성은 성능 버그 / 제한 사항입니다. 아마도 동일한 실행 장치로 이동하는 다른 uop처럼 동작하도록하는 트랜지스터 / 전력의 가치가있을 것입니다. 유일한 성능 향상은 다른 uarch 제한과의 상호 작용입니다 . Haswell의 인덱스 주소 지정 모드로 메모리 피연산자를 마이크로 융합 할 수 있지만 Intel이 LZCNT / TZCNT에 대한 false dep를 제거한 Skylake에서는 인덱스 주소 지정 모드를 "un-laminate"하는 반면 POPCNT는 여전히 모든 addr 모드를 마이크로 퓨즈 할 수 있습니다.

다른 답변의 아이디어/코드 개선:

@hidefromkgb의 대답 에는 3n + 1 후에 오른쪽 교대를 한 번 할 수 있다는 좋은 관찰이 있습니다. 단계 사이의 검사를 생략하는 것보다 더 효율적으로이를 계산할 수 있습니다. 그 대답의 asm 구현은 깨졌지만 (개수가 1보다 큰 ROR rdi,2 SHRD rdi,rdi,2 보다 빠르며 두 개의 CMOV 명령어를 사용합니다. 임계 경로에서 병렬로 실행할 수있는 추가 테스트보다 느립니다.

나는 깔끔한 / 개선 된 C (컴파일러가 더 나은 asm을 생성하도록 안내)를 넣고 테스트 + 더 빠른 asm (C 아래의 주석에서)을 Godbolt에 올려 놓았습니다. @ hidefromkgb의 답변 링크를 참조하십시오. (이 답변은 큰 Godbolt URL에서 30k 문자 제한에 도달했지만 shortlink 는 썩을 수 있으며 어쨌든 goo.gl에는 너무 길었습니다.)

또한 한 번에 하나의 문자를 쓰는 대신 write() 를 만들도록 출력 인쇄를 개선했습니다. perf stat ./collatz (성능 카운터를 기록하기 위해)를 사용하여 전체 프로그램 타이밍에 미치는 영향을 최소화하고, 중요하지 않은 일부 asm을 난독 화했습니다.

@Veedrac의 코드

우리가 알고있는 만큼 오른쪽으로 이동하고 루프를 계속하기 위해 확인하면서 약간의 속도 향상을 얻었습니다. limit = 1e8의 경우 7.5 초에서 Core2Duo (Merom)의 경우 7.275 초로 풀림 계수가 16입니다.

코드 + Godbolt에 대한 주석 . 이 버전을 clang과 함께 사용하지 마십시오. 지연 루프로 어리석은 일을합니다. tmp 카운터 k count 추가하면 clang이 수행하는 작업이 변경되지만 gcc가 약간 손상됩니다.

의견 토론을 참조하십시오 : Veedrac의 코드가 BMI1 (즉,하지 셀러론 / 펜티엄)와 CPU에서 우수

출처 : https://stackoverflow.com/questions/40354978/why-does-c-code-for-testing-the-collatz-conjecture-run-faster-than-hand-writte
728x90
반응형

'프로그래밍 언어 > C++' 카테고리의 다른 글

C ++ 표준 int, long 유형의 크기 기준  (0) 2021.07.27
C ++ 컴파일이 오래 걸리는 이유  (0) 2021.07.23
C ++ 프로그래머가 'new'사용을 최소화해야하는 이유  (0) 2021.07.23
확실한 C ++ 의 가이드 및 목록  (0) 2021.07.23
C 및 C ++에서 char를 int로 변환  (0) 2021.07.23

'프로그래밍 언어/C++'의 다른글

  • 현재글Collatz 추측을 테스트하기위한 C ++ 코드가 손으로 작성한 어셈블리보다 빠르게 실행되는 이유

관련글

댓글

티스토리툴바