通常示される理由は、現代の中央処理装置には非常に多くのパイプラインと制御の競合があり、対処する必要があるため、単純なアセンブラー・プログラムはそれらを処理するときにうまく機能しないことです。
しかし、そうですか？ インターネット上の一部の人の言葉を聖書の啓示として信じるだけでなく、少し実験して調べてみましょう。
単純なコードを取り、レビューするだけです。 エキゾチックな組み込み関数から大きな利益を得ることができる例を選択するつもりはありません。 代わりに、古い標準のクイックソートを使用します。
テストするC ++のクイッククイックソートを次に示します。
struct Item { int key; int value; }; extern "C" void sortRoutine(Item *items, int count) { if (count <= 1) return; // already sorted if only zero/one element // Pick the pivot. Item pivot = items[count-1]; int low = 0; for (int pos=0;pos<count-1;pos++) { if (items[pos].key <= pivot.key) { // swap elements Item tmp = items[pos]; items[pos] = items[low]; items[low] = tmp; low++; } } items[count-1] = items[low]; items[low] = pivot; sortRoutine(items, low); sortRoutine(items+low+1, count-1-low); }
異常なことは何もありません。 これは世界で最高のソートアルゴリズムではありません。また、これは最適な実装でさえありませんが、単純であり、その仕事はうまくいきます。
ここで、このアプローチの簡単な実装をアセンブラーで直接実行してみましょう。
sortRoutine: ; rcx = items ; rdx = count sub rdx, 1 jbe done ; Pick the pivot. mov r8, [rcx+rdx*8] ; r8 = pivot data xor r9, r9 ; r9 = low xor r10, r10 ; r10 = pos partition: cmp [rcx+r10*8], r8d jg noswap ; swap elements mov rax, [rcx+r10*8] mov r11, [rcx+r9*8] mov [rcx+r9*8], rax mov [rcx+r10*8], r11 inc r9 noswap: inc r10 cmp r10, rdx jb partition ; move pivot into place mov rax, [rcx+r9*8] mov [rcx+rdx*8], rax mov [rcx+r9*8], r8 ; recurse sub rdx, r9 lea rax, [rcx+r9*8+8] push rax push rdx mov rdx, r9 call sortRoutine pop rdx pop rcx test rdx, rdx jnz sortRoutine done: ret
主にIntelメモリ用の柔軟なアドレス指定演算子により、非常に簡単に記述できました。 興味深いことに、私は計画、パイプライン化などに注意を向けようとはしませんでした。 これを単純なアセンブラプログラムとして作成しました。
次に、費やした時間を評価しましょう。 1,000,000個のアイテムの配列を並べ替える簡単なテストプログラムを作成しました。 テストは100回実行され、セット全体で最良の値が取得されました。 C ++バージョンは、gcc 4.8.1、clang 3.8.0、およびMSVC 2013を使用してコンパイルされました。
結果
sort_cpp_recurse_gcc.exe : 99 - 100 sort_cpp_recurse_clang.exe : 99 - 100 sort_cpp_recurse_ms.exe : 98 - 100 sort_asm_recurse.exe : 92 - 100
まあ、それは面白いです。 異なるコンパイラは基本的に同じ結果をもたらしますが、MSVCよりもわずかに有利です。 しかし、アセンブラのバージョンは明らかに高速です -この場合、ほぼ7％です。
事は、C ++では、基礎となるマシンの良いビューが常にあるとは限らないということです。 これは変数に関しては正常ですが、スタックの表現は非常に限られています。 C ++は、呼び出しにのみスタックを使用できると考えていますが、実際には、スタックをデータスタックとして使用することができます。
何が起こるか見てみましょう。 sortRoutineへの再帰呼び出しを削除し、代わりにスタックから直接データ範囲を抽出します。 これにより、実際に再帰に頼ることなく、単一のループで作業することができます。 多くの場合、このアプローチは、機能への入り口/出口からの時間損失を排除するため、大きな利点をもたらすことができます。
対応するプログラムは、以下のアーカイブファイルで入手できます。
sort_cpp_recurse_gcc.exe : 99 - 100 sort_cpp_recurse_clang.exe : 99 - 100 sort_cpp_recurse_ms.exe : 98 - 100 sort_asm_recurse.exe : 92 - 100 sort_cpp_iter_gcc.exe : 106 - 100 sort_cpp_iter_clang.exe : 97 - 100 sort_cpp_iter_ms.exe : 95 - 100 sort_asm_iter.exe : 92 - 100
面白い。 アセンブラバージョンでもほぼ同じ結果が得られました。 これは、反復的なアプローチによって関数の操作の損失が排除されるが、手書きバージョンのx64でのこのような損失は実際には小さいため、利益がないという事実によるものと考えます。
ただし、C ++バージョンの場合、状況は異なります。 ほとんどは速度のわずかな増加を示しましたが、gccは明らかに遅いです！ 分解からわかる限り、制御はそれ自体を混乱させようとしているように構築されます。 制御ルートの増加と関連する付加機能により、複雑な「ジャグリング」が発生しました。
これらのテストは、デフォルトの呼び出し規則がfastcallであるx64でコンパイルしました。 代わりに、cdeclスタックに基づく契約を使用して32ビットバージョン用にソリューションをコンパイルした場合、非再帰バージョンの方が比較的良い結果になると考えています。 試したことはありません-読者のための演習として残しておきます。
おわりに
「現代のコンパイラは、アセンブラで書いたプログラムよりも常に速い」という古い言い回しは必ずしも正しいとは思えません。
ただし、コンパイラーが十分にその仕事をすることは正しいことであり、コードを扱う方が簡単です。 したがって、もう少し速度を絞ることは可能ですが、メンテナンスに関連する新たな困難のために、これはほとんど正当化されません。
アセンブラーのバージョンはまだ高速でした。 この投稿で自分に役立つものを見つけた場合、インターネット上の人々 が完全に間違っていることを言うことがあると思います。
素材
sorttest.zip-この記事で使用されるすべてのコード。