The heap problem

malloc / new are designed for general-purpose allocation: arbitrary sizes, arbitrary lifetimes, arbitrary order. That generality has costs:

Fragmentation — allocating and freeing blocks of different sizes creates gaps in the heap that can’t be filled by future requests. A system that has 10 kB free can still fail a 1 kB allocation if the free space is scattered in 500-byte islands. Long-running systems (servers, embedded devices, media players) degrade over time.

Non-determinism — how long does malloc(64) take? It depends on the current state of the free list. In the worst case it walks the entire heap. Real-time systems can’t tolerate that.

Overhead — each allocation has bookkeeping: size, alignment, free list pointers. The allocator itself is a lock-protected data structure that serialises all threads.

Custom allocators trade generality for predictability. The right allocator for your use case can be faster, deterministic, and use no fragmentation at all.

Pool allocator — fixed-size blocks

A pool allocator pre-allocates a chunk of memory and slices it into fixed-size blocks. All blocks are the same size — no fragmentation, O(1) allocation and deallocation.

 1template <typename T, size_t Count>
 2class PoolAllocator {
 3public:
 4    PoolAllocator() {
 5        // Build the free list through the raw storage
 6        for (size_t i = 0; i < Count - 1; ++i)
 7            blocks_[i].next = &blocks_[i + 1];
 8        blocks_[Count - 1].next = nullptr;
 9        head_ = &blocks_[0];
10    }
11
12    T* allocate() {
13        if (!head_) return nullptr;       // pool exhausted
14        Block* b = head_;
15        head_ = b->next;
16        return reinterpret_cast<T*>(b->storage);
17    }
18
19    void deallocate(T* ptr) {
20        Block* b = reinterpret_cast<Block*>(ptr);
21        b->next = head_;
22        head_   = b;
23    }
24
25private:
26    union Block {
27        alignas(T) char storage[sizeof(T)];
28        Block* next;
29    };
30    std::array<Block, Count> blocks_;
31    Block* head_ = nullptr;
32};

Usage:

1PoolAllocator<SensorSample, 64> pool;
2
3SensorSample* s = pool.allocate();
4if (s) {
5    new (s) SensorSample{tick, voltage};  // placement new — construct in pool memory
6    // ... use s ...
7    s->~SensorSample();                   // explicit destructor
8    pool.deallocate(s);
9}

Allocation: pop from free list — two pointer reads and a write. O(1), always. Deallocation: push to free list — O(1). Fragmentation: none. All blocks are the same size. Limit: one type per pool, fixed count.

Thread-safe pool

Add a spinlock (or use std::atomic for the head pointer with compare-exchange):

1T* allocate() {
2    std::lock_guard<std::mutex> lock(mutex_);
3    // ... same as above
4}

On embedded single-core MCUs, disable interrupts around the pointer swap instead.

STL-compatible pool allocator

For use with std::vector, std::list, etc., the pool must satisfy the Allocator named requirement. A minimal version:

 1template <typename T>
 2struct PoolAlloc {
 3    using value_type = T;
 4
 5    T* allocate(size_t n) {
 6        if (n != 1) throw std::bad_alloc{};  // pool only handles single objects
 7        return pool_.allocate();
 8    }
 9
10    void deallocate(T* p, size_t) {
11        pool_.deallocate(p);
12    }
13
14private:
15    static PoolAllocator<T, 256> pool_;  // shared pool per type
16};
17
18std::list<SensorSample, PoolAlloc<SensorSample>> samples;
19// Each node allocated from pool, not from heap

Arena allocator — linear bump allocation

An arena (also called a bump allocator or region allocator) allocates from a contiguous block by advancing a pointer. Deallocation is free individually — the entire arena is freed in one shot.

 1class Arena {
 2public:
 3    explicit Arena(size_t capacity)
 4        : buf_(new char[capacity]), cap_(capacity), used_(0) {}
 5
 6    // No-heap variant for embedded: pass a stack or static buffer
 7    Arena(char* buf, size_t cap)
 8        : buf_(buf), cap_(cap), used_(0), owned_(false) {}
 9
10    ~Arena() { if (owned_) delete[] buf_; }
11
12    void* allocate(size_t size, size_t align = alignof(std::max_align_t)) {
13        size_t offset = align_up(used_, align);
14        if (offset + size > cap_) return nullptr;  // out of space
15        used_ = offset + size;
16        return buf_ + offset;
17    }
18
19    void reset() { used_ = 0; }  // free all at once
20
21    size_t used()      const { return used_; }
22    size_t remaining() const { return cap_ - used_; }
23
24private:
25    static size_t align_up(size_t n, size_t align) {
26        return (n + align - 1) & ~(align - 1);
27    }
28
29    char*  buf_;
30    size_t cap_;
31    size_t used_ = 0;
32    bool   owned_ = true;
33};

Usage — parse a frame, process it, reset:

 1static char arenaBuf[4096];
 2Arena arena(arenaBuf, sizeof(arenaBuf));
 3
 4// Parse a protocol frame — allocate all temporaries from arena
 5ParsedFrame* frame   = new (arena.allocate(sizeof(ParsedFrame))) ParsedFrame();
 6uint8_t*     payload = static_cast<uint8_t*>(arena.allocate(frame->payloadLen));
 7
 8processFrame(*frame, std::span(payload, frame->payloadLen));
 9
10arena.reset();  // all of the above freed in one pointer reset

Allocation: one addition + alignment round-up. Faster than malloc. Deallocation: reset() — one pointer store. Individual frees don’t exist. Fragmentation: none. Limit: objects must not outlive the arena.

Per-request arenas (server pattern)

1void handleRequest(Request& req) {
2    char buf[8192];
3    Arena arena(buf, sizeof(buf));  // stack arena — no heap at all
4
5    auto response = new (arena.allocate(sizeof(Response))) Response();
6    // build response using arena-backed temporaries
7    send(*response);
8    // arena destroyed on return — all allocations freed implicitly
9}

Each request gets its own arena. No lock contention between threads, no heap fragmentation, deterministic cleanup.

Stack allocator

A stack allocator extends the arena with a LIFO deallocation constraint. It allows individual frees, but only in reverse order.

 1class StackAllocator {
 2public:
 3    explicit StackAllocator(size_t cap)
 4        : buf_(new char[cap]), cap_(cap), top_(0) {}
 5
 6    struct Marker { size_t pos; };
 7
 8    Marker mark() const { return {top_}; }
 9
10    void* allocate(size_t size, size_t align = alignof(std::max_align_t)) {
11        size_t offset = align_up(top_, align);
12        if (offset + size > cap_) return nullptr;
13        top_ = offset + size;
14        return buf_.get() + offset;
15    }
16
17    void freeToMarker(Marker m) { top_ = m.pos; }
18
19private:
20    static size_t align_up(size_t n, size_t a) { return (n + a - 1) & ~(a - 1); }
21    std::unique_ptr<char[]> buf_;
22    size_t cap_, top_;
23};

Usage — temporary allocations within a scope:

1StackAllocator sa(65536);
2
3auto m = sa.mark();             // mark top of stack
4void* tmp1 = sa.allocate(1024);
5void* tmp2 = sa.allocate(512);
6// use tmp1, tmp2 ...
7sa.freeToMarker(m);             // pop both — O(1)

Commonly used in game engines and graphics pipelines where per-frame allocations are freed at end-of-frame with a single pointer reset.

Embedded — static storage, no heap at all

On MCUs with no MMU and tight flash/RAM, the correct answer is often no heap:

1// All objects statically allocated — linker assigns addresses at compile time
2static SensorPipeline   pipeline;
3static RingBuffer<uint8_t, 64> uartRxBuf;
4static PoolAllocator<Message, 16> msgPool;
5
6int main() {
7    pipeline.init();
8    // Nothing allocated from heap — ever
9}

Static allocation:

  • Allocation at link time — no runtime cost
  • Total memory use visible in the map file
  • No fragmentation possible
  • Linker error (not runtime crash) if you exceed RAM

Combine static allocation with a pool for variable-count objects:

1// At most 16 messages in flight — pool allocated from static storage
2static char msgBuf[sizeof(Message) * 16 + alignof(Message) * 16];
3static Arena msgArena(msgBuf, sizeof(msgBuf));

Choosing an allocator

Allocator Alloc cost Dealloc cost Fragmentation Use case
malloc/new O(n) O(n) Yes General purpose
Pool O(1) O(1) None Fixed-size objects, many lifetimes
Arena O(1) O(1) batch None Request-scoped temporaries
Stack O(1) O(1) LIFO None Frame/scope temporaries
Static 0 (compile time) N/A None Known-count embedded objects

Detecting heap problems

Valgrind (Linux/desktop) catches heap corruption, use-after-free, double-free, and leaks:

1valgrind --leak-check=full --track-origins=yes ./your_binary

Address Sanitizer (Clang/GCC) — faster than valgrind, same classes of bugs:

1clang++ -fsanitize=address -g your.cpp -o your_binary
2./your_binary

Heap usage measurement on embedded — check the end of the heap at runtime:

1// Newlib / FreeRTOS
2extern char _end;           // start of heap (linker symbol)
3void* heapTop = sbrk(0);   // current break
4size_t used = (size_t)heapTop - (size_t)&_end;

Or use FreeRTOS xPortGetFreeHeapSize() / xPortGetMinimumEverFreeHeapSize() to track high-water marks.

Summary

  • Default heap is fragmentation-prone and non-deterministic — avoid it in embedded and high-throughput paths
  • Pool allocator: O(1) alloc/dealloc, no fragmentation, fixed object type and count
  • Arena allocator: bump pointer, batch-free all at once — perfect for request-scoped temporaries
  • Stack allocator: LIFO dealloc in addition to batch-free — frame allocations in games/graphics
  • Static allocation: zero runtime cost, size validated at link time — the embedded default

What’s next