最も速い処理は、行わない処理です。メッセージごとの処理を減らす3つの方法と、小さな判断を軽くする1つの方法を紹介します。
- 検索表。 小さな入力(バイト、メッセージの種類、価格帯)を受け取る関数が遅かったり
ifだらけだったりする場合は、すべての答えを一度だけ配列に計算しておき、ホットパスでは配列をインデックスで参照します。
- 賢く探す。 並べ替え済みのデータでは、
std::lower_boundがn回ではなく約log2(n)回の比較で位置を見つけます。
- 不変の処理をループの外に出す。 ループの反復ごとに結果が同じ呼び出しは、ループの前に置くべきです。
- 分岐を減らす。 プロセッサーは各分岐の方向を予測して先に実行し、予測が外れるとその処理を捨てます。小さな判断なら、
std::minとstd::maxは通常、分岐がまったくないコードにコンパイルされます。
ブラウザーからは分岐予測を見ることができず、ここでの計測値はノイズになるため、この演習では代わりに処理の量を数えます。遅い関数が何回実行されるか、探索で何回比較するかです。数える関数はテストが用意します。