8个版本
| 0.1.7 | 2022年11月9日 |
|---|---|
| 0.1.6 | 2022年10月21日 |
#84 in 内存管理
2,283次月下载
在 talloc 中使用
150KB
2K SLoC
galloc - good_memory_allocator
这是一个链表分配器，受dlmalloc算法的启发，用于在no_std环境（如操作系统内核）中使用。每次分配的开销是一个usize。实现优先考虑运行时效率，同时也提供了非常好的内存利用率。分配器经过大量测试，测试用例涵盖了几乎所有代码路径；模糊测试用于覆盖其余部分。
使用方法
创建静态分配器
use good_memory_allocator::SpinLockedAllocator;
#[global_allocator]
static ALLOCATOR: SpinLockedAllocator = SpinLockedAllocator::empty();
在开始使用此分配器之前，您需要对其进行初始化
pub fn init_heap() {
unsafe {
ALLOCATOR.init(heap_start, heap_size);
}
}
SMALLBINS_AMOUNT 和 ALIGNMENT_SUB_BINS_AMOUNT。
此分配器允许配置它使用的smallbins和alignment sub-bins的数量。对于不熟悉smallbins的用户，它们是分配器用于跟踪空闲块的数据结构。每个smallbin由多个alignment sub-bins组成。分配器使用的smallbins和alignment sub-bins的默认数量存储在相应的常量DEFAULT_SMALLBINS_AMOUNT和DEFAULT_ALIGNMENT_SUB_BINS_AMOUNT中。
增加smallbins的数量将提高运行时性能和内存利用率，特别是在进行大量相对较小的分配时，但它也会增加Allocator结构的大小。
增加alignment sub-bins的数量也将提高运行时性能和内存利用率，特别是在进行大量相对较大对齐的分配时，但它也会增加Allocator结构的大小。建议为alignment sub-bins的数量选择2的幂，因为这将提高smallbins内存的利用率。alignment sub bins的数量必须至少为2，否则您将得到编译错误。
如果您处于内存受限的环境中，可能需要使用这些常量的较低值，因为使用默认值时Allocator结构的大小相对较大。
功能
spin（默认值）：提供一个使用自旋锁实现的SpinLockedAllocator类型，该类型实现了GlobalAlloc特性。allocator：为SpinLockedAllocator类型提供对不稳定Allocator特性的实现。
性能
在大多数情况下，分配是 O(1)，主要针对相对较小的分配和相对较小的对齐。释放分配总是 O(1)。重新分配使用自定义算法，该算法尽量减少内存复制，通过原地重新分配。
分配器的整体性能非常出色，并且比我们在 crates.io 上找到的所有其他替代分配器都表现更好。
基准测试
我们使用多个基准测试对 galloc 进行了基准测试，与其他在 crates.io 上找到的、似乎提供类似功能的 2 个 crate 进行比较：simple-chunk-allocator 和 linked-list-allocator。在每个基准测试中，每个分配器都有一个特定的持续时间，必须在给定的时间内尽可能执行更多操作。
随机操作
我们使用的第一个基准测试被称为 random_actions。在这个基准测试中，每个分配器试图在给定的时间内执行尽可能多的分配、释放和重新分配操作。分配和重新分配的大小和对齐是随机的。在每次迭代中，基准测试随机选择分配、释放或重新分配。
在图例下方左上角，你可以看到 galloc 与其他每个分配器之间操作次数的百分比差异。百分比差异使用以下公式计算：a / b * 100，其中 a 是 galloc 的分数，而 b 是其他分配器的分数。你可以看到 galloc 比其他两个分配器几乎高出一个数量级。
堆耗尽
我们使用的第二个基准测试被称为 heap_exhaustion。在这个基准测试中，每个分配器在给定的时间内尽可能执行更多的分配操作。分配的大小和对齐是随机的。一旦分配请求失败，这意味着堆已耗尽，分配器的分数将因强制它暂停一定时间而受到惩罚。因此，这个基准测试衡量了分配器利用其内存的能力，因为所有分配器都分配了相同大小的堆。
在这里，galloc 也优于其他两个分配器。
简单块分配器基准测试
simple-chunk-allocator crate 提供了自己的基准测试。以下是来自 simple-chunk-allocator 的说明
基准测试执行不同大小和对齐的随机分配，并释放一些较旧的分配。随着时间的推移，堆会变得满载，这就是为什么成功分配的数量与尝试分配的数量之间的差异较高的原因。
我们在包括 galloc 在内的 3 个分配器上运行了这些基准测试，结果如下
持续时间：1 秒
RESULTS OF BENCHMARK: Chunk Allocator
51244 allocations, 15404 successful_allocations, 35840 deallocations
median= 1210 ticks, average= 1232 ticks, min= 218 ticks, max=144410 ticks
RESULTS OF BENCHMARK: Linked List Allocator
34937 allocations, 10829 successful_allocations, 24108 deallocations
median= 28778 ticks, average= 41553 ticks, min= 78 ticks, max=1165606 ticks
RESULTS OF BENCHMARK: Galloc
51694 allocations, 15651 successful_allocations, 36043 deallocations
median= 176 ticks, average= 654 ticks, min= 90 ticks, max=989542 ticks
持续时间：10 秒
RESULTS OF BENCHMARK: Chunk Allocator
79818 allocations, 23909 successful_allocations, 55909 deallocations
median= 1294 ticks, average=320782 ticks, min= 174 ticks, max=13773388 ticks
RESULTS OF BENCHMARK: Linked List Allocator
113181 allocations, 30521 successful_allocations, 79611 deallocations
median= 91688 ticks, average=120273 ticks, min= 80 ticks, max=1831252 ticks
RESULTS OF BENCHMARK: Galloc
147720 allocations, 32754 successful_allocations, 103313 deallocations
median= 214 ticks, average= 39177 ticks, min= 88 ticks, max=2228776 ticks
如你所见，在两个测试用例中，galloc 都优于它们。这在 10 秒测试中尤为明显。