LLVMのパワーと、アセンブラーに対する高レベル言語の利点についての短い話を共有したいと思います。
私はParity Technologiesで働いており
、Parity Ethereum clientをサポートし
ています 。 このクライアントでは、ハードウェアでサポートされているハードウェアがないため、ソフトウェアレベルでエミュレートする必要がある高速256ビット演算が必要です。
長い間、2つの算術実装を並行して行ってきました。1つは安定したアセンブリ用のRustで、もう1つは組み込みアセンブラコード(ナイトリーバージョンのコンパイラで自動的に使用されます)です。 これは、256ビットの数値を64ビットの配列として格納するためです
u64
では、2つの64ビットの数値を乗算して64ビットを超える結果を得る方法はありません(Rustの整数型は
u64
しか到達しないため)。 これは、x86_64(メインのターゲットプラットフォーム)が64ビットの数値で128ビットの計算結果をネイティブにサポートしているという事実にもかかわらずです。 したがって、各64ビット数を2つの32ビット数に分割します(2つの32ビット数
を乗算して64ビットの結果を取得できるため)。
impl U256 { fn full_mul(self, other: Self) -> U512 { let U256(ref me) = self; let U256(ref you) = other; let mut ret = [0u64; U512_SIZE]; for i in 0..U256_SIZE { let mut carry = 0u64;
コードがどれほど最適でないかを知るためにコードを理解する必要さえありません。 コンパイラの出力を確認すると、生成されたアセンブラコードが非常に最適ではないことがわかります。 基本的にRustの制限を回避するために、多くの追加作業を行います。 したがって、組み込みアセンブラーでコードのバージョンを作成しました。 x86_64は、最初に2つの64ビット値の乗算をサポートして128ビットの結果を得るため、アセンブラーコードのバージョンを正確に使用することが重要です。 Rustが
a * b
とき、
a
と
b
が
u64
形式の場合、プロセッサは実際にそれらを乗算して128ビットの結果を取得し、Rustは上位64ビットをスローします。 これらの64個の上位ビットを残し、それらに効果的にアクセスする唯一の方法は、組み込みアセンブラコードを使用することです。
ご想像のとおり、アセンブリ言語の実装ははるかに高速であることがわかりました。
名前u64.bench ns / iter inline_asm.bench ns / iter diff ns / iter diff%スピードアップ
u256_full_mul 243.159 197.396 -45.763 -18.82%x 1.23
u256_mul 268.750 95.843 -172.907 -64.34%x 2.80
u256_mul_small 1.608 789-819 -50.93%x 2.04
u256_full_mul
は上記の関数をチェックし、
u256_mul
は256ビットの結果を得るために2つの256ビットの数値を乗算します(Rustでは512ビットの結果を作成して上半分を破棄しますが、アセンブラーでは別の実装があります)、
u256_mul_small
は2つの小さな256ビットの
u256_mul_small
乗算します数字。 ご覧のとおり、アセンブラコードは2.8倍高速です。 それははるかに優れています。 残念なことに、これは夜間バージョンのコンパイラでのみ機能し、x86_64プラットフォームでも機能します。 真実は、アセンブラの「少なくとも」2倍の速度でRustコードを作成するのに多くの努力と多くの失敗した試みが必要だったということです。 必要なデータをコンパイラに渡す良い方法がまったくありませんでした。
Rustバージョン
1.26ではすべてが変更されました。 これで
a as u128 * b as u128
書くことができます-コンパイラはx86_64プラットフォームにネイティブなu64からu128への乗算を使用します(両方の数値を
u128
変換しても、それらは「実際に」すべて
u64
であると理解し、結果
u128
が必要
u128
)。 つまり、コードは次のようになります。
impl U256 { fn full_mul(self, other: Self) -> U512 { let U256(ref me) = self; let U256(ref you) = other; let mut ret = [0u64; U512_SIZE]; for i in 0..U256_SIZE { let mut carry = 0u64; let b = you[i]; for j in 0..U256_SIZE { let a = me[j];
これはほぼ確実にLLVMのネイティブ
i256
タイプよりも遅いですが、速度は非常に向上しています。 ここで、元のRust実装と比較します。
名前u64.bench ns / iter u128.bench ns / iter diff ns / iter diff%スピードアップ
u256_full_mul 243.159 73.416 -169.743 -69.81%x 3.31
u256_mul 268.750 85.797 -182.953 -68.08%x 3.13
u256_mul_small 1.608 558 -1.050 -65.30%x 2.88
最も注目すべき点は、安定したバージョンのコンパイラで速度が向上したことです。 安定したバージョンのクライアントバイナリのみをコンパイルするため、以前はソースからクライアントをコンパイルしたユーザーのみが速度の利点を得ることができました。 したがって、現在の改善は多くのユーザーに影響を及ぼしています。 しかし、ちょっと、それだけではありません! 256ビットの結果を得るために256ビットの数値を乗算するテストでさえ、アセンブラーでの実装を大幅にマージンを超えてコンパイルした新しいコードです。 これは、Rustコードが最初に512ビットの結果を生成し、次に上半分を破棄し、アセンブリ言語がそれを行わないという事実にもかかわらずです。
名前inline_asm.bench ns / iter u128.bench ns / iter diff ns / iter diff%スピードアップ
u256_full_mul 197.396 73.416 -123.980 -62.81%x 2.69
u256_mul 95.843 85.797 -10.046 -10.48%x 1.12
u256_mul_small 789558 -231 -29.28%x 1.41
完全な乗算では、特に元のコードが高度に最適化されたアセンブラーの呪文を使用していたため、これは非常に強力な改善です。 生成されたアセンブラーに飛び込むので、ここでかすかな心が消えます。
これは手書きのアセンブラコードです。 コンパイラーによって実際に作成されたバージョンにコメントしたいので、コメントなしでそれを提示しました(お分かりのように、
asm!
は予想以上に隠れるので):
impl U256 {
そして、それが生成するものです。 人生でアセンブラーを操作したことがない場合でも何が起こるかを理解できるように、コードについて大量にコメントしましたが、メモリとレジスタの違いなど、低レベルプログラミングの基本的な概念を知っておく必要があります。 CPU構造に関するチュートリアルが必要な場合
は、プロセッサの構造と実装に関するWikipediaの記事から始めることができ
ます 。
bigint::U256::full_mul:
コメントからわかるように、コードには多くの欠陥があります。 乗算はレジスタからではなくメモリからの変数によって行われ、不必要なストアおよびロード操作が実行されます。また、CPUは「実際の」コードを受信する前に大量のストアおよびロードを強制されます(乗算加算サイクル)。 これは非常に重要です。CPUは計算と並行して保存と読み込みを実行しますが、コードはすべてが読み込まれるまでCPUが計算を開始しないように書かれています。 これは、
asm
マクロが多くの詳細を隠すためです。 基本的に、必要な場所に入力を配置し、文字列操作を使用してアセンブラコードに代入するようにコンパイラに指示します。 コンパイラーはすべてをレジスターに保存しますが、入力配列をメモリー(入力パラメーターの前の
"m"
)に入れて、すべてを再びメモリーにロードするように命令します。 このコードを最適化する方法はありますが、経験豊富な専門家でも非常に困難です。 そのようなコードはエラーを起こしやすいです-出力レジスタを一連の
xor
命令でリセットしなかった場合、コードは時々失敗しますが、常にではなく、呼び出し関数の内部状態に依存する一見ランダムな値を生成します。
"m"
を
"r"
置き換えることでおそらく高速化できます(古いアセンブラーコードが非常に遅い理由を記事で確認し始めたときのみ発見したため、テストしませんでした)が、ソースを見ることは明らかではありません。 LLVMアセンブラ構文の深い知識を持つ専門家のみがすぐに理解できます。
比較のために、
u128
を使用したRustコードは非常に明確に見えます:書かれているのはあなたが得るものです。 最適化を目指していなかったとしても、おそらく最も簡単な解決策と似たようなものを書くでしょう。 同時に、LLVMコードは非常に高品質です。 手で書かれたコードとそれほど違わないことに気付くかもしれませんが、いくつかの問題を解決し(以下で説明)、また私が考えもしない最適化をいくつか含んでいます。 彼が見落としていた重要な最適化は見つかりませんでした。
生成されたアセンブラコードは次のとおりです。
bigint::U256::full_mul:
生成されたLLVMバージョンにはさらにいくつかの命令がありますが、最も遅いディレクティブ(ロードとストア)の数は最小限に抑えられます。 ほとんどの場合、LLVMは冗長な作業を回避し、多くの大胆な最適化も適用します。 その結果、コードははるかに高速に実行されます。
慎重に作成されたRust実装がビルドコードを超えたのはこれが初めてではありません。 数か月前、Rustでの加算と減算の実装を書き直し、アセンブリ言語に比べてそれぞれ20%と15%加速しました。 そこでは、
u64:: checked_add/ checked_sub
コードを超えるために128ビット演算は必要ありませんでした(Rustで完全なハードウェアサポートを使用するには、
u64:: checked_add/ checked_sub
を指定するだけです)。
ここでこの例からのコードを見ることができ
ます 、そして、
ここで加算/減算を実装するためのコードを見ることができ
ます 。 後者はすでにアセンブラーでの実装よりも乗算の優位性をベンチマークで示していますが、これは実際にはほとんどの場合ベンチマークが0による乗算を実行したという事実によるものです。 これから教訓が得られる場合、この情報に基づいた最適化は、代表的なベンチマークなしでは不可能です。
LLVMの最適化方法を勉強し、アセンブラコードのバージョンを手動で書き直す必要はないと思います。重要なのは、コンパイラの最適化はすでに本当に優れているということです。彼らは非常に賢い人によって書かれており、コンピューターは、人々がそれをかなり難しいと感じる最適化のタイプ(数学的な意味で)で本当に優れています。言語開発者の仕事は、オプティマイザーに可能な限り完全に通知するために必要なツールを提供することであり、真の意図は何か、そしてより大きな整数サイズはこれに向けた別のステップです。Rustは、プログラマーが人とコンパイラーの両方にとって理解しやすいプログラムを作成するための素晴らしい仕事をしてきました。主に彼の成功を決定したのはこの力でした。