From 15c8c96a9e40c9a8549e3c3966f78091e7d15d81 Mon Sep 17 00:00:00 2001 From: "Peter H. Froehlich" Date: Thu, 14 Oct 2021 00:47:05 +0200 Subject: Brief descriptions of the allocators --- README.md | 90 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 88 insertions(+), 2 deletions(-) diff --git a/README.md b/README.md index f77852b..1ae9c51 100644 --- a/README.md +++ b/README.md @@ -1,7 +1,88 @@ # Simple Allocators -If you're curious about simple memory allocation schemes in C, maybe you'll be -able to learn a thing or two here. +If you're curious about memory allocation schemes in C, maybe you'll be able to +learn a thing or two here. + +## The Allocators + +The terminology around different memory allocation strategies is not exactly +"settled" so different people will call similar things by different names and +vice versa. In an effort to clear things up at least for the code here, let me +try to explain what "my" terms mean. + +### Arena + +An "arena" allocator starts with a big chunk of memory and carves it up into +smaller slices for allocation; these allocations can be of any size that "still +fits" into the arena. Here's a picture: + +``` + ________________ capacity ________________ + / \ ++----+--------+----+------+------------------+ +| a1 | a2 | a3 | a4 | free | ++----+--------+----+------+------------------+ + ^ + | used +``` + +Allocating a slice of `size` bytes is *very* cheap: +check `used + size <= capacity` and if it fits +`used += size` finishes the allocation. +There is no way to free an individual object, only the arena as a whole can be +freed. +An arena allocator is best used when a data structure is built up, processed, +and torn down *completely* again. + +### Cached + +The "cached" allocator tries to keep a certain number of objects around for +reuse; this works best if all objects are the same size. Here's a picture: + +``` + 0 1 2 3 4 5 6 7 ++---+---+---+---+---+---+---+---+ +| * | * | - | - | - | - | - | - | ++-|-+-|-+---+---+---+---+---+---+ + | v + | +---+ + | | | + | +---+ + v ++---+ +| | ++---+ +``` + +If we need to allocate another object, we check the cache, return the object +from slot 1 and clear that slot; no actual allocation was done. +If we later need to free an object, we check the cache and put the object into +slot 1; no actual freeing was done. +Of course if there are no more objects in the cache, we have to allocate, and +if there's no more room in the cache, we have to free; but if we have a good +"guess" for the working set (how many objects are needed "on average") we can +keep the number of actual allocation (or free) operations low. + +### Pool + +The "pool" allocator starts with a big chunk of memory and carves it up into +smaller slices for allocation; these allocations are all the same size. Here's +a picture: + +``` + ________________ capacity ________________ + / \ ++----+----+----+----+----+----+----+----+----+ +| a1 | | a2 | | | | a3 | | | ++----+----+----+----+----+----+----+----+----+ +``` + +Allocating an object requires finding an unused slot; we use a bitmap for that, +but other options, such as a free list, would also be possible. +Individual objects can be freed, unlike in the arena allocator. +A pool allocator works well if there's a useful upper limit on the number of +fixed-size objects and if there's considerable dynamism in terms of object +life-times. ## Limitations @@ -16,6 +97,11 @@ fixed maximum capacity that may not be appropriate for all programs; code to "grow" the arena when necessary might be a good addition. Nothing here is thread-safe either, so you may need to throw in a lock or three. +## Benchmark + +The simplistic benchmark puts the arena allocator first, followed by the pool +and cached allocators. + ## License I very much doubt that you can use the code "as is" for a real system, but feel -- cgit 1.4.1-2-gfad0