Eliminate Memory Fragmentation: Understanding Memory Pools

1. Introduction to Memory Fragmentation

In everyday development, slow performance, high memory usage, and crashes often stem from memory fragmentation rather than business‑logic bugs. Frequent system calls that allocate and free scattered memory fragments large contiguous regions, making it appear that memory is sufficient while large blocks cannot be allocated.

1.1 What Is Memory Fragmentation

Memory fragmentation refers to non‑contiguous free spaces that cannot be effectively used. When the OS allocates memory, it searches for suitable free regions; many small free blocks that cannot be merged form external fragmentation, while unused portions within allocated blocks constitute internal fragmentation.

1.2 How Fragmentation Is Produced

In C++ (or C), repeated new / delete (or malloc / free) operations create fragmentation. For example:

#include <iostream>
#include <cstdlib>
int main() {
    // Allocate three blocks
    char* ptr1 = new char[10];
    char* ptr2 = new char[20];
    char* ptr3 = new char[15];
    // Free two blocks
    delete[] ptr1;
    delete[] ptr3;
    // Allocate a new block of size 25
    char* ptr4 = new char[25];
    return 0;
}

After freeing ptr1 and ptr3, two separate free blocks of 10 and 15 bytes remain. Although their total size equals 25, they are non‑contiguous, so allocating ptr4 fails, demonstrating external fragmentation.

A mixed long‑term and short‑term object scenario also creates many tiny free blocks after short‑lived objects are destroyed, further fragmenting memory.

1.3 Harm of Memory Fragmentation

Fragmentation reduces usable memory, increases allocation time, and can hide memory leaks, eventually exhausting system memory and causing crashes.

2. Memory Pool Details

2.1 What Is a Memory Pool

A memory pool pre‑allocates a large contiguous memory region and then serves allocation requests from this region, similar to a warehouse that stores goods in advance.

2.2 Working Mechanism of a Memory Pool

The mechanism consists of four steps: pre‑allocation, block division, free‑list maintenance, and allocation/free operations.

Pre‑allocation – At program start, a large block is requested from the OS, e.g., 10 MB for a network server:

#include <stdio.h>
#include <stdlib.h>
// Core structure
typedef struct MemPool {
    void* pool_start;   // start address of the large block
    size_t block_size;   // size of each small block
    size_t block_count;  // total number of blocks
} MemPool;

MemPool* mem_pool_pre_alloc(size_t block_size, size_t block_count) {
    MemPool* pool = (MemPool*)malloc(sizeof(MemPool));
    size_t total_size = block_size * block_count;
    pool->pool_start = malloc(total_size);
    pool->block_size = block_size;
    pool->block_count = block_count;
    printf("Pre‑allocation completed: total size %zu bytes
", total_size);
    return pool;
}

Block Division – The large block is split into equal (or varied) small blocks:

void divide_mem_blocks(MemPool* pool) {
    if (!pool || !pool->pool_start) return;
    char* block_ptr = (char*)pool->pool_start;
    printf("Dividing blocks: size %zu, count %zu
", pool->block_size, pool->block_count);
    for (int i = 0; i < pool->block_count; i++) {
        block_ptr += pool->block_size; // move pointer to next block
    }
}

Free‑list – A singly linked list records which blocks are free:

typedef struct MemBlock {
    struct MemBlock* next; // next free block
} MemBlock;

typedef struct MemPool {
    void* pool_start;
    size_t block_size;
    size_t block_count;
    MemBlock* free_list; // head of free list
} MemPool;

void init_free_list(MemPool* pool) {
    pool->free_list = (MemBlock*)pool->pool_start;
    MemBlock* current = pool->free_list;
    for (int i = 1; i < pool->block_count; i++) {
        current->next = (MemBlock*)((char*)current + pool->block_size);
        current = current->next;
    }
    current->next = NULL;
    printf("Free list initialized
");
}

Allocation – The pool takes the head of the free list; if empty, it may request more memory or merge blocks:

void* mem_pool_alloc(MemPool* pool) {
    if (!pool || !pool->free_list) {
        printf("Allocation failed: no free blocks
");
        return NULL;
    }
    MemBlock* alloc_block = pool->free_list;
    pool->free_list = alloc_block->next;
    printf("Allocation succeeded: address %p
", alloc_block);
    return alloc_block;
}

Free – Returned blocks are inserted back into the free list:

void mem_pool_free(MemPool* pool, void* ptr) {
    if (!pool || !ptr) return;
    MemBlock* free_block = (MemBlock*)ptr;
    free_block->next = pool->free_list;
    pool->free_list = free_block;
    printf("Free succeeded: address %p
", ptr);
}

2.3 How a Memory Pool Solves Fragmentation

Because the pool pre‑allocates a contiguous region and hands out whole blocks, external fragmentation is largely avoided; blocks are either fully used or returned to the free list, allowing easy merging. Internal fragmentation is reduced by choosing block sizes that match typical request sizes, e.g., using 20‑byte blocks for frequent 10‑20‑byte allocations.

2.4 Core Advantages

Reduces system‑call overhead: after the initial large allocation, subsequent allocations occur in user space without kernel transitions.

Minimises fragmentation: fixed‑size blocks eliminate internal waste; free‑list management and optional buddy‑system merging curb external fragmentation.

Improves concurrency: per‑thread caches (e.g., TCMalloc) or mutex‑protected pools reduce lock contention, boosting multithreaded performance.

3. Implementation Approaches

3.1 Simple Fixed‑Size Memory Pool

A straightforward implementation uses a fixed block size and a free list:

#include <iostream>
#include <cstdlib>
class FixedSizeMemoryPool {
private:
    struct Block { Block* next; };
    char* pool;          // start address
    Block* freeList;     // head of free list
    size_t blockSize;
    size_t numBlocks;
public:
    FixedSizeMemoryPool(size_t size, size_t count) : blockSize(size), numBlocks(count) {
        if (blockSize < sizeof(Block*)) blockSize = sizeof(Block*);
        pool = new char[blockSize * numBlocks];
        freeList = nullptr;
        for (size_t i = 0; i < numBlocks; ++i) {
            Block* block = reinterpret_cast<Block*>(pool + i * blockSize);
            block->next = freeList;
            freeList = block;
        }
    }
    ~FixedSizeMemoryPool() { delete[] pool; }
    void* allocate() {
        if (!freeList) return nullptr;
        Block* block = freeList;
        freeList = freeList->next;
        return block;
    }
    void deallocate(void* ptr) {
        if (ptr) {
            Block* block = static_cast<Block*>(ptr);
            block->next = freeList;
            freeList = block;
        }
    }
};

This design works well for high‑frequency allocation of objects of the same size.

3.2 General‑Purpose Memory Pool

A more flexible pool maintains several free lists for different block sizes. The Linux kernel’s slab allocator (kmalloc) follows this pattern.

#include <stdio.h>
#include <stdlib.h>

typedef struct Block { struct Block* next; } Block;

typedef struct GeneralMemPool {
    size_t sizes[8];       // supported block sizes
    Block* free_lists[8];  // one list per size
    int size_count;        // number of size classes
} GeneralMemPool;

void general_pool_init(GeneralMemPool* pool) {
    pool->sizes[0] = 16; pool->sizes[1] = 32; pool->sizes[2] = 64;
    pool->sizes[3] = 128; pool->sizes[4] = 256; pool->size_count = 5;
    for (int i = 0; i < pool->size_count; i++) pool->free_lists[i] = NULL;
}

int get_fit_index(GeneralMemPool* pool, size_t size) {
    for (int i = 0; i < pool->size_count; i++) {
        if (pool->sizes[i] >= size) return i;
    }
    return -1; // no suitable size
}

void* general_pool_alloc(GeneralMemPool* pool, size_t size) {
    if (!pool || size == 0) return NULL;
    int idx = get_fit_index(pool, size);
    if (idx == -1) return malloc(size);
    Block* block = pool->free_lists[idx];
    if (block) {
        pool->free_lists[idx] = block->next;
        return block;
    }
    return malloc(pool->sizes[idx]);
}

void general_pool_free(GeneralMemPool* pool, void* ptr, size_t size) {
    if (!pool || !ptr) return;
    int idx = get_fit_index(pool, size);
    if (idx == -1) { free(ptr); return; }
    Block* block = (Block*)ptr;
    block->next = pool->free_lists[idx];
    pool->free_lists[idx] = block;
}

3.3 Thread‑Safe Memory Pool

In multithreaded environments, a mutex (or other synchronization primitive) protects pool operations:

#include <iostream>
#include <mutex>
class ThreadSafeMemoryPool {
private:
    struct Block { Block* next; };
    Block* freeList;
    char* memory;
    size_t blockSize;
    size_t poolSize;
    std::mutex mtx;
public:
    ThreadSafeMemoryPool(size_t count, size_t size) : blockSize(size), poolSize(count) {
        if (blockSize < sizeof(Block*)) blockSize = sizeof(Block*);
        memory = new char[blockSize * poolSize];
        freeList = nullptr;
        for (size_t i = 0; i < poolSize; ++i) {
            Block* block = reinterpret_cast<Block*>(memory + i * blockSize);
            block->next = freeList;
            freeList = block;
        }
    }
    ~ThreadSafeMemoryPool() { delete[] memory; }
    void* allocate() {
        std::lock_guard<std::mutex> lock(mtx);
        if (!freeList) return nullptr;
        Block* block = freeList;
        freeList = freeList->next;
        return block;
    }
    void deallocate(void* ptr) {
        std::lock_guard<std::mutex> lock(mtx);
        if (ptr) {
            Block* block = static_cast<Block*>(ptr);
            block->next = freeList;
            freeList = block;
        }
    }
};

Other techniques such as read‑write locks, thread‑local pools, and cache‑line padding can further reduce contention and false sharing.

4. Usage Considerations and Optimisation

4.1 Choosing the Pool Size

The pool size should be estimated from workload characteristics. For example, handling 1 000 simultaneous 5 KB files requires at least 5 MB, plus a safety margin (20‑30 %). Too small a pool forces frequent OS allocations, degrading performance; too large a pool wastes memory and increases management overhead.

4.2 Optimisation Strategies

Dynamic block size : Adjust block sizes based on observed request patterns to minimise internal waste.

Cache layer : Keep a hot cache of recently used blocks (e.g., LRU or FIFO) to avoid traversing the free list.

Merge & split : Periodically coalesce adjacent free blocks and split larger blocks to satisfy big requests, improving both external fragmentation and allocation flexibility.

Applying these techniques enables high‑performance, low‑fragmentation memory management for latency‑sensitive services such as graphics rendering engines, database caches, and high‑concurrency network servers.

Memory pools, by pre‑allocating, carefully dividing, and efficiently reusing memory blocks, provide a powerful tool to combat fragmentation, improve allocation speed, and enhance overall system stability.