Allocator Metadata and the Real Cost of a Small Object

Ask a program how much memory it uses and it will add up the sizes it passed to malloc. The answer is a lower bound and can be far below what the process is charged for. Between the requested size and the resident page there are at least four layers that add bytes: the allocator’s per-object metadata, the rounding to a size class, the unused space inside partially filled spans, and the alignment the platform requires. For large objects the additions are noise. For a program whose allocation traffic is dominated by objects of a few dozen bytes, they can double the footprint.

The header question

The simplest allocator design stores a fixed header before every block, holding the block size and a mark bit for coalescing. A 16-byte header on a 32-byte request is a 50 percent overhead before anything else is counted. It is also the design that scales best in one specific dimension: freeing requires a single load at a fixed negative offset, with no lookup structure and no lock.

Headerless designs move the same information into side tables indexed by address. A page-level map records, for each page of the heap, which size class it belongs to; the size class then implies the object size, and the object’s index within its span gives its position. The cost is a lookup on every free (usually one memory access into a table that is small enough to stay cached) plus the table’s own memory, which is a few bytes per page rather than per object. On a machine with 4 KiB pages and 32-byte objects, that is a few bytes per 128 objects, which is an order of magnitude cheaper than a header.

The trade is between a per-object cost paid always and a per-page cost plus a lookup paid on free. Headerless wins for small objects, which is why the allocators that optimise small allocations are headerless and the ones that optimise simplicity are not.

A third design places the size in a bitmap at the start of the span, one or two bits per object indicating allocated or free, with sizes derived from the span’s class. This is cheaper still than a per-page map, at the cost of an extra indirection when the span’s base must be found from an object address, which is normally a single mask of the address against the span size.

Size classes and the rounding tax

An allocator that serves exact sizes would need a free list per size, and the number of distinct sizes a program requests is unbounded. Size classes bound the problem: requests are rounded up to the next class, and the allocator maintains one free list per class. A geometric progression with a small ratio keeps the waste bounded: rounding to the next multiple of 16 for small sizes wastes at most 15 bytes, and doubling classes for large sizes waste up to a factor of two.

The rounding tax is easy to compute and worth computing before optimising anything:

• A request for 33 bytes in a class that rounds to 48 wastes 15 bytes, 45 percent of the request.
• A request for 4097 bytes in a class that rounds to 8192 wastes 4095 bytes, 100 percent.
• A request for 24 bytes in a class of 32 wastes 8 bytes, 33 percent.

Real allocators use more classes than a pure power-of-two sequence to keep the tax low for medium sizes, at the cost of more free lists and more per-thread state. The tax is not a defect; it is the price of a constant-time lookup from size to class and a bounded number of lists. The useful number is the average ratio across a program’s actual allocation sizes, which requires the size histogram that a tracing allocator can produce.

Partially filled spans

Below the size class sits the span, a run of contiguous pages carved into objects of one class. A span holds floor(pages * page_size / class_size) objects, and the remainder is unusable padding. For a class of 96 bytes and a span of four 4 KiB pages, 16384 bytes hold 170 objects with 64 bytes left over, well under one percent of the span. For classes just above a page size, the waste is much larger: a class of 5000 bytes in a span of two pages holds one object and leaves 3192 bytes, roughly 39 percent of the span.

The larger effect is occupancy. A span can only be returned to the page allocator when it is empty, so a class whose live objects are spread thinly across many spans holds far more pages than its bytes require. Ten live objects of a size that fits four to a page need three spans in the best case, when they are packed, and ten when each lives alone in a span of its own. This is the mechanism behind fragmentation , and it is why the interesting allocator statistic is not live bytes but live bytes per span.

/* Round a request up to its size class: 16-byte steps below 128, then powers of two. */
static size_t round_up_to_class(size_t n)
{
    if (n <= 128) return (n + 15) & ~(size_t)15;
    size_t c = 128;
    while (c < n) c <<= 1;
    return c;
}

/* Bytes of span consumed per object, amortising the padding a span cannot use. */
static size_t span_bytes_per_object(size_t request, size_t page, size_t span_pages)
{
    size_t cls = round_up_to_class(request);
    size_t span = span_pages * page;
    size_t per_span = span / cls;                 /* whole objects the span can hold */
    if (per_span == 0) return span;               /* one object owns the whole span */
    return span / per_span;                       /* span padding amortised over its objects */
}

The returned value is the span size divided by the number of objects it holds, which is the number worth comparing against the request. The ratio between the two is the total structural overhead for that size class, before any occupancy effect from partially filled spans.

Metadata that scales with the heap

Beyond per-object and per-span costs, allocators maintain structures proportional to the address space they manage: page maps, radix trees mapping spans to their owning heap, per-thread cache descriptors, and the free lists themselves. These are usually a fraction of a percent of the heap, but they have two properties that matter for profiling.

First, they are allocated from the same heap, so a program that allocates very little still pays a fixed baseline. The first malloc in a process initialises allocator state whose size scales with the number of size classes and arenas it manages, so a short-lived program’s footprint is dominated by a constant that a long-running process amortises away.

Second, they grow in steps. A radix tree that covers the heap at one granularity must add a level when the heap crosses a size boundary, doubling or quadrupling its own footprint at that moment. A footprint graph shows a step change with no corresponding change in live objects, and the step is the metadata adapting to a larger heap.

Alignment and the over-aligned case

The C library guarantees that a returned pointer is suitably aligned for any object of fundamental type, which on the common 64-bit platforms means 16 bytes. A request for 17 bytes therefore occupies a class of at least 32 in most allocators, because the class must be a multiple of the alignment and the object must start on an aligned boundary. The effective minimum object size is 32 bytes on such a platform regardless of how small the request was.

Over-aligned requests, for a vector type that requires 32 or 64 bytes or for a device that requires page alignment, are worse. A 64-byte-aligned request of 64 bytes cannot be satisfied from a 64-byte class unless the span’s base is itself 64-byte aligned and the object offset is a multiple of 64, which is true only when the class size is a multiple of the alignment. Allocators handle this by rounding the class to the alignment, so a 64-byte-aligned 64-byte object occupies a 64-byte slot with no waste, whereas a 64-byte-aligned 65-byte object occupies 128. A program that aligns many small structures to a cache line pays the rounding on every one of them.

The alignment guarantee is also why the address arithmetic used to find a block’s span works at all: the allocator can mask the address against the span size only because the span’s base is aligned to it, which in turn requires that spans be allocated from page-aligned memory. A program that passes a non-heap pointer to free violates the contract, and an allocator that looks up its page map before validating the range will read metadata for an address it never allocated.

Measuring the gap

The comparison that matters is between bytes requested and bytes resident, and it is made by instrumenting three points: the sizes passed to the allocator, the sizes the allocator actually reserves, and the pages the process holds. The middle point is rarely exposed by a public interface, which is why the measurement is usually done by an allocator with a statistics interface or by a replacement allocator that tracks spans itself.

Two ratios come out of it. The per-object ratio is reserved bytes over requested bytes for live objects, and it captures headers, class rounding, and alignment. The heap ratio is resident bytes over reserved bytes for live objects, and it captures span occupancy, free lists held in caches, and pages not yet returned. The first ratio is bounded by the class table: a request that sits just above a class boundary can be rounded to roughly twice its size, so a workload clustering at those boundaries approaches a ratio of 2 from the rounding alone, while a workload of well-sized requests pays only the header. The second ratio can be arbitrarily large when a workload’s live set has just collapsed, because nothing shrinks until the allocator decides to release pages.

The second ratio is where most surprising footprint numbers come from, and it is not a defect in the allocator so much as a policy decision about when to return memory to the kernel. The policy and its measurement are covered under fragmentation , where the distinction between unusable free space and releasable free space becomes the central question.