GitHub - adanil-code/LRUHashTable: A cross-platform, multi-core optimized C++20 LRU Hash Table featuring zero runtime allocations, custom TTAS spinlocks, and Windows Kernel support.

High-Performance Array-Backed LRU Hash Table Concurrent LRU Hash Table optimized for: multi-core scalability predictable tail latency NUMA architectures zero runtime allocations Table of Contents The Problem: The Standard Library Bottleneck The Solution: Core Architecture & Algorithms Benchmarks & Scaling Performance When This Table May Not Be the Best Fit Quick Start API Overview Project Structure Building test code Conclusion & Future Hardware Extrapolation License & Contributing A high-performance concurrent LRU hash table designed for demanding systems programming workloads such as caching layers, network infrastructure, and kernel components. By leveraging shard-based parallelism and cache-friendly memory layouts, the implementation delivers high throughput in environments where standard library containers degrade under contention. Key Architectural Highlights Zero Runtime Allocations: Pre-allocated flat arrays eliminate heap fragmentation and OS-level lock stalls. Custom TTAS Spinlocks: Replaces std::shared_mutex to eliminate OS context switches, achieving 14x+ throughput and sub-microsecond tail latencies. (Note: User-mode uses a custom TTAS Spinlock for raw speed, while Kernel-mode relies on EX_PUSH_LOCK). Sharded Architecture: Eliminates global lock convoys, scaling linearly with physical CPU core counts. NUMA-Aware Memory: Distributes shard allocations across physical CPU sockets to maximize memory controller bandwidth. Lock-Free Destruction: Payloads are explicitly destroyed outside the synchronization boundary, ensuring flat tail latencies. Lazy LRU Promotion: A tunable "Safe Zone" bypasses exclusive lock upgrades on hot reads, yielding an ~20% throughput boost. Custom Allocators (User-Mode): Supports template-injected allocators for domain-specific memory management. Dual Environment Ready: Full cross-platform user-mode support alongside a dedicated Windows 10+ Kernel implementation (IRQL < DISPATCH_LEVEL). The implementation prioritizes mechanical sympathy, cache locality, lock scalability, and predictable memory behavior, making it suitable for demanding environments such as: High-Frequency Trading (HFT) infrastructure Storage subsystem caches Real-time network routing Kernel / driver components High-throughput web servers The implementation provides O(1) average-time operations for insertion, lookup, and removal while maintaining a strict or probabilistic Least Recently Used (LRU) eviction policy. The Problem: The Standard Library Bottleneck Typical concurrent LRU implementations (e.g., combining std::unordered_map + std::list protected by a global std::shared_mutex) suffer from severe architectural flaws on modern high-core-count CPUs: Global Lock Contention: A single lock creates a catastrophic "lock convoy," where adding threads actually decreases total throughput. Pointer Chasing: Node traversal across the heap destroys L1/L2 cache locality. Allocator Overhead: Every insertion/eviction triggers heap allocation/deallocation (new/delete), resulting in memory fragmentation and OS-level lock stalls. False Sharing: Unaligned memory structures cause adjacent CPU cores to invalidate each other's L1 cache lines, silently destroying performance. The Solution: Core Architecture & Algorithms This project solves the standard library bottlenecks through a combination of sharding, flat-array memory management, and lock-free destruction techniques. This diagram illustrates the architecture of a LRU hash table that eliminates global lock contention by partitioning data into independent, cache-aligned shards. Each shard operates autonomously with its own exclusive TTAS spinlock, metadata counters, and a contiguous "Mega-Block" of memory containing the bucket and node arrays. Within these arrays, both the hash collision chains and the doubly-linked LRU queues are constructed using 32-bit array indices rather than standard 64-bit pointers, which halves the structural memory overhead and improves L1/L2 cache locality during hot-path operations. At a high level, the table is partitioned into independent shards, each managing its own hash table and LRU chain: ============================================================================= [ Master Hash Table Object ] ============================================================================= | +---> [ Shard Array ] (Contiguous block, scaled to ~ CPU Cores * 32) | +--- [ Shard 0 ] (64/128-byte aligned to prevent false sharing) | | | +-- Synchronization : Exclusive TTAS Spinlock | | | +-- Meta Counters : ActiveCount, Capacity, Generation | | | +-- Chain Pointers : LruHead, LruTail, FreeHead (32-bit indices) | | | | (Hash Collision Chain via HashNext) | +-- Buckets Array : [ Head_Idx ] [ INVALID ] [ Head_Idx ] ... | | | | | | v v | +-- Nodes Array : [ Node 0 ] [ Node 4 ] | (The Mega-Block) [ Node 1 ] <--- FreeHead | | [ Node 2 ] <--- LruHead v | [ Node 3 ] [ Node 5 ] | ... | [ Node N ] <--- LruTail (Next Eviction) | | (Inside LruNode) --> +-----------------------------------+ | | HOT PATH: Hash, HashNext, LruPrev | | | MATCH: TKey | | | COLD: TValue*, LruNext | | +-----------------------------------+ | +--- [ Shard 1 ] (Isolated locks & capacity bounds) | | | +-- Synchronization : ... | +-- Buckets Array : [ ... ] | +-- Nodes Array : [ ... ] | +--- [ Shard 2 ] | ... | +--- [ Shard N ] Node Memory Layout (Mechanical Sympathy) To maximize L1/L2 cache hit rates, the internal node structure explicitly separates data based on access frequency during traversal: The Hot Path (First Cache Line): Variables critical for navigating collision chains and verifying matches (Hash, HashNext, LruPrev, and the Key) are tightly packed into the first hardware cache line (64 bytes or 128 bytes depending on architecture). This ensures that the CPU can scan deep hash buckets in a single memory fetch without triggering expensive main-memory stalls. The Cold Path: Variables required only after a successful key match or during an eviction (Value*, LastPromoted, LruNext) are pushed off to secondary cache lines. This guarantees that the memory controller never wastes bandwidth fetching payload pointers or age metrics for nodes that are merely being passed over during a lookup scan. ------------------------------------------------- | Hash | HashNext | LruPrev | Key | | ------------------------------------------------- | Value* | LastPromoted | LruNext | | ------------------------------------------------- HOT PATH (cache line) COLD PATH 1. Sharded Parallelism The table is split into independent, isolated shards. Each shard contains its own hash buckets, LRU list, spinlock, and capacity limits. Shard count is dynamically scaled based on processor topology (shards ≈ CPU cores × 32). Threads are routed using a MurmurHash3-style avalanche mixer (MixHash) to force entropy into the lower bits. This ensures uniform shard distribution under typical hash quality regardless of the quality of the user-provided hash function: shard = MixHash(hash) & (ShardCount - 1). This ensures uniform workload distribution and avoids global lock contention by design. 2. Array-Backed Mega-Blocks & 32-bit Indices Instead of allocating nodes individually on the heap, all nodes and buckets are pre-allocated in contiguous flat arrays (Mega-Blocks). Zero Runtime Allocations: Once initialized, the table never calls new or delete. Relative 32-bit Indices: Linked lists (LRU chains and Hash collisions) are implemented using 32-bit array indices instead of 64-bit pointers. This cuts the structural memory overhead in half and dramatically increases the number of nodes that fit inside the CPU's L1/L2 cache. NUMA Awareness: The user-mode table utilizes VirtualAllocExNuma (Windows) or libnuma (Linux) to distribute shard allocations evenly across physical CPU sockets, maximizing memory controller bandwidth. 3. Mechanical Sympathy & Cache Management Memory layout is strictly controlled to respect hardware-specific cache alignment, i.e., 64 bytes on x86_64 and ARM64, and 128 bytes on Apple silicon. False Sharing Prevention: struct alignas(CACHE_LINE_SIZE) Shard { ... }; Shards are explicitly padded to hardware-specific cache line boundaries (64-byte or 128-byte). A thread locking Shard A will never invalidate the cache line for a thread accessing Shard B. Hot/Cold Path Struct Packing: struct LruNode { // --- HOT PATH (First Cache Line) --- uint64_t Hash; // Cached to avoid rehashing uint32_t HashNext; // Hash collision chain index uint32_t LruPrev; // LRU chain index TKey Key; // Starts at 16-byte boundary // --- COLD PATH --- TValue* Value; // Accessed only on exact match uint64_t LastPromoted; // Age tracking uint32_t LruNext; // LRU chain index }; Variables required for hash traversal packed into the first portion of the first cache line. The CPU fetches these together in a single read, guaranteeing a cache hit during deep collision chain probing. 4. Advanced Concurrency Controls Out-of-Lock Destruction: Deadlocks and latency spikes are avoided by guaranteeing that user code never executes inside the synchronization boundary. Evicted nodes are detached, the lock is dropped, and only then is the payload destructed/released. Lazy LRU Promotion (Generation Counter): Traditional LRUs promote items to the MRU head on every read, requiring an exclusive write-lock. This implementation uses a probabilistic