C ++での長演算の最適化

明けましておめでとうございます！ アセンブラーインサートを使用したC ++での長い演算の最適化-古典的なプロットについて説明します。 しかし、Habréではまだそうではなかったので、少しためらってここに投稿することにしました。あなたがかつて同じことを書いて、私より先に進んだなら、あなたは私を許します:-)


フィールドをvoid * words-mass words、int wc-long intを表すBigIntクラスで配列内の単語数を宣言します。バイト単位の単語長はコンパイル段階で設定されます。 純粋なC ++での加算の実装は次のようになります。

... typedef unsigned int uInt; typedef unsigned long long int uLong; #define MAX_uInt ((uInt)(-1)) #define MUL ((uLong)MAX_uInt) // MUL: Max_uInt in Unsigned Long int BigInt::WS = sizeof(uInt); BigInt & BigInt::operator+=(const BigInt &rhs) { ... //  ,   uLong carry = 0; for ( uInt *th = (uInt*)words, *oz = (uInt*)rhs.words, *limit = oz + rhs.wc, *thl = th + wc; oz < limit || carry && th < thl; oz++, th++) { uLong t = carry + *th; t += oz < limit ? *oz : 0; if (t > MUL) { carry = 1; t &= MUL; } else carry = 0; *th = (uInt)t; } if (carry) { ... //     } return *this; } 

Cは問題の解決にはあまり適していないことがわかります。1つのオーバーフロービットの余地がないため、一度に8バイトを追加することはできません。

プロセッサが長整数のワードの配列から4バイトごとに追加するのに費やすクロックサイクルの数を検討します。 このようなもの：

 struct timespec t1, t2; BigInt *a = ..., *b = ...; //    - 400 clock_gettime(CLOCK_MONOTONIC_RAW, &t1); for (int j = 0; j < 10000000; j++) { *a += *b; *a -= *b; } clock_gettime(CLOCK_MONOTONIC_RAW, &t2); printf(...); //   t1  t2 

GCC最適化キーの進捗は次のとおりです。

-O1	-O2	-O3
7	6	6

アセンブラー挿入を使用して、加算メソッドの本体を書き直します。

 // uInt  int  long long int BigInt & BigInt::operator+=(const BigInt &rhs) { ... //  ,   uInt *th = (uInt*)words, *oz = (uInt*)rhs.words; asm goto ( "clc\n" "l1:\t" "mov\t(%[oz]), %[ax]\n\t" "adc\t%[ax], (%[th])\n\t" "lahf\n\t" "add\t%[ws], %[th]\n\t" "add\t%[ws], %[oz]\n\t" "sahf\n\t" "loop\tl1\n\t" "jnc\t%l[nocarry]\n" : : [th] "r" (th), [oz] "r" (oz), [ws] "I" (sizeof(uInt)), [ax] "a" ((uInt)0), "c" (wc) : : nocarry ); ... //     nocarry: return *this; } 

将来、コンパイル結果をすぐに書きます（uInt for long long intの場合）：

 ... clc lo: mov (%rbx), %rax adc %rax, (%rdx) lahf add $8, %rdx add $8, %rbx sahf loop lo jnc nocarry ... 

ここで何が起こっているかについて簡単に説明します。bxおよびdxレジスタには現在のワードへのポインタが含まれています。adcはソース、レシーバ、オーバーフローフラグを追加する非常に便利な命令です。 lahfおよびsahfは基本フラグを保存およびロードします-addはオーバーフローフラグをリセットするため、これらの命令が必要です。 ループは、cxレジスタで実行する回数だけ繰り返します。

これはまさに（正直に）最初に書いたものです。 このオプションは、両方のバージョンでそれぞれ7サイクル、「ロングバージョン」で4バイトごとに3.5サイクル実行されます。 GCCはまだ最高の状態ですが、結果のアセンブラはまだ最適化および最適化されていません。

。

悪い噂はループ文を回避します。 特にほとんど費用がかかりませんので、それなしで試してください：

 ... clc lo: mov (%rbx), %rax adc %rax, (%rdx) lahf add $8, %rdx add $8, %rbx sahf dec %rcx jnz lo jnc nocarry ... 

結果は5（2.5）メジャーです！ ループを使用しないでください-行を節約しますが、各反復で最大2クロックサイクルを消費します。

。

ポインタの増加に対処したい-CF（キャリーフラグ-「転送」のフラグ、オーバーフロー）に触れない方法はありませんか？ 幸いなことに、lea命令はメモリ参照を計算し、フラグに触れることなくレシーバレジスタに格納します。 これを使用してポインターをインクリメントする方法は次のとおりです。

 ... clc lo: mov (%rbx), %rax adc %rax, (%rdx) lea 8(%rdx), %rdx lea 8(%rbx), %rbx dec %rcx jnz lo jnc nocarry ... 

本質的に

  lea 8（％rdx）、％rdx 

と同じ

  $ 8、％rdxを追加 

-ワードサイズをレジスタに追加します。

このオプションでは、プロセッサは2クロックサイクル（4バイトごとに1クロックサイクル）を消費します。 率直に言って、lahf / sahfにそれほど時間がかかるとは思っていませんでした。

。

次に何をする？ SSEは 、残念ながらここでは役に立ちません。64ビットアーキテクチャが使用されている限り、存在しないpadc xmm 、 xmm命令は、基本的に2つの通常の加算のシーケンスと同じマイクロ命令のストリームを生成しますが、オーバーフロー加算を並列化することは不可能です。 正確には、2つの追加を連続して記述し、アセンブラーサイクルを展開する必要があることを意味します。 ゴールデン最適化のトリック。

 // WS = 16 ... clc lo: mov (%rbx), %rax adc %rax, (%rdx) mov 8(%rbx), %rax adc %rax, 8(%rdx) lea 16(%rbx), %rbx lea 16(%rdx), %rdx dec %rcx jnz lo jnc nocarry ... 

現在、1反復は3サイクルで実行されます。これは、4バイトあたり0.75サイクルに相当します。

やった！ GCC -O2は8回行われました！ さらに考える時間はありません！ これからもまたすべて！