Boost.Pool #2 に打ち勝った方法:インライン展開が重要

関数の呼び出しには一定のオーバーヘッドがあります。レジスタを保存し、新しいスタックフレームをプッシュする必要があります…小さな関数の場合、このオーバーヘッドは関数の実際の実装よりも大きくなります!

それらについては、コンパイラが実装を呼び出しサイトに直接コピーアンドペーストする方がはるかに優れています。これがインライン化の機能です。

幸いなことに、コンパイラは通常、この最適化を行うことができます.それとも可能でしょうか?

このシリーズでは、私が行った変更について説明し、Boost.Pool を打ち負かす過程で学んだ最適化に関するいくつかの教訓を共有します。今回は、インライン化について説明します。ガイドラインの一部を共有します。学習したので、メモリの内部コードと設計のいくつかを見てみましょう.

ガイドライン I:リンク時の最適化を有効にする

Boost.Pool には (不当な) 利点があります:完全にヘッダーのみです。

関数がヘッダーで定義されている場合、コンパイラは非常に簡単にインライン化できます。

全体ライブラリはヘッダーで定義されます - Boost.Pool の場合と同様に、コンパイラは呼び出したすべての関数の実装を確認し、手間をかけずにインライン化できます。これにより、非常に簡単に高速化できます。

一方、私のライブラリは完全にヘッダーのみではありません。問題のアロケータ - memory_stack と memory_pool は実際にはテンプレートですが、実装の多くは含まれていません。それを説明するために、私のライブラリの内部構造を調べてみましょう少し。

パート 1 で、スタックとプールの両方が巨大なメモリブロックを取り、それらを割り当てに使用することを非常に簡単に説明しました。巨大なメモリブロックで動作し、それらに対して特定の割り当て戦略を使用するアロケータは、アリーナアロケータ .彼らは 2 つのことをしなければなりません:

1 つまたは複数の巨大なメモリブロックを管理します。管理とは、適切な割り当てとその後の割り当て解除を意味します。これは、それらへのポインターをどこかに保存することも意味します。

何らかの方法で現在の (またはすべての) メモリブロックを操作します。例えば。スタックは現在のブロックのトップポインターを維持し、プールはそれらを細分化し、各ノードをフリーリストに入れます。

また、単一責任の原則に従って、これも 2 つの異なるクラスで行いました。メモリブロックの管理はクラステンプレート memory_arena にアウトソーシングされ、割り当ては内部クラスによって処理されます。

そのうちの 1 つは 02 です。 18 の場合 .これは、単一のメモリブロックに対するスタックアロケータです。3 つのクラス 28 、 36 と 43 58 で使用される 3 つのフリーリストの実装です。 .

すべての内部クラスは、自分自身でメモリを割り当てず、作業中のメモリを所有しないという共通点があります。また、これらの内部クラスはヘッダーのみではなく、ソースファイルで定義されています。

これらの内部クラスの助けを借りて、アリーナアロケーター自体は簡単です。内部クラスにまだ使用可能なメモリがある場合は、内部クラスに転送します。そうでない場合は、63 から新しいメモリブロックを要求します。 .

たとえば、これは 75 のコード全体です :

void* allocate_node()
{
 if (free_list_.empty())
 allocate_block();
 FOONATHAN_MEMORY_ASSERT(!free_list_.empty());
 return free_list_.allocate();
}

フリーリストが空の場合、新しいメモリブロックを要求し、フリーリストに挿入します。これは、ヘルパー関数 88 によって行われます。 .Else またはその後は 94 を呼び出すだけです .Deallocation はさらに単純です。108 に転送するだけです。 .

また、内部関数の割り当て関数自体は非常に短いため、インライン化の最適な候補です。ただし、ソースファイルで定義されているため、内部ヘルパーの呼び出しではなく、ヘッダーのみのテンプレートの呼び出しのみがインライン化されます。

関数をヘッダーファイルで宣言するかソースファイルで宣言するかは問題ではないと誰もが言うので、これには驚かれるかもしれません。コンパイラは十分にスマートです。いずれにせよ単なるヒントです.

私も驚きました。

結局のところ、コンパイラは誰もが言うようにインライン化できません。

これに役立つのは、いわゆるリンク時間最適化 (LTO) です。現在 GCC はより多くのコードをインライン化できます。これだけで、1 行も変更することなく、最大 500% 高速化できました!

CMake ベースのプロジェクトと GCC では、126 の両方を変更する必要があります。そして 131 、 148 を追加

ガイドライン II:アセンブラを見る

この時点で、コンパイラが呼び出しを完全にインライン化していないことがどうしてわかったのか不思議に思うかもしれません。

答えは簡単です。私は生成されたアセンブラコードを見てきました。パフォーマンスが重要なコードを記述するときは、常にアセンブラを見て、優れた抽象化がすべて最適化されていることを確認する必要があります。

生成されたアセンブラは、CMake ベースのプロジェクトで非常に簡単に確認できます。158 を変更するだけです。正しいフラグを含めます。 167

次に、通常どおりコードをビルドします。ビルドディレクトリ内に、170 のファイルがあります。これが探しているアセンブラ出力です。

テンプレートがインスタンス化されていない限り、実際にはコンパイルされないため、テンプレートのアセンブラーコードを取得するのはよりトリッキーです。また、それらの定義は、テンプレートが定義されているファイル (これはヘッダーです。私にとってうまくいくのは、明示的なテンプレートのインスタンス化を伴う空のファイルです。アセンブラー出力でテンプレートコード全体を見つけることができます。

コードが適切にインライン化されているかどうかをアセンブラで検査するのは、実際よりも難しいように聞こえますが、心配する必要はありません。実際にアセンブラを理解している必要はありません。

関数が 180 かどうかを知りたいとしましょうインライン化されています。そのためには、呼び出し関数 194 を確認する必要がありますそこにインライン化されているかどうか。特定の関数がフラット化されているかどうかのみを確認できます呼び出された関数のインライン化を通じて。

呼び出し元の関数の名前を含む意味不明な部分が見つかるまで、コードに目を通します。これは 壊れた 関数の名前。そこにアセンブラコードがあります。

次に 208 を探しますまたは 213 オペランドがインライン化されるべき関数名である命令または同様のもの.アセンブラコードにそれらが含まれている場合、呼び出し元の関数はまだアセンブラレベルでいくつかの関数を呼び出しています.経験則として、224 233 よりも「悪い」 .A 246 256 に対して、命令を別のコードの場所に直接ジャンプするだけです。より高価な「通常の」関数呼び出しです。

また、アセンブラを理解するのに役立つのは、一部のコード部分を選択的にコメントアウトして、どのステートメントがどのアセンブラ命令を生成するかを確認することです。

ガイドライン III:パフォーマンスクリティカルな関数をヘッダーファイルに入れる

リンク時の最適化を有効にしても、コンパイラは必要なすべてをインライン展開することはできません。

269 を考えてみましょう例として:

void* allocate(std::size_t size, std::size_t alignment)
{
 detail::check_allocation_size(size, next_capacity(), info());
 auto mem = stack_.allocate(block_end(), size, alignment);
 if (!mem)
 {
 allocate_block();
 mem = stack_.allocate(block_end(), size, alignment);
 FOONATHAN_MEMORY_ASSERT(mem);
 }
 return mem;
}

まず、273 を呼び出します。 284 で .内部スタックの固定メモリが使い果たされたためにこの割り当てが失敗した場合、新しいブロックが割り当てられます.再び、ヘルパー関数 295 will - 307 と同じように - 316 から新しいメモリブロックを要求しますその後、制限に達することなく固定スタックから割り当てることができます。これは、最初の行のチェックによって保証されます。

ただし、ヘルパー関数 322 の呼び出しに注意してください固定スタック内。これは、スタックがしないために必要です。現在のメモリブロックの末尾へのポインタを保持し、現在のスタックの一番上へのポインタを維持します。

ただし、現在のメモリブロックに十分なスペースがあるかどうかを判断するには、この情報が必要です。そのため、割り当て関数に渡されます。

335 349 から現在のブロックをリクエストします 352 経由 function.A 366 それへのポインターとサイズ情報で構成されているため、その末尾は非常に簡単に計算できます。

375 アリーナは成長する可能性があるため、つまり複数のメモリブロックを一度に管理するため、それらすべてをどこかに格納する必要があります。これは、それらをメモリブロックの個別にリンクされたリストに配置することによって行われます。それぞれの次のポインタブロックはブロック自体に埋め込まれます。383 と同様の方法で /399 、 401 BlockAllocator によってカスタマイズでき、他の複数のクラスを管理するだけなので、それ自体がテンプレートです。

そのうちの 1 つが 411 です。このリンクされたリストを実装します。次のようになります:

class memory_block_stack
{
public:
 // default ctor, dtor, move, swap omitted
 // typedefs omitted

 // pushes a memory block
 void push(allocated_mb block) FOONATHAN_NOEXCEPT;

 // pops a memory block and returns the original block
 allocated_mb pop() FOONATHAN_NOEXCEPT;

 // ...

 inserted_mb top() const FOONATHAN_NOEXCEPT;

 // empty(), size()

private:
 struct node;
 node *head_;
};

概念的には、2 種類のメモリブロックを扱います。421 によって直接返されるもの .それらは 432 に渡されます 449 によって返されますそして、アリーナアロケータで使用できるブロックがあります。これらは、457 によって返されるブロックよりも少し小さいです。リストノードも含まれているためです。一番上のノードは 469 によって返されます。、これは 475 によって直接呼び出されます .

クラスは最初のノードへのポインターのみを必要とするため、ノードタイプ自体が不完全なタイプであり、ヘッダーで定義されている可能性があります。これにより、クライアントにまったく影響を与えずにノードタイプを変更できます。

487 ブロック内にノードタイプを作成し、ブロックサイズが小さくなったため、ブロックサイズを調整します。リストにも挿入します。497 リストからノードを消去し、ブロックサイズを再び増やします。

500 ブロックサイズを調整する必要はありませんが、ポインターを調整する必要があります。ですが、アリーナアロケーターによってオーバーライドされてはなりません。次のようになります:

memory_block_stack::inserted_mb memory_block_stack::top() const FOONATHAN_NOEXCEPT
{
 FOONATHAN_MEMORY_ASSERT(head_);
 auto mem = static_cast<void*>(head_);
 return {static_cast<char*>(mem) + node::offset, head_->usable_size};
}

なぜなら 521 530 への両方のアクセスが必要ですのメンバー変数と 544 へ 557 のサイズと完全な定義が必要です。ヘッダーに直接入れることはできません - 566 の宣言しかありませんさらに重要なことに、コンパイラは 573 への呼び出しをインライン化できません。したがって、最終的に 589 への呼び出し 590 内 .

これはまずい。

関数呼び出しのオーバーヘッドは、ここで割り当てコードの実際のコストよりも大きくなります!

したがって、このオーバーヘッドを回避するために、コンパイル時の分離よりも速度を選択し、604 を定義しました。 619 を許可するヘッダー内

ガイドライン IV:パフォーマンスクリティカルなコードパスを特定する

やみくもにガイドライン III に従い、パフォーマンスクリティカルな関数によって呼び出されるすべての関数をヘッダーファイルに移動する前に、次のガイドラインを教えてください。

最も些細な機能を除く各機能には、複数の実行パスがあります。通常のコードパス、エラーの場合に実行される異常なコードパス、およびその他のコードパスがあります。各コードパスを見て、ほとんどの場合に実行されるパスを特定します。次に、それらのみを最適化します。

たとえば、620 を見てください。もう一度:

void* allocate(std::size_t size, std::size_t alignment)
{
 if (size > next_capacity())
 handle_error();
 auto mem = stack_.allocate(block_end(), size, alignment);
 if (!mem)
 {
 allocate_block();
 mem = stack_.allocate(block_end(), size, alignment);
 FOONATHAN_MEMORY_ASSERT(mem);
 }
 return mem;
}

この関数には 4 つのコードパスがあり、そのうちの 3 つが直接表示されます:

異常なもの:If 633 645 より大きいエラー処理に直接進みます。

スタックに十分なメモリがある場合:すべての 659 s は 661 です関数は 679 の結果を返すだけです .

スタックに十分なメモリがなく、新しいブロックの割り当てが成功した場合:次に、2 番目の 686

スタックに十分なメモリがなく、新しいブロックの割り当てが成功した場合:次に、2 番目の 692 も入力されていますが、 706 エラー処理ルーチンに入ります。

これら 4 つのケースのうち、2 番目のケースが最も一般的なケースです。ケース 1 と 4 は、定義上最適化する必要のないエラー処理ルーチンであり、ケース 3 はコストがかかります (新しいメモリをメモリから割り当てる必要があります)。デフォルト実装の OS)。

ケース 2 は、割り当て自体が少数の高速な命令で構成されているため、インライン化が最も重要なケースでもあります。そのため、他のケースではなく、すべてをインライン化するように特別な注意を払いました。たとえば、ケース 3 です。最終的に 716 を呼び出します新しいブロックを保存するために、ヘッダーファイルに入れられない

ガイドライン V:デバッグ機能でコンパイラを支援する

不適切なメモリ管理は、追跡が困難な多くのエラーにつながる可能性があります。そのため、優れた (メモリ関連の) ライブラリは、デバッグを支援する方法を提供します。私のライブラリも例外ではありません。

デバッグモードでは、デバッグチェックと機能の複雑なシステムがアクティブです。これらは、バッファオーバーフローや無効な割り当て解除ポインタ/ダブルフリーの多くのケースなど、一般的なエラーをすべて単独で検出するか、ユーザーがそれらを検出するのに役立ちます。 -after- free.もちろん、これらの機能にはかなりのオーバーヘッドがあるため、リリースモードでは無効になっています。オーバーヘッドはゼロになるはずです。そもそも存在しなかったようにすべきです!

それらを実装する一般的な方法は、それを正確に保証することです:無効化されている場合、それらは存在しません。

これはマクロを意味します。

しかし、インターフェースマクロは絶対に嫌いです 721 .したがって、絶対に必要な場合にのみそれらを使用し、可能な場合はいつでも別の実装方法を使用します.

デバッグシステムの完全な説明は、ここでは範囲外です。

代わりに、737 だけに注目しましょう .これは 741 と同様に機能します配列に特定の値を入力しますが、758 の場合のみです 769 に設定されています .

たとえば、use-after-free エラーの検出を支援するためにメモリが解放された後に呼び出されます。しかし、この関数はさらに多くのチェックの基礎となるため、すべてのアロケータで頻繁に呼び出されます。ガイドライン IV によると、完全に消えることが非常に重要です。デバッグ充填が無効になっている場合。

774 のように実装しました 789 です異なる値を指定:

#if FOONATHAN_MEMORY_DEBUG_FILL
 void detail::debug_fill(void *memory, std::size_t size, debug_magic m) FOONATHAN_NOEXCEPT
 {
 // simplified
 std::memset(memory, static_cast<int>(m), size);
 }

 // other functions omitted
#else
 void detail::debug_fill(void *, std::size_t, debug_magic) FOONATHAN_NOEXCEPT {}

 // likewise
#endif

791 の場合 800 です、関数の本体が空です。本体が空の関数は完全に最適化する必要がありますよね?

このコードはソースファイルにあります。そして、結局のところ、コンパイラは関数呼び出しのセットアップコード全体を実行して、呼び出された関数をすぐに返します!

したがって、適切なインライン化を実現するために、すべてのデバッグ関数の空の定義をヘッダーファイルに抽出しました。その後、それらはアセンブラーの出力から実際に消えます。