From e14dc2e64357ee9415ffc784595a18f1c0affd7c Mon Sep 17 00:00:00 2001 From: Matthew Sotoudeh Date: Fri, 17 May 2024 14:47:53 -0700 Subject: more readme --- README | 11 ++++++++++- 1 file changed, 10 insertions(+), 1 deletion(-) (limited to 'README') diff --git a/README b/README index 6e2ba19..f47ea00 100644 --- a/README +++ b/README @@ -10,7 +10,9 @@ Benefits over buddy allocators that store a free-or-not bit on the block: 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. + huge amounts of space. This can be pretty important if, e.g., you're + doing a per-process buddy allocator over the entire virtual memory + space in an embedded operating system context. 2. Comparably simple implementation; only ~250 loc, and there is no need to track a metadata region. @@ -43,6 +45,13 @@ 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? + + 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 + worst-case time and space guarantees of our approach, without the + 2^-128 chance of failure. + Traditional optimized buddy allocators (see Knuth Vol 1) require at least 1/2 extra bit per allocation region. -- cgit v1.2.3