Allocators in libualloc

Comparison of allocators

  Allocation size Per page cost Standard calls Per allocation cost
mcache fixed n/a (not paged) alloc, free, clean 2 pointers
slabap fixed 2 pointers + 1 long + at most one slab_size alloc, free, clean 1 pointer + alignment
acache fixed n/a (not paged) alloc, free 1 pointer
stackd arbitrary 1 pointers + 2 size_t + arbitrary fitting losses alloc, clean 0
slab fixed 2 pointers + 1 long + at most one slab_size alloc, free, clean 2 pointers + alignment
stacks fixed 1 pointers + 2 size_t + at most 1 elem_size for fitting alloc, free*, clean alignment

List of allocators

mcache

Method: memory allocation cache

Remember all allocations per context in two doubly linked lists: one for currently in use, one for currently free (cache). Serve new allocations from the cache. Same as acache, but is more expensive and has clean().

Allocation sizefixed
Per page costn/a (not paged)
Standard callsalloc, free, clean
Per allocation cost2 pointers

slabap

Method: fixed size slabs over 2^n aligned pages

Serve fixed size slabs from a list of aligned pages allocated in batch. Similar to slab, but is a bit cheaper while requiring 2^n aligned page allocation.

Allocation sizefixed
Per page cost2 pointers + 1 long + at most one slab_size
Standard callsalloc, free, clean
Per allocation cost1 pointer + alignment

acache

Method: simple allocation cache

Remember all allocations free'd in a doubly linked list (cache). Serve new allocations from the cache. Same as mcache, but is cheaper and has no clean().

Allocation sizefixed
Per page costn/a (not paged)
Standard callsalloc, free
Per allocation cost1 pointer

stackd

Method: stack allocation with dynamic sized data, no free/pop

Allocate arbitrary sized elements in order, packing them in a linked list of pages. In other words, allocations are pushed on a stack. Free is possible only in reverse order of allocation (always popping and discarding the topmost element of the stack). Allocate arbitrary sized elements in order, packing them in a linked list of pages. In other words, allocations are pushed on a stack. There is no free or pop operation, the whole stack needs to be discarded at once after use.

Allocation sizearbitrary
Per page cost1 pointers + 2 size_t + arbitrary fitting losses
Standard callsalloc, clean
Per allocation cost0

slab

Method: fixed size slabs over unaligned pages

Serve fixed size slabs from a list of pages allocated in batch. Similar to slabap, but is a bit more expensive while not assuming 2^n aligned page allocation.

Allocation sizefixed
Per page cost2 pointers + 1 long + at most one slab_size
Standard callsalloc, free, clean
Per allocation cost2 pointers + alignment

stacks

Method: stack allocation with fixed sized data

Allocate fixed sized elements in order, packing them in a linked list of pages. In other words, allocations are pushed on a stack. Free is possible only in reverse order of allocation (always popping and discarding the topmost element of the stack).

Allocation sizefixed
Per page cost1 pointers + 2 size_t + at most 1 elem_size for fitting
Standard callsalloc, free*, clean
Per allocation costalignment