LRU: Replace std::list with intrusive list for better cache locality

[jsrivaya]

Problem

The current LRU implementation uses std::list<std::pair<K, V>> which allocates each node separately on the heap. This causes:

• Poor cache locality (nodes scattered in memory)
• Allocation overhead on every insert
• Cache misses when traversing the list

Benchmark Impact

Operation	Current	unordered_map	Overhead
put	255 ns	49 ns	5x slower
get (hit)	15 ns	7.5 ns	2x slower

Proposed Solution

Replace std::list with a pre-allocated intrusive doubly-linked list:

struct Node {
    K key;
    V value;
    Node* prev;
    Node* next;
};

std::vector<Node> nodes_;  // Pre-allocated, contiguous memory
std::unordered_map<K, Node*> map_;
Node* head_;  // MRU
Node* tail_;  // LRU
Node* free_;  // Free list for reuse

Benefits

• Contiguous memory: All nodes in a single std::vector, better cache locality
• Zero allocation on hot path: Nodes reused from free list
• Reduced indirection: Direct pointer manipulation vs iterator abstraction

Expected Improvement

• put: 3-4x faster (closer to raw hash map)
• get: 1.5-2x faster

References

• Boost.Intrusive
• Similar approach used in high-performance LRU implementations like LevelDB's LRUCache