performance - the collatz conjecture answer - コラッツ予想を検証するためのC++コードが、手書きのアセンブリよりも高速に動作するのはなぜですか?

collatz conjecture c code / c++ / assembly / optimization / x86

Project Euler Q14のこれら2つのソリューションを、アセンブリとC ++で作成しました。それらは、コラッツ予想をテストするために同一の強引なアプローチを実装します。アセンブリソリューションは、次のもので組み立てられました。

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 ++を作成しようとする場合は、コンパイラにその処理を任せても問題ありません。また、アセンブリはコンパイルされた言語よりも高速ですか?。答えの1つは、さまざまなCコンパイラがクールなトリックでいくつかの非常に単純な関数を最適化する方法を示すこれらのきちんとしたスライドへのリンクです。Matt GodboltのCppCon2017の講演「最近、私のコンパイラは私のために何をしてくれましたか?コンパイラのふたのボルトを外す」も同様です。

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      # ++count;
    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            # ++count;
    cmp     rax, 1
    jne     .L9            #}while(n!=1)

手動ベクター化のための未検証のアイデア

#YMM0で始まる= [n_d、n_c、n_b、n_a](64ビット要素)
#ymm4 = _mm256_set1_epi64x(1):インクリメントベクトル
#ymm5 =すべてゼロ:カウントベクトル

.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

    #整数insn間の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が一度もなかった要素のcount ++ == 1

    vptest   ymm4, ymm4
    jnz  .inner_loop
    #ある時点ですべてのn値が1に達し、増分ベクトルがすべてゼロになると、フォールスルーします。

    vextracti128 ymm0, ymm5, 1
    vpmaxq .... crap this doesn't exist
    #実際には、最後まで水平最大の実行を遅らせるだけです。ただし、maxとmaxiを記録する方法が必要です。

そのため、ループは次のようになります。

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