Boost.Pool に勝つ方法 #4:抽象化とアルゴリズムについて

最後の投稿では、確実にインライン化する、ブランチを削除するなどの低レベルの手法を示しました。

しかし、これらのテクニックだけでは十分ではありませんでした.

このシリーズでは、私が行った変更について説明し、Boost.Pool を打ち負かす過程で学んだ最適化に関するいくつかの教訓を共有します。最後の投稿では、抽象化を設計する際にこれらの手法を適用する方法とスマート アルゴリズムの重要性を示します。

抽象化について

2 番目の投稿では、07 の 0.5 実装を紹介しました。 :

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;
}

10 に転送するだけです .それは次のように見えました (ここに示していないデバッグ要素とコメントを差し引いたもの):

void* fixed_memory_stack::allocate(const char *end, std::size_t size, std::size_t alignment) FOONATHAN_NOEXCEPT
{
 if (cur_ == nullptr) // stack is empty
 return nullptr;

 auto remaining = std::size_t(end - cur_);
 auto offset = align_offset(cur_, alignment); // calculate offset necessary for alignment

 if (offset + size > remaining)
 return nullptr; // not enough memory available
 cur_ += offset; // properly align cur

 auto memory = cur_; // cur_ now points to the memory needed
 cur_ += size; // bump cur_ past the memory

 return memory;
}

22 メモリ ブロック内の現在のポインターのみを維持する小さなクラスです。割り当ては単にこのポインターをバンプします。このクラスは 39 を維持しないことに注意してください。 パート 2 で説明したように、ブロック内の残りのバイト数を計算する関数に渡す必要があります。

このクラスは、従来の OOP パラダイムに従います。スタックのデータ - 42 ポインター - カプセル化され、メンバー関数によってのみ変更されます。これらのメンバー関数は、一般 をモデル化します そのような単純なスタックでやりたいことの種類:59 、 60 以前に照会した場所と 75 に 場所を照会します。

このインターフェースでは、83 -複数のブロックで操作できる必要がある-上記のように使用します。最初に現在のブロックに割り当てようとします。それが失敗した場合、新しいブロックを割り当てて再試行します。

この抽象化の問題

しかし、上記のコードは遅い .のように、本当に 遅い.インライン化したら良くなったが、それでも遅い.

なぜですか?

コンパイラの仕事をして、2 つの呼び出しを手動でインライン化しましょう:

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);
 void *mem;
 if (stack_.cur_ == nullptr)
 mem = nullptr;
 else
 {
 auto remaining = std::size_t(block_end() - stack_.cur_);
 auto offset = detail::align_offset(stack_.cur_, alignment);

 if (offset + size > remaining)
 mem = nullptr;
 else
 {
 stack_.cur_ += offset;

 mem = stack_.cur_;
 cur_ += size;
 }
 }

 if (!mem)
 {
 allocate_block();
 //mem = stack_.allocate(block_end(), size, alignment);
 if (stack_.cur_ == nullptr)
 mem = nullptr;
 else
 {
 auto remaining = std::size_t(block_end() - stack_.cur_);
 auto offset = detail::align_offset(stack_.cur_, alignment);

 if (offset + size > remaining)
 mem = nullptr;
 else
 {
 stack_.cur_ += offset;

 mem = stack_.cur_;
 cur_ += size;
 }
 }
 FOONATHAN_MEMORY_ASSERT(mem);
 }
 return mem;
}

これは大量のコードで、一部は重複しています。また、92 の事後条件を考えると、コードの他の部分は不要です。 .コンパイラもそれを最適化できません.まず第一に、事後条件がありません.

もっと良くする

それでは、手動で最適化しましょう。

101 の最後に 115 を要求するアサーションがあります。 124 の事後条件であるため、これは論理的です。 サイズが 139 の新しいメモリ ブロックが割り当てられていることです。 .そして 143 の前提条件 メモリが 157 より小さいことです .

だから 169 178 です その分岐の終わりは、事前または事後条件の違反によるものです。したがって、180 になる分岐を安全に削除できます。 191 であること :

void* allocate(std::size_t size, std::size_t alignment)
{
 detail::check_allocation_size(size, next_capacity(), info());

 void *mem;
 if (stack_.cur_ == nullptr)
 mem = nullptr;
 else
 {
 auto remaining = std::size_t(block_end() - stack_.cur_);
 auto offset = detail::align_offset(stack_.cur_, alignment);

 if (offset + size > remaining)
 mem = nullptr;
 else
 {
 stack_.cur_ += offset;

 mem = stack_.cur_;
 cur_ += size;
 }
 }

 if (!mem)
 {
 allocate_block();

 auto offset = detail::align_offset(stack_.cur_, alignment);

 stack_.cur_ += offset;

 mem = stack_.cur_;
 cur_ += size;
 }
 return mem;
}

最初のブランチを見ると、ネストされた 204 が 2 つあります。 -218 cases.Because 228 230 で動作します これは最初のものの外に置くことができます. 242 の計算 しかし、変数を削除して短絡状態の 2 番目のブランチで実行すると、両方のケースをマージできます:

void* allocate(std::size_t size, std::size_t alignment)
{
 detail::check_allocation_size(size, next_capacity(), info());

 void *mem;

 auto offset = detail::align_offset(stack_.cur_, alignment);
 if (stack_.cur_ && offset + size <= std::size_t(block_end() - stack_.cur_))
 {
 stack_.cur_ += offset;

 mem = stack_.cur_;
 cur_ += size;
 }
 else
 mem = nullptr;

 if (!mem)
 {
 allocate_block();

 auto offset = detail::align_offset(stack_.cur_, alignment);
 stack_.cur_ += offset;

 mem = stack_.cur_;
 cur_ += size;

 FOONATHAN_MEMORY_ASSERT(mem);
 }
 return mem;
}

これで、2 番目の 251 がはっきりとわかります 266 だけです さらに、279 の値の計算 そして次の 283 の隆起 2 つの分岐でまったく同じように実行されます。そのため、重複したコードを関数の最後に移動して、1 回だけ実行できます。

void* allocate(std::size_t size, std::size_t alignment)
{
 detail::check_allocation_size(size, next_capacity(), info());

 auto offset = detail::align_offset(stack_.cur_, alignment);
 if (stack_.cur_ && offset + size <= std::size_t(block_end() - stack_.cur_))
 {
 stack_.cur_ += offset;
 }
 else
 {
 allocate_block();

 auto offset = detail::align_offset(stack_.cur_, alignment);
 stack_.cur_ += offset;
 }

 auto mem = stack_.cur_;
 cur_ += size;

 return mem;
}

まだ少し重複があります。スタックのアライメントは両方のブランチで行われます。ここでは大したことではありませんが、実際のコードではアライメント バッファを埋め、デバッグ フェンスを追加する必要もあります。これはかなりの量の重複です。

したがって、配置は最後に配置できます。次に、最初の 297 完全に空なので、条件を逆にして 301 の前に置くことで削除できます :

void* allocate(std::size_t size, std::size_t alignment)
{
 auto offset = detail::align_offset(stack_.cur_, alignment);
 if (stack_.cur_ || offset + size <= std::size_t(block_end() - stack_.cur_))
 {
 allocate_block();

 // recalculate alignment offset
 offset = detail::align_offset(stack_.cur_, alignment);

 detail::check_allocation_size(offset + size, next_capacity(), info());
 }

 stack_.cur_ += offset;
 auto mem = stack_.cur_;
 cur_ += size;

 return mem;
}

これがコードの最後の部分です。最初のバージョンと比較すると、このコードがはるかに高速で小さいことがはっきりとわかります。

実際に必要な抽象化を反映する

上記のコードは 319 を直接操作します の唯一のメンバーです。もしそれが正しければ、おそらくそのままにしておくでしょう。実際、私はおそらく 327 を削除します それはただのポインターだからです。

しかし、実際の製品コードは少し複雑で、毎回 333 です。 オフセットによって増加すると、メモリ範囲が満たされます。したがって、ポインタのインクリメントだけでなく、 345 の呼び出しでもあります .これら 2 つのタスクは常に一緒に実行する必要があるため、ここで抽象化することは理にかなっています。

ここで実際に行う必要があるのはどのような機能ですか?

<リ>

355 への読み取りアクセス権があります 365 の状態で 376 の呼び出しでも .これは、getter 関数 383 によって実行できます。

<リ>

位置合わせプロセスのために、ポインターを一定量インクリメントする (また、古い場所と新しい場所の間のメモリを埋める) 必要があります。したがって、関数 392 が必要です .

<リ>

インクリメント (およびフィル) する必要がありますが、実際のメモリ割り当てのために古い場所にアクセスする必要があります。したがって、関数 403 が必要です .

この抽象化により、コードは次のようになります:

void* allocate(std::size_t size, std::size_t alignment)
{
 auto offset = detail::align_offset(stack_.top(), alignment);
 if (stack_.top() || offset + size <= std::size_t(block_end() - stack_.top()))
 {
 allocate_block();

 // recalculate alignment offset
 offset = detail::align_offset(stack_.top(), alignment);

 detail::check_allocation_size(offset + size, next_capacity(), info());
 }

 stack_.bump(offset);
 return stack_.bump_return(size);
}

関数の実装は単純明快です。

これが効率的なコードの外観です!

ガイドライン:適切な抽象化レベルを選択してください

抽象化は良いことです。

これにより、開発者は小さくて複雑な詳細を常に気にする必要がなくなり、より高いレベルのタスクのための使いやすいビルディング ブロックを作成できるようになります。また、抽象化により、コードの重複が防止され、現在の機能に集中できるようになるため、エラーの可能性が減少します。

抽象化はネストされ、コア関数は高レベル関数によって呼び出される中間レベル関数によって呼び出されます.そして明らかに、高レベル抽象化の設計は低レベル抽象化とは根本的に異なります.

低レベルの抽象化は、本当に小さな問題しか解決しません.しかし、それは迅速かつ適切に解決します.それはまた、一般的にも解決します.低レベルの抽象化を使用することで、より冗長になるという犠牲を払って、あなたが望むあらゆる問題を解決することができます.

高レベルの抽象化では、複数の低レベルの抽象化を結合することで、この冗長性を取り除きます。高レベルの抽象化のクライアントは、同じタスクを実行するために記述するコードを少なくする必要がありますが、詳細を制御することも少なく、問題を解決するだけです 抽象 問題。

元のコードの問題は、私が 419 を作ったことです。 高レベルの抽象化です。「スタックからメモリを割り当てる」問題を解決しました。非常にうまく機能し、使いやすかったです。

問題は、それを使用して別の高レベルの抽象化 421 を実装することでした。 、あまり効果がありませんでした。431 実際には、「スタックからのメモリの割り当て」を解決する抽象化は必要ありませんでした。それがそれです。

「メモリ ブロック内のトップ ポインターの管理」を解決する抽象化が必要でした。これは、より効率的な抽象化の選択であり、正しい選択でした。

オブジェクト指向設計の落とし穴にぶち当たりました。 444 を書くとき スタック アロケータのユーザーを念頭に置いていたので、メモリ スタックで実行したい操作を自然に与えました。これにより、高レベルの抽象化が行われました。

実際の使用は簡単で、単純な実装が可能でしたが、抽象化のレベルが適切でなかったため、非効率的でした.より低レベルの抽象化に切り替えることで、パフォーマンスが向上しました.

したがって、クラスを設計するときは常に 実際の使用法と必要な抽象化レベルを念頭に置いてください。特に 455 にあるクラス 名前空間には高レベルの抽象化を含めるべきではありません。

常に考えてください:

<リ>

高レベルですか、それとも低レベルですか?

<リ>

クラスはどこで使用されますか?

<リ>

それは何のために使われますか?

<リ>

最も重要なこと:正確 解決すべき問題は?

これは、使いやすいだけでなく効率的な抽象化を作成するのに役立ちます。

アルゴリズムについて

「遅い」0.5 に戻っても、最適化前は 466 逆バルクでパフォーマンスを失うことなく、バルクで順序付けられたプールよりも大幅に高速でした。

最初の投稿で説明したように、順序付けられた空きリストの割り当てを解除するには、ノードを挿入する正しい位置を検索するためにリストを調べる必要があります。リンクされたリストはランダム アクセスではなく、ノード 474 、ノード 489 にアクセスする必要があります 492 へ 最初.したがって、それらは線形にのみトラバースできます.位置の検索は、連続メモリで実行できる高速バイナリ検索を実行できません (500 のように) ) ただし、あるノードから次のノードに移動する必要があります。

また、フリー リストは単独でリンクされたリストであるため、選択できるのは並べ替え順序だけです。それに応じて、ノードを最初に直接挿入する必要があるため、一括または一括逆順のいずれかが高速です。それ以外の場合は、検索が必要です。 全体を調べる 適切な位置を見つける前にリストします。同じ理由で、順序付けされた Boost.Pool のバタフライは中間にあります。短いトラバーサルしか必要としないノードもあれば、長いトラバーサルしか必要としないノードもあります。

では、どうすれば高速化できるでしょうか?私は明らかにそれを管理しました.どのように?

a) 連続ストレージを使用する

適切な二分探索を行うには、継続的なストレージが必要です。そうすると、解放は簡単に対数的な複雑さを持ちます。

ただし、フリー リストで連続ストレージを使用することはできません。これには、実際のノードなどへのポインターの連続シーケンスのためだけに余分なメモリを割り当てる必要があります。

独自のアロケーターを取得できるようになるまでに多くの追加の簿記メモリを実際に必要とするアロケーターは、一種の無意味なアロケーターです。

b) リストの最後のノードを記憶する

フリー リストの最初のノードだけでなく、最後のノードも覚えていれば、少なくとも最後に挿入するという最悪のケースを回避できます。トラバースする前に、最後にチェックするだけです。

これにより、実際には両方のバルクが高速になります.

しかし、これだけでも、標準がその仕様で行うよりもさらに不正行為です.バタフライにも役に立ちません.手動の最適化なしで、私のリストは同等のパフォーマンスを示しました!

c) リスト内の最後に割り当て解除されたノードを記憶する

それでは、最後のステップをさらに進めましょう。リストの最後を覚える代わりに (またはそれに加えて)、最後に割り当て解除されたノードを覚えておいてください。次に、そこを確認してください。

最後に解放されたノードのアドレスが現在のアドレスよりも小さい場合は、先頭から検索します。そうでない場合は、最後に解放されたノードから検索します。

指定されたソート順では、割り当てられたノードが最後のノードよりも大きい場合、つまり、割り当てと同じ順序で割り当て解除された場合は非常に高速ですが、逆の順序ではノードを配置する必要があるため、それでも低速です最後のノードの前です。これは、リストを先頭からトラバースすることを意味します。これは、単独でリンクされたリストの 1 つのノードだけに戻ることはできないためです。

d) 双方向リンク リストを使用する

「ねえ」、「それは 517 のチャンクで発生したのと同じ問題です。 パート 3 に戻ります。私は何をすべきかを知っています:二重リンク リストを使用してください。」

その通りです。それはまったく同じ問題です。また、マーカーから始まるソートされたリスト内の位置を見つける必要がありました。双方向にリンクされたリストを使用すると、リストを双方向にトラバースできるため、非常に簡単に後方に移動できます。

しかし、双方向リンク リストには欠点があります。ポインタが 1 つだけではなく、2 つあるのです。小さな空きリストでは、すべてのノードではなくチャンクだけがポインタを持っていたため、このオーバーヘッドはそれほど悪くはありませんでした。

しかし、順序付けられた空きリストでは、ポインターはノードに直接埋め込まれます。それらのためのスペースが必要です。ノードは十分な大きさでなければなりません。通常の空きリストは、最小サイズ 524<しか必要としないため、単独でリンクされます。 /コード> .しかし、二重にリンクされたリストでは、このサイズは 2 倍になります!

// advances a pointer pair forward/backward
void xor_list_iter_next(char *&cur, char *&prev)
{
 auto next = xor_list_get_other(cur, prev);
 prev = cur;
 cur = next;
}

char *xor_list_get_other(void *address, char *prev_or_next)
{
 return from_int(get_int(address) ^ to_int(prev_or_next));
}

void xor_list_change(void *address, char *old_ptr, char *new_ptr)
{
 auto other = xor_list_get_other(address, old_ptr);
 xor_list_set(address, other, new_ptr);
}

void xor_list_set(void *address, char *prev, char *next)
{
 set_int(address, to_int(prev) ^ to_int(next));
}