From bdffdb1e9e3b8e4a023c6b55fe24c12b628625c4 Mon Sep 17 00:00:00 2001 From: Matthew Sotoudeh Date: Fri, 17 May 2024 17:39:10 -0700 Subject: mention benchmarks --- README | 20 +++++++++++++++----- 1 file changed, 15 insertions(+), 5 deletions(-) (limited to 'README') diff --git a/README b/README index f47ea00..8d718ca 100644 --- a/README +++ b/README @@ -2,12 +2,12 @@ A buddy allocator with zero metadata overhead. -Benefits over buddy allocators that store a free-or-not bit on the block: +#### Benefits over buddy allocators that store a free-or-not bit on the block: 1. When you request an allocation of 2^k, it only allocates 2^k space, not 2^{k+1} to account for the extra free-or-not-bit. -Benefits over buddy allocators that store a bitset: +#### Benefits over buddy allocators that store a bitset: 1. You save at least a few MB in metadata, or more if you're allocating huge amounts of space. This can be pretty important if, e.g., you're @@ -17,7 +17,17 @@ Benefits over buddy allocators that store a bitset: 2. Comparably simple implementation; only ~250 loc, and there is no need to track a metadata region. -Features of the allocator shared with other buddy allocators include: +Benchmarking magic_buddy allocator for the Lua interpreter against another +single-file buddy allocator (https://spaskalev.github.io/buddy_alloc/) shows +magic_buddy giving ~4x better end-to-end performance on my machine for some +benchmarks, even though we have about 10x less code (see lua_benchmark/ and +run "bash benchmark.sh tests/Lua-Benchmarks/binary-trees.lua"). + +The reason for this seems to be that Spaskalev's buddy_alloc always walks the +tree, whereas we keep free lists. So if your program involves frequent +allocations of similar sizes, we can do much better. + +#### Features of the allocator shared with other buddy allocators include: 1. All operations are constant time/linear only in the number of address bits. @@ -31,7 +41,7 @@ Features of the allocator shared with other buddy allocators include: 4. Core functionality is reasonably well-tested with an exhaustive implementation model checker. -Caveats are: +#### Caveats are: 1. The minimum allocation size is nontrivial, approximately 64 bytes @@ -45,7 +55,7 @@ Caveats are: 4. Some advanced allocator features, e.g., iterating over allocated regions or attempting to dynamically improve cache locality, are not supported. -What should you use instead? +#### What should you use instead? 1. Zach Yedidia suggests a K&R style free list using two interleaved AVL trees instead of a linked list. This provides essentially the same -- cgit v1.2.3