diff options
| -rw-r--r-- | README | 11 |
1 files changed, 10 insertions, 1 deletions
@@ -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. |