InstrumentsによるCPUのパフォーマンス最適化

InstrumentsによるCPUのパフォーマンス最適化

Instrumentsの2つの新しいハードウェア支援ツールを使用して、Appleシリコン向けにアプリを最適化する方法を学びましょう。最初にアプリのプロファイリング方法を説明したあと、Processor Traceで呼び出される各関数を確認しつつ詳細を解説します。また、CPUカウンタの各種モードを使用したコード分析によりCPUのボトルネックを特定する方法についても説明します。

関連する章
- 0:00 - イントロダクションとアジェンダ
- 2:28 - パフォーマンスに対するマインドセット
- 8:50 - プロファイラ
- 13:20 - Span
- 14:05 - Processor Trace
- 19:51 - ボトルネック分析
- 31:33 - まとめ
- 32:13 - 次のステップ
リソース
関連ビデオ

WWDC25
WWDC24
- Swiftのパフォーマンスの詳細
WWDC23
- Instrumentsによるハング分析
WWDC22
- Swiftの並行処理を視覚化して最適化する
こんにちは OSカーネルエンジニアのMattです Instrumentsを使ってAppleシリコンCPU 向けにコードを最適化する方法を説明します CPUリソースを効率的に使うことでアプリで大量のデータを処理する場合や迅速な応答が求められる場合に待ち時間を短縮できますしかしソフトウェアのパフォーマンスの予測は2つの理由から困難です 1つ目は Swiftのソースコードと実際に実行される環境の間に抽象化レイヤーがあることですアプリ用に記述したソースコードは機械語の命令にコンパイルされ最終的にCPU上で実行されますただしコードは単独では実行されませんコンパイラで生成されたサポートコード、Swiftランタイム、その他のシステムフレームワークによって拡張されアプリの代わりにカーネルのシステムコールが特権的操作を処理します
このためコードが依存するソフトウェア抽象化のコストは把握しづらくなりますコードのパフォーマンスを予測するのが難しい2つ目の理由は CPUが与えられた命令を実行する方法です単一のCPU内では各機能単位が並行して動作します命令を効率的に実行するためですこれに対応できるように命令は順不同で実行されます順番に実行されているように見えるだけですさらにCPUはいくつかの層からなるメモリキャッシュの恩恵を受けますデータに迅速にアクセスできるのですこれらの特性によってコーディングの一般的なパターンは劇的に高速化されます例えばメモリの線形スキャンやまれな条件下で早期退出する防御的チェックなどがこれにあたりますただし一部のデータ構造、アルゴリズム、実装アプローチは慎重に最適化するか大幅に再構成しないと CPUが効率的に実行できません CPU向けにコードを最適化するための正しい方法を説明します最初にパフォーマンスの調査方法を確認しましょうまずはデータを指針とした最大限の高速化に注目してみます次に従来のプロファイリング用アプローチを検討しますこれはコード内の過剰なCPU使用率を特定する良いきっかけとなりますさらに掘り下げてプロファイリングのギャップを埋めるため Processor Traceを使用してすべての命令を記録しソフトウェア抽象化のコストを測定します最後に改良されたCPU CountersでCPUのボトルネックを分析しアルゴリズムを詳細に最適化する方法を学びますまずはパフォーマンス調査にアプローチするための正しい考え方を知りましょう大切なのは先入観を持たないことです減速の原因は予想外で驚くことがあります前提条件をテストするためのデータを収集しコードの実行に関するメンタルモデルが正確かどうかを検証します
例えばシングルスレッドの CPUパフォーマンスだけでなく他にも原因があるかもしれません CPUでの実行とは別の問題としてスレッドやタスクもファイルなどのリソースや共有可変状態にすぐにアクセスできず待機状態となる場合があります「Visualize and optimize Swift concurrency」セッションでタスクが実行待ちになる理由を把握するためのツールを紹介しています
スレッドのブロックが解除され実行状態になった場合も不適切な品質のサービスクラスがコードに適用されたり暗黙的に作成するスレッド数が多すぎるなど APIが誤って使用されている可能性があります詳しくはコードのパフォーマンスのチューニングに関する文書をご覧くださいしかし効率に問題がある場合はアルゴリズムとそれに関連するデータ構造を変更するかまたはそのアルゴリズムをプログラミング言語で実装する方法を見直す必要がありますツールを使ってまずこのツリーのどの部分に焦点を当てるべきかを判断します Xcodeの内蔵CPUゲージを使ってアプリの操作中における CPUの使用率を確認してみましょうスレッド間のブロックの動作と最終的にどのスレッドがブロックを解除するかを分析するには System Traceを使用します
UIまたはアプリのメインスレッドに影響を与える問題については専用のHangsを使用してくださいアプリのCPU使用率の最適化が必要かどうかを確認する方法の詳細については「Analyze hangs with Instruments」をご覧くださいただしツールからのガイダンスがあっても実装する最適化の種類には注意してくださいむやみなマイクロ最適化はコードの拡張や推論を難しくするかもしれませんまた多くの場合コンパイラ最適化に依存していて自動ベクトル化や参照カウントの省略のように脆弱な場合があります煩わしいマイクロ最適化に取り組む前に代替手段を探してくださいこれにより運用の低速化を完全に回避できるかもしれませんそもそもなぜそのコードを実行するのかを考えてみましょう実行する必要がなければコードを削除するだけですご視聴ありがとうございました… いえ冗談です実際のところこれはまず不可能ですがその処理の結果が本当に重要かを検討することができます
またクリティカルパス外で後で作業を試みたり結果がユーザーに表示される場合に限定する方法もあります同様に値を事前計算することで作業の完了にかかる時間を短く見せることができますビルド時に値をベイクする方法もこれに含まれますしかしこれらのアプローチは不必要に電力を消費したりサイズを大きくしたりする場合があります同じ入力内容で繰り返し操作を行うのならキャッシュも有効ですしかしこれも多くの場合一連の困難な問題が伴いますキャッシュの無効化やメモリ使用量の増加などですパフォーマンスの問題があってその処理をどうしても回避できない場合は CPUでの実行速度を向上させる必要がありますそれが今日のセッションの主眼ですユーザー体験への影響が最も大きいコードを優先して最適化してください通常これはアプリを操作するユーザーのクリティカルパスに関与するコードですパフォーマンスの問題が表面化しやすいと同時に実行が長時間にわたり多くの電力を消費する可能性もありますこのセッションでは準備済みの整数のリストの検索に注目します私のアプリのクリティカルパスだからです
このアプリはバイナリ検索を使っていますソートされた配列を使う古典的なアルゴリズムで検索範囲を半分にし続けて要素を見つけますこの例では配列に16個の要素があり数字の5を保持する要素を検索しようとしています 5は配列の中央にある要素 20より小さい数ですつまり 5という要素は前半にあるはずです 5は配列の前半にある要素 9より小さい数ですつまり配列の最初の 4分の1のどこかにあるはずです 3と比較すると一致する数にたどり着くのでわずか4ステップですこれは私のアプリで使っているフレームワークでのバイナリ検索の実装ですこのスタンドアロン関数では干し草の山から針を見つけるという言い回しに由来するパラメータ名を付けています haystackコレクションから Comparableとなるneedleを検索できますここでは2つの変数を追跡します startでは現在の検索エリアの開始を lengthでは検索対象の要素の残数を追跡します検索対象の要素が残っている場合は検索範囲の中央の値を確認します needleがその値より小さい場合は検索範囲を半分にするだけです startはそのまま残します needleが値と等しい場合は要素が見つかっているので middleインデックスが返されますそれ以外の場合は開始位置を調整する必要があります中央の要素の直後に移し検索範囲を半分に減らしました
このアルゴリズムを段階的に最適化するための準備をします検索のスループットやアルゴリズムが毎秒完了可能な検索の数を比較しながら各ステップで進捗を確認します変更を加えるたびに大きな改善が見られなくても構いません一つひとつは定量化が難しくても積もり積もって大きな改善につながります
継続的に最適化できるように検索スループットを測定する自動テストを作成しましたパフォーマンスを見積もるだけなので難しいセットアップは不要ですこのrepeat-whileループにより指定された期間が経過するまで検索クロージャを呼び出します検索クロージャの呼び出しでは OSSignposter intervalを使用しています最適化テストの部分をツールで絞り込めるようにするためです .pointsOfInterestカテゴリを選択しました Instrumentsには既定で含まれていますタイミング自体にはContinuousClockを使用します Dateとは異なり逆行できずオーバーヘッドが小さいですこのように単純かつ効果的な方法でアルゴリズムのパフォーマンスの大まかなデータを収集できます searchCollectionというテストでアプリでのバイナリ検索をシミュレートします 1回の記録で複数のテストを実行する場合は signpostに付けた説明的な名前で 1秒間検索を実行しますクロージャ内のループは binarySearch関数を呼び出して時間を確認するコストを償却しますこのテストを Instrumentsプロファイラで実行してバイナリ検索のCPUパフォーマンスを分析してみましょう CPUに重点を置いたプロファイラは2つあり Time Profilerと CPU Profilerから選択できます従来のTime ProfilerはシステムのCPU上で実行される処理をタイマーに基づいて定期的にサンプリングしますこの例では 2つのCPUで処理が実行されています Time Profilerは CPU上で実行される各スレッドのユーザー空間コールスタックを各サンプルポイントでキャプチャします
Instrumentsはこれらのサンプルをコールツリーまたはフレームグラフとして詳細ビューで視覚化し CPUのパフォーマンス改善のためにはどのコードを最適化するべきかおおむね予測しますこれは時間経過に伴う処理の分散や同時にアクティブになるスレッドを探すのに役立ちますこのようにタイマーでサンプリングするとエイリアシングが問題になりますエイリアシングとはシステム上の一部の定期処理がサンプリングタイマーと同じ頻度で発生することですこの例では青い領域が CPU時間のほとんどを占めていますがサンプラがコールスタックを収集するたびにオレンジ色の関数が実行されていますその結果 Instrumentsのコールツリーにはオレンジ色が不当に多く表示されます
この問題を回避するために CPU Profilerを利用できますこれは各CPUのクロック周波数に基づいて CPUを個別にサンプリングします CPUの最適化はTime Profilerよりも CPU Profilerを優先しましょう CPUリソースを消費するソフトウェアをより正確かつ公平に重み付けしてくれます
ベルはCPUのサイクルカウンタがサンプリングするタイミングを表しています AppleシリコンのCPUは非対称で一部はクロック周波数がやや遅いですがそのぶん電力効率に優れています周波数をスケールアップした個々のCPUはより頻繁にサンプリングされます Time Profilerのような高速実行の CPUに対するバイアスはありません CPU Profilerを使って binarySearch関数の中でCPUサイクルを最も消費している部分を調べましょう XcodeのTest NavigatorでユニットテストからInstrumentsを素早く起動できますテスト名を副ボタンでクリックしてプロファイル項目を選択するだけです今回は「Profile searchCollection」を選択します
Instrumentsが開きテンプレート選択画面が表示されますを選択しますでモードに切り替えてオーバーヘッドを減らし記録を開始しますプロファイラのデフォルトの即時モードはアプリをキャプチャしながら操作を確認するのに役立ちますしかしInstrumentsと同じマシンで自動テストを行う場合はツールによるオーバーヘッドの増大は最小限に抑えたいところです記録が停止するまで待ってから分析します Instrumentsの新しいドキュメントはしばしば煩雑ですウィンドウが2つに分かれています上部のトラックはタイムライン上のアクティビティを示しています各トラックに複数のレーンを追加してレベルや領域を示すグラフを表示できます
タイムラインの下の詳細ビューには調査対象のタイムライン範囲に関するサマリ情報が表示されます右側にはさらに詳しい情報が表示されます方向付けのためにトラックで検索が行われている領域を見つけます副ボタンで領域をクリックすると調査範囲の設定が提案され下の詳細ビューはsignpost間隔内でのキャプチャデータのみに絞り込まれますテストランナープロセスのトラックをクリックするとタイムラインの下の詳細ビューに CPUプロファイルが表示されますここには各CPUのサイクルカウンタによってサンプリングされたテスト内の関数のコールツリーが表示されますオプションを押しながら一覧の最初の関数の横にある下向き矢印をクリックするとサンプル数が大きく異なる最初のポイントまでツリーが展開しますこれはbinarySearch関数に近いです名前の横にある矢印をクリックして binarySearch関数に焦点を当てを選択します各関数はサンプル数に各サンプル間のサイクル数を掛けた数値で重み付けされますこのコールツリーはCollection型に応じてバイナリ検索によって呼び出された関数で取得された多くのサンプルを示していますこのprotocol witnessはサンプルの約4分の1に出現しています割り当てのほかObjective-C型の Arrayチェックもありますいま私が検索している型のデータによく一致するコンテナタイプに切り替えると Arrayとジェネリクスのオーバーヘッドを回避できます新しいSpan型を試しましょう要素がメモリに連続格納されている場合 Collectionの代わりに使用できますこれは多くの種類のデータ構造に共通しています事実上はベースアドレスとカウントですそれが使用されている関数の外部でのメモリ参照のエスケープやリークも防止されます Spanの詳細については「Improve memory usage and performance with Swift」をご覧ください Spanを採用するにはhaystackと戻り値の型をSpanに変更するだけでよくアルゴリズム自体の変更は不要です
この小規模な変更だけで検索が4倍速くなりますしかしこのバージョンのバイナリ検索はまだアプリに影響を与えているので Spanの境界チェックがオーバーヘッドに影響しているかどうかを調査したいと思います Processor Traceという新しいツールでさらに掘り下げます Instruments 16.3以降では Processor Traceを使用してアプリのプロセスがユーザー空間で実行するすべての命令のトレースを収集できますソフトウェアパフォーマンスの革新的な測定方法でありサンプリングバイアスが発生しませんアプリのパフォーマンスへの影響はたった1%なので無視できます Processor Traceには M4搭載のMacとiPad Proまたは A18搭載のiPhoneでのみ利用できる専用のCPU機能が必要ですまず Processor Trace用にデバイスを設定する必要があります Macで> の設定をオンにします iPhoneまたはiPadの場合この設定はセクションにあります Processor Traceで最大限にエクスペリエンスを引き出すにはトレースを数秒だけに制限してみてください CPU Profilerによるサンプリングとは異なり作業のバッチ処理が不要です最適化したいコードのインスタンス1つだけでも十分です Spanバージョンのバイナリ検索で Processor Traceを実行してみましょうあとは何回か反復処理をしてテストを実行するだけですこのテストをプロファイリングするには行番号のガター部分にあるテストアイコンを副ボタンでクリックします前に使用したメニューが表示されますがナビゲータを切り替えるより簡単です Processor Traceテンプレートを選択して
記録を開始します
Processor Traceは大量のデータを扱う必要があるのでキャプチャと分析に時間がかかる場合があります Processor Traceはすべての分岐判断を記録するようにCPUを設定しますサイクル数と現在時刻も記録され各関数に費やされた CPUの使用時間を追跡しますその後Instrumentsはアプリとシステムフレームワークの実行可能バイナリを使用して実行パスを再構築し関数呼び出しに経過したサイクルと期間の注釈を付けますトレースに費やす時間は制限します CPUが記録する情報は最小限に抑えられているとはいえマルチスレッドのアプリでは毎秒数ギガバイトのデータになる可能性がありますドキュメントの準備ができたので binarySearch関数の呼び出しを詳しく調べてみましょう検索は今や記録全体のほんの一部しか占めていないのでタイムラインの下の詳細ビューのリストで探しますこの行を副ボタンでクリックしを選択しますバイナリ検索を実行しているスレッドを見つけるにはセルを副ボタンでクリックしを選択します
Processor Traceは各スレッドトラックにフレームグラフという新関数を追加しますピンの区切り線を上にドラッグしてスペースを確保しますね
Processor Traceは実行をフレームグラフとして視覚的に示しますフレームグラフは関数のコストと関係をグラフィカルに表現したものですバーの幅は関数の実行にかかった時間を表し行はネストされたコールスタックを表しますしかしほとんどのフレームグラフはサンプリングのデータを示しておりそのコストはサンプル数に基づく推定値です一方 Processor Traceのタイムラインフレームグラフでは経時的な呼び出し記録が表示されます CPUで実行されたタイミングとまったく同じです各バーの色は由来しているバイナリの種類を表しますシステムフレームワークは茶色マゼンタはSwiftランタイムと標準ライブラリ青は任意のカスタムフレームワークかアプリのバイナリにコンパイルされたコードこのトレースの最初の部分はsignpostを出力するオーバーヘッドを示しますでは範囲の終わり近くにあるバイナリ検索コードを拡大してみましょう Optionキーを押しながらタイムラインをクリックしドラッグして拡大します
10回の反復処理から任意の binarySearch関数呼び出しを選択できます調査範囲を設定して副ボタンのクリックでズームしますこれがProcessor Traceの力です数百ナノ秒しか実行されない 1つの関数によって行われたすべての呼び出しを確認できますさらに拡大することもできますが今回はタイムラインの下にある関数呼び出しの要約を使用しますタイムラインと同じ情報が表形式で示されます短時間使用の関数まで含めてフルネームが表示されますこの表をサイクル順に並べ替えます
境界チェックが速度低下の原因だという私の最初の仮定は誤りでしたこのバイナリ検索の実装はまだプロトコルのメタデータのオーバーヘッドの処理中です数値比較のインライン展開はできず検索の合計サイクル数の割合は結局かなりのものになるでしょうこれは汎用的なComparable パラメータが使用される要素の型に特化されていないためです
このコードはアプリによってリンクされたフレームワークにあるので Swiftコンパイラはバイナリ検索の呼び出し元によって渡された型専用の特別なバージョンを提供できません
これが原因でフレームワークのコードでオーバーヘッドが発生する場合フレームワークの関数に inlinable注釈を追加してフレームワークのクライアントのバイナリ実行ファイルで特別な実装を生成する必要があります
しかしインライン展開すると呼び出し元と混ざり合うためコードの解析が難しくなりますテストハーネスへのインライン展開は避けたいのでこの関数ではアプリやテスト用のInt型用として手動で特化させて新しい関数名を付けますコードは汎用性をかなり失いますが約1.7倍高速になりますさらに最適化を続けましょうまだバイナリ検索がアプリの速度低下を引き起こしているからです 1つの関数の最適化に長時間かかるのは奇妙な事態です定期的に再評価してデータを収集しコードを非効率にしている他の要因がないか探りましょう特別なSpanバイナリ検索には Processor Traceの予期せぬ関数呼び出しも表示されていないのでコードがCPU上でどのように実行および進行しているか把握する必要があります CPU Countersを使用すると CPUでの実行中コードにどのようなボトルネックがあるかがわかります Instrumentsを再び使用する前に CPUの動作についてメンタルモデルを構築する必要があります基本的には CPUは命令のリストに従っているだけですレジスタとメモリの変更や周辺機器との相互作用などがあります
CPUが処理を実行する時は一連の手順に従う必要がありますこれは大きく2つのフェーズに分類されます 1つ目は実行するべき命令を CPUに届けるための命令送信 2つ目はそれらを実行する命令処理です命令送信では命令がフェッチされマイクロ操作にデコードされて CPUが実行しやすい形になりますほとんどの命令は単一のマイクロ操作にデコードされますがメモリリクエストの発行やインデックス値のインクリメントなど複数の場合もありますマイクロ操作は Map and Scheduleユニットに送信されてルーティングとディスパッチが行われますその後実行ユニットに割り当てられます操作がメモリにアクセスする必要があれば Load-Storeユニットに割り当てられます
これらのフェーズを順番に実行する場合 CPUがフェッチを再開するまでに時間がかかるので Appleシリコンプロセッサはパイプライン化されますユニットは処理を完了すると次の操作に移るのでどれも常にビジーです
実行ユニットのパイプライン化と追加コピーの作成は命令レベルの並列処理を容易にします
これはプロセスまたはスレッドレベルの並列処理とは異なります Swiftの並行処理または Grand Central Dispatchで複数のCPUが異なるOSスレッドを実行しているところへアクセスするのではなく命令レベルの並列処理では 1つのCPUが時間的に有利を得ますユニットがアイドル状態の時にパイプラインすべてをビジー状態に保ちハードウェアを効率的に使用できるからです Swiftソースコードはこの並列処理を直接制御することはできません代わりにコンパイラによる従順な命令シーケンスの生成を支援します
残念ながら並列化可能な命令シーケンスは CPU内のユニット間のやり取りの性質上あまり直感的ではありませんユニット間の矢印は並列処理が制限されパイプラインの操作が停止する可能性を示していますこれをボトルネックと呼びます
ワークロードに関連するボトルネックを見つけるには AppleシリコンCPUで各ユニットの特徴的なイベントや実行される命令のその他の特性をカウントします CPU Countersはこれらのカウンタを読み取りより高いレベルのメトリックを構築します今年はカウンタにプリセットモードが追加されて非常に使いやすくなりました Instrumentsはこれらをガイド付きの反復的手法で使用しコードのパフォーマンスをボトルネック分析しますこれを使って関数呼び出しに明らかなオーバーヘッドがないにもかかわらずバイナリ検索がまだ遅い理由を調べてみましょう CPU Countersはワークロードのサンプリングに依存するため CPU Profilerで使ったテストハーネスに戻りスループットを再測定する必要があります
特別なSpan実装のテストを Instrumentsでプロファイリングします
テンプレートを選択します
厳選されたモードで使えるガイド付きの構成を使って測定できます
各モードの機能に興味がおありの場合はモード選択の横にある情報アイコンから利用可能なドキュメントをご参照くださいカウントを始めましょう
この最初のCPU Bottlenecksモードでは CPUが実行した処理が分析され CPUの潜在的なパフォーマンスを占める 4つの主なカテゴリが表示されます Instrumentsはこれらを色付きの積み重ね横棒グラフとして表示します詳細ビューには概要テーブルもあります記録中 Instrumentsはテストで使用したスレッドのCPUカウンタデータを収集しそれらをボトルネックの割合に変換します前と同じようにPoints of Interestを使って指針を定めズームして検索を選択します
次にバイナリ検索の実装を実行しているスレッドをタイムラインにピン留めします
レーンにカーソルを置くと破棄されたボトルネックの割合が高いことがわかります下の詳細ビューは調査範囲内のメトリックの集計を示していますの行を選択すると右側の詳細ビューに説明が表示されますまた Instrumentsではタイムラインのチャート上にコメントが表示されますそのコメントをクリックするとさらなる詳細が下に表示されますこれは便利ですが検索のどの部分がボトルネックの原因かはまだわかりませんセルを副ボタンでクリックします列の下ですここではワークロードを様々なモードで再プロファイリングできます試してみましょうこのモードは CPUボトルネックとは少し異なります引き続きカウンタのデータを収集しますがサンプリングをトリガーするためのカウンタの設定もしていますサンプルデータは破棄された処理を生成する命令に限定されています再びでそのことを確認しましょう
次にテストプロセスのトラックを選択し
タイムラインの下にある命令サンプルに移動します
これはコールスタックではなく実際に問題の原因となっている命令です関数名の横にある矢印をクリックするとサンプリングされたソースコードがソースビューアに表示されます CPUが間違った分岐方向に向かったので確認しますここではneedleと中間値の間で行われている比較が誤って予測されていますこれらのソースラインが不正確な予測を多発させている理由を理解するには CPUの特徴をもう少し知る必要があります
実は CPUは命令を順不同で実行します命令が完了した後で並べ替えているため命令が順番に実行されるように見えるだけですこれはCPUが先を見て次に実行する命令を予測していることを意味します分岐予測機能は通常は正確ですが以前の実行に一貫したパターンがない場合は誤った経路をたどる可能性もあります
今回のバイナリ検索アルゴリズムのループには2種類の分岐があります最初のループ条件は通常はループの終わりまで適用されますこれは予測に成功しておりサンプリングには現れませんでしたしかしneedleのチェックは事実上ランダムな分岐なので予測に問題が発生したのも不思議ではありません
制御フローに影響を与える分岐の予測が難しくならないようにループ本体を書き直します ifステートメントの本文は条件に基づいて値を代入しているだけですこれでSwiftコンパイラは条件付きの移動命令を生成することで別の命令への分岐を回避できます関数から戻ることや条件に基づいてループを中断することは分岐で実装する必要があるため早期リターンも削除する必要がありました分岐先でプログラムが終了しないように未チェックの算術演算も使用しましたこれはマイクロ最適化が脆弱化して停止しやすい領域の1つであり安全性とわかりやすさが低いことは言うまでもありませんこのような変更を行う場合は最初のCPU Bottlenecksモードに戻って残りのボトルネックにどのように影響するかを確認します今回は既に分岐のない新しいバイナリ検索の痕跡を集めました分岐のあるバージョンの約2倍の速さです現在はほぼ完全に命令処理のボトルネックになっています Instrumentsはワークロードを Instruction Processingモードで再実行する必要性を示しています
このモードにはL1D Cache Miss Sampling モードの実行を推奨するコメントがありましたキャッシュミスのサンプルは配列からメモリへのアクセスが原因で CPUが命令を効率的に実行できないことを示していますその理由を知るため CPUとメモリについて詳しく学びましょう
CPUは同じアドレスに繰り返しアクセスするキャッシュ階層または予測可能なアクセスパターンでメモリにアクセスすることで高速化を図りますこれは各CPU内にある L1キャッシュから始まりますあまり多くのデータは保存できませんがメモリへのアクセスが最速です L2キャッシュはより低速ですがCPUの外にありヘッドルームが大幅に増加します最後にどちらのキャッシュも使わずにメインメモリにアクセスするリクエストは早いパスと比較して50倍遅くなりますキャッシュはメモリを64または128バイトのキャッシュラインにグループ化します命令が4バイトしか要求しない場合でもキャッシュはより多くのデータをプルします後続の命令で近くのバイトにもアクセスする必要性を予期するからです
これがバイナリ検索アルゴリズムにどのように影響するか考えてみましょうこの例の青い線は配列内の要素です灰色のカプセルはCPUキャッシュが動作するキャッシュラインです
配列は完全にキャッシュから開始します最初の比較ではキャッシュラインと数個の要素がL1データキャッシュに取り込まれますしかし次の比較ではキャッシュミスが発生しますその後の反復処理でもキャッシュミスが続きますこれはキャッシュラインサイズの領域上で検索が絞り込まれるまで続きますバイナリ検索は CPUのメモリ階層にとっては異常なケースだとわかるでしょう
要素を並べ替えてキャッシュしやすくすることを許容できるなら検索ポイントを同じキャッシュラインに配置できますこれはこのように家系図を整理した16世紀のオーストリアの系図学者にちなんで Eytzingerレイアウトと呼ばれていますこれは軽微な結果を期待する一般的な最適化ではありません検索速度は向上しますが順序に沿ったトラバース速度が低下しその操作はキャッシュミスされますバイナリ検索の最初の例に戻りソート済みの配列をEytzingerレイアウトに並べ替える方法を示しましょう中央の要素をルートとして開始しバイナリ検索操作をツリーとしてモデル化します中間点は子孫ノードです Eytzingerレイアウトはそのツリーの幅優先トラバースとして配置されます
ツリーのルートに近い要素はより密に配置されキャッシュラインを共有しやすくなります 5を再度検索すると最初の3ステップが同じキャッシュラインで実施されますリーフノードは配列の最後にソートされるのでキャッシュミスが避けられません
Eytzingerバイナリ検索の CPUボトルネックトレースを記録しましたこれもまた分岐のない検索より 2倍高速であることを示していますしかしこの例では興味深いことが強調されています命令処理上まだ技術的なボトルネックであるということです実装をキャッシュしやすくしましたがワークロードはまだ本質的にメモリに縛られています
パフォーマンスを監視しアプリの他のコードを停止／最適化するタイミングを把握する必要がありますこの検索はもはやクリティカルパスのパフォーマンスに影響しないからですこのプロセスにより検索スループットが大幅に向上しましたまずCPU Profilerを使用してCollectionから Spanへの切り替えを大幅に高速化しました
次にProcessor Traceで全般的なオーバーヘッドを確認しました最後にボトルネック分析を活用したマイクロ最適化でパフォーマンスを大幅に向上させました Instrumentsにより検索機能は全体で約25倍高速化しましたこれらの高速化を達成するために正しいマインドセットを確認しましたツールを使って推測を確認し抽象化のコストについての直感を養うことができました続いてより詳細なツールを適用して予期せぬオーバーヘッドを見つけ出しました実際に測定しないと見落としやすいですが対処も簡単でしたその後ソフトウェアのオーバーヘッドに対処し CPUボトルネックに焦点を当てた最適化を検討しました CPUで利用できる機能をより深く意識し寄り添えるようになりましたこの順序は重要でした CPU重視のツールとソフトウェアランタイムの余分なオーバーヘッドを混同してはならないからです
これを自分のアプリに適用するにはデータを収集しパフォーマンスのマインドセットに従いますパフォーマンステストはInstrumentsで繰り返し測定できるように記述しますこれらのツールに関するご意見やご質問をフォーラムにお寄せくださいここで紹介したセッションとWWDC24の Swiftパフォーマンスのセッションは Swiftの強力な抽象化のコストに関するより正確なメンタルモデルの構築に役立ちます CPUがコードを実行する方法について理解を深めるには「Apple Silicon CPU Optimization Guide」をご覧くださいありがとうございました Instrumentsを活用しコードという「干し草の山」から最適化の「針」を見つけてください

public func binarySearch<E, C>(
    needle: E,
    haystack: C
) -> C.Index where E: Comparable, C: Collection<E> {
    var start = haystack.startIndex
    var length = haystack.count

    while length > 0 {
        let half = length / 2
        let middle = haystack.index(start, offsetBy: half)
        let middleValue = haystack[middle]
        if needle < middleValue {
            length = half
        } else if needle == middleValue {
            return middle
        } else {
            start = haystack.index(after: middle)
            length -= half + 1
        }
    }

    return start
}

7:49 - Throughput benchmark

import Testing
import OSLog

let signposter = OSSignposter(
    subsystem: "com.example.apple-samplecode.MyBinarySearch",
    category: .pointsOfInterest
)

func search(
    name: StaticString,
    duration: Duration,
    _ search: () -> Void
) {
    var now = ContinuousClock.now
    var outerIterations = 0
    
    let interval = signposter.beginInterval(name)
    let start = ContinuousClock.now
    repeat {
        search()
        outerIterations += 1
        now = .now
    } while (start.duration(to: now) < duration)
    let elapsed = start.duration(to: now)
    let seconds = Double(elapsed.components.seconds) +
            Double(elapsed.components.attoseconds) / 1e18
    let throughput = Double(outerIterations) / seconds
    signposter.endInterval(name, interval, "\(throughput) ops/s")
    print("\(name): \(throughput) ops/s")
}

let arraySize = 8 << 20
let arrayCount = arraySize / MemoryLayout<Int>.size
let searchCount = 10_000

struct MyBinarySearchTests {
    let sortedArray: [Int]
    let randomElements: [Int]
    
    init() {
        let sortedArray: [Int] = (0..<arrayCount).map { _ in
                .random(in: 0..<arrayCount)
        }.sorted()
        self.randomElements = (0..<searchCount).map { _ in
            sortedArray.randomElement()!
        }
        self.sortedArray = sortedArray
    }

    @Test func searchCollection() throws {
        search(name: "Collection", duration: .seconds(1)) {
            for element in randomElements {
                _ = binarySearch(needle: element, haystack: sortedArray)
            }
        }
    }
}

13:46 - Binary search in Span

public func binarySearch<E: Comparable>(
    needle: E,
    haystack: Span<E>
) -> Span<E>.Index {
    var start = haystack.indices.startIndex
    var length = haystack.count

    while length > 0 {
        let half = length / 2
        let middle = haystack.indices.index(start, offsetBy: half)
        let middleValue = haystack[middle]
        if needle < middleValue {
            length = half
        } else if needle == middleValue {
            return middle
        } else {
            start = haystack.indices.index(after: middle)
            length -= half + 1
        }
    }

    return start
}

15:09 - Throughput benchmark for binary search in Span

extension MyBinarySearchTests {
    @Test func searchSpan() throws {
        let span = sortedArray.span
        search(name: "Span", duration: .seconds(1)) {
            for element in randomElements {
                _ = binarySearch(needle: element, haystack: span)
            }
        }
    }

    @Test func searchSpanForProcessorTrace() throws {
        let span = sortedArray.span
        signposter.withIntervalSignpost("Span") {
            for element in randomElements[0..<10] {
                _ = binarySearch(needle: element, haystack: span)
            }
        }
    }
}

19:17 - Binary search in Span

public func binarySearchInt(
    needle: Int,
    haystack: Span<Int>
) -> Span<Int>.Index {
    var start = haystack.indices.startIndex
    var length = haystack.count

    while length > 0 {
        let half = length / 2
        let middle = haystack.indices.index(start, offsetBy: half)
        let middleValue = haystack[middle]
        if needle < middleValue {
            length = half
        } else if needle == middleValue {
            return middle
        } else {
            start = haystack.indices.index(after: middle)
            length -= half + 1
        }
    }
    return start
}

23:04 - Throughput benchmark for binary search in Span

extension MyBinarySearchTests {
    @Test func searchSpanInt() throws {
        let span = sortedArray.span
        search(name: "Span<Int>", duration: .seconds(1)) {
            for element in randomElements {
                _ = binarySearchInt(needle: element, haystack: span)
            }
        }
    }
}

26:34 - Branchless binary search

public func binarySearchBranchless(
    needle: Int,
    haystack: Span<Int>
) -> Span<Int>.Index {
    var start = haystack.indices.startIndex
    var length = haystack.count

    while length > 0 {
        let remainder = length % 2
        length /= 2
        let middle = start &+ length
        let middleValue = haystack[middle]
        if needle > middleValue {
            start = middle &+ remainder
        }
    }

    return start
}

27:20 - Throughput benchmark for branchless binary search

extension MyBinarySearchTests {
    @Test func searchBranchless() throws {
        let span = sortedArray.span
        search(name: "Branchless", duration: .seconds(1)) {
            for element in randomElements {
                _ = binarySearchBranchless(needle: element, haystack: span)
            }
        }
    }
}

29:27 - Eytzinger binary search

public func binarySearchEytzinger(
    needle: Int,
    haystack: Span<Int>
) -> Span<Int>.Index {
    var start = haystack.indices.startIndex.advanced(by: 1)
    let length = haystack.count

    while start < length {
        let value = haystack[start]
        start *= 2
        if value < needle {
            start += 1
        }
    }
    
    return start >> ((~start).trailingZeroBitCount + 1)
}

30:34 - Throughput benchmark for Eytzinger binary search

struct MyBinarySearchEytzingerTests {
    let eytzingerArray: [Int]
    let randomElements: [Int]

    static func reorderEytzinger(_ input: [Int], array: inout [Int], sourceIndex: Int, resultIndex: Int) -> Int {
        var sourceIndex = sourceIndex
        if resultIndex < array.count {
            sourceIndex = reorderEytzinger(input, array: &array, sourceIndex: sourceIndex, resultIndex: 2 * resultIndex)
            array[resultIndex] = input[sourceIndex]
            sourceIndex = reorderEytzinger(input, array: &array, sourceIndex: sourceIndex + 1, resultIndex: 2 * resultIndex + 1)
        }
        return sourceIndex
    }

    init() {
        let sortedArray: [Int] = (0..<arrayCount).map { _ in
            .random(in: 0..<arrayCount)
        }.sorted()
        var eytzingerArray: [Int] = Array(repeating: 0, count: arrayCount + 1)
        _ = Self.reorderEytzinger(sortedArray, array: &eytzingerArray, sourceIndex: 0, resultIndex: 1)
        self.randomElements = (0..<searchCount).map { _ in
            sortedArray.randomElement()!
        }
        self.eytzingerArray = eytzingerArray
    }

    @Test func searchEytzinger() throws {
        let span = eytzingerArray.span
        search(name: "Eytzinger", duration: .seconds(1)) {
            for element in randomElements {
                _ = binarySearchEytzinger(needle: element, haystack: span)
            }
        }
    }
}

関連する章

リソース

関連ビデオ

WWDC25

WWDC24

WWDC23

WWDC22