Performance Optimization: Integrate Boost.Pool Allocators for Linked-List Stack Implementations #8

Current benchmarks of the ModernThreadSafeLinkedStack show significant performance degradation compared to the basic mutex-wrapped std::deque implementation. Even though the linked-list approach minimizes lock-holding time by constructing nodes outside the critical section, the overhead of frequent heap allocations (new/delete) and poor cache locality makes it a bottleneck.

Benchmark Context

Testing on an 8-core CPU with a 4 Producer / 4 Consumer load (100k items each) yielded the following results for the Heavy Payload (1KB) category:

The Problem

1. Allocation Overhead: Every push operation triggers a call to the global allocator for a new Node.
2. Memory Fragmentation: Standard heap allocation leads to scattered nodes in memory, resulting in frequent CPU cache misses during stack traversal.
3. SharedPtr Control Block: Using std::make_shared adds an additional allocation for the control block, further slowing down the process.

Proposed Solution: Boost.Pool Integration

I propose replacing the standard std::allocator with boost::fast_pool_allocator (from the Boost.Pool library) for node management.

Key Improvements:

• Chunk Allocation: Pre-allocate memory blocks to handle multiple nodes at once.
• O(1) Allocation: Significantly faster node creation/destruction.
• Enhanced Cache Locality: Nodes will be stored contiguously in memory pages.
• Reduced Contention: Move to a thread_local pool strategy to eliminate allocator-level locking.

Tasks

• Research the thread-safety requirements for boost::fast_pool_allocator in a concurrent environment.
• Implement a custom PoolDeleter for std::unique_ptr<Node>.
• Refactor ModernThreadSafeLinkedStack::push to use std::allocate_shared with the pool allocator.
• Re-run benchmarks and compare results with the std::deque baseline.