Performance & OptimizationMemory OptimizationMedium

Implement Memory Pool for Fixed-Size Objects

Master the fundamental concepts of memory optimization through this focused micro-challenge.

~45 minutes Memory Optimization Ready to learn

Topic Overview

O(1) Fixed-Size Allocation

General-purpose malloc carries metadata, coalescing, and thread-cache logic. Games, network stacks, and kernels use memory pools when objects are one size and lifetimes are short. PostgreSQL buffer pools and slab allocators in Linux follow the same pattern at different scales.

Pool Design

Preallocate a slab of N objects. Free list threads through objects with an embedded next pointer. Allocate and free are pointer swaps.

c
Loading…

Align object size to pointer width for free-list integrity
Pools reduce fragmentation for uniform objects
Thread-local pools avoid atomic contention on global free lists
Fall back to malloc for rare oversized requests

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

Trace first: walk one failing input step by step
Read the manual: skim the official doc for the mechanism named in this task
Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will implement a fixed-size memory pool with allocate and free in O(1). This exercise asks you to beat malloc on a microbenchmark creating many same-sized objects.

Implementation Task

Your Task

A fixed-size memory pool hands out equal-sized slots in O(1). Free slots form a singly linked list, and the "next" pointer is stored inside the free slot itself, so the pool needs no extra memory for bookkeeping. Implement the pool, optionally growing by whole chunks, and detect double frees.

Input

c
Loading…

Rules

Slot size. SIZE rounded up to a multiple of 8, and at least 8 (a free slot must hold a pointer).
Addresses. Chunk k starts at 0x10000 * k, and slot s is at chunk base + (s mod CAPACITY) * slot_size. Slots are numbered globally: chunk k holds slots k*CAPACITY, k*CAPACITY + 1, …
A new chunk's slots go onto the free list so that the lowest address comes out first.
alloc pops the head of the free list. When the list is empty: with growth on, add a chunk (, new chunk), otherwise print alloc NAME: pool exhausted (NULL). A name that is already live prints alloc NAME: name in use.
free pushes the slot onto the head of the free list (LIFO, so it is reused next). Freeing a name that is not live prints free NAME: not allocated (double free or bad pointer).
pool: size >= 1, capacity 1..256 is printed for bad parameters.

Output

c
Loading…

pool adds , grows to its header when growth is on. free list: empty is printed when the list is empty. Peak is the largest number of slots in use at once.

Example

Input:

c
Loading…

Output:

c
Loading…

Requirements

Make alloc and free O(1): a pop and a push on the intrusive free list. Never scan for a free slot.
Keep a per-slot "allocated" flag, so a double free is reported instead of corrupting the list.

Hidden tests cover LIFO reuse after several frees, growth across three chunks, turning growth on after the pool is full, tiny objects rounded up to 8 bytes, invalid pool parameters, and freeing names that were never allocated.