blog - c++ optimization pdf




Collat z推測を手書きアセンブリよりも速くテストするためのC++コード-なぜですか? (8)

C ++プログラムは、ソースコードからマシンコードを生成するときにアセンブリプログラムに変換されます。 アセンブリがC ++より遅いと言うのは事実上間違っています。 さらに、生成されるバイナリコードはコンパイラごとに異なります。 そのため、スマートC ++コンパイラ 、ダムアセンブラのコードよりも最適で効率的なバイナリコードを生成 でき ます。

しかし、プロファイリング方法には特定の欠陥があると思います。 プロファイリングの一般的なガイドラインは次のとおりです。

  1. システムが正常/アイドル状態であることを確認してください。 起動した、またはCPUを集中的に使用する実行中のプロセス(アプリケーション)をすべて停止します(またはネットワーク経由でポーリングします)。
  2. データサイズのサイズを大きくする必要があります。
  3. テストは5〜10秒以上実行する必要があります。
  4. 1つのサンプルだけに依存しないでください。 テストをN回実行します。 結果を収集し、結果の平均または中央値を計算します。

Project Euler Q14の これら2つのソリューションは、アセンブリとC ++で作成しました。 これらは、 コラッツ予想 をテストするための同一のブルートフォースアプローチです。 アセンブリソリューションは、

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>

using namespace std;

int sequence(long n) {
    int count = 1;
    while (n != 1) {
        if (n % 2 == 0)
            n /= 2;
        else
            n = n*3 + 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;
        }
    }

    cout << maxi << endl;
}

速度とすべてを改善するためのコンパイラの最適化については知っていますが、アセンブリソリューションをさらに最適化する多くの方法はありません(数学的にではなく、プログラム的に言えば)。

C ++コードには、すべての用語のモジュラスと偶数の用語ごとの区分があり、アセンブリは偶数の用語ごとに1つの区分のみです。

ただし、アセンブリはC ++ソリューションよりも平均で1秒長くかかります。 どうしてこれなの? 私は主に好奇心を求めています。

実行時間

私のシステム:1.4 GHz Intel Celeron 2955U(Haswell microarchitecture)上の64ビットLinux。

  • g++ (最適化されていない):平均1272 ms

  • g++ -O3 平均578ミリ秒

  • 元のasm(div)平均2650ミリ秒

  • Asm (shr) 平均679ミリ秒

  • nasm avg 501 msでアセンブルされた @johnfound asm

  • @hidefromkgb asm 平均200ミリ秒

  • @Peter Cordesによって最適化された@hidefromkgb asm 平均145ミリ秒

  • @Veedrac C ++ -O3 で平均81ミリ秒、 -O0 で305ミリ秒


Collat​​z問題の場合、「テール」をキャッシュすることでパフォーマンスを大幅に向上させることができます。 これは時間とメモリのトレードオフです。 参照:メモ化( https://en.wikipedia.org/wiki/Memoization )。 また、他の時間/メモリのトレードオフのために動的プログラミングソリューションを検討することもできます。

Pythonの実装例:

import sys

inner_loop = 0

def collatz_sequence(N, cache):
    global inner_loop

    l = [ ]
    stop = False
    n = N

    tails = [ ]

    while not stop:
        inner_loop += 1
        tmp = n
        l.append(n)
        if n <= 1:
            stop = True  
        elif n in cache:
            stop = True
        elif n % 2:
            n = 3*n + 1
        else:
            n = n // 2
        tails.append((tmp, len(l)))

    for key, offset in tails:
        if not key in cache:
            cache[key] = l[offset:]

    return l

def gen_sequence(l, cache):
    for elem in l:
        yield elem
        if elem in cache:
            yield from gen_sequence(cache[elem], cache)
            raise StopIteration

if __name__ == "__main__":
    le_cache = {}

    for n in range(1, 4711, 5):
        l = collatz_sequence(n, le_cache)
        print("{}: {}".format(n, len(list(gen_sequence(l, le_cache)))))

    print("inner_loop = {}".format(inner_loop))

アセンブリを見なくても、最も明白な理由 /= 2 はおそらく最適化されていることで >>=1 あり、多くのプロセッサには非常に迅速なシフト操作があるためです。 ただし、プロセッサにシフト演算がない場合でも、整数除算は浮動小数点除算より高速です。

編集: 上記の「整数除算は浮動小数点除算よりも速い」ステートメントで、マイル数が異なる場合があります。 以下のコメントは、現代のプロセッサが整数除算よりもfp除算の最適化を優先していることを明らかにしています。 したがって、誰かがこのスレッドの質問が尋ねるスピードアップの最も可能性の高い理由を探していた場合、コンパイラーは最適 な最初の場所 /=2 として 最適化 する >>=1 でしょう。

無関係なノート ならば、 n 奇数である、式は n*3+1 常に偶数となります。 そのため、確認する必要はありません。 そのブランチを変更できます

{
   n = (n*3+1) >> 1;
   count += 2;
}

したがって、ステートメント全体は次のようになります

if (n & 1)
{
    n = (n*3 + 1) >> 1;
    count += 2;
}
else
{
    n >>= 1;
    ++count;
}

コンパイラによって生成されたコードを投稿しなかったので、ここにいくつかの推測がありますが、それを見たことがなくても、これは言うことができます:

test rax, 1
jpe even

... 50%の確率でブランチを予測しますが、それは高価になります。

コンパイラーはほぼ確実に両方の計算を行い(div / modが非常に長いレイテンシーであるため無視できるほどコストがかかるため、乗加算は「無料」です)、CMOVでフォローアップします。 もちろん、これは 予測ミスの可能性が ゼロ パーセントです。


簡単な答え:

  • MOV RBX、3およびMUL RBXを実行するのは高価です。 RBX、RBXを2回追加するだけ

  • ADD 1は、おそらくここでINCよりも高速です

  • MOV 2およびDIVは非常に高価です。 ちょうど右にシフト

  • 通常、64ビットコードは32ビットコードよりも著しく遅く、アライメントの問題はより複雑です。 このような小さなプログラムでは、それらをパックする必要があるため、32ビットコードよりも高速になる可能性があるため、並列計算を実行しています

C ++プログラムのアセンブリリストを生成すると、アセンブリとの違いを確認できます。


64ビットDIV命令が2で割るのに良い方法だと思うなら、コンパイラのasm出力が -O0 (高速でコンパイル、追加の最適化なし、メモリへのストア/リロード)を使用しても手書きのコードに勝るのも不思議ではありませんデバッガーが変数を変更できるように、すべてのCステートメントの後/前)。

効率的なasmの記述方法については、 Agner Fogの最適化アセンブリガイド を参照してください。 彼はまた、特定のCPUの特定の詳細についての指示表とマイクロアーチガイドを持っています。 その他のperfリンクについては、 x86 タグwikiも参照してください。

手書きasmを使用してコンパイラーを打つことに関するこのより一般的な質問も参照してください。 インラインアセンブリ言語はネイティブC ++コードよりも遅いですか? 。 TL:DR:間違った場合(この質問のように)はい。

通常、特に 効率的にコンパイルできるC ++を記述しようとする 場合は、コンパイラにそのことを任せて大丈夫です。 また、 アセンブリはコンパイルされた言語よりも高速ですか? 。 回答の1つは、 これらの すてき なスライド へのリンクで、さまざまなCコンパイラーがいくつかの本当に簡単な機能をクールなトリックで最適化する方法を示しています。

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

Intel Haswellでは、 div r64 は36 uopであり、 レイテンシは32-96サイクル 、スループットは21-74サイクルごとに1です。 (さらに2つのuopを追加してRBXをセットアップし、RDXをゼロにしますが、アウトオブオーダー実行はそれらを早期に実行できます)。 DIVのような高uopカウントの命令はマイクロコード化されており、フロントエンドのボトルネックを引き起こす可能性もあります。 この場合、遅延はループに依存する依存関係チェーンの一部であるため、最も重要な要素です。

shr rax, 1 は同じ符号なし除算 を実行します 。1uop、1cレイテンシ 、クロックサイクルごとに2を実行できます。

比較のために、32ビット除算は高速ですが、それでも恐ろしい対シフトです。 idiv r32 は、9 uops、22-29cのレイテンシ、およびHaswellで8-11cのスループットごとに1つです。

gccの -O0 asm出力( Godboltコンパイラエクスプローラー )を見るとわかるように、シフト命令のみを使用しています 。 clang -O0 は、64ビットIDIVを2回使用しても、思ったように単純にコンパイルします。 (最適化時に、コンパイラがIDIVをまったく使用している場合、ソースが同じオペランドで除算とモジュラスを行う場合、コンパイラはIDIVの両方の出力を使用します)

GCCには完全に単純なモードはありません。 常にGIMPLEを介して変換されるため、一部の「最適化」を無効にできません 。 これには、定数による除算の認識と、シフト(2のべき乗)または 固定小数点乗算逆数 (2の非べき乗)を使用してIDIVを回避することが含まれます(上記のgodboltリンクのdiv_by_13を参照)。

gcc -Os (サイズの最適化) 、乗法の逆コードがわずかに大きいだけで、はるかに高速の場合でも、2のべき乗以外の除算にIDIVを使用 ます。

コンパイラーの支援

(この場合の要約: uint64_t n 使用)

まず、最適化されたコンパイラの出力を見るのは興味深いだけです。 ( -O3 )。 -O0 速度は基本的に意味があり -O0

asm出力を確認します(Godboltで、または GCC / clangアセンブリ出力から「ノイズ」を除去する方法を 参照してください ? )。 コンパイラがそもそも最適なコードを作成しない場合: 通常、コンパイラがより良いコードを作成するようにガイドする方法でC / C ++ソースを作成するのが最良のアプローチ です。 asmを知り、何が効率的かを知る必要がありますが、この知識を間接的に適用します。 コンパイラーも優れたアイデアのソースです。clangが何かクールなことをすることもあります。gccを握って同じことをすることもできます。 この答え と、以下の@Veedracのコードで展開されていないループで行ったことをご覧ください)

このアプローチは移植性があり、20年後には、新しいISA拡張機能または自動ベクトル化を使用して、将来のコンパイラが将来のハードウェア(x86であろうとなかろうと)で効率的なものにコンパイルできます。 15年前の手書きのx86-64 asmは、通常、Skylake用に最適に調整されません。 たとえば、compare&branchマクロ融合は当時存在していませんでした。 1つのマイクロアーキテクチャの手作り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 をお読み https://gcc.gnu.org/wiki/DontUseInlineAsm 。 (そして、MSVCスタイルのインラインasmを避けてください。入力/出力はメモリ を 通過する必要があるため、 オーバーヘッドが追加されます 。)

この場合 n には符号付きの型があり、gccは正しい丸めを与えるSAR / SHR / ADDシーケンスを使用します。 (IDIVと負の入力の場合の算術シフト「ラウンド」は異なります。SARinsn set ref手動 入力を参照してください)。 (gccが n が負の値にならないことを証明しようとして失敗した場合、IDK。符号付きオーバーフローは未定義の動作なので、できるはずです。)

uint64_t n を使用する必要があったので、SHRになります。 そのため、 long が32ビットのみのシステム(x86-64 Windowsなど)に移植できます。

ところで、 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以降では1サイクル)。

合計:反復あたり5サイクル、遅延のボトルネック 。 アウトオブオーダー実行は、これと並行して他のすべてを処理します(理論的には、5c / iterで実際に実行されるかどうかを確認するためにperfカウンターでテストしていません)。

cmov のFLAGS入力(TESTが生成)は、RAX入力(LEA-> MOVから)よりも生成が速いため、クリティカルパス上にはありません。

同様に、CMOVのRDI入力を生成するMOV-> SHRは、LEAよりも高速であるため、クリティカルパスから外れています。 IvyBridge以降のMOVのレイテンシはゼロです(レジスタ名の変更時に処理されます)。 (まだuopとパイプラインのスロットが必要なので、無料ではなく、待ち時間がゼロになります)。 LEA depチェーンの余分なMOVは、他のCPUのボトルネックの一部です。

cmp / jneもクリティカルパスの一部ではありません。クリティカルパスのデータ依存関係とは異なり、制御依存関係は分岐予測+投機的実行で処理されるため、ループキャリーではありません。

コンパイラーを破る

GCCはここでかなり良い仕事をしました。 誰もP4と部分フラグ変更命令の誤った依存関係を気にしないので add edx, 1 代わりに inc edx を使用することで1コードバイトを節約できます。

また、すべての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のフラグ結果に分岐してCMPを削除し、CMOVに使用します:nが1(または0)である場合のみゼロ。 (面白い事実: フラグの結果を読み取ると、Nehalem以前でカウントが1のSHRがストールを引き起こします 。これが、シングルuopになった理由です。1シフトごとの特別なエンコードは問題ありません。)

MOVを避けると、Haswellのレイテンシーがまったく改善されません( x86のMOVを実際に「無料」にすることはできますか?なぜこれをまったく再現できないのですか? )。 Intel pre-IvB、AMD Bulldozer-familyなどのMOVがゼロ遅延ではないCPUで 非常 に役立ち ます 。 コンパイラの無駄なMOV命令はクリティカルパスに影響します。 BDの複雑なLEAとCMOVはどちらもレイテンシが低いため(それぞれ2cと1c)、レイテンシの大きな割合を占めています。 また、2つの整数ALUパイプしかないため、スループットのボトルネックが問題になります。 @johnfoundの答えをご覧ください。AMDCPU からのタイミング結果があります。

Haswellでも、このバージョンは、非クリティカルなuopがクリティカルパス上のポートから実行ポートを盗み、実行を1サイクル遅らせる場合のある種の遅延を回避することにより、少し助けになるかもしれません。 (これはリソースの競合と呼ばれます)。 また、レジスタを保存します。これは、インターリーブループで複数の n 値を並行して実行するときに役立ちます(以下を参照)。

LEAのレイテンシは 、Intel SnBファミリCPU のアドレス指定モードに依存し ます。 3つのコンポーネントの場合は3c( [base+idx+const] 、2つの別個の追加が必要)、ただし2つ以下のコンポーネントの場合は1c(1つの追加)。 一部のCPU(Core2など)は、1サイクルで3コンポーネントのLEAを実行しますが、SnBファミリは実行しません。 さらに悪いことに、 Intel SnBファミリはレイテンシを標準化しているため、2cのuopはありません 。そうでない場合、3コンポーネントLEAはブルドーザーのように2cになります。 (3コンポーネントLEAは、AMDでも同様に遅くなりますが、それほど大きくはありません)。

lea rcx, [rax + rax*2] / inc rcx は、HaswellなどのIntel SnBファミリーCPUで lea rcx, [rax + rax*2 + 1] よりも2cレイテンシーしかありません。 BDでは損益分岐点、Core2では悪化します。 通常、1cのレイテンシを節約する価値はありませんが、余分なuopがかかりますが、レイテンシはここでの主要なボトルネックであり、Haswellには余分なuopスループットを処理するための十分なパイプラインがあります。

gcc、icc、clang(godbolt上の)は、常にANDまたはTESTを使用してSHRのCF出力を使用しませんでした 。 愚かなコンパイラ。 :Pそれらは複雑な機械のすばらしい部分ですが、賢い人間はしばしば小規模な問題でそれらを打ち負かすことができます。 (それについて考えるのに数千から数百倍の時間が与えられます!もちろん、コンパイラはすべての可能な方法を検索するために徹底的なアルゴリズムを使用しません、なぜならそれは多くのインラインコードを最適化するのに時間がかかりすぎるからですまた、少なくとも IACA や他の静的分析ツールと同じ詳細ではなく、ターゲットのマイクロアーキテクチャでパイプラインをモデル化せず、いくつかのヒューリスティックを使用します。

単純なループの展開は役に立ちません 。 このループは、ループのオーバーヘッド/スループットではなく、ループで実行される依存関係チェーンの遅延にボトルネックがあります。 これは、CPUが2つのスレッドからの命令をインターリーブする時間が長いため、ハイパースレッディング(または他の種類のSMT)でうまくいくことを意味します。 これは、 main でループを並列化することを意味しますが、各スレッドは n 値の範囲をチェックするだけで、結果として整数のペアを生成できるため、問題ありません。

単一のスレッド内で手動でインターリーブすることも実行可能 です。 おそらく、それぞれが数個のレジスタを使用するだけで、同じ max / maxi 更新できるため、数値のペアのシーケンスを並列に計算する可能性があります。 これにより、 命令レベルの並列性が向上し ます。

トリックは、開始 n 値の別のペアを取得する前にすべての n 値が 1 に達するまで待機するか、または終了条件に到達した1つだけの新しい開始点を取得して、他のシーケンス。 おそらく、各チェーンを有用なデータで機能させ続けることが最善です。そうでない場合は、条件付きでカウンターをインクリメントする必要があります。

n がまだ 1 達していないベクトル要素のカウンターを条件付きでインクリメントするために、SSEのパック比較を使用してこれを行うこともできます。 そして、SIMD条件付きインクリメント実装のさらに長いレイテンシを隠すために、 n 値のより多くのベクトルを空中に保持する必要があります。 おそらく256bベクトル(4x uint64_t )でのみ価値があります。

1 「スティッキー」を検出するための最善の戦略は、カウンターを増分するために追加するすべて1のベクトルをマスクすることだと思います。 したがって、要素に 1 されると、increment-vectorの値はゼロになり、+ = 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

    # There may be a better way to do this blend, avoiding the bypass delay for an FP blend between integer insns, not sure.  Probably worth it
    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 )を使用して、1ステップで複数の n/=2 反復を実行できることを指摘しています。 SSEまたはAVX命令はそれを行うことができないため、SIMDベクトル化よりもおそらく優れています。 ただし、異なる整数レジスタで複数のスカラー 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のcrazy-CISC設計について不満を述べている人々が言及している種類です。 これにより、ISAが今日ほとんどゼロから設計された場合でも、ほとんど同様の方法でx86 CPUが遅くなります。 (つまり、これは速度/電力を要する「x86税」の一部です。)SHRX / SHLX / SARX(BMI2)は大きな勝利です(1 uop / 1cレイテンシ)。

また、クリティカルパス上にtzcnt(Haswell以降では3c)を配置するため、ループで伝達される依存関係チェーンの合計遅延が大幅に長くなります。 ただし、CMOV、または n>>1 保持するレジスタを準備する必要はありません。 @Veedracの答えは、複数の反復に対してtzcnt / shiftを延期することでこれをすべて克服します。これは非常に効果的です(以下を参照)。

その時点で n がゼロになることはないため、 BSF または TZCNT 安全に交換して使用できます。 TZCNTのマシンコードは、BMI1をサポートしないCPUでBSFとしてデコードします。 (無意味なプレフィックスは無視されるため、REP BSFはBSFとして実行されます)。

TZCNTは、それをサポートするAMD CPU上でBSFよりもはるかに優れているため、出力ではなく入力がゼロの場合にZFを設定する必要がない場合でも、 REP BSF を使用することをお勧めします。 -mno-bmi を使用しても __builtin_ctzll を使用すると、一部のコンパイラはこれを行います。

Intel CPUでも同じように動作するので、問題があればバイトを保存してください。 IntelのTZCNT(Skylake以前)は、入力= 0のBSFがその宛先を変更しないままにする文書化されていない動作をサポートするために、BSFと同様に、おそらく書き込み専用の出力オペランドに誤った依存関係があります。 そのため、Skylake専用に最適化しない限り、この問題を回避する必要があります。したがって、追加のREPバイトから得られるものは何もありません。 (Intelは、x86 ISAマニュアルが必要とするものを超えて、頻繁に使用されるべきではない、または遡及的に禁止されているコードを壊さないようにすることがよくあります。たとえば、 Windows 9xはTLBエントリの投機的プリフェッチを想定していません が、これは安全でした IntelがTLB管理ルールを更新する前 に、コードが記述されたとき。

とにかく、HaswellのLZCNT / TZCNTにはPOPCNTと同じ誤った依存関係があります。 このQ&Aを 参照してください。 これが、@ Veedracのコードのgccのasm出力で、dst = srcを使用しない場合に、TZCNTのデスティネーションとして使用しようとしているレジスタで xor-zeroing を使用し てdepチェーンを壊す 理由です。 TZCNT / LZCNT / POPCNTは宛先を未定義または未変更のままにしないため、Intel CPUの出力へのこの誤った依存関係は、純粋にパフォーマンスのバグ/制限です。 おそらく、同じ実行ユニットに送られる他のuopのように動作させるには、いくつかのトランジスタ/電力の価値があります。 ソフトウェアから見える唯一の 利点は 、別のマイクロアーキテクチャの制限との相互作用です。Haswellで インデックス付きアドレス指定モード メモリオペランドをマイクロ融合できます が、LZCNT / TZCNTの誤った依存関係を削除したSkylakeでは、「積層解除」 POPCNTが任意のaddrモードを引き続きマイクロフューズできる一方で、インデックス付きアドレッシングモード。

他の回答からのアイデア/コードの改善:

@hidefromkgbの答えに は、3n + 1の後に1回の右シフトができることが保証されているという素晴らしい観察結果があります。 これは、ステップ間のチェックを省略するよりもさらに効率的に計算できます。 ただし、その答えのasm実装は壊れています(カウント> 1のSHRDの後に定義されていないOFに依存します)、遅い: ROR rdi,2SHRD rdi,rdi,2 よりも速く SHRD rdi,rdi,2 つのCMOV命令を使用しますクリティカルパスでは、並行して実行できる追加のTESTよりも低速です。

整頓された/改善されたC(コンパイラがより良いasmを生成するように導く)をテストし、Godsboltでテストし、より高速なasm(Cの下のコメントで)をテストしました。 (この答えは、Godboltの大きなURLから3万文字の制限に達しましたが、 ショート リンク は腐る可能性が あり、とにかくgoo.glには長すぎました。)

また、文字列に変換して、一度に1つの文字を書き込む代わりに1つの write() を作成するように出力印刷を改善しました。 これにより、パフォーマンスカウンターを記録するために perf stat ./collatz プログラム全体のタイミングへの影響が最小限に抑えられ、重要ではないasmの一部の難読化が perf stat ./collatz れました。

@Veedracのコード

私たち 必要とする限り、右シフトとループの継続チェックから非常に小さなスピードアップを得ました。 limit = 1e8の7.5秒から7.275秒まで、Core2Duo(Merom)で、展開係数は16です。

Godboltの コード+コメント。 このバージョンをclangで使用しないでください。 defer-loopでばかげたことをします。 tmpカウンター k を使用し、それを後で count するために追加すると、clangの動作が変わりますが、それはgccを 少し 傷つけます。

コメントの議論を参照してください:Veedracのコードは、BMI1を搭載したCPUで 優れ ています(つまり、Celeron / Pentiumではありません)


コメントから:

しかし、このコードは決して停止しません(整数オーバーフローのため)!?! イヴ・ダウスト

多くの数値では オーバーフローし ません

それ オーバーフローする 場合 -それらの不運な初期シードの1つについて、オーバーフローした数は別のオーバーフローなしで1に収束する可能性が非常に高くなります。

まだこれは興味深い質問を提起します、いくつかのオーバーフロー循環シード番号はありますか?

単純な最終収束シリーズは、2のべき乗の値で始まります(十分に明らかですか?)。

2 ^ 64はゼロにオーバーフローしますが、これはアルゴリズムによる未定義の無限ループです(1でのみ終了)が、 shr rax ZF = 1 が 生成 されるため、最適な解は終了し ます。

2 ^ 64を生成できますか?開始番号がの場合 0x5555555555555555 、それ は 奇数で、次の番号は3n + 1、つまり 0xFFFFFFFFFFFFFFFF + 1 = 0 です。理論的にはアルゴリズムの定義されていない状態ですが、johnfoundの最適化された答えは、ZF = 1で終了することで回復します。 cmp rax,1 ピーターコルドのは、 無限ループに終了する (QEDバリアント1、不定介して「安っぽい」 0 番号)。

複雑な数はどう 0 ですか? 率直に言って、私は確信していません、私の数学理論は真剣なアイデアを得るにはあまりにもかすんでいる、どのように真剣に対処するか。 しかし、直感的には、3n + 1の式が元の数値(または中間)の2以外のすべての素因数を遅かれ早かれ2の累乗にゆっくりと変えるため、系列はすべての数値に対して1に収束します:0 <数値。 したがって、元のシリーズの無限ループについて心配する必要はありません。オーバーフローのみが妨げになります。

そこで、数個の数字をシートに入れて、8ビットの切り捨てられた数字を見てみました。

3にあふれた値があります 0227170 および 8585 に直接行く 0 、他の2つはに向かって進んで 85 )。

しかし、循環オーバーフローシードを作成する価値はありません。

おかしなことに、私はチェックを行いました。これは、8ビットの切り捨てに苦しむ最初の数であり、すでに 27 影響を受けています! 9232 適切な切り捨てられていないシリーズの 値 に 到達し (最初の切り捨てられた値は 322 12番目のステップにあります)、非切り詰められた方法で2から255個の入力番号のいずれかに到達した最大値は 13120255 それ自体に対して)、最大ステップ数です収束するの 1 は約 128 (+ -2、「1」がカウントするかどうかなどではありません)。

興味深いことに、(私にとって)数 9232 は他の多くのソース番号の最大値ですが、何が特別なのでしょうか? :-O 9232 = 0x2410 ...うーん、わかりません。

残念ながら、私はなぜそれが収束ん、このシリーズのいずれかの深い理解を得ることができないと何にそれらを切り捨てる意義ある k個 のビットは、しかしで cmp number,1 終了条件、それは特定の入力値として終わると、無限ループにアルゴリズムを置くことは確かに可能だ 0 後切り捨て。

しかし、 27 8ビットの場合にオーバーフロー する値 は一種の警告です。これは、値に達するまでのステップ数を数えると、 1 整数のkビットセットの合計から大部分の数について間違った結果が得られる ように見え ます。 8ビット整数の場合、256個のうち146個の数字が切り捨てによってシリーズに影響を与えています(それらの一部は、おそらく偶然に正しいステップ数に達する可能性があり、チェックするのが面倒です)。


パフォーマンスを向上させるための簡単な変更は、n = 3n + 1の後、nが偶数になるため、すぐに2で除算できることです。 また、nは1にならないため、テストする必要はありません。 したがって、いくつかのifステートメントを保存して、次のように記述できます。

while (n % 2 == 0) n /= 2;
if (n > 1) for (;;) {
    n = (3*n + 1) / 2;
    if (n % 2 == 0) {
        do n /= 2; while (n % 2 == 0);
        if (n == 1) break;
    }
}

ここに 大きな 勝利があります。nの最下位8ビットを見ると、2で8で割るまでのすべてのステップは、それらの8ビットによって完全に決定されます。 たとえば、最後の8ビットが0x01の場合、それは2進数で、数値は????です。 0000 0001次のステップは次のとおりです。

3n+1 -> ???? 0000 0100
/ 2  -> ???? ?000 0010
/ 2  -> ???? ??00 0001
3n+1 -> ???? ??00 0100
/ 2  -> ???? ???0 0010
/ 2  -> ???? ???? 0001
3n+1 -> ???? ???? 0100
/ 2  -> ???? ???? ?010
/ 2  -> ???? ???? ??01
3n+1 -> ???? ???? ??00
/ 2  -> ???? ???? ???0
/ 2  -> ???? ???? ????

したがって、これらすべてのステップは予測可能であり、256k + 1は81k + 1に置き換えられます。同様のことが、すべての組み合わせで発生します。 したがって、大きなswitchステートメントでループを作成できます。

k = n / 256;
m = n % 256;

switch (m) {
    case 0: n = 1 * k + 0; break;
    case 1: n = 81 * k + 1; break; 
    case 2: n = 81 * k + 1; break; 
    ...
    case 155: n = 729 * k + 425; break;
    ...
}

n≤128までループを実行します。その時点で、nは8未満の2除算で1になる可能性があり、一度に8以上のステップを実行すると、初めて1に到達するポイントが失われます。 次に、「通常の」ループを続行します。または、1に到達するためにさらに多くのステップが必要なことを示すテーブルを用意します。

PS。 Peter Cordesの提案がそれをさらに速くするだろうと強く疑います。 条件分岐は1つを除いてまったく存在せず、ループが実際に終了する場合を除き、その分岐は正しく予測されます。 したがって、コードは次のようになります

static const unsigned int multipliers [256] = { ... }
static const unsigned int adders [256] = { ... }

while (n > 128) {
    size_t lastBits = n % 256;
    n = (n >> 8) * multipliers [lastBits] + adders [lastBits];
}

実際には、nの最後の9、10、11、12ビットを一度に処理する方が速いかどうかを測定します。 ビットごとに、テーブル内のエントリの数が2倍になり、テーブルがL1キャッシュに収まらなくなったときに速度が低下します。

PPS。 操作の数が必要な場合:各反復で、正確に8の2除算と可変数(3n + 1)の操作を行うため、操作をカウントする明白な方法は別の配列になります。 しかし、実際にステップ数を計算できます(ループの反復回数に基づいて)。

問題をわずかに再定義できます。奇数の場合はnを(3n + 1)/ 2に置き換え、偶数の場合はnをn / 2に置き換えます。 その後、すべての反復で正確に8ステップが実行されますが、不正行為と見なすことができます:-)したがって、n個の操作n <-3n + 1とs個の操作n <-n / 2があると仮定します。 n <-3n + 1はn <-3n *(1 + 1 / 3n)を意味するため、結果は非常に正確にn '= n * 3 ^ r / 2 ^ sになります。 対数を取ると、r =(s + log2(n '/ n))/ log2(3)になります。

n≤1,000,000までループを実行し、n≤1,000,000の開始点から必要な反復回数を事前に計算したテーブルがある場合、上記のようにrを計算して最も近い整数に丸めると、sが本当に大きくない限り正しい結果が得られます。





x86