How I Built a Cache-Line Aligned Hash Table in Rust That Fits Every Bucket in 64 Bytes

Most hash tables waste memory. They store data in one place, eviction metadata in another, and chain everything together with pointers. Every lookup chases 2-3 pointers across memory, each one potentially a cache miss. I wanted to see if I could eliminate that — pack data and eviction logic into a single 64-byte CPU cache line, so the hardware does the heavy lifting.
The result is PulseMap, an open-source Rust crate. This post explains the design, what worked, what didn't, and the actual benchmark numbers — including where PulseMap loses.
The Problem: Bounded Caches Are Surprisingly Hard
A HashMap stores everything you give it. Memory grows linearly with the number of entries. For a cache, that's unacceptable — you need a fixed memory ceiling. When the cache is full, something has to go.
The typical solution is a HashMap + a doubly-linked list (LRU cache). The linked list tracks access order, so you can evict the least-recently-used entry. But this means every lookup touches two data structures in different memory regions. The HashMap gives you the entry; then you update the linked list node, which lives somewhere else in the heap. That's at least two cache misses per operation.
I started with a different question: what if the eviction metadata lived inside the hash table entry itself, in the same cache line?
The 64-Byte Bucket
Modern x86 CPUs read memory in 64-byte chunks called cache lines. When the CPU reads byte 0 of a 64-byte block, bytes 1-63 come along for free — they're already in L1 cache.
PulseMap's fundamental unit is a Bucket: exactly 64 bytes, forced to align on a 64-byte boundary.
#[repr(C, align(64))]
pub struct Bucket {
pub meta: MetaWord, // 8 bytes
pub slots: [Slot; 4], // 4 × 14 = 56 bytes
}
// 8 + 56 = 64 bytes = exactly 1 cache line
const _: () = assert!(core::mem::size_of::<Bucket>() == 64);
One bucket holds four key-value entries and all the metadata needed to decide which one to evict. One memory fetch gets everything.
MetaWord: 8 Bytes That Do Everything
The first 8 bytes of every bucket is a MetaWord — a single u64 integer that packs three pieces of information for all four slots:
Bits 63-56: Slot states (4 slots × 2 bits = 8 bits)
Bits 55-28: H2 fingerprints (4 slots × 7 bits = 28 bits)
Bits 27-0: Eviction scores (4 slots × 7 bits = 28 bits)
Let me break down each one.
Slot States (2 bits each): Empty, Full, Deleted, or Tombstone. Nothing surprising here.
H2 Fingerprints (7 bits each): When a key is hashed (PulseMap uses WyHash), the top 7 bits of the hash become a fingerprint. During lookup, PulseMap compares the query's fingerprint against all four stored fingerprints before doing any key comparison. Since a 7-bit fingerprint has 128 possible values, a random non-matching entry has only a 0.78% chance of passing this filter. In practice, this means 99.2% of non-matching slots are rejected by reading just the MetaWord — no need to touch the actual key data at all.
Eviction Scores (7 bits each): This is where PulseMap differs from a standard LRU. Each slot's 7-bit score is split into:
- Frequency (4 bits, range 0-15): incremented on each access
- Recency (3 bits, range 0-7): set to max on access, decayed over time
This makes PulseMap's eviction policy a hybrid of LFU (Least Frequently Used) and LRU (Least Recently Used). An entry that was accessed many times recently has both high frequency and high recency bits. An entry that was popular yesterday but hasn't been touched since has high frequency but decaying recency. When eviction is needed, the slot with the lowest combined score goes.
How On-Access Priority Updates Work (Lock-Free)
When a lookup finds a cache hit, PulseMap needs to update the priority bits. The accessed slot's frequency goes up and its recency resets to maximum. The other three slots in the same bucket have their recency decremented by one.
Since the MetaWord is an AtomicU64, this update uses a Compare-and-Swap (CAS) loop:
pub fn on_access(&self, slot: u8) {
loop {
let current = self.load();
let mut new_val = current;
// ... modify priority bits for all 4 slots ...
match self.0.compare_exchange_weak(
current, new_val,
Ordering::Relaxed, Ordering::Relaxed,
) {
Ok(_) => break,
Err(_) => continue, // another thread modified it, retry
}
}
}
The CAS loop means this works from a shared reference (&self) — no mutex needed. If two threads update the same MetaWord simultaneously, one succeeds and the other retries with the updated value. No data is lost.
Slot: 14 Bytes, Two Modes
Each of the four slots in a bucket is exactly 14 bytes. The high bit of the first byte determines the storage mode:
Inline Mode (bit 7 = 0): For keys up to 6 bytes and values up to 7 bytes, everything is stored directly in the 14-byte slot. No heap allocation. No pointer. A u32 key and a u64 value? Fits inline.
Byte 0: header (key length + value length encoded in 6 bits)
Bytes 1-6: key data
Bytes 7-13: value data
Slab Mode (bit 7 = 1): For larger entries, the slot stores a pointer into a separate arena allocator (SlabPool), plus a 39-bit extended fingerprint. Before chasing the pointer to compare the full key, PulseMap checks this fingerprint — if it doesn't match, the heap access is skipped entirely.
Byte 0: header + 7-bit extended fingerprint (high)
Bytes 1-4: 32-bit extended fingerprint (low)
Byte 5: flags
Bytes 6-13: slab index (u64)
The Hash: One Hash, Four Uses
PulseMap hashes each key once with WyHash and extracts four values from the 64-bit result:
h1: full 64-bit hash → bucket index (masked to table size)
h2: bits 57-63 → 7-bit fingerprint (stored in MetaWord)
ext_fp_hi: bits 50-56 → 7-bit extended fingerprint (slab mode)
ext_fp: bits 18-49 → 32-bit extended fingerprint (slab mode)
The bit ranges are chosen so that none of them overlap with each other, and h2 (from the top bits) is independent of the bucket index (from the bottom bits after masking). This prevents a subtle bug where keys in the same bucket would tend to share the same fingerprint, defeating the purpose of the H2 filter.
Three Concurrency Levels
PulseMap offers three tiers, depending on how much concurrency you need.
PulseMapRaw — Single-threaded only. Implements Send (can be moved between threads) but NOT Sync (cannot be shared via &reference). Earlier versions incorrectly implemented Sync, which was a soundness bug fixed in v0.6.2.
ConcurrentPulseMap — Uses a global RwLock (for resize) plus one AtomicU8 spinlock per bucket. Normal reads and writes only take the RwLock in shared mode, so they run in parallel. The spinlock only serializes access to the same bucket.
ShardedPulseMap — 16 independent ConcurrentPulseMaps. Each key is routed to a shard using bits 14-17 of the hash (chosen to avoid overlap with both the bucket index and the H2 fingerprint). Threads accessing keys in different shards never contend. Resize happens one shard at a time — the other 15 continue serving requests.
AccessBuffer: Why Reads Don't Need Locks
In v0.6.2, I introduced a lock-free lossy ring buffer called AccessBuffer. The problem it solves: on a cache hit, get() needs to update the MetaWord priority bits. Before AccessBuffer, this required holding the per-bucket spinlock during reads.
Now, get() pushes a small access event (bucket index + slot index, packed into 4 bytes) into the ring buffer instead. The priority updates are applied later, piggybacked on the next insert() operation. No background thread needed.
The buffer is intentionally lossy — if it fills up, new events are silently dropped. This is fine because eviction priorities are approximations. Missing a few access events slightly delays how quickly an entry's priority increases, but does not cause incorrect eviction. Under heavy load (when the buffer fills), eviction accuracy matters less than read latency anyway.
TTL: Count-Based, Not Clock-Based
PulseMap's TTL system uses an insertion counter, not wall-clock time. Every insert() increments a monotonic epoch. Each entry records its insertion epoch. On access, if (current_epoch - entry_epoch) exceeds the TTL threshold, the entry is considered expired.
This was a deliberate trade-off. Wall-clock TTL requires either periodic background sweeps (adding complexity and latency spikes) or checking system time on every access (a syscall on some platforms). Insertion-count TTL is a single integer subtraction — essentially free.
The limitation is real: if you need "expire after 30 seconds," PulseMap is not the right tool. Moka handles wall-clock TTL well.
In v0.6.2, the epoch type was widened from u32 to u64. A u32 overflows after ~4.3 billion insertions — reachable in minutes under high throughput. A u64 won't overflow in any practical scenario.
Benchmark Results (Honest Assessment)
All numbers measured on a Dell Latitude 7490 (i7-8650U, Linux). I'm including where PulseMap wins AND where it loses.
SINGLE-THREADED (100K operations):
INSERT:
PulseMap 6.1ms, quick_cache 5.6ms, lru 19.1ms, moka 161ms
LOOKUP:
quick_cache 2.8ms, PulseMap 5.4ms, lru 5.4ms, moka 40ms
EVICTION (50K inserts into a full cache):
PulseMap 1.9ms, lru 2.3ms, quick_cache 3.3ms, moka 55.5ms
PulseMap wins at eviction by a wide margin. It loses at pure lookup — quick_cache is roughly 1.9x faster because it stores native Rust values directly, while PulseMap serializes values to bytes (the trade-off for no_std and FFI support).
MULTI-THREADED WRITE PRESSURE (8 threads, 1M inserts, 15 trials):
p99 latency (mean ± stddev):
PulseMap: 911ns ± 46ns
QuickCache: 1.44µs ± 54ns
LRU (Mutex): 42.25µs ± 2.32µs
Moka: 389.57µs ± 13.53µs
The gap between PulseMap and Moka at p99 is 427x — this is not close. Moka's background eviction threads create queue backpressure under sustained write load. Against QuickCache, PulseMap is 1.6x faster — a real but modest gap. Both are in the same performance tier.
EVICTION QUALITY (hit rate under 10% capacity, Zipfian distribution):
PulseMap: 96.73%
QuickCache: 96.49%
Moka: 96.40%
LRU: 95.83%
PulseMap's LFU+LRU hybrid produced the highest hit rate. The gaps are small but consistent across all tested workloads and significantly larger than the run-to-run noise.
MEMORY (measured RSS at 1M entries):
PulseMap: 25.6 bytes/entry
QuickCache: 36.0 bytes/entry
LRU: 67.7 bytes/entry
Moka: 305.3 bytes/entry
PulseMap uses 29% less memory per entry than QuickCache and 91% less than Moka.
Where PulseMap Fits (and Where It Doesn't)
PulseMap is a good fit for:
Write-heavy caches under contention (DNS, rate limiters, session stores)
Memory-constrained environments (containers, embedded)
Workloads where p99 tail latency matters more than average throughput
Applications that need predictable, upfront memory allocation
PulseMap is NOT a good fit for:
Read-dominated, low-contention caching (QuickCache is faster here)
Wall-clock TTL requirements (Moka handles this well)
Datasets that fit entirely in memory (just use HashMap)
Async-native APIs (PulseMap is synchronous)
Try It
cargo add pulse_map
Want the deeper architecture breakdown? I've written a more detailed version covering the full design decisions on LinkedIn.
Licensed under MIT or Apache-2.0.
About the author
- Java Developer with 5+ years building scalable microservices and distributed systems using Spring Boot, Kafka & SQL. Also into Rust for performance-critical tooling — author of LineFault (concurrency static analyzer) and WireDoctor (Spring Boot diagnostics). and pulse_map(cache line) Always learning, always shipping.
Comments
Join the discussionNo comments yet. Be the first to comment.
