performance - elements of programming interviews pdf c++ github - Collatz 추측을 테스트하기위한 C ++ 코드가 손으로 작성한 어셈블리보다 빠르게 실행되는 이유는 무엇입니까?

elements of programming interviews 300 questions and solutions pdf / c++ / assembly / optimization / x86

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

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

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

g++ p14.cpp -o p14
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
#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;
}

Igor Burago



Answer #1

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

even:
    mov rbx, 2
    xor rdx, rdx
    div rbx
 # gcc5.4 -O3 및 내 의견

 # edx= count=1
 # rax= uint64_t n

.L9:                   # 하다{
    lea    rcx, [rax+1+rax*2]   # rcx = 3*n + 1
    mov    rdi, rax
    shr    rdi         # rdi = n>>1;
    test   al, 1       # n % 2 (일명 n & 1)를 기반으로 플래그 설정
    mov    rax, rcx
    cmove  rax, rdi    # n= (n%2) ? 3*n+1 : n/2;
    add    edx, 1      # ++ 개수;
    cmp    rax, 1
    jne   .L9          #}while(n!=1)

  cmp/branch to update max and maxi, and then do the next n
 ### gcc가하는 일의 수동 최적화 버전
.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            # ++ 개수;
    cmp     rax, 1
    jne     .L9            #}while(n!=1)

수동 벡터화에 대한 테스트되지 않은 아이디어

# YMM0으로 시작 = [n_d, n_c, n_b, n_a] (64 비트 요소)
# ymm4 = _mm256_set1_epi64x (1) : 증분 벡터
# ymm5 = 모두 0 : 카운트 벡터

.inner_loop:
    vpaddq    ymm1, ymm0, xmm0
    vpaddq    ymm1, ymm1, xmm0
    vpaddq    ymm1, ymm1, set1_epi64(1)     # ymm1 = 3 * n + 1.이 작업을 더 효율적으로 할 수 있을까요?

    vprllq    ymm3, ymm0, 63                # 비트 1을 부호 비트로 이동

    vpsrlq    ymm0, ymm0, 1                 # n /= 2

    # 정수 insns 간의 FP 블렌드는 추가 우회 대기 시간이 필요할 수 있지만 정수 블렌드는 전체 qword를 제어하는 ​​1 비트가 없습니다.
    vpblendvpd ymm0, ymm0, ymm1, ymm3       # 각 64 비트 요소의 부호 비트에 의해 제어되는 가변 블렌드. 나는 소스 피연산자를 거꾸로 가질 수 있습니다. 항상 이것을 찾아야합니다.

    # ymm0 = 각 요소에서 업데이트 된 n.

    vpcmpeqq ymm1, ymm0, set1_epi64(1)
    vpandn   ymm4, ymm1, ymm4         # 비교가 참인 ymm4의 요소를 제로

    vpaddq   ymm5, ymm5, ymm4         # n이 == 1이 아닌 요소의 개수 ++

    vptest   ymm4, ymm4
    jnz  .inner_loop
    # 모든 n 값이 어느 시점에서 1에 도달하고 증분 벡터가 모두 0이면 통과

    vextracti128 ymm0, ymm5, 1
    vpmaxq .... crap this doesn't exist
    # 실제로는 맨 끝까지 수평 최대 작업을 지연하십시오. 그러나 최대 및 최대를 기록하는 방법이 필요합니다.

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

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