コンパイラを信頼する: モダンC++

コンパイラを信頼する C++プログラマーは、経験則として多くのパフォーマンスに関する知恵を吸収します。高速逆平方根1、XORスワップ2、手動アンロールループ3、ダフのデバイス4、例外は遅い、仮想呼び出しは遅い、除算は遅い、ルックアップテーブルはしばしば数学よりも優れている、などです。これらがかつて真実であったとしても、ハードウェア、ソフトウェア、コンパイラの進歩により状況は劇的に変化し、多くは現在では当てはまりません。John CarmackのDEC AlphaやPentium Proは、現代のZen 5 x86_64コアとはほとんど似ていません。そのブランチ予測子だけでも、当時のiDのオフィスにあった全ワークステーションよりも多くのトランジスタを含んでいる可能性があります。さらに、LLVMのClangやGNUのGCCは、単純な入力から最適なコードを生成するほど高度になっています。例えば、両方のコンパイラには、コードセグメントが実際にはpopcountの偽装であるかどうかをチェックする最適化パスがあります5。実際、「賢い」コードを書くことは、「悪い」コードになる可能性があります。それはオプティマイザーから意図を不明瞭にし、ベクトル化、インライン化、ターゲット固有のローリングを失う可能性があります。この記事では、いくつかの古いトリックを取り上げ、それらを明白なバージョンと比較し、それらがどのように振る舞うかを見ていきます。以下の数値は、以下の環境で生成されました。 Ubuntu 24.04 LTS (Linuxカーネル 6.18.1更新済み) AMD Ryzen 9 9950X, 16コア / 32スレッド 128 GB DDR5/3600メモリ Clang 21.1.1, -O3 -ffast-math -mtune=native この投稿にはベンチマークコードが付属しています。すべてのベンチマークはGoogle Benchmarkを使用しています。 6 内容 パート1: 新しい犬、古いトリック 高速逆平方根 Popcountとビット操作 数値レシピと行ポインタ const& everywhere vs forwarding intent パート2: ライブラリ Rangesとアルゴリズム 例外 vs std::expected vs エラーコード 仮想ポリモーフィズム vs 静的ポリモーフィズム ベンチマークの使用方法 締めくくり パート1: 新しい犬、古いトリック 高速逆平方根 Quake III7のQ_rsqrtをここに再現します。 float Q_rsqrt( float number ) { long i; float x2, y; const float threehalfs = 1.5F; x2 = number * 0.5F; y = number; i = * ( long * ) &y; i = 0x5f3759df - ( i >> 1 ); y = * ( float * ) &i; y = y * ( threehalfs - ( x2 * y * y ) ); return y; } この仕組みを説明する記事は数多くあります1が、ここでは省略します。要するに、90年代後半のCPUの浮動小数点ユニットは今日のものとは全く異なっていました。Quake 3 Arenaの開発中、iDの開発者は、頂点法線（新しいライティングモデルに使用）を決定するのに多くの時間が費やされていることを発見しました。この時間の多くは、1つの操作、つまり逆平方根に費やされていました。彼らのアプローチは、精度を犠牲にし、この1つの操作に対して「推定して改善する」アプローチを取ることでした。これは、単純な1.0f / sqrtf(x)を大幅に上回ることができました。8087 FPUでは、FSQRTとFDIVは500サイクル以上かかることがありましたが、iDの方法では安価な整数演算と1回のニュートン反復を使用していました8。 現代のCPU IntelはSSE9でx86ファミリーのアーキテクチャにrsqrtssとrsqrtpsを導入しました。AVXは後に、より広いSIMD幅のためにvrsqrtssとvrsqrtpsの形式を追加しました。これらの命令は、近似逆平方根を直接計算し、文書化されたエラーバウンドを持ち、x87 fsqrt10よりも大幅に低いレイテンシを持ちます。ARMv8/AArch64には、同等の逆平方根推定命令があります11。 命令 x86-64 SSE x86-64 AVX ARMv8 NEON スカラー rsqrtss vrsqrtss frsqrte (スカラー) SIMD (4x f32) rsqrtps vrsqrtps frsqrte4 x f32 なぜこれが重要なのか？ 現代のC++でこのコードを書くと、次のようになるかもしれません。 constexpr float Q_rsqrt(float number) noexcept { static_assert(sizeof(float) == sizeof(std::uint32_t)); auto i = std::bit_cast<std::uint32_t>(number); auto magic = 0x5f3759dfu - (i >> 1); auto y = std::bit_cast<float>(magic); return y * (1.5f - (number * 0.5f * y * y)); } 単純なバージョンと比較してください。 constexpr float naive_rsqrt(float x) noexcept { return 1.0f / std::sqrt(x); } 次に、Compiler ExplorerでClang 21.1.0を使用して-std=c++23 -O3 -ffast-math -march=znver4で生成された関連アセンブリを比較します。ベンチマーク実行では-march=nativeが使用されました。アセンブリ抜粋はznver4を使用しているため、ターゲットは明示的です。-ffast-mathの部分は重要です。これは、コンパイラが積極的で潜在的に損失のある浮動小数点仮定を可能にします1213。そのため、この例では正の有限入力が仮定され、すべての厳密なIEEE浮動小数点エッジケースは保持されません。 Q_rsqrt(float): movd eax, xmm0 sar eax mov ecx, 1597463007 sub ecx, eax mulss xmm0, dword ptr [rip + .LCPI0_0] movd xmm1, ecx movdqa xmm2, xmm1 mulss xmm2, xmm1 mulss xmm0, xmm2 addss xmm0, dword ptr [rip + .LCPI0_1] mulss xmm0, xmm1 ret naive_rsqrt(float): vrsqrtss xmm1, xmm0, xmm0 vmulss xmm0, xmm0, xmm1 vfmadd213ss xmm0, xmm1, dword ptr [rip + .LCPI1_0] vmulss xmm1, xmm1, dword ptr [rip + .LCPI1_1] vmulss xmm0, xmm1, xmm0 ret ベンチマーク 理論的には理にかなっていますが、それは今でも本当でしょうか？ 操作 スカラー時間 配列カーネル (n=1024) 時間 配列カーネル (n=65536) 時間 Q_sqrt 380 ns 24.5 ns 1865 ns naive_rsqrt 373 ns 25.0 ns 2161 ns スカラーケースは実質的に引き分けで、明白なバージョンがわずかに先行しています。配列カーネルでは、Quakeバージョンはこの特定の実行ではいくぶん高速ですが、トリックをデフォルトとして正当化するほどではありません。ソースは不明瞭で、有用なドメインが狭く、コンパイラとCPUがすでに大変な作業を行っているからこそ競争力があるのです。さらに、単純な方法ではエラーの明示的な境界が提供されます。 持ち帰り コンパイラに作業を任せましょう。同等のパフォーマンス、より明確なコード、そして意味するところを伝える実装が得られます。 Popcountとビット操作 C++20は<bit>を提供しました。std::popcount, std::countl_zero, std::countr_zero, std::bit_width, std::has_single_bitなどです14。x86では、関連するターゲット機能が有効になっている場合、これらの多くは単一の命令にマッピングされます。 関数 x86-64 (BMI/POPCNT) ARMv8 std::popcount popcnt cnt + add std::countl_zero lzcnt clz std::countr_zero tzcnt rbit + clz 比較: constexpr int modern(std::uint64_t x) noexcept { return std::popcount(x); } constexpr int kernighan(std::uint64_t x) noexcept { int c = 0; while (x != 0U) { x &= x - 1U; ++c; } return c; } constexpr int swar(std::uint64_t x) noexcept { x = x - ((x >> 1) & 0x5555'5555'5555'5555ULL); x = (x & 0x3333'3333'3333'3333ULL) + ((x >> 2) & 0x3333'3333'3333'3333ULL); x = (x + (x >> 4)) & 0x0f0f'0f0f'0f0f'0f0fULL; return static_cast<int>((x * 0x0101'0101'0101'0101ULL) >> 56); } -march=native と popcnt が利用可能な場合、pop_modern は 1 つの命令になります。さらに興味深いのは、現代のコンパイラが古いトリックを popcount として認識する可能性があることです。このベンチマーク構成では、Kernighan ループと SWAR バージョンも popcnt に折りたたまれます。ターゲット命令がない場合、区別が戻ってきます。Kernighan はデータ依存ループですが、SWAR はシフトとマスクの短いシーケンスです。標準的なスペルは、どちらの場合も意図を明示します。 C++20 より前は、GCC/Clang で __builtin_popcountll、MSVC で __popcnt64 を使用できました。std::popcount はポータブルなスペル15であり、ハードウェア popcnt がないターゲットでは、実装は効率的なソフトウェアフォールバックを提供できます。 ベンチマーク 操作 時間 BM_popcount_modern 94.5 ns BM_popcount_kernighan 94.5 ns BM_popcount_swar 94.5 ns 持ち帰り <bit> を使用してください。ただし、それを含まないフリースタンディング組み込み環境をターゲットにしている場合を除きます。 数値レシピと行ポインタ 継承された知恵の一部は、行列の行ポインタアクセスがインデックス計算よりも高速であるということです。これは、乗算が高価で、アドレス生成ハードウェアが能力が低く、コンパイラがインデックス計算を簡略化する余地が少なかった頃は信じやすかったです。Numerical Recipes in C — Pressらによる有名な赤い本 — もこのスタイルを広めるのに役立ちました。そのdmatrix/nrutilヘルパーは、アルゴリズムを行インデックスで記述できるように行間接参照を使用し、数学的表記を維持し、Fortranからの転写をより直接的にします。それは妥当なインターフェースの選択肢になり得ますが、それ自体はパフォーマンスの向上ではありません。興味のある読者のために、ベンチマークコードには行列クラスの実装が3つ含まれています。flat_matrix (アクセスは乗算で行われ、連続したd