Lock Free Memory Pool

A high-performance, thread-safe, lock-free memory pool implementation in C++20.

Features

• Lock-free allocation/deallocation - Fixed-capacity pools for low-latency allocation paths
• Two strategies - Index-queue free list or per-slot CAS scanning
• RAII support - Custom deleter + std::unique_ptr wrapper
• Global pool management - Simple macros for defining type-specific pools
• Header-only library - Easy integration, just include the headers
• Cross-platform - Works on Windows, Linux, and macOS
• Exception safe - Construction failures return slots back to the pool

Quick Start

1. Include the header

#include "IndexQueuePool.h"  // or "ScanningPool.h"
using namespace lfmemorypool;

2. Define global pools for your types

// Define pools for your types (must be at global scope, not inside namespaces)
DEFINE_LOCKFREE_POOL(MyClass, 1024);  // IndexQueuePool (power of two)
DEFINE_LOCKFREE_POOL(AnotherType, 4096);

// For arbitrary sizes, use the scanning strategy instead
// DEFINE_LOCKFREE_SCANNING_POOL(AnotherType, 5000);

Note: IndexQueuePool requires a power-of-two capacity. Use DEFINE_LOCKFREE_SCANNING_POOL if you need arbitrary sizes.

Important: The DEFINE_LOCKFREE_POOL macro must be invoked at global scope (outside of any namespace). However, the types themselves can be in namespaces:

namespace myapp {
    struct MyType { /* ... */ };
}

// Macro must be at global scope
DEFINE_LOCKFREE_POOL(myapp::MyType, 1024);

namespace myapp {
    void use_pool() {
        // Usage code can be inside namespaces
        auto obj = lfmemorypool::lockfree_pool_alloc_safe<MyType>();
    }
}

3. Use the pools

// Safe allocation with RAII (recommended)
auto obj1 = lockfree_pool_alloc_safe<MyClass>(constructor_args...);
// obj1 is automatically cleaned up when it goes out of scope

// Fast allocation for performance-critical paths
MyClass* obj2 = lockfree_pool_alloc_fast<MyClass>(constructor_args...);
// Must manually call lockfree_pool_free_fast(obj2) when done
lockfree_pool_free_fast(obj2);

Building

Prerequisites

• C++20 or later compiler (GCC 10+, Clang 10+, MSVC with C++20 support)
• CMake 3.16+
• Google Test (automatically downloaded if not found)

Build Instructions

Linux/macOS:

# Create build directory
mkdir build && cd build

# Configure
cmake ..

# Build
make -j$(nproc)

# Run tests
ctest --verbose
# or
make run_tests

# Optional: Build and run examples
cmake .. -DBUILD_EXAMPLES=ON
make
./examples/basic_usage

Windows (PowerShell):

# Create build directory
mkdir build
cd build

# Configure (Visual Studio)
cmake ..

# Build
cmake --build . --config Release

# Run tests
ctest --verbose -C Release

Build Options

• BUILD_TESTS=ON/OFF - Build tests (default: ON)
• BUILD_EXAMPLES=ON/OFF - Build usage examples (default: OFF)
• BUILD_BENCHMARKS=ON/OFF - Build performance benchmarks (default: OFF)
• ENABLE_TSAN=ON/OFF - Enable ThreadSanitizer for lock-free validation (default: OFF)
• ENABLE_ASAN=ON/OFF - Enable AddressSanitizer for memory error detection (default: OFF)
• CMAKE_BUILD_TYPE=Debug/Release - Build configuration (default: Release)

Example:

cmake -DBUILD_EXAMPLES=ON -DBUILD_BENCHMARKS=ON -DCMAKE_BUILD_TYPE=Release ..

Testing with ThreadSanitizer

ThreadSanitizer is useful for validating lock-free code across different CPU architectures.

# Build with ThreadSanitizer enabled
cmake -DCMAKE_BUILD_TYPE=Debug -DENABLE_TSAN=ON ..
make -j$(nproc)

# Run tests with TSan - will detect data races and memory ordering issues
./build/test/lockfree_mempool_tests

# For thorough testing, also run concurrent tests multiple times
for i in {1..10}; do ./build/test/lockfree_mempool_tests --gtest_filter="*Concurrent*"; done

Note: ThreadSanitizer has significant performance overhead and should only be used during development and testing, not in production builds.

API Reference

Individual Pool Usage

// Create a pool
LockFreeMemoryPool<MyType, IndexQueuePool, 1024> pool;
// or: IndexQueueLockFreeMemoryPool<MyType, 1024> pool;
// or: LockFreeMemoryPool<MyType, ScanningPool, 5000> pool;
// or: ScanningLockFreeMemoryPool<MyType, 5000> pool;

// Safe allocation with RAII
auto obj = pool.allocate_safe(constructor_args...);

// Fast allocation
MyType* ptr = pool.allocate_fast(constructor_args...);
pool.deallocate_fast(ptr);

// Get statistics
auto stats = lfmemorypool::stats::get_pool_stats(pool);
std::cout << "Pool utilization: " << stats.utilization_percent << "%" << std::endl;

Global Pool Functions

// After defining pools with DEFINE_LOCKFREE_POOL or DEFINE_LOCKFREE_SCANNING_POOL
auto obj = lockfree_pool_alloc_safe<MyType>(args...);
MyType* ptr = lockfree_pool_alloc_fast<MyType>(args...);
lockfree_pool_free_fast(ptr);
auto stats = lfmemorypool::stats::lockfree_pool_stats<MyType>();

Pool Statistics

The library provides comprehensive pool monitoring through the lfmemorypool::stats namespace. Include LockFreeMemoryPoolStats.h to enable statistics collection:

#include "IndexQueuePool.h"  // or "ScanningPool.h"
#include "LockFreeMemoryPoolStats.h"

// Pool instance statistics
lfmemorypool::LockFreeMemoryPool<MyType, lfmemorypool::IndexQueuePool, 1024> pool;
auto stats = lfmemorypool::stats::get_pool_stats(pool);

// Global pool statistics
auto global_stats = lfmemorypool::stats::lockfree_pool_stats<MyType>();

// Statistics structure
struct PoolStats {
    size_t total_objects;        // Total pool capacity
    size_t free_objects;         // Available objects
    size_t used_objects;         // Currently allocated objects  
    double utilization_percent;  // Usage percentage (0-100)
};

std::cout << "Pool utilization: " << stats.utilization_percent << "%" << std::endl;
std::cout << "Free objects: " << stats.free_objects << "/" << stats.total_objects << std::endl;

Performance Characteristics

• IndexQueuePool: O(1) allocation/deallocation (fixed power-of-two capacity)
• ScanningPool: O(N) worst-case allocation, O(1) deallocation
• Lock-free - No blocking between threads
• Fixed capacity - Predictable memory usage, no fragmentation

Thread Safety

The memory pool is fully thread-safe:

• Multiple threads can allocate simultaneously
• Multiple threads can deallocate simultaneously
• Allocation and deallocation can happen concurrently

Error Handling and Edge Cases

Pool Exhaustion

When the pool is exhausted (all objects are allocated):

• allocate_safe() returns nullptr (no exceptions thrown)
• lockfree_pool_alloc_safe() returns nullptr (no exceptions thrown)
• allocate_fast() returns nullptr (no exceptions thrown)
• lockfree_pool_alloc_fast() returns nullptr (no exceptions thrown)

// Safe handling of pool exhaustion
auto obj = lockfree_pool_alloc_safe<MyType>();
if (!obj) {
    // Pool is exhausted - handle gracefully
    std::cerr << "Pool exhausted, falling back to heap allocation\n";
    auto heap_obj = std::make_unique<MyType>();
    // ... continue with heap_obj
}

Constructor Exceptions

If object construction throws an exception:

• Memory is automatically returned to the pool
• Exception is propagated to the caller
• Pool remains in a consistent state

struct ThrowingType {
    ThrowingType() { throw std::runtime_error("Construction failed"); }
};

try {
    auto obj = lockfree_pool_alloc_safe<ThrowingType>();
    // obj will be nullptr - exception was caught internally
} catch (const std::exception& e) {
    // This won't be reached for safe allocation
    // Fast allocation would propagate the exception
}

Invalid Pointer Handling

• deallocate_fast() and lockfree_pool_free_fast() are safe with nullptr
• Performance Note: For maximum speed, the library does not validate that pointers belong to the pool
• Passing invalid pointers results in undefined behavior - users must ensure correct usage
• Debug builds may catch some invalid usage through assertions

// Safe usage patterns
MyType* obj = lockfree_pool_alloc_fast<MyType>();
if (obj) {
    // ... use obj
    lockfree_pool_free_fast(obj);  // Safe
}

lockfree_pool_free_fast(nullptr);  // Safe - no-op

// INCORRECT - undefined behavior:
// MyType external_obj;
// lockfree_pool_free_fast(&external_obj);  // DON'T DO THIS!

License

This project is licensed under the MIT License - see the LICENSE file for details.

Contributing

Contributions are welcome! Please feel free to submit a Pull Request. For major changes, please open an issue first to discuss what you would like to change.

Performance Benchmarking

This project includes comprehensive performance benchmarks using Google Benchmark, a popular C++ benchmarking framework. The benchmarks provide detailed performance measurements comparing heap allocation to pool allocation.

Quick Performance Test

# Install Google Benchmark (Ubuntu/Debian)
sudo apt install libbenchmark-dev

# Build and run
cmake -S . -B build -DBUILD_BENCHMARKS=ON
cmake --build build
./build/benchmarks/google_benchmark

The Google Benchmark suite includes:

• Allocation Benchmarks: Heap vs Pool (index-queue and scanning) across different object counts
• Multi-threaded Benchmarks: Concurrent allocation performance
• Fragmentation Tests: Realistic allocation/deallocation patterns
• Mixed Workloads: Combined allocation patterns

For installation and detailed usage, see benchmarks/README.md.

Examples

See the examples/ directory for comprehensive usage demonstrations:

• basic_usage.cpp - Complete example showing safe/fast allocation, thread safety, pool exhaustion handling, and exception safety
• Examples README - Detailed explanation of all example programs

Quick example run:

cmake -B build -DBUILD_EXAMPLES=ON
cmake --build build
./build/examples/basic_usage