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）。
