Boost.Pool #3 に打ち勝った方法:分岐が悪い

分岐と条件付きジャンプは、すべてのプログラムにとって不可欠です。分岐と条件付きジャンプがなければ、最も単純なコードしか記述できません。ただし、特定のオーバーヘッドが発生する場合があり、パフォーマンスの重要なコード パスで問題が発生する可能性があります。

多くの場合、それらが存在しない方が高速です.しかし、どうすればそれができるでしょうか?

このシリーズでは、私が行った変更について説明し、Boost.Pool を打ち負かす過程で学んだ最適化に関するいくつかの教訓を共有します。 .

ブランチの問題は何ですか?

しかし、最初にブランチの問題について話させてください。

16 で使用されているような条件付きジャンプ ,29 などには 1 つの問題があります。遅いです。

わかりました、これは部分的にしか当てはまりません:命令自体は本質的に他の命令より遅いわけではなく、その実行は遅くなる可能性があります。

問題は…ええ、本当に良いことは、CPU がパイプラインで命令を実行することです。これにより、現在の命令がまだ処理されている間に次の命令の作業を開始できます。次の命令が何であるかを予測できる限り、パイプラインは正常に機能します。

ただし、条件付きジャンプがある場合、次の命令は実行される分岐によって異なります!

したがって、理論的には、CPU は分岐でパイプライン処理を行うことができず、どの分岐が実行されているかがわかるまで待機する必要があります。これは実行可能ではありませんが、遅すぎます。

私が最も気に入っている Stackoverflow の回答の 1 つは、優れたアナロジーを使用して解決策を説明しています。

アナロジーは電車のジャンクションを使用します:

しかし、列車は停止して再び加速する時間が必要なため、これは遅いです.CPU のパイプラインのように.

したがって、CPU は予測しようとします。 どの分岐を取るか。この手法は分岐予測と呼ばれます。

同じことが分岐予測です。CPU はどの分岐が行われるかを推測し、その命令の実行を開始します。推測が正しければ、ペナルティはありません。しかし、推測が間違っていれば、他の命令を実行するためにパイプラインの実行を中止する必要があります。

それ 遅いです。

ありがたいことに、CPU の分岐予測子はこれらの点で優れています。たとえば、エラー パスがある場合、CPU は、通常は入力しないことを学習します。したがって、通常のコード パスでは、分岐のオーバーヘッドはあまりありません。

ある エラーが発生し、エラー処理パスを入力する必要があります。通常、分岐予測は失敗します - 結局、これは異常なケースです - そしてパイプラインのフラッシュが遅くなります. 幸いなことに、これは問題ではありません。 !パフォーマンスに影響はありません。

一方、通常のフローに関する分岐があります。正常なケースと異常なケースがまだありますが、異常なケースの方が頻繁です。

そうすると、分岐がパフォーマンスに悪影響を与える可能性があります。

ブランチに関しては、別の、より些細なコストもあります。次のコードを検討してください:

if (alignment > max_alignment())
 throw bad_alignment(...);

31 があります 、したがって、分岐命令のコストを支払う必要があります。CPU はケースの 1 つがめったに実行されないことを検出するため、小さいはずです。したがって、分岐予測は正しいことを行います。しかし、コストもあります 評価

そして、このコストは最初のガイドラインに直接つながります。

ガイドライン I:オプションで前提条件チェックを無効にする

すべての最適化を行った後、コードをインライン化した後、他のブランチを削除した後 (この投稿)、アルゴリズムを最適化した後 (次の投稿、私の 48)

まあ、それは完全に真実ではありません.速くなったので、プロファイリング コードを変更しました.その後、遅くなりました.

51 クラスです。 68 に固有の特定のインターフェイスがあります .たとえば、79 があります。 次のシグネチャを持つ関数:

void* allocate_node();

この関数は、プールからノードを返します。ノードはプールであるため、ノードのサイズを渡す必要はありません。サイズは暗黙的に指定されます!

しかし 84 のインターフェースは はプールに固有です。他のアロケーターは、92 に与えるサイズが必要です。 暗黙のノード サイズがないためです。

したがって、一般的なコードでは、関数を直接呼び出すと問題が発生します。

私は allocator_traits によってこの問題を解決しました。これらは特殊化されたインターフェイスに適応するように特化することができます。

次に、汎用コードがその 101 を呼び出します 、サイズ (および配置) を渡す必要があります:

static void* allocate_node(allocator_type &state, std::size_t size, std::size_t alignment);

プロファイリング コードでは、トレイトを介してアロケータにアクセスしました。

これは唯一だった 変更!コンパイラはすべてをインライン化しましたよね?もしそうなら、どのようにして大幅なパフォーマンスの変化につながるのでしょうか?

答えは、前提条件のチェックです。

一般的な 110 from にはカスタム サイズと配置パラメータがあります。明らかに、プールはそのノード サイズ以下のサイズのみを受け入れることができます。そうしないと、悪いことが起こります™。

これらを防ぐために、サイズと位置合わせのチェックがあります。これらのチェックは分岐です。 …

しかし、問題は分岐コードそのものではありませんでした。私が言ったように、分岐予測は正しく推測したはずです.

問題はアラインメント チェックでした。サポートされているプールのアラインメントの最大値は、124 に転送されるフリー リストによって決定されます。 小さいサイズの対数を計算します。これ 遅いです。

したがって、何があってもフルスピードが必要な場合は、高価な前提条件チェックを無効にするオプションを検討してください。それらは速度を低下させる可能性があります。

もちろん、本当に必要な場合にのみ使用してください 安全第一なので必要です。

ガイドライン II:到達不能コードを到達不能としてマークする

不必要に評価される式について言えば、私も自分の 133 を書いています。 macro.それは見えた そのように:

#if FOONATHAN_MEMORY_DEBUG_ASSERT && !defined(FOONATHAN_MEMORY_ASSERT)
 #define FOONATHAN_MEMORY_ASSERT(Expr) \
 static_cast<void>((Expr) || (detail::handle_failed_assert("Assertion \"" #Expr "\" failed",__FILE__, __LINE__, __func__), true))
#else
 #define FOONATHAN_MEMORY_ASSERT(Expr) static_cast<void>(Expr)
#endif

エラーを見つけましたか?

リリース モードでは、assert は評価を 148 にキャストします。 .これはまだ評価する

それを取り除くことで、簡単にスピードアップできました。

でも、間違いを犯して良かったです。

私がそこにいる間、私は自分の「到達不能」なマクロも見なければなりませんでした.

#if FOONATHAN_MEMORY_DEBUG_ASSERT && !defined(FOONATHAN_MEMORY_ASSERT)
 #define FOONATHAN_MEMORY_UNREACHABLE(Msg) \
 detail::handle_failed_assert("Unreachable code reached: " Msg, __FILE__, __LINE__, __func__)
#else
 #define FOONATHAN_MEMORY_UNREACHABLE(Msg)
#endif

ここでは正反対のことをしました!リリースモードでは何もしませんでした.

これも悪いことです。到達できないコード パスは、まあ、到達できません。コンパイラは、到達できない分岐を排除するようにコードを生成する必要があります。これにより、分岐が少なくなり、アセンブラー コードが短くなる可能性があります。

しかし、リリース モードでは、マクロは何も評価されないため、コンパイラはコード パスに到達できないという情報を取得しません。それを返すために、単純に 152 への呼び出しを挿入しました。 .

これはほんの些細なことですが、コード生成が改善されました。実際にプロファイリングしたわけではないので、まったく意味がないかもしれません.

より良い方法は、 166 のようなものを挿入することです または 178 .これらは、コードパスが到達不能であることを伝える適切な実装依存の方法です.しかし、 187 とにかくコンパイラが伝える必要がある属性。

ガイドライン III:検索を高速化するために並べ替えを維持することを検討してください

常に遅い分岐の特定の形式はループです。ループの反復回数を少なく保つと、より高速なコードが得られます。

フリー リストは、未使用のメモリ内に次のノードへのリンクを格納します。これは素晴らしいですが、すべてのノードが 199 より大きい場合にのみ機能します。 .200 - Modern C++ Design のアロケーターにインスパイアされた - 213 のみを保存することでそれを回避 すべてのオブジェクト サイズを許可しますが、メモリを (通常) 227 のチャンクに分割する必要があります。

割り当ては最初に空きメモリのあるチャンクを見つける必要があり、割り当て解除はメモリを所有するチャンクを見つける必要があります.速度を上げるために、ポインターは割り当てと割り当て解除に最後に使用されたチャンクに保存されます.最初にポインターがチェックされ、次にすべてのチャンクが検索されます。

割り当てに関しては、これはそれほど悪くありません。 237 ごとにのみ ノードは新しいチャンクを見つける必要があります。このチャンクは通常、最後に割り当てられたチャンクの近くにあるため、検索は高速です。

特定の割り当て解除シナリオの場合 - バタフライ ! - ただし、割り当て解除は良くありません。おそらく、ノードごとにチャンクのリストを検索する必要があるからです。

さらに悪いことに、パート 1 で説明したように、並べ替え順序に応じて、高速 一括 または高速 リバース バルク 、両方ではありません。なぜなら、片方向にリンクされたリストは一方向にしかトラバースできないからです.

でも待って!

チャンク リストについては、単一リンク リストに限定する必要はありません。二重リンク リストを使用できます。4/8 バイトのスペース オーバーヘッドがありますが、最小で格納できる 255 バイトと比較すると、これはあまりありません。

また、双方向にリンクされたリストでは双方向のトラバーサルが可能であるため、正しいチャンクの検索も一度に両方向に進むことができます。これにより、両方のバルクが高速になります。

しかし、蝶はどうですか?

チャンクが常にソートされている場合、速度が向上する可能性があります。最良の場合、リストを半分に分割できるからです。

249 のチャンクを見つけたいと考えてください。 .3 つのケースがあります:

    <リ>

    251 最後の解放チャンクに属します。

    <リ>

    260 最後の割り当て解除チャンクが管理するメモリよりも大きい。それから 275 のどこかにあります .

    <リ>

    288 最後の割り当て解除チャンクが管理するメモリよりも小さいです。それから 292 のどこかにあります .

その後、リストの対応する半分を検索するだけで済みます。適切なチャンクが見つかるまで、最初と最後から同時に検索できます。

これは価値のある最適化でしたが、コストがかかりました:小さな空きリストにメモリを挿入するとき、チャンクを挿入する適切な位置を見つけて、すべてが順序付けられたままになるようにする必要があります.Now 306 したがって、リスト (の一部) を走査する必要があります。

しかし、前回の投稿で論じたように、310 実際にメモリを割り当てる必要があるため、常に低速です。また、予測よりも多くのメモリを使用しているため、あまり頻繁に呼び出すべきではありません。

したがって、余分なコストはそれほど重要ではありません。しかし、物事を整理しておくことを決定するときは、すべてを念頭に置いてください。

ガイドライン IV:データ構造内の分岐を最小限に抑える

328 の他の検索 最後の割り当てチャンクから開始する必要があります。容量のある次のチャンクはおそらく近くにあります。

したがって、検索はそこから開始され、両方向に進みます.いいえ、問題に遭遇しました.ほとんどの場合、一方の方向から他方の方向に先立って最後に到達します.その後、それを停止し、反対方向のみを続行する必要があります.

これにより、コードが複雑になり、この投稿の目的にとってさらに重要なことに、ブランチが含まれます。

または、別の例を挙げてみましょう:双方向リンク リストそのものです。

双方向リンク リストの先頭にノードを挿入するには、次のようにします。

node->prev = nullptr;
node->next = first;

first = node;

if (!last) // insert into empty list
 last = node;

最初のノードを消去すると、次のようになります:

first = node->next;

if (node->next) // not the last node
 node->next->prev = nullptr;
else // last node
 last = nullptr;

どちらの関数にも - ご想像のとおり/見たことがある - 分岐があります。

そして、これらの分岐が実際にパフォーマンスに悪影響を及ぼしていることがわかります。どうしますか?

最初の例の問題は、1 つの反復子がリストの最後まで実行されることです。反復し続けることができればより良いでしょう。これは、循環リストにすることで実現できます。 336 最後のチャンクのポインターは最初のチャンクと 343 を指します 最初のもののポインターは最後のものを指します。これで、エッジの実行を心配することなく、リストに対して双方向に自由に反復できます。

また、二重にリンクされたリストの例では、問題は、リストが挿入前に空であるか、消去後に空である可能性があることです.これは、リストが決して空にならないようにすることで回避できます.常に最後のプロキシノードを使用するだけです. list.Now 354 の要素 何があっても常にそれを指すため、更新する必要はありません。

作成することでさらに最適化できます このプロキシ ノードの最後のポインタ、つまりそれをメンバーとして埋め込みます。その後、最後の real に直接アクセスできます list object.And erase はブランチを必要としません。これは、「最後のポインタ」、つまりプロキシにはまだ 364 があるためです。 アクセスして設定できるポインタ。

もちろん、これらの最適化にはコストがかかります。

循環リストの例では、チャンクのリストへのより高価な挿入、つまりより多くの分岐があります。しかし、前述したように、いずれにせよ挿入は遅いです。

また、プロキシ オブジェクトをメンバ変数として格納すると、コピー/移動が遅くなります。これは、プロキシ オブジェクトへのポインタを変更する必要があるためです。リスト ノードは別のリスト オブジェクトのプロキシを参照できません!しかし、挿入/消去が多く、コピー/移動が少ないリストがある場合、情報は価値があるかもしれません.

ガイドライン V:&&と || の隠しブランチに注意してください

ブランチについて話すとき、構文シュガーの背後に隠れている特定の条件付きジャンプがあります。たとえば、374 オペレーターは短絡評価を行っています。最初のオペランドが 385 の場合、2 番目のオペランドは評価されません .

これは便利ですが、どのように達成できますか?

アセンブラ レベルに条件付きジャンプがあります。

392 の実際の例を挙げましょう。 .循環リストは、メンバーとして二重リストの例のようにプロキシ ノードを格納することによって実装されます。それは次のようになりました:

struct chunk_base
{
 chunk_base *prev;
 chunk_base *next;
};

class small_free_memory_list
{
public:
 ...
 
private:
 chunk_base base_; 
};

// in the source file
struct chunk : chunk_base
{
 ...
};

401 412 に対して、チャンク リストに必要な 2 つのポインターしかありません。 フリーリストの管理に必要な実際のコードとメンバーが含まれています。428 を変換すると便利になりました 430 に .これはもちろん、アドレスが 440 と等しくない場合にのみ可能です。 .だから私は小さなヘルパーを書きました:

chunk* make_chunk(chunk_base *ptr)
{
 return ptr == &base_ ? nullptr : static_cast<chunk*>(ptr);
}

次のように使用できるようになりました:

if (auto c = make_chunk(ptr))
{
 // do sth with c
}

しかし、時々 453 へのポインタだけです 必要なのはそれだけではありません。追加のチェックも必要です。容量のあるチャンクの検索と同様に、チャンクに容量があるかどうかも確認する必要があります。

auto c = make_chunk(ptr);
if (c && c->capacity > 0u)
{
 // do sth with c
}

464 475 のメンバ変数です .これで条件ができました。

どうすれば回避できますか?

483 を入れるだけです メンバーを 498 に下げる .その後、 501 を持っている間にアクセスできます のみ - より大きな空きリスト オブジェクトを犠牲にして。

結論

ブランチは、アプリケーションの速度を低下させることがあります。ブランチは削除できますが、他の操作でより多くの作業が必要になります。

ここでは、実行する各最適化のプロファイルを作成することが特に重要です。ブランチを削除するために、他の場所に追加コストを導入することを時期尚早に決定しないでください。これは、少数の特殊なケースでのみ利点となります。

もう一度繰り返します:すべての最適化の前後にプロファイルを作成します.目に見えるプラスの効果があり、他の場所での追加コストが害を及ぼさないと確信している場合にのみ、最適化を維持します.そうでない場合は元に戻します.

シリーズのこの時点で、さまざまなアロケーターの最適化について多くのことを示してきました。シリーズの次の (おそらく最終) パートでは、519 の変更を示して終了します。 そして最後に、私がどのようにしてこのような高速の 526 を管理したかを説明します .抽象化のコストとアルゴリズムがすべてです。

読み続けてください!