buddy allocator workshop
1.0.0
このリポジトリには、バディアロケーターの小さな例の実装が含まれています。これらは物理的なメモリを割り当てるように設計されていますが、ヒープなどの他のタイプの割り当てに使用できます。最終的に、最高のパフォーマンスのあるものは花に統合されます。
まず、レポをクローンします。次に、 cdに入り、すべてのデモアロケーターを実行するためにcargo +nightly run 。デフォルトでは、ブロックサイズは4KIBで、ブロックの量は100 000であるため、リンクされたリストの例には時間がかかる場合があります。心配しないでください、それは実際には何も割り当てられません - モックメモリブロックのみ。パス-hまたは--helpヘルプを取得して使用を表示します。ソースコードを編集して、MIN/MAXブロックサイズなどを変更して、ユニットテストを実行して、 cargo testを実行できます。残念ながら、まだ貨物のベンチマークはありませんが、Windowsマシンではかなり非科学的にベンチマークしています。
Builtinレポートを使用してさまざまな実装をタイミングして、Windowsマシンに4KIBブロック（印刷した状態で）にギビブを割り当てることにより、アルゴリズムをテストしました。他に追加するベンチマークがある場合は、貢献をご覧ください。
（MSI CX61-2QF）
| 実装 | 時間 | スループット |
|---|---|---|
| リスト - ベクトル | 2分 | 〜8.33e-3 gib/s |
| リスト - 二重リンクリスト | 25分 | 〜6.66e-4 gib/s |
| RBツリー - ベクター | 〜0.3s | 〜3.33ギブ/s |
| RBツリー - 単独でリンクされたリスト | 〜0.5s | 〜2ギブ/s |
| ビットマップツリー | 〜0.07s | 〜14.28ギブ/s |
注：スループットは、4KIBブロックに1つのGIBを割り当てるのにかかった時間から外挿されます。複雑さ> o（log n）（ナイーブリストベースの実装など）を持つ実装の場合、これは正確ではありません - より多くのブロックが割り当てられるにつれてスループットは遅くなります。ただし、これは、O（log n）以下の複雑さを持つものでは正確である必要があります。
この実装は、ブロックの順序ごとにリストを保持します。使用されるタイプのリストよりも一般的です。私は2種類のリストを使用することにしました：ベクトル（ stdからのVec ）と二重リンクリスト（ stdからのLinkedList ）。リンクされたリストは、多くの場合、予測可能なプッシュ時間（プッシュには再配置は必要ありません）に賞賛されますが、ベクターは、要素が連続したメモリブロックで割り当てられるため、より良いキャッシュ局所性を持っています。インデックスがリストの開始または終了に近いかどうかに応じて、背面または前面から繰り返すことができるため、単独でリンクされたリストよりもインデックス作成の方が高速であるため、二重リンクリストを使用しました。どちらが全体的に優れたパフォーマンスを発揮するかを確認するために両方をテストすることにしました。
実装は再帰的です。 Order Kの無料ブロックを割り当てるために、最初にOrder Kブロックのリストにある無料のブロックを検索します。無料リストを保持しません。何も見つからない場合、注文のブロックをK + 1のブロックを割り当てようとすることで再び繰り返されます。最後に、一点がない場合は、無料のブロックが見つかった場合、あきらめてパニックに陥ります。すぐにそれを半分に分割し、元のブロックを注文リストから削除し、半分を注文リストにすぐに押します。次に、最初のブロックの順序とインデックスを注文リストに戻します。このアルゴリズムはfind_or_splitで見つけることができます。
私のWindowsマシンの迅速で非科学的なベンチマークは、完全なギビブ（1024^3バイト）を割り当てるのに約2分かかったと言います。要素をプッシュするためにベクトル全体を再配置しなければならなかったとき、私は時々スプリットの秒の一時停止に気づきました。
stdの二重リンクリスト同様のベンチマークでは、完全なギビブテを割り当てるのに25分かかったと言います。これは、ベクトルを使用した同じ実装よりも12倍以上遅いです。ただし、この実装はリンクリスト用に最適化されていなかったため、わずかに不公平です。ベクトルを使用した実装とは異なり、私は一時停止に気付きませんでしたが、割り当ては徐々に遅くなり、遅くなりました。
理論の二重リンクリストは、ベクトルよりもプッシュするのが高速ですが、ベクターの12倍遅いと結論付けることができます。これは、実装がベクトル（多くのインデックス作成）にわずかに有利であるか、ベクターのキャッシュ局所が高いため、キャッシュミスが少なくなっているため、リンクされたリストが発生したため、個別にヒープに割り当てられた要素があるため、キャッシュミスが少なくなったためです。
この実装により、すべてのブロックに1つの赤黒ツリー（ intrusive_collectionsから）が保持され、各注文に無料リストが保持されます。無料リストは、STDのVecおよびintrusive_collectionsのSinglyLinkedListに実装されました。二重リンクには本当の利点がなかったため、単独でリンクされたリストを選択しました。利益を得た唯一の方法はFreeList::removeですが、これは常にこのフリーリストの2番目の要素で最大で呼び出されます。赤黒の木は各ノードを個別にヒープで割り当てます。これにより、キャッシュ効率が悪化しますが、 stdのBTreeSet / BTreeMap検索はO(log n) O(log n)が、 stdは線形検索を使用します。ただし、 stdのツリーは個別にノードを割り当てるものではないため、局所性をキャッシュする方が良いです。これは真実ですが、バディアロケーターは非常に多数のブロックに対処しなければならないため、より効率的な検索アルゴリズムを持つことがより重要であると判断しました。
実装は再帰的です。 Order Kの無料ブロックを割り当てるために、最初にOrder Kブロックの無料リストリストで無料ブロックを検索します。何も見つからない場合、注文のブロックをK + 1のブロックを割り当てようとすることで再び繰り返されます。最後に、一点がない場合は、無料のブロックが見つかった場合、あきらめてパニックに陥ります。すぐにそれを半分に分割して、元のブロックをツリーから削除し、半分を挿入して、アドレスを関連する無料リストに押し上げます。次に、最初のブロックを指すカーソルを返します。このアルゴリズムはfind_or_splitで見つけることができます。再帰の最も外側の層（実際に再帰find_or_split関数を呼び出す関数）で、返されたブロックは使用されているとマークされ、フリーリストから削除されます。
フリーリストとしてベクトルを使用すると、完全なギブを割り当てるのに〜0.3秒かかりました。これは、フリーリストバージョンとしてリンクされたリストよりも〜0.2秒高くなっています。これは、おそらくベクターがより良いキャッシュローカリティを持っているためです。
フリーリストとしてリンクされたリストを使用して、完全なギブを割り当てるのに〜0.5秒かかりました。上記のセクションのフリーリストとしてベクトルを参照してください。
この実装は、ナイーブリストベースの実装よりも400倍高速でした（せいぜい、ベクターをフリーリストとして使用しています）。これは、おそらく、ベクターまたはリンクされたリストの検索、挿入、削除よりも速く、全面的にO(log n)操作を備えた赤黒樹の木が原因です。
この実装は、厳密にはビットマップではありませんが、ビットマップシステムの変更です。基本的に、ツリー内の各ブロックは、その下のどこかに最大の順序（完全にマージされた）を保存します。たとえば、4つの注文ですべて無料のツリーは次のようになります。
3
2 2
1 1 1 1
0 0 0 0 0 0 0 0
1つの注文0ブロックを割り当てると、このように見えます（tはt akenです）：
2
1 2
0 1 1 1
T 0 0 0 0 0 0 0
それは平らなアレイとして実装されています。
1
2 3
表現は1; 2; 3 。これには、1からのインデックスを使用する場合（つまり、オフセットではなくインデックス）、特定のインデックスの左子のインデックスは2 * indexであり、右子は単に2 * index + 1であるという素晴らしいプロパティがあります。親はfloor(index / 2)です。これらの操作はすべて2秒で動作するため、効率的なビットシフトを使用して実行できます（ index << 1 、 (index << 1) | 1 、およびindex >> 1 ）。
バイナリ検索を行い、目的の順序がないブロックを見つけることができます。最初に、ルートブロックをチェックして、目的の注文のブロックが無料であるかどうかを確認します。ある場合、左の子供が十分に自由になっているかどうかを確認します。もしそうなら、もう一度左の子供などを確認します。ブロックの左の子供に十分なブロックがない場合は、単に右の子供を使用します。適切な子供には十分な自由が必要であるか、ルートブロックが無効であることがわかっています。
この実装は非常に高速でした。私のコンピューターでは、1GIBを割り当てるのに約0.07秒しかかかりませんでした。ただし、コンピューターで最大0.04秒のパフォーマンスを発揮するのを見てきましたが、パフォーマンスは少し変動します。これはCPU負荷に関係すると思います。
この実装には、レベルが互いから遠く離れて保存されるため、この実装にはあまり優れたキャッシュローカリティがありません。したがって、親ブロックは子供から非常に遠くなる可能性があります。しかし、他のすべてはまだ非常に速いので、それは補われています。また、o（log n）ですが、実際には非常に速いため、これは実際には重要ではありません。参照：8GIBの割り当ては私に0.6Sを取りましたが、 @Gegy1000のラップトップで150msを超えるとはるかに優れたパフォーマンスを見てきました。
追加するものがある場合（readmeの編集や別の実装やベンチマークなど）、プルリクエストをお気軽に送信してください！問題を作成することもできます。チャットしたい場合は、Rustの不一致（Restioson＃8323）でお気軽にお願いします。
