mention benchmarks

1 files changed, 15 insertions, 5 deletions

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