Simple Allocators

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

I've tried to keep the code for these allocators as simple as possible, so if you want to use any of them "in production" you'll have to add a few more bells and whistles. For starters, real programs will require more than just one object size, so you will have to generalize the code for cached and pool allocators to support "allocator objects" of some kind. The arena allocator already supports "arbitrary" object sizes, but it has a 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 free to take it as a starting point if that seems helpful. Since it's under a 0-clause BSD license, which essentially makes it public domain, you're welcome to do as you please. If the code was helpful to you I'd appreciate an email, but it's certainly not required.