Part 6 of 7 · 4 min read
Cost and alternatives
Cost, and a simpler allocator
In plain words: A call to malloc and free for a small block took about 9.5 ns per pair in a loop on the test machine, because glibc keeps a small per-thread cache of recently freed blocks and serves the next request from it with no lock. That is fast, though not free: a program that makes hundreds of millions of tiny blocks spends noticeable time here. Each block also carries the header and the rounding of section 2.
A program can use a simpler allocator when many blocks live and die together, such as all the nodes of one parse tree or one web request. An arena allocator (also called a bump allocator) takes one big block and hands out pieces by moving an offset forward. It never frees a single piece. It frees all of them at once by resetting the offset to 0:
typedef struct { char *base; size_t size, used; } Arena;
static int arena_init(Arena *a, size_t size){
a->base = malloc(size); a->size = size; a->used = 0;
return a->base != NULL; }
static void *arena_alloc(Arena *a, size_t n){
n = (n + 15) & ~(size_t)15; /* keep 16-byte alignment */
if (a->used + n > a->size) return NULL; /* arena full */
void *p = a->base + a->used; a->used += n; return p; }
static void arena_reset(Arena *a){ a->used = 0; } /* frees everything at once */
With a 1 MiB arena, a request for 10 ints (40 bytes), then 5 bytes, then one double returned the offsets 0, 48 and 64, with 80 bytes used in all, and after the reset, 0. Each size was rounded up to a multiple of 16: 40 to 48, 5 to 16 and 8 to 16. The cost of an allocation is a few instructions, there is no header, and there is no fragmentation. The price is that the program cannot free one piece early, so the arena suits groups of objects with the same lifetime.
Arena allocator
An arena allocator is an allocator that obtains one large block, serves each request by moving an offset forward, and releases all its pieces together by resetting the offset or freeing the block.
Example: a compiler allocates all the nodes of one source file from an arena, and releases them with one call when the file is done.
Interview angle
"What does malloc do when you call it?" A strong answer says that it is a library function, that it serves small requests from a free list, that it asks the kernel with brk or mmap only when it needs more, and that free usually does not return memory to the kernel. It mentions headers and fragmentation.
Check yourself:
1. Why is a small malloc and free so fast?
2. What does an arena allocator give up?
3. When is an arena a good choice?
Words you will meet
| Word | Meaning |
|---|---|
| Allocator | Library code that serves small memory requests from large blocks |
| Heap | The region from which malloc serves most requests |
| Program break | The end of the heap region, moved by brk |
| Free list | The list of unused pieces |
| Header | The size record kept just before a block |
| Splitting | Cutting a large free piece in two |
| Coalescing | Joining neighbouring free pieces |
| mmap threshold | The size above which a request gets its own mapping |
| RSS | The pages of a process now in memory |
| Arena allocator | Hand out by moving an offset, free all at once |
Quick notes
- The program break is the address of the end of a process's heap region, and the system call
brkmoves it up to enlarge the heap or down to shrink it. - A free list is the allocator's list of the unused pieces of the heap, from which
malloctakes a piece, and to whichfreereturns it, joining it to its free neighbours if there are any. - The mmap threshold is the request size above which the allocator, when the heap cannot serve a request, gets a separate region from the kernel with
mmapand later returns it withmunmap. - Heap fragmentation is the state in which a heap contains much free space that cannot be returned to the kernel, or cannot serve a request, because it is spread among blocks that are still in use.
- An arena allocator is an allocator that obtains one large block, serves each request by moving an offset forward, and releases all its pieces together by resetting the offset or freeing the block.