Why a List Uses More Memory Than Its Raw Byte Count

Question

A list of 5000 longs (8 bytes each) should need about 40KB. Why does q actually allocate noticeably more than that, and where does the extra memory go?

Solution

\ts l:til 5000      / 0 65856 — about 64KB allocated
-22!l               / 40014 — for comparison, the serialised size (data + a small header)

q's allocator rounds every allocation up to the next power-of-two block size — there's no block sized exactly "40,000 bytes," only 32KB, 64KB, 128KB, and so on. A request just over a boundary gets bumped up to the next block, so 40KB of real data can end up costing 64KB or more of actual memory.

Explanation

This is the buddy allocation algorithm: memory is split into blocks whose sizes are all powers of two. Allocating a block means finding the smallest power-of-two block that fits the request (splitting a bigger block in half, repeatedly, if nothing the right size is free); freeing a block means merging it back with its "buddy" if that buddy is also free, to keep larger blocks available.

The practical effect is that real memory usage is rarely a clean multiple of bytes per element × count — it's whatever the next power-of-two block happens to be. This is why a process can appear to need "more memory than the data justifies": the gap isn't waste so much as the rounding cost of an allocator that prioritises fast allocation and fragmentation control over packing every byte tightly.