HN 日本語サマリー

← 一覧へ戻る
プログラミング

現代C++ CPUのための効率的なC++プログラミング、第4章/パート2

Efficient C++ Programming for Modern C++ CPUs, Chapter 4/part 2 (6it.dev)

36 pointsby birdculture4 コメント

要約

本記事は、近刊書籍からの草稿として、現代の64ビットCPUにおける様々なC++操作のCPUサイクルコストを詳細に解説しています。特に、整数乗算と除算が他の整数演算よりも著しく高価である点を強調し、RTTI、C++例外(エラーが稀なケースでは「ゼロコスト例外」が有利)、アトミック操作、そしてインライン化を含む関数呼び出しのパフォーマンスへの影響について議論しています。著者は、マイクロベンチマークの代わりに、操作コストの包括的な図を提供することを目指していますが、数値はおおよそのオーダーであることを注意しています。

全文翻訳

インフォグラフィック:CPUクロックサイクルにおける操作コスト、第2弾

これは、Sherry IgnatchenkoとDmytro Ivanchykhinによる近刊書「Efficient C++ Programming for Modern 64-bit CPUs」の第1巻、第4章「CPU物理学とCPUサイクルについて」の第2部の下書きです。事実上の不整合を見つけた場合は、遠慮なくコメントしてください。修正させていただきます。

第4章の第1部については、https://6it.dev/blog/infographics-operation-costs-in-cpu-clock-cycles-take-2-80736 を参照してください。

[画像: インフォグラフィック:CPUクロックサイクルにおける操作コスト、第2弾 - 画像1]

冷徹な数字

上記の情報(および[Ignatchenko16a]、[Fog]、その他下記にリストされた情報源からの情報を追加)を基に、多くの実用的な目的でマイクロベンチマークに取って代わる、非常に重要な図を作成し、開発者の語彙で最も一般的な操作のコストを示すことができます。

免責事項:以下の数値はすべて、桁レベルでのみ正確です!

ここで、上記で議論されていない項目がいくつかあり、追加の説明が必要になる場合があります。

乗算 / 除算

利用可能なR-R操作の中で、乗算、特に除算はパフォーマンスの観点から非常に特殊です。乗算と除算以外のすべての整数演算は「Darn Cheap™」(非常に安い)です。通常、レイテンシは1サイクル、あるいはCPU設計者によって重要度が低いと判断された演算であれば2CPUサイクルです。さらに、乗算と除算以外の演算では、オペランドのビット幅によってパフォーマンスに違いが生じることはほとんどありません。つまり、乗算と除算以外の演算は、8ビット、16ビット、32ビット、64ビットのオペランドに対してほぼ同じ時間を要します。

対照的に、乗算は3〜5CPUサイクルを要し、さらに、32ビットと64ビットのオペランドで異なるCPUサイクル数を要する場合があります。除算はさらに悪く、最新のCPUでも64ビット除算に最大15CPUサイクルを要することがあります(そして、これらの数値でさえ感謝すべきです。[Fog]では100サイクル以上とリストされています、痛い!)。より最近のCPUでは、[uops]と[Cortex-A78]が以下の操作レイテンシ(CPUサイクル単位)を提供しています。

Skylake-X (2017)Zen 2 (2019)Cortex-A78 (2020)Alder Lake-P (2021)Alder Lake-E (2021)Zen 4 (2022)
Archx64/Intelx64/AMDAArch64x64/Intelx64/Intelx64/AMD
IMUL R32, R32332 (MUL, W-form)333
IMUL R64, R64332 (MUL, X-form)353
IDIV R3223-288-255-12 (DIV, W-form)10-1511-289-14
IDIV R6437-968-415-20 (DIV, X-form)14-1811-249-19

要約すると(本当に最新の64ビットCPU、つまりおおよそ2019年から2021年以降を対象として):

  • すべての改善にもかかわらず、除算は依然として「Darn Expensive™」(非常に高価)ですが、かつてほどひどく高価ではありません。
  • 2020年頃から、32ビットと64ビットの除算の差はそれほど劇的ではなくなりましたが、依然として存在します。
  • 乗算に関しては、32ビット版と64ビット版でほぼ同じです(一部のEコアを除く)。

TODO: 浮動小数点乗算/除算を追加

RTTI

RTTI(実行時型情報)は非常に高価になる可能性があり、dynamic_cast<> は単純な仮想関数呼び出しよりも最大5倍高価になることがあります(sic!)[TR][Didriksen]。

TODO: 仮想関数呼び出し vs typeid vs dynamic_cast のパフォーマンスをベンチマークする(ソースは非常に矛盾しており、潜在的に時代遅れのデータを提供しているため、自分で実験する必要があります)。

ただし、特定の主張(例:[Fog04, セクション7.23]を参照)とは異なり、RTTIはクラスオブジェクトのインスタンスに何も追加しません(ポリモーフィックなクラスの場合、RTTIは既に存在する同じvfptrを使用し、非ポリモーフィックなクラスにはRTTIは全くありません)。それでも、RTTIはコードサイズを増加させます。

C++例外 vs 返り値とチェック

C++は、例外がCスタイルのエラーコードの返却とチェックよりも効率的であるという立場を長らく取ってきました。そして実際、エラーが非常に稀なコードでは、その立場が正しいようです。例えば、[Nayar]のマイクロベンチマークは、エラーコードを返してチェックする方が、エラーコードなしで返すよりもCPUサイクルで2サイクル多くかかると示しています。一方、C++例外が発生した場合、それは「Damn Lot™」(非常に高価)です。 [Ongaro]によると、例外は約5,000サイクル(sic!)かかり、[Nayar]によると約2,700サイクルです。これは、関数呼び出し100回につき例外が1回発生する場合、返り値を使用する方が良いことを意味しますが、例外1回あたり10,000回の成功した呼び出し以上であれば、C++例外が有利になります。

これは[Fog04]の「例外が発生しない場合でも、すべての関数は例外ハンドラのために何らかの情報を保存しなければならない」という主張に反するように見えるかもしれませんが、この声明は2026年現在では時代遅れです。[Fog04]のこの観察は、おそらくスタックフレームを特別に調整してアンワインド情報を格納すること([TR, セクション5.4]の「The Code Approach」を参照)を指していると思われますが、長らく主要なコンパイラは同じセクションの「The Table Approach」を実装しており、これは現在一般的に「ゼロコスト例外」と呼ばれています。

アトミック操作、CAS、LL/SC
FSB

Front-Side Bus

歴史的に、アトミック操作(特にCAS=compare-and-swap)は、FSBベースのアーキテクチャでシステム全体でFSBを「LOCK」することを使用して導入されました。しかし、2000年代初頭からFSBは消滅し(x86/x64の世界でNUMAへの切り替えを先駆けたAMD64とOpteronのおかげ)、現在はキャッシュコヒーレンスプロトコル、通常はMESIのバリエーションが中心です。CPUサイクルに関しては、[AlBahra]はCAS操作について約15CPUサイクルの見積もりを提供しています。しかし、マルチソケットNUMAシナリオでは、これは簡単に300〜600サイクルに達する可能性があります。

さらに、アトミック操作は、レイテンシの直接的な増加を超える不快な副作用を持つ傾向があります。FSB時代には、アトミック操作はグローバルバスロックを引き起こし、マルチコア/マルチソケットシステムで観測可能なパフォーマンス低下を意味しました。現在、FSBはNUMAとMESIライクなプロトコルに置き換えられ、状況は改善しましたが、依然として「命令レベルの並列性を妨げ、帯域幅を大幅に制限する(単純な書き込みと比較して最大30倍)、たとえ連続する操作間に依存関係がなくても」[SchweizerEtAl]といったかなり顕著な影響を引き起こします。書き込みストールのような関連効果については、[Josuttis]も参照してください。

LL/SC

Load-Link / Store-Conditional。Store-conditionalは、先行するLoad-Link以降にその場所への更新がない場合にのみデータを格納します。

RISC-Vでのアトミック操作のサポートはCAS指向ではなく、LL/SC指向であり、独自の利点と癖があります。最近のARMはLL/SCとCASの両方をサポートしており、x64は伝統的にCAS指向です。

関数呼び出しとインライン化

歴史的に、[BulkaMayhew, p.115]は、パラメータの数に応じて、関数呼び出しのCPUコストを約25〜250サイクルと見積もっています。しかし、2000年の本は現在ではかなり古く感じられ、権威ある現代的な参照は見つかっていません😕。とはいえ、私たちの経験に基づくと、適度な数のパラメータを持つ関数は、直接的なコストとしては15〜30サイクル程度です。この観察は、[Ruskin]が指摘しているように、非Intel CPUでも同様のようです。

関数ポインタ経由の呼び出し(間接呼び出し)については、[Ignatchenko16a]は20〜50サイクル、C++仮想関数呼び出しについては30〜60サイクルと見積もっており、これは[Ruskin]とも一致しているようです。最後になりましたが、コンパイラが関数をインライン化した場合に何が起こるかを考慮する必要があります。そのような場合、直接呼び出し、間接呼び出し、または仮想呼び出しのいずれであっても、関数呼び出しの直接コストは発生しなくなります。さらに、コンパイラはインライン化後、呼び出し元関数とインライン化された呼び出し先関数を全体として最適化します。例として、次のようなコードがあるとします。

int square(int x) {
  return x*x;
}
int cube(int x) {
  return x*x*x;
}
int g(int x) {
  return square(x) + cube(x);
}

g()がsquare()とcube()をインライン化してコンパイルされると、x64 Clangはこれを単純なコードに削減します。

mov  eax, edi
imul eax, eax
imul edi, eax
add  eax, edi

ご覧のとおり、乗算は2回、加算は1回です。しかし、インライン化を禁止した場合、生成される効果的なコードは(直接関数呼び出しコストに帰属する可能性のある追加のmov、push/pop、スタックポインタの操作を除いても)、3回のimulと1回のaddになります。つまり、インライン化の欠如により、少なくとも1回のimulが最適化されずに残っています。言い換えれば、インライン化されていないコードでは、少なくとも1回のimulはインライン化の欠如による機会損失を表しています。これは理にかなっています。考えてみれば、インライン化なしでは、このような余分なimulの最適化(square()の計算がcube()内の計算の一部として使用できることを認識し、コンパイラが効果的にx*x+x*x*xを(x*x)*(1+x)に書き換えて1回の乗算を節約する)は全く不可能であることに気づくでしょう(sic!)。そして実際には、このような機会損失は容易に数十CPUサイクルに達する可能性があります。別の例として、同じパラメータで関数f()を2回呼び出し、f()が任意に高価である場合、コンパイラはインライン化されない限り、2回目のf()の呼び出しを最適化して削除することはできません(もしf()に副作用があるとしたらどうでしょう?)。しかし、f()の本体が見えれば、コンパイラは「これは副作用がないので、2回目の呼び出しを削除できる!」と認識するのに十分な情報を持っています。インライン化が救世主となる例については、[TODL: 非ミュータブルセマンティクスに関するヒント]、および第12章の[Carruth19]での議論も参照してください。

([Godbolt19]で強調されているように)インライン化によって可能になる最適化の一部(すべてではない)は、実際にはインライン化そのものではなく、コンパイラが関数本体を可視できるかどうかに関係しています(例:上記の関数f()の2回目の呼び出しに関する例を参照)。一方で、インライン化なしで可視性を確保することは(例えば、ヘッダーファイルに関数を強制的にアンインライン化して宣言するなど)可能かもしれませんが、通常は実用的ではありません。したがって、「インライン化はコンパイラの最適化を助ける」という一般的な格言は依然として有効です。

スレッドローカルストレージ

(データへの直接アクセスと比較して)thread_local変数は無料ではありません。さらに、コンパイラごとの実装は、単一のプラットフォームであっても大きく異なります。最後に確認したとき、GCCとClangの下でのx64では、TLSへのポインタは実際にFSレジスタに格納されており、TLSアクセスは1回の追加の間接参照のコストがかかりますが、MSVCの下では最大3回の追加の間接参照が発生する可能性があります。これらのアクセスされる場所は通常よくキャッシュされますが、それでも間接参照であり、thread_local変数へのアクセスコストを増加させます😔。

スレッドコンテキストスイッチ

スレッドコンテキストスイッチに関しては、一般的な意見は「Damn Expensive」(非常に高価)であるということです(結局のところ、nginxがApacheよりもパフォーマンスが高い理由はおそらくこれです)。しかし、「Damn Expensive」とは具体的にどの程度高価なのでしょうか? 私たちの経験では、コンテキストスイッチは10,000から100,000CPUサイクルの間でコストがかかる傾向があります。これは、関連する実際の観察とよく一致しています。例えば、Windows/x64のCRITICAL_SECTIONでは、デフォルトのスピンカウントは4000イテレーションです。これは、ロックを待つだけで15〜20K CPUサイクル、時には40〜50Kサイクルを消費することが一般的であり、その唯一の目的は、その「Damn Thread Context Switch™」を回避することです(そして、4000回のスピンが無駄になり、スピンのコストとスレッドコンテキストスイッチのコストの両方を負担する可能性があります!)。もちろん、それは回避しようとしているコンテキストスイッチが、スピンに費やされた15〜50K CPUサイクルよりも大幅に高価であることを強く示唆しています。とはいえ、多くの情報源ははるかに低い数値を報告しています。この不一致は、実際に何を測定しているかに大きく依存することから生じます。[LiEtAl]が説明するように、コンテキストスイッチには2種類のコストが関連しています。

まず、スレッドを切り替える直接的なコストがあります。これは比較的軽量な部分で、通常は約2,000CPUサイクルです。しかし、間接的なコスト、主にキャッシュ無効化によるものは、はるかに大きい傾向があります。[LiEtAl]によると、これは最大300万CPUサイクルに達する可能性があります。理論的には、完全にランダムなメモリアクセスパターンを持つ、12MBのL3キャッシュを持つ最新のCPU(L3アクセスとメインメモリアクセスを比較して、キャッシュミスあたり約150サイクルと仮定)では、コンテキストスイッチあたり最大3000万サイクルのペナルティが発生する可能性があります。しかし、実際には通常それほど深刻ではありませんが、たとえ100万サイクルであっても、「Damn Expensive」(非常に高価)という言葉に間違いなく該当します。


参考文献

[Ignatchenko16a] S. Ignatchenko, Operation Costs in CPU Clock Cycles 1 ↩ 2 ↩

[Fog] Agner Fog, Instruction tables. Lists of instruction latencies, throughputs and micro-operation breakdowns for Intel, AMD, and VIA CPUs 1 ↩ 2 ↩

[uops] uops.info table ↩

[Cortex-A78] Arm® Cortex®-A78 Software Optimization Guide ↩

[TR] Technical Report on C++ Performance 1 ↩ section 5.4 ↩ 3 ↩

[Didriksen] Tino Didriksen, C++ dynamic_cast Performance ↩

[Fog04] Agner Fog, Optimizing software in C++ section 7.23 ↩ 2 ↩ 3 ↩

[Nayar] Amit Nayar, Investigating the performance overhead of C++ exceptions 1 ↩ 2 ↩

[Ongaro] Diego Ongaro, The Cost of Exceptions in C++ ↩

[AlBahra] Samy Al Bahra, Nonblocking Algorithms and Scalable Multicore Programming ↩

[SchweizerEtAl] Hermann Schweizer, Maciej Besta, and Torsten Hoefler, Evaluating the Cost of Atomic Operations on Modern Architectures ↩

[Josuttis] Nicolai Josuttis, The Price of Shared Pointers or Why Passing them by-reference can be Useful ↩

[BulkaMayhew] Dov Bulka, David Mayhew, Efficient C++: Performance Programming Techniques p.115 ↩

[Ruskin] Elan Ruskin, HOW SLOW ARE VIRTUAL FUNCTIONS REALLY? 1 ↩ 2 ↩

[Carruth19] Chandler Carruth, There Are No Zero-cost Abstractions ↩

[Godbolt19] Matt Godbolt, Optimizations in C++ Compilers ↩

[LiEtAl] Chuanpeng Li, Chen Ding, Kai Shen, Quantifying The Cost of Context Switch 1 ↩ 2 ↩