私がメモリ 0.5 をリリースしたとき、reddit のある人が私のライブラリと Boost.Pool との比較を尋ねてきました。私は機能の比較を提供し、Boost と私の実装の両方をすばやくプロファイリングしました。悲しいことに、Boost.Pool は私のライブラリを打ち負かしました - ほとんどの場合.
そのため、過去数週間にわたって、パフォーマンスの問題に対処し、実装を書き直しました。したがって、バージョン 0.5-1 でも、基本的には同じアルゴリズムを使用していますが、現在、私のライブラリは Boost.Pool と同等か高速です。
このシリーズでは、私が行った変更について説明し、変更を行って学んだ最適化に関するいくつかの教訓を共有します。最初の部分では、ここで使用されるさまざまな割り当てアルゴリズムを紹介し、プロファイリング結果の概要を示します。
アロケーター
私のライブラリには、アロケータでいくつかのパフォーマンス比較を実行する単純なプロファイリング ターゲットが含まれています。それらは:
- <リ>
ヒープ :私の heap_allocator は、std::malloc() を使用して割り当てます .
新規 :私の new_allocator は、::operator new を使用して割り当てます .
スタック :スタック アロケータをモデル化した私の memory_stack 。スタック アロケータは巨大なメモリ ブロックを取り、トップ ポインタを維持します。割り当ては、トップ ポインターを必要なバイト数だけ前方にシフトし、古い位置を返すだけです。解放は直接サポートされていません。アンワインドのみです 以前に照会された場所へのトップ ポインター。
<リ>ノード :私の memory_pool、通常のメモリ プール。プールは 1 つのサイズ (ノード サイズ) の割り当てのみを処理できます .巨大なメモリ ブロックを使用し、現在空いているすべてのノードのリンク リストを維持します。割り当ては単純に最初のノードをポップし、割り当て解除はノードをリストに戻します。空きノードのメモリは無料なので、リンクをそれらに直接埋め込むことができます。ノードのサイズが小さすぎる場合は、大きくする必要があります。
<リ>
配列 :私の memory_pool<array_pool> 、配列割り当てのサポートが向上したプール。配列の割り当てでは、ノードをメモリに連続して格納する必要があります。最初はそうです。しかし、リストで多くの (割り当て解除) を行った後、ノードをシャッフルすることができます。したがって、この無料リストは順序付けされています 、ノードは常にソートされたままです。これにより遅くなりますが、配列割り当てのサポートは改善されています。
小 :私の memory_pool<small_node_pool> 小さなノード用に最適化されたプール。フリー リストにポインターを格納する代わりに、インデックスを unsigned char として格納するだけです。 .これにより、小さなノードが可能になりますが、unsigned char 以降、簿記が少し増えます。 (通常) 256 しか保持できません 異なる値。そのため、チャンクのリストが維持され、それぞれに個別の空きリストがあります。これは、最新の C++ 設計で説明されているアロケータと同じ設計ですが、わずかに最適化されています。
また、この比較では、Boost のプールの 2 つのバリアントを使用します。1 つは「通常の」割り当てを使用し、もう 1 つは ordered_ を使用します。 バージョン。最初のものは私の Node に似ています プール、私の 配列 への 2 つ目 プール。
Node を参照します 通常/ノード プールとしての順不同の Boost.Pool と私の配列 ordered/array プールとして順序付けられた Boost.Pool どちらも類似した特性とアルゴリズムを持っているためです.
プロファイリング構造
プロファイリング コードは、以下に説明する各割り当て戦略を 1024 回実行し、ナノ秒単位で必要な最小時間を取ります。 すべて (デバッグ) ライブラリのチェックが無効になり、リンク時の最適化を含むすべての最適化が有効になります。
テストされたノード サイズは 1 です 、 2 、 4 、 8 と 256 、繰り返し 256 、 512 そして 1024 times.配列の場合、{1, 4, 8} * {1, 4, 8} を割り当てます 配列の割り当てをサポートするアロケータのみがテストされます。これは、Small を除くすべてのアロケータです。 そして通常のBoost.Pool.
戦略
割り当て戦略は、要素を割り当てるさまざまな方法を表します。もちろん、アロケーターの存続期間中は、さまざまな割り当て戦略が混在するため、これらは完全に現実的な条件ではありません。
戦略は次のとおりです。
- <リ>
シングル :単純に 1 つのノード (または 1 つの配列) を割り当てて、割り当てを解除します。これを繰り返す n 回。シングル たとえば、ローカルの std::unique_ptr がある場合、割り当て戦略が発生します。 毎回作成され、後で破棄されるループ内。
バルク :n を割り当てます ノード (または n ノードの配列) を割り当て、後で同じ割り当て順序で割り当てを解除します。これは、std::vector<std::unique_ptr<T>> がある場合に発生する可能性があります .あなたは n を持っています 作成および破棄される要素 (ここで話しているのはポインターであり、ベクトルの割り当てではありません)。
一括 (リバース) :バルクと同じです ただし、逆の順序で割り当てを解除します。つまり、最後にすべてコーティングされたノード (配列) が最初に割り当て解除されます。これは std::vector でも発生する可能性があります 、解放の順序は指定されておらず、両方の方法に合理的な議論があります。したがって、優れたアロケーターは両方の Bulk をサポートする必要があります
- バタフライ :別の バルク です 割り当て解除がランダムな (無秩序な) 順序で行われるバリアント、つまり、割り当てられたポインターが定数シードでシャッフルされます。これは、プログラム内に 1 つのアロケーターからのポインターが多数ある場合に発生する可能性があります。
実際には、単一の戦略ではなく、組み合わせがあります。たとえば、すべての戦略は、以前の割り当てなしでアロケーターから始まります。これはおそらくそうではありません。
期待される結果
ヒープ /新規 任意のを処理する必要がある汎用アロケータです。 割り当てサイズ/スキーム。したがって、他のアロケータのように特定のスキームに特化することはできません。したがって、一般に、他のアロケータよりも遅くなるはずです。
スタック かなり その割り当ては基本的にポインターのインクリメントであり、プロファイリング コードには割り当て解除が存在しないため、他の何よりも高速です。
通常のプールの割り当てはノードをポップし、割り当て解除はノードを押し戻すだけです。これは割り当て戦略に依存しないため、my と Boost の両方の実装のすべての戦略で一定の結果が得られるはずです。
同じことが小さなノード プールにも当てはまります。ただし、フリー リストはチャンクのみであり、最初に適切なチャンクを見つける必要があるため、遅くなります。
ただし、順序付けられたプールは異なります。割り当てはノードをポップするだけですが、割り当て解除はそれを正しい位置に挿入する必要があります リストの順序を維持するため。単一リンク リスト (ノードごとに 1 つのポインター) のみを扱っているため、各ノードを 1 つずつ比較して先頭からリストをトラバースする必要があります。ストラテジーでは、これは前に挿入するだけですが、他の戦略では後ろに挿入する必要があるため、全体 をトラバースする必要があります。 list.ひどいパフォーマンスが Bulk であるかどうか および バルク (リバース) ソート順によって異なります。そして Butterfly 間にあります:一部のノードではリストの大部分を通過する必要がありますが、他のノードでは非常に早く終了する可能性があります。
これは、配列とノード割り当ての両方で同じである必要があります。同じ基本アルゴリズムを使用しているため、私のプール実装と Boost のプール実装に大きな違いはないはずです。
実際の結果 (バージョン 0.5)
これが私が得た実際の結果です:https://gist.github.com/foonathan/3aa3114284863bf3141a
汎用アロケータは 遅い、スタック 最速で小さい およびノード 小さいと同様の安定したパフォーマンスを持っている 少し遅いです。また、順序付けされた Boost.Pool は、順序付けられたプールの期待される動作を示しています。 バルク (リバース) に最適化されていることは明らかです .
これまでのところ、期待どおりです。
しかし…
Boost.Pool はすべてのアロケータを 大幅に 上回っています 、スタックも !また、私の配列プールは、両方のバルクで一定のパフォーマンスを管理し、Butterfly の回帰のみを管理します Boost と同様のパフォーマンスを発揮します。
明らかに、これは私が望んでいるものではありません。
実際の結果 (バージョン 0.5-1)
したがって、一連の最適化の後、次の結果が得られました:https://gist.github.com/foonathan/904ed04f57aeecd132e3
今、スタック は大幅に高速であり、2 つの通常のプールのパフォーマンスは同様です (私のものは 2 つのバルクと Butterfly でわずかに高速です) ).
小さいノード プールも高速ですが、通常のプールよりも低速です。空きリストを使用しますが、チャンクごとに 1 つずつ複数の空きリストを使用します。割り当てと特に割り当て解除は、最初に適切なチャンクを見つける必要があります。
注文したプールは同じ特性を示していますが、はるかに高速です。Single ではわずかに遅いだけです。 および バルク (リバース) しかしかなり 他のバルクでより速く そしてバタフライ 、 Butterfly ではまだ悪いですが .
これは、配列の割り当てについても同じです。指摘しておくべき唯一のことは、通常のプールも配列の割り当てをサポートしており、それらは順序付けられたプールよりも高速であることです。これは、配列の割り当てに通常のプールを選択する必要があるという意味ではありません。
フリー リストでの配列の割り当てでは、リストをスキャンして、割り当てを満たすのに十分な数の隣接する空きノードを探す必要があります。アロケータの再割り当ては最小限に抑えられます。ただし、通常のプールのようにノードの順序が維持されていない場合、これが発生する可能性が高くなります。また、検索に時間がかかる場合があります。
ソートされた割り当て解除スキームを使用した単一の割り当て戦略しかないため、この動作はここでは明らかになりません (Butterfly を除く)。 ) で、プールの容量は十分に大きいです。しかし、実際には、ノード プールは配列の割り当てに劣り、アロケーターがさらに大きくなる可能性があります。
では、ここで何が起きているのでしょうか?
2 つのバルク ケースで、どのようにして優れた順序付きプールを持つことができたのでしょうか?
では、0.5 でメモリ スタックとプールをどうやって台無しにしてしまったのでしょうか?
このシリーズでは、これらの質問にお答えします。何が起こるかを正確にカバーし、優れた最適化で学んだ一般的なアドバイスを提供します。 ™.
どうぞお楽しみに！