Allocators and memory pools

Every list node, tree node or order that a program creates comes from an allocator, and the allocator decides which addresses they get. A general-purpose malloc spreads small objects out with headers and with the program's own temporary objects; a pool packs them. This lecture models both and walks the same list with 3.3 times fewer cache misses from a pool.

When a program asks for memory for an object, an allocator gives it a block and returns the address. A general-purpose allocator has to remember how big each block is, so it keeps a small header in front of it, and it rounds blocks up to a multiple of 16 bytes so that any kind of value can be stored in them. The simplest model of this never reuses memory: each request takes a block right after the previous one, and the program gets the address just after the header.

def round_up(n, align):    return -(-n // align) * aligndef malloc_addresses(sizes, header=HEADER_BYTES, align=ALIGN):    addresses = []    start = 0    for size in sizes:        addresses.append(start + header)1        start += round_up(size + header, align)    return addressesprint(malloc_addresses([24, 100, 24]))print([round_up(size + 16, 16) for size in (24, 100)])

[16, 64, 192]
[48, 128]

1. 1The block is the request plus the header, rounded up to a multiple of 16: 24 bytes need a 48-byte block, 100 bytes need 128.

A node of 24 bytes (a close, a volume and a next pointer, 8 bytes each) gets a block of 48 bytes, twice what it needs, and a temporary object of 100 bytes gets 128. The three addresses are 16, 64 and 192: the second request starts after the 48-byte block of the first one, the third after the 128-byte block of the second.

Real code does not build a list in a vacuum. Between two nodes it formats a message, builds a key or parses a line, and those temporary objects are allocated too. With a simple allocator that never reuses memory they sit between the nodes. The first function below builds the plan of requests, a node followed by three temporaries of 100 bytes, and the second serves the plan and keeps the addresses of the nodes only. For comparison we also write a pool, which gives out fixed slots one right after the other.

def alloc_plan(n_nodes, garbage_per_node, garbage_bytes, node_bytes):    sizes = []    node_index = []    for _ in range(n_nodes):        node_index.append(len(sizes))        sizes.append(node_bytes)        sizes.extend([garbage_bytes] * garbage_per_node)    return sizes, node_indexdef node_addresses(n_nodes, garbage_per_node, garbage_bytes, node_bytes):    sizes, node_index = alloc_plan(n_nodes, garbage_per_node, garbage_bytes, node_bytes)    addresses = malloc_addresses(sizes)    return [addresses[i] for i in node_index]def pool_addresses(n, slot_bytes, base=0):    return [base + i * slot_bytes for i in range(n)]print(node_addresses(3, 3, 100, 24))print(node_addresses(3, 0, 100, 24))print(pool_addresses(3, 24))

[16, 448, 880]
[16, 64, 112]
[0, 24, 48]

With three temporaries per node the nodes are 432 bytes apart: 48 for the node and 3 × 128 for the garbage. Without temporaries they are 48 bytes apart. In a pool they are 24 bytes apart, exactly the size of a node, with no header and no garbage. A 64-byte line holds one scattered node, 1.3 nodes with headers only, and 2.7 nodes in the pool. We now walk 3,000 nodes, reading the first and the last byte of each, through the cache of the earlier topics.

def traversal_misses(addresses, node_bytes):    cache = Cache()    for address in addresses:        cache.access(address)        cache.access(address + node_bytes - 1)    return cache.missesn = 3000for name, addresses in (("scattered", node_addresses(n, 3, 100, 24)), ("headers only", node_addresses(n, 0, 100, 24)), ("pool", pool_addresses(n, 24))):    print(name, traversal_misses(addresses, 24), "misses, last node at", addresses[-1] // 1024, "KB")

scattered 3750 misses, last node at 1265 KB
headers only 2250 misses, last node at 140 KB
pool 1125 misses, last node at 70 KB

The scattered list takes 3,750 misses and spreads over 1,265 KB. The pool, which holds the very same 3,000 nodes, takes 1,125 misses over 70 KB: 3.3 times fewer, and the nodes would even fit in an L2 cache. The program, the data and the order of the walk are the same; only the addresses changed.

The lab follows the lecture: the rounding, the simple general-purpose allocator, the pool, the plan of requests with temporaries, the addresses of the nodes, the count of misses of a walk and the study on a list of SPY days.

• Function · questionBuilds on
• round_up(n, align)What is n rounded up to a multiple?Plain arithmetic
• malloc_addresses(sizes)Where does a general-purpose allocator put each block?round_up
• pool_addresses(n, slot_bytes)And a pool?Plain arithmetic
• alloc_plan(...)Which requests does the program make?Plain arithmetic
• node_addresses(...)Where do the nodes end up?alloc_planmalloc_addresses
• traversal_misses(addresses, node_bytes)How many misses does a walk cost?Cache
• study(bars)How much does a pool save on the SPY list?node_addressespool_addressestraversal_misses

Next topic: so far every cost came from memory. The last hardware effect of this skill comes from the processor's guesses. In Branch prediction you model a predictor, count its mistakes on a loop with an if inside and see why the same loop is faster on sorted data.