buddy allocator workshop
1.0.0
該存儲庫包含一些夥伴分配器的一些小示例實現。它們旨在分配物理內存，儘管它們可用於其他類型的分配，例如堆。最終，表現最好的一體將合併為花。
首先，克隆回購。然後， cd進入其中，並進行cargo +nightly run以運行所有演示分配器。默認情況下，塊大小為4KIB，塊的數量為100 000，因此鏈接列表示例可能需要一段時間。不用擔心，它實際上不會分配任何內容 - 只有模擬內存塊。通過-h或--help來獲得幫助並查看使用情況。您可以編輯源代碼以更改最小/最大塊大小等，以運行單元測試，運行cargo test 。不幸的是，還沒有貨物基準，但是我在Windows機器上毫不客氣地對其進行了基準測試。
我通過使用內置報告進行各種實現來測試算法，並在Windows計算機上分配了4KIB塊（並打印出來）的Gibibyte。如果您還有其他基準要添加，請參閱貢獻。
（MSI CX61-2QF）
| 執行 | 時間 | 吞吐量 |
|---|---|---|
| 列表 - 向量 | 2分鐘 | 〜8.33e-3 gib/s |
| 列表 - 雙重鏈接列表 | 25分鐘 | 〜6.66e-4 gib/s |
| RB樹 - 向量 | 〜0.3s | 〜3.33 gib/s |
| RB樹 - 單鏈接列表 | 〜0.5s | 〜2 gib/s |
| 位圖樹 | 〜0.07 | 〜14.28 gib/s |
注意：從在4KIB塊中分配1個GIB的時間開始，吞吐量就可以推斷出來。對於具有復雜性> O（log n）的實現（例如基於天真的列表的實現），這將不准確 - 隨著分配更多的塊，吞吐量會減慢。對於具有O（log n）或更少複雜性的人來說，這應該是準確的。
此實現將保留每個訂單訂單的列表。它比使用的類型列表是通用的。我決定使用兩種列表：向量（來自std的Vec ），以及雙重鏈接列表（ LinkedList ，也來自std ）。鏈接的列表通常因其可預測的推動時間（不需要推動所需的重新分配）而珍貴，而矢量具有更好的緩存位置，因為元素被分配在連續的內存塊中。我使用了雙重鏈接列表，因為它們的索引速度比單鏈接列表要快，因為它們可以從背面還是前面迭代，具體取決於索引是否接近列表的開始還是結束。我決定測試兩者，以查看總體表現更好。
實施是遞歸的。要分配訂單K的自由塊，它首先搜索訂單k塊列表中的任何自由塊。它不會保留免費列表。如果找不到，它會通過嘗試分配k + 1訂單的塊來遞歸。最後，如果沒有發現任何自由塊，就會放棄並慌張。一旦將其分為一半，將原始塊從其訂單列表中刪除，並將半部分推到訂單列表，立即將其推入訂單列表。然後，它返回其訂單列表中第一個塊的訂單和索引。您可以在find_or_split中找到此算法。
我的Windows機器上的快速，非科學的基準測試說，分配完整的Gibibyte（1024^3字節）大約需要兩分鐘。我確實注意到，當它不得不重新分配整個向量以推動元素時，我確實會一次又一次的暫停。
std的雙重鏈接列表類似的基准說，分配完整的吉比比亞特花了25分鐘。這比使用向量的同一實現慢了十二倍。但是，此實現並未針對鏈接列表進行優化，因此它有些不公平。與矢量實現不同，我沒有註意到任何停頓，但分配逐漸越來越慢。
我們可以得出結論，儘管理論上的雙重鏈接列表在推動方面的速度比向量較快，但它們的速度仍然比向量慢12倍。這可能是因為實現略有支持矢量（大量索引），或者是因為矢量具有較高的緩存位置，因此較少的緩存失誤，而鏈接的列表則經歷了高速緩存的錯過，因為它們單獨堆積了堆積的元素。
此實現將所有塊的一棵紅黑樹（來自intrusive_collections ）和每個訂單的免費列表。免費列表是針對STD的Vec和intrusive_collections的SinglyLinkedList實現的。我選擇了一個單獨的鏈接列表，因為雙重鏈接並沒有真正的好處 - 唯一受益（可以忽略的）是FreeList::remove ，但這始終在此免費列表中的第二個元素上最多呼喚，因此優化此元素沒有真正的觀點。紅黑樹單獨堆放每個節點，這會使緩存效率變得更糟，但是與std的BTreeSet / BTreeMap不同，其搜索為O(log n) ，而std的搜索使用線性搜索，這不是O(log n) （您可以在此處閱讀此信息）。但是， std的樹不會單獨堆放節點，因此緩存局部性更好。我決定，儘管這是真的，但由於好友分配器必須處理大量塊，因此擁有更有效的搜索算法更為重要。
實施是遞歸的。要分配訂單k的免費塊，它首先搜索訂單k塊的免費列表中的任何自由塊。如果找不到，它會通過嘗試分配k + 1訂單的塊來遞歸。最後，如果沒有發現任何自由塊，就會放棄並慌張。一旦將其分成兩半，將原始塊從樹上拆下並插入一半，將其地址推向相關的免費列表。然後，它返回一個指向第一個塊的光標。您可以在find_or_split中找到此算法。在遞歸的最外層（實際上稱為遞歸find_or_split函數的函數），將返回的塊標記為使用並從免費列表中刪除。
使用矢量作為免費列表需要〜0.3s來分配完整的吉布。這比鏈接列表作為免費列表版本快〜0.2s。這可能是由於向量具有更好的緩存位置。
使用鏈接列表作為免費列表需要約0.5秒來分配完整的GIB。請參見上面的免費列表部分。
該實現比基於幼稚列表的實現快400倍（充其量是將向量作為免費列表）。這可能是由於紅色樹木全面具有O(log n)操作，比搜索，插入和刪除向量或鏈接列表的速度更快。
本身本身並不是嚴格的位圖，而是對位圖系統的修改。從本質上講，樹上的每個塊都存儲在其下方的某個地方最大的順序（完全合併）。例如，一棵帶有4個訂單的樹，看起來像這樣：
3
2 2
1 1 1 1
0 0 0 0 0 0 0 0
如果我們分配一個訂單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開始的索引（IE索引而不是偏移），則任何給定索引的左子女的索引為2 * index ，而正確的孩子則只是2 * index + 1 。父母是floor(index / 2) 。因為所有這些操作都與2s一起使用，所以我們可以使用有效的bitshifting執行它們（ index << 1 ， (index << 1) | 1 ， index >> 1 ）。
我們可以進行二進制搜索以找到沒有所需順序的塊。首先，我們通過檢查根部塊是否有免費訂單的任何塊。如果有的話，我們檢查左孩子是否有足夠的免費。如果是這樣，那麼我們再次檢查它是左子女等。我們知道，合適的孩子必須有足夠的自由，否則根塊是無效的。
這個實現非常快。在我的計算機上，分配1GIB只需〜0.07。不過，我已經看到它在我的計算機上的性能高達0.04，而且性能確實有些波動。我認為這與CPU負載有關。
該實現不是很好的緩存局部性，因為級別遠離彼此的級別，因此父塊可能離孩子很遠。但是，其他所有內容仍然非常快，因此可以彌補。它也是o（log n），但實際上是如此之快，以至於這並不重要。供參考：分配8GIB為我花了0.6秒，但我看到它在 @gegy1000的筆記本電腦上的性能> 150ms。
如果您有任何要添加的內容（例如編輯讀數或其他實現或基準），請隨時提交拉動請求！您還可以創建一個問題。如果您只想聊天，請隨時在Rust Discord上ping（Restioson＃8323）。
