Designed for embedded real-time systems. Assumes you have an entire memory pool to work with (as you do on embedded systems.)

Used by the Nim programming language.

Araq compared this to Mimalloc and said it was faster but does not does not have the benefits of being lock-free.

Memory indices are split twice: first by a power of two to determine a range and then linearly within that range.

Example:

  [2048 to 4096]
   ^ Size class (first level index)
  [2048, 2457, 2866, 3275, 3684, 4096]
   ^ Linear split (second level index on a pool with 5 splits)

How

• First level consists of size classes in powers of two.
• Second level consists of a linear division within that size class.
• Third level is a linked list of free blocks.

Allocation of memory is thus always O(1) if memory is available. Releasing memory is O(n) where n is the number of free blocks adjacent to the newly freed block.

Each block has a hidden header which stores the next and previous block in the free list, as well as the size of the block, and a pointer to the previous physical block.

When you release a block it is then merged with any immediately adjacent blocks if they are also free.

Personal

• Araq's favorite allocator