Search code examples
cmallocapr

Why is apr_palloc faster than malloc?


Reading through The Apache Modules Book, I come across this claim in part 3.4.3:

"A secondary benefit is that pool allocation is faster than malloc on most platforms!"

An open question, I realize, but.. well, why?


Solution

  • In addition to Lars' point about locality, pool allocation is simply a different speed/flexibility tradeoff than malloc.

    malloc has to track each allocated block, be able to free blocks individually, handle free block fragmentation and coalescing, have some strategy for choosing which of several free blocks to allocate from, etc.

    This is required for a general purpose allocator, but pools avoid all this complexity (and the associated space & runtime overhead) by making the caller decide some of this behaviour statically.

    The Apache example seems to allow only whole-pool deallocation (so it's like an arena allocator). This means it doesn't need to track individual allocation records, their lifetimes, and a fragmented free store. It just needs to keep track of one (or more) big chunks of memory, and update a pointer to the next unused space. Note that even if these big chunks are allocated using malloc, this cost is typically amortized over many pool allocations.

    Other pool types may be limited to objects of the same size (or type), which simplifies them still further; they can even keep a LIFO free list at close to zero cost, allowing per-record deallocation.