PulseMap

A CPU cache-line hash table with zero-cost eviction.

💡 Use PulseMap anywhere you’d use HashMap but can’t afford unbounded memory growth.

What is PulseMap?

PulseMap is a bounded, concurrent hash table where every bucket fits in exactly one 64-byte CPU cache line. Unlike HashMap which grows forever until you run out of memory, PulseMap has a fixed capacity and automatically evicts the least-useful entries when full.

Key insight: By packing metadata (state, H2 fingerprint, frequency counter, recency bits) into the same cache line as the data slots, eviction decisions cost zero additional cache misses.

Why PulseMap?

Quick Example

#![allow(unused)]
fn main() {
use pulse_map::ConcurrentPulseMap;
use std::sync::Arc;
use std::thread;

// Create a thread-safe map with auto-resize
let map = Arc::new(ConcurrentPulseMap::<String, u64>::with_auto_resize(256));

// Concurrent writes from 4 threads
let handles: Vec<_> = (0..4).map(|t| {
    let m = map.clone();
    thread::spawn(move || {
        for i in 0..1000 {
            m.insert(format!("key_{}", t * 1000 + i), i as u64);
        }
    })
}).collect();

for h in handles { h.join().unwrap(); }

// Read back
assert!(map.get(&"key_0".to_string()).is_some());
println!("Entries: {}, Evictions: {}", map.len(), map.eviction_count());
}

Features

• 🏗️ Cache-Line Architecture — 64-byte buckets with 4 slots each
• ⚡ Zero-Cost Eviction — LFU+LRU metadata embedded in bucket
• 🔒 Thread-Safe — Per-bucket spinlocks, &self API
• 🏗️ 16-Shard Concurrency — ShardedPulseMap: 2.4–3.1x faster than global lock
• ⏱️ Per-Entry TTL — Individual expiry per key, or global default
• 📏 Bounded Memory — Fixed capacity, no unbounded growth
• 🔄 Auto-Resize — Optional dynamic growth at 75% load
• 🌐 C FFI Bindings — Use from C, or build your own language bridge
• 🔧 no_std Compatible — Core data structures work without allocator

Supported Platforms

License

Dual licensed under MIT or Apache-2.0.

Copyright (c) 2026 Deendayal Kumawat.

Getting Started

Installation

Add PulseMap to your Cargo.toml:

[dependencies]
pulse_map = "0.6.1"

Or via command line:

cargo add pulse_map

Minimum Supported Rust Version

PulseMap requires Rust 1.70.0 or later.

Your First PulseMap

1. Single-Threaded — TypedPulseMap<K, V>

use pulse_map::TypedPulseMap;

fn main() {
    // 64 buckets = 256 slot capacity
    let mut map: TypedPulseMap<String, String> = TypedPulseMap::new(64);

    map.insert("name".to_string(), "Deendayal".to_string());
    map.insert("lang".to_string(), "Rust".to_string());

    assert_eq!(map.get(&"name".to_string()), Some("Deendayal".to_string()));
    assert_eq!(map.get(&"missing".to_string()), None);

    map.remove(&"lang".to_string());

    println!("Entries:   {}", map.len());
    println!("Capacity:  {}", map.capacity());
    println!("Evictions: {}", map.eviction_count());
}

2. Multi-Threaded — ConcurrentPulseMap<K, V>

Good for 1–2 threads:

use pulse_map::ConcurrentPulseMap;
use std::sync::Arc;
use std::thread;

fn main() {
    let map = Arc::new(ConcurrentPulseMap::<String, u64>::with_auto_resize(64));

    let handles: Vec<_> = (0..2).map(|t| {
        let m = map.clone();
        thread::spawn(move || {
            for i in 0..1000 {
                m.insert(format!("t{}_{}", t, i), i as u64);
            }
        })
    }).collect();

    for h in handles { h.join().unwrap(); }
    println!("Total: {}", map.len());
}

3. High-Concurrency — ShardedPulseMap<K, V> ✅ Recommended

Best for 3+ threads — 2.4–3.1x faster than ConcurrentPulseMap:

use pulse_map::ShardedPulseMap;
use std::sync::Arc;
use std::thread;

fn main() {
    // 16 shards × 256 buckets = 16,384 capacity
    let map = Arc::new(ShardedPulseMap::<u32, u64>::new(256));

    let handles: Vec<_> = (0..8).map(|t| {
        let m = map.clone();
        thread::spawn(move || {
            for i in 0..10_000u32 {
                m.insert(t * 10_000 + i, i as u64);
            }
        })
    }).collect();

    for h in handles { h.join().unwrap(); }
    println!("Entries:   {}", map.len());
    println!("Evictions: {}", map.eviction_count());
}

4. With Per-Entry TTL (v0.6.1+)

#![allow(unused)]
fn main() {
use pulse_map::ShardedPulseMap;

let map = ShardedPulseMap::<String, String>::new(256);
map.set_ttl(1000);  // global: expire after 1000 inserts

// Per-entry overrides
map.insert_ttl("session:abc".to_string(), "data".to_string(), 50);     // short-lived
map.insert_ttl("config:key".to_string(), "value".to_string(), u32::MAX); // never expire
map.insert("normal".to_string(), "val".to_string());                     // uses global 1000
}

Choosing the Right Type

Capacity Planning

actual_buckets = next_power_of_2(num_buckets)
total_capacity = actual_buckets × 4  (4 slots per bucket)

# ShardedPulseMap:
total_capacity = 16 × actual_buckets × 4

Rule of thumb: num_buckets = expected_entries / 3. The ~75% fill rate balances performance with memory.

Running Examples

git clone https://github.com/ddsha441981/pulse_map.git
cd pulse_map

cargo run --example basic
cargo run --example concurrent
cargo bench

Core Concepts

The Cache-Line Problem

Modern CPUs don’t read memory byte-by-byte. They load 64-byte cache lines at a time. A traditional hash table stores metadata (hash, state) separately from data (key, value), causing 2+ cache misses per lookup:

Traditional HashMap:
  1. Load metadata → cache miss #1
  2. Follow pointer to key → cache miss #2
  3. Follow pointer to value → cache miss #3

PulseMap solves this by packing everything into one 64-byte cache line:

PulseMap Bucket (64 bytes):
  ┌─────────────────────────────────────────────────┐
  │ MetaWord (8 bytes, AtomicU64 for lock-free reads)│
  │  ├── 4× Slot state (2 bits each)                │
  │  ├── 4× H2 fingerprint (7 bits each)            │
  │  └── 4× Priority (7 bits each: freq[4]+rec[3])  │
  ├─────────────────────────────────────────────────┤
  │ Slot 0 (14 bytes) — header(1) + payload(13)    │
  │ Slot 1 (14 bytes) — header(1) + payload(13)    │
  │ Slot 2 (14 bytes) — header(1) + payload(13)    │
  │ Slot 3 (14 bytes) — header(1) + payload(13)    │
  └─────────────────────────────────────────────────┘
  Total: 8 + (4 × 14) = 64 bytes = 1 cache line ✅

Result: One cache miss per lookup, including eviction decision.

Slot Storage Modes

Each slot has two modes, determined by the header byte’s MSB:

Inline Mode (mode=0)

For small key-value pairs (key ≤ 6 bytes, value ≤ 7 bytes):

data[0]:    header byte
              bit 7:   mode (0 = inline)
              bits 6-4: key_len (0-6)
              bits 3-1: val_len (0-7)
              bit 0:   reserved
data[1..7]:  key bytes (up to 6)
data[7..14]: value bytes (up to 7)

Zero-allocation. Everything lives inside the 14-byte data array.

Slab Mode (mode=1)

For large key-value pairs (key > 6 bytes OR value > 7 bytes):

data[0]:     header byte
               bit 7:   mode (1 = slab)
               bits 6-0: ext_fp_hi (7-bit extended fingerprint)
data[1..5]:  ext_fp (32-bit extended fingerprint, LE)
data[5]:     flags (reserved)
data[6..14]: slab_idx (u64 index into SlabPool, LE)

The actual key+value data is stored in the SlabPool arena allocator.

Hash Function

PulseMap uses WyHash (one of the fastest non-cryptographic hash functions):

Input: key bytes
  │
  ▼
WyHash64(key) → 64-bit hash
  │
  ├── H1 (upper 32 bits) → bucket index
  ├── H2 (7 bits) → fingerprint for fast rejection
  ├── ext_fp_hi (7 bits) → extended fingerprint (slab mode)
  └── ext_fp (32 bits) → full extended fingerprint (slab mode)

H2 matching provides a fast first-pass filter: 99.2% of non-matching slots are rejected without examining the actual key.

Eviction: LFU + LRU Hybrid

When all 4 slots in a bucket are full and a new entry must be inserted, PulseMap evicts the least-useful entry. The eviction decision uses embedded metadata:

LFU Counter (4 bits per slot)

Tracks access frequency (0-15). Incremented on every get() or insert() hit. Saturates at 15.

LRU Recency (3 bits per slot)

Tracks relative recency among the 4 slots. Set to max (7) on access, other slots decay by 1.

Eviction Score

score = lfu_count + (recency × 2)
evict = slot with minimum score

Zero additional cache misses — all metadata is in the same 8-byte MetaWord already loaded for the H2 check.

Memory Layout

ConcurrentPulseMap
  ├── RwLock<MapInner>
  │     ├── Vec<UnsafeCell<Bucket>>   ← 64 bytes each, cache-aligned
  │     ├── BucketLocks               ← 1 AtomicU8 per bucket
  │     ├── Mutex<SlabPool>           ← arena for large KV pairs
  │     ├── Mutex<Vec<SlotTTL>>       ← per-entry TTL metadata (v0.6.1+) (epoch: u64, ttl: u64)
  │     ├── access_buffer: AccessBuffer
  │     ├── current_epoch: AtomicU64
  │     ├── default_ttl: AtomicU64
  │     ├── num_buckets: usize
  │     └── bucket_mask: usize       ← num_buckets - 1 (power of 2)
  ├── count: AtomicUsize             ← number of entries
  ├── eviction_count: AtomicUsize    ← total evictions
  ├── auto_resize: bool
  └── resize_threshold: f64          ← default 0.75

ShardedPulseMap (v0.6.1+)
  └── shards: [ConcurrentPulseMap; 16]
        ├── Shard 0:  independent RwLock + buckets + slab
        ├── Shard 1:  independent RwLock + buckets + slab
        ├── ...
        └── Shard 15: independent RwLock + buckets + slab
      Shard = h1 & 0xF (low-bits routing)

API Reference

PulseMap provides four map types. Choose based on your concurrency requirements:

Type Aliases

#![allow(unused)]
fn main() {
/// Raw byte-level map — maximum control
pub type PulseMap = PulseMapRaw;
}

Traits

PulseKey

#![allow(unused)]
fn main() {
pub trait PulseKey: Clone + PartialEq {
    type Bytes: AsRef<[u8]>;
    fn to_bytes(&self) -> Self::Bytes;
    fn from_bytes(bytes: &[u8]) -> Option<Self>;
}
}

Implemented for: String, Vec<u8>, u8, u16, u32, u64, u128, i8, i16, i32, i64, i128

PulseValue

#![allow(unused)]
fn main() {
pub trait PulseValue: Clone {
    type Bytes: AsRef<[u8]>;
    fn to_bytes(&self) -> Self::Bytes;
    fn from_bytes(bytes: &[u8]) -> Option<Self>;
}
}

Implemented for: Same types as PulseKey.

Common Methods (all map types)

See sub-pages for type-specific APIs and examples.

PulseMapRaw (Raw Byte API)

The lowest-level API. Works directly with &[u8] byte slices.

#![allow(unused)]
fn main() {
pub type PulseMap = PulseMapRaw;
}

Construction

#![allow(unused)]
fn main() {
use pulse_map::PulseMap;

// Fixed-size (256 slots)
let map = PulseMap::new(64);

// With auto-resize at 75% load
let map = PulseMap::with_auto_resize(64);
}

Operations

#![allow(unused)]
fn main() {
// Insert raw bytes
map.insert(b"hello", b"world");

// Lookup — returns Option<&[u8]>
if let Some(value) = map.get(b"hello") {
    println!("Found: {} bytes", value.len());
}

// Remove
let removed: bool = map.remove(b"hello");

// Contains
let exists: bool = map.contains_key(b"hello");
}

Stats

#![allow(unused)]
fn main() {
println!("Entries:   {}", map.len());
println!("Capacity:  {}", map.capacity());
println!("Load:      {:.1}%", map.load_factor() * 100.0);
println!("Evictions: {}", map.eviction_count());
}

TTL (v0.6.0+)

#![allow(unused)]
fn main() {
// Set global TTL: entries expire after 500 insertions
map.set_ttl(500);

// Query state
println!("TTL setting: {}", map.get_ttl());       // 500
println!("Epoch:       {}", map.current_epoch()); // total inserts

// Disable TTL
map.set_ttl(0);
}

Per-Entry TTL (v0.6.1+)

#![allow(unused)]
fn main() {
// Per-entry override
map.insert_ttl(b"session", b"data", 50);      // expires after 50 inserts
map.insert_ttl(b"config", b"val", u64::MAX);  // never expires
map.insert(b"normal", b"val");                 // uses global TTL
}

See the TTL page for full details.

When to Use PulseMapRaw

• You already have byte-serialized keys/values
• Maximum performance (no serialization overhead)
• Building custom protocols over raw bytes
• Interfacing with C FFI bindings

Thread Safety: PulseMapRaw is Send but NOT Sync (fixed in v0.6.2). It cannot be shared across threads via &PulseMapRaw.

TypedPulseMap<K, V>

Type-safe single-threaded map. Works with any type implementing PulseKey and PulseValue.

Construction

#![allow(unused)]
fn main() {
use pulse_map::TypedPulseMap;

// String → String cache
let mut cache: TypedPulseMap<String, String> = TypedPulseMap::new(256);

// u64 → u64 counter store
let mut counters: TypedPulseMap<u64, u64> = TypedPulseMap::new(1024);

// With auto-resize
let mut cache: TypedPulseMap<String, Vec<u8>> = TypedPulseMap::with_auto_resize(64);
}

CRUD Operations

#![allow(unused)]
fn main() {
// Insert (uses global TTL)
cache.insert("session_abc".to_string(), "user_data_json".to_string());

// Insert with per-entry TTL (v0.6.1+)
cache.insert_ttl("session_abc".to_string(), "user_data".to_string(), 200);
cache.insert_ttl("config".to_string(), "val".to_string(), u32::MAX);  // never expire

// Get — returns owned Option<V>
let val: Option<String> = cache.get(&"session_abc".to_string());

// Peek — like get() but doesn't update eviction priority
let val: Option<String> = cache.peek(&"session_abc".to_string());

// Contains
let exists: bool = cache.contains_key(&"session_abc".to_string());

// Remove
let removed: bool = cache.remove(&"session_abc".to_string());
}

Numeric Keys

#![allow(unused)]
fn main() {
let mut map: TypedPulseMap<u32, u64> = TypedPulseMap::new(256);

map.insert(42, 100);
map.insert(1337, 9001);

assert_eq!(map.get(&42), Some(100));
}

Stats

#![allow(unused)]
fn main() {
println!("Entries:     {}", cache.len());
println!("Empty:       {}", cache.is_empty());
println!("Capacity:    {}", cache.capacity());
println!("Load Factor: {:.1}%", cache.load_factor() * 100.0);
println!("Evictions:   {}", cache.eviction_count());
println!("Buckets:     {}", cache.num_buckets());
}

Performance Tips

1. Use small keys (≤ 6 bytes) when possible — they stay inline (no heap allocation)
2. Use small values (≤ 7 bytes) when possible — same reason
3. Pre-size correctly — avoid auto-resize overhead for known workloads
4. Use peek() for read-heavy paths where you don’t want to affect eviction priority

ConcurrentPulseMap

Thread-safe map for production concurrent workloads. All methods take &self — no Mutex wrapping needed.

Construction

#![allow(unused)]
fn main() {
use pulse_map::ConcurrentPulseMap;
use std::sync::Arc;

// Fixed-size
let map = Arc::new(ConcurrentPulseMap::<String, String>::new(1024));

// Auto-resize (doubles at 75% load)
let map = Arc::new(ConcurrentPulseMap::<String, u64>::with_auto_resize(256));
}

Thread-Safe Operations

All methods take &self — safe to call from multiple threads simultaneously:

#![allow(unused)]
fn main() {
use std::thread;

let map = Arc::new(ConcurrentPulseMap::<u32, u32>::with_auto_resize(64));

// Spawn writers
let handles: Vec<_> = (0..8).map(|t| {
    let m = map.clone();
    thread::spawn(move || {
        for i in 0..10_000 {
            m.insert(t * 10_000 + i, i);
        }
    })
}).collect();

for h in handles { h.join().unwrap(); }

// Read from any thread — no lock needed
println!("Entries: {}", map.len());
}

API

#![allow(unused)]
fn main() {
// Insert (thread-safe, no &mut needed)
map.insert("key".to_string(), "value".to_string());

// Insert with per-entry TTL (v0.6.1+)
map.insert_ttl("key".to_string(), "value".to_string(), 100u64);  // expires after 100 inserts
map.insert_ttl("key".to_string(), "value".to_string(), u64::MAX);  // never expires

// Get (updates eviction priority atomically)
let val: Option<String> = map.get(&"key".to_string());

// Peek (no priority update — pure read)
let val: Option<String> = map.peek(&"key".to_string());

// Remove
let existed: bool = map.remove(&"key".to_string());

// Contains
let exists: bool = map.contains_key(&"key".to_string());
}

Tip: For 3+ threads, use ShardedPulseMap — 2.4–3.1x faster under contention.

Manual Resize

#![allow(unused)]
fn main() {
// Force resize to 2048 buckets (8192 capacity)
map.resize(2048);
}

⚠️ Resize is stop-the-world — acquires exclusive write lock, blocking all operations until rehashing completes. This is brief (~1ms for 10K entries) but causes a latency spike.

Stats (Lock-Free)

#![allow(unused)]
fn main() {
map.len()             // AtomicUsize — no lock
map.capacity()        // Acquires read lock (cheap)
map.load_factor()     // Derived from len/capacity
map.eviction_count()  // AtomicUsize — no lock
map.num_buckets()     // Acquires read lock
}

Locking Model

Read operations (get, peek, contains, stats):
  └── RwLock::read() + AtomicU64 MetaWord read (deferred LRU/LFU via AccessBuffer)

Write operations (insert, remove):
  └── RwLock::read() + per-bucket spinlock

Resize:
  └── RwLock::write() (exclusive — blocks everything)

Key insight: Normal reads and writes only acquire a read lock on the RwLock, so they run concurrently. The per-bucket spinlock serializes access to the same bucket only. Reads use an AtomicU64 MetaWord and AccessBuffer for deferred LRU/LFU updates, completely avoiding locks on read paths.

Production Pattern

#![allow(unused)]
fn main() {
use pulse_map::ConcurrentPulseMap;
use std::sync::Arc;

// Shared application cache
struct AppState {
    cache: ConcurrentPulseMap<String, String>,
}

impl AppState {
    fn new() -> Self {
        Self {
            cache: ConcurrentPulseMap::with_auto_resize(4096),
        }
    }
}

// Use from any handler — no mutex needed
fn handle_request(state: &AppState, key: &str) -> Option<String> {
    state.cache.get(&key.to_string())
}
}

ShardedPulseMap

Added in v0.6.1

A 16-shard concurrent map built on top of ConcurrentPulseMap. Each shard is a fully independent ConcurrentPulseMap — near-zero cross-thread contention.

Why Sharded?

ConcurrentPulseMap uses a single RwLock + per-bucket spinlocks. Under high thread counts, the RwLock becomes a bottleneck. ShardedPulseMap eliminates this by splitting data across 16 shards — each with its own RwLock.

Result: 2.4–3.1x faster than ConcurrentPulseMap on 4-thread workloads.

Construction

#![allow(unused)]
fn main() {
use pulse_map::ShardedPulseMap;
use std::sync::Arc;

// 16 shards × 4096 buckets each = 262,144 total capacity
let map = Arc::new(ShardedPulseMap::<u32, u32>::new(4096));

// Auto-resize: each shard auto-grows at 75% load
let map = Arc::new(ShardedPulseMap::<String, String>::with_auto_resize(256));
}

Thread-Safe Operations

Same API as ConcurrentPulseMap — all methods take &self:

#![allow(unused)]
fn main() {
use std::thread;

let map = Arc::new(ShardedPulseMap::<u32, u32>::new(4096));

// 8 threads inserting concurrently
let handles: Vec<_> = (0..8).map(|t| {
    let m = map.clone();
    thread::spawn(move || {
        for i in 0..10_000 {
            m.insert(t * 10_000 + i, i);
        }
    })
}).collect();
for h in handles { h.join().unwrap(); }

println!("Total entries: {}", map.len());
}

API

#![allow(unused)]
fn main() {
// CRUD — routed to shard by key hash
map.insert(key, value);
map.insert_ttl(key, value, ttl);  // per-entry TTL (v0.6.1+)
map.get(&key);                     // Option<V>
map.peek(&key);                    // no priority update
map.remove(&key);                  // bool
map.contains_key(&key);            // bool

// TTL — applied to all shards
map.set_ttl(500u64);
map.get_ttl();                     // → 500u64
map.current_epoch();               // max across shards (u64)

// Stats — aggregated across all shards
map.len();
map.capacity();
map.load_factor();
map.eviction_count();

// Resize — per-shard, no stop-the-world
map.resize_all(new_buckets_per_shard);
}

Shard Selection

Shards are selected using the low 4 bits of the wyhash:

shard_index = h1 & 15    // bits [3:0] → 0..15
bucket_index = (h1 >> 4) & mask  // upper bits → bucket within shard

This ensures shard selection is independent from bucket selection — no correlation, no hot-spotting.

resize_all() — No Stop-the-World

Unlike ConcurrentPulseMap::resize() which blocks ALL operations, resize_all() rehashes one shard at a time. Other shards remain fully operational during the resize.

#![allow(unused)]
fn main() {
// Only shard N is blocked while being rehashed
// Shards 0..N-1 and N+1..15 continue serving requests
map.resize_all(8192);
}

When to Use

Performance

Entry API

The Entry API provides in-place access for complex insert-or-update patterns.

Usage

#![allow(unused)]
fn main() {
use pulse_map::TypedPulseMap;

let mut map: TypedPulseMap<String, u64> = TypedPulseMap::new(256);

// Insert-or-update pattern
map.insert("counter".to_string(), 0);

// Update existing value
if let Some(old) = map.get(&"counter".to_string()) {
    map.insert("counter".to_string(), old + 1);
}
}

Insert-or-Default

#![allow(unused)]
fn main() {
// If key doesn't exist, insert default
let key = "visits".to_string();
if !map.contains_key(&key) {
    map.insert(key.clone(), 0);
}

// Now safely increment
if let Some(count) = map.get(&key) {
    map.insert(key, count + 1);
}
}

Atomic Upsert Pattern (Concurrent)

#![allow(unused)]
fn main() {
use pulse_map::ConcurrentPulseMap;

let map = ConcurrentPulseMap::<String, u64>::new(256);

// Thread-safe upsert — insert always succeeds
// If key exists, value is overwritten (last-writer-wins)
map.insert("key".to_string(), 42);
map.insert("key".to_string(), 99);  // overwrites

assert_eq!(map.get(&"key".to_string()), Some(99));
}

Note: PulseMap’s insert() is an upsert — it inserts if the key is new, or updates if the key exists. There is no separate update() method.

Eviction Strategy

PulseMap uses a hybrid LFU+LRU eviction policy that requires zero additional cache misses — all eviction metadata is embedded in the 8-byte MetaWord of each bucket.

How Eviction Works

When all 4 slots in a bucket are full and a new entry hashes to that bucket:

1. Calculate eviction score for each slot
2. Evict the slot with the lowest score
3. Insert the new entry in the freed slot

Eviction Score Formula

score(slot) = lfu_count(slot) + recency(slot) × 2

• LFU count (4 bits, range 0-15): How many times this entry was accessed
• Recency (3 bits, range 0-7): How recently this entry was accessed relative to siblings

The slot with the minimum score is evicted.

MetaWord Layout (8 bytes)

The MetaWord is implemented as an AtomicU64, supporting lock-free atomic loads and CAS operations.

Bit Layout (64 bits):
┌──────────────────────────────────────────────────────────────┐
│ Slot 3          │ Slot 2          │ Slot 1          │ Slot 0 │
├─────────────────┼─────────────────┼─────────────────┼────────┤
│ st│h2   │freq│rec│ st│h2   │freq│rec│ st│h2   │freq│rec│st│h2..│
│ 2b│7b   │4b  │3b │ 2b│7b   │4b  │3b │ 2b│7b   │4b  │3b │2b│7b. │
└──────────────────────────────────────────────────────────────┘

st  = Slot State (2 bits): Empty(0), Full(1), Tombstone(2)
h2   = H2 Fingerprint (7 bits): Fast hash match filter
freq = Frequency Counter (4 bits): Access count (0-15)
rec  = LRU Recency (3 bits): Relative age (0=oldest, 7=newest)

Eviction Behavior

Frequency Dominates

Frequently accessed entries survive eviction even if they haven’t been accessed recently:

Slot 0: freq=15, recency=0 → score = 15 + 0 = 15  (survives!)
Slot 1: freq=1,  recency=7 → score = 1 + 14 = 15  (tied)
Slot 2: freq=0,  recency=1 → score = 0 + 2 = 2    (EVICTED)
Slot 3: freq=5,  recency=4 → score = 5 + 8 = 13   (survives!)

Cold Start

New entries start with freq=0, recency=7 (newest). They must earn frequency to survive.

Frequency Saturation

LFU counter saturates at 15 (4 bits). This prevents long-lived entries from becoming permanently sticky — a recently-inserted entry with moderate access can still compete.

AccessBuffer Deferred Tracking

PulseMap uses a lock-free lossy ring buffer (AccessBuffer) to track accesses during get() operations. This allows read-heavy workloads to record access frequency (LFU) and recency (LRU) without acquiring bucket spinlocks, significantly reducing lock contention. The deferred accesses are later applied to the AtomicU64 MetaWord via CAS.

Eviction Statistics

#![allow(unused)]
fn main() {
let map = ConcurrentPulseMap::<String, String>::new(64);

// Fill beyond capacity
for i in 0..1000 {
    map.insert(format!("key_{}", i), format!("val_{}", i));
}

println!("Evictions: {}", map.eviction_count());
// Will show evictions once capacity (256) is exceeded
}

Comparison with Other Policies

PulseMap achieves near-LFU hit rates with FIFO-level overhead.

Tuning

PulseMap’s eviction is not configurable by design. The 4-bit LFU + 3-bit LRU hybrid was chosen after extensive benchmarking as the optimal tradeoff for 4-slot buckets.

If you need different eviction behavior:

• More capacity instead of better eviction → Use auto-resize: with_auto_resize(n)
• No eviction at all → Use auto-resize with large initial size
• TTL-based expiration → Use set_ttl(n) (global) or insert_ttl(k, v, n) (per-entry)
• Permanent entries → Use insert_ttl(key, val, u64::MAX) — never expire

TTL — Automatic Expiry

Global TTL added in v0.6.0 · Per-entry TTL added in v0.6.1 · Migrated to u64 in v0.6.2

PulseMap supports insertion-epoch TTL — entries automatically expire after a fixed number of insertions. No background thread, no timer, zero overhead when disabled.

How It Works

Every insert bumps a monotonic current_epoch: u64 counter. Each slot stores the epoch at which its entry was inserted. On every get() or peek():

age = current_epoch - slot_epoch
if age > effective_ttl → entry is expired → return None

This is a single wrapping subtraction + comparison — effectively free on modern CPUs.

Quick Start — Global TTL

#![allow(unused)]
fn main() {
use pulse_map::PulseMap;

let mut cache = PulseMap::new(1024);

// Set TTL: entries expire after 500 insertions
cache.set_ttl(500);

cache.insert(b"session:abc", b"user_data");  // epoch 1

// High-traffic server: 500 more inserts
for i in 0u64..501 {
    cache.insert(&i.to_le_bytes(), b"traffic");
}

// session:abc was inserted at epoch 1
// current_epoch is now 502, age = 501 > ttl = 500
assert_eq!(cache.get(b"session:abc"), None);  // expired ✓
}

Per-Entry TTL (v0.6.1+)

Individual entries can have their own TTL, overriding the global default:

#![allow(unused)]
fn main() {
use pulse_map::PulseMap;

let mut cache = PulseMap::new(1024);
cache.set_ttl(500); // global default

// Per-entry overrides
cache.insert_ttl(b"session", b"data", 50);      // expires after 50 inserts
cache.insert_ttl(b"config", b"val", u64::MAX);  // never expires
cache.insert(b"normal", b"val");                 // uses global TTL = 500
}

TTL Parameter Semantics

Available On All Map Types

#![allow(unused)]
fn main() {
// PulseMap (raw bytes)
map.insert_ttl(b"key", b"val", 100);

// TypedPulseMap<K, V>
map.insert_ttl(42u32, 100u64, 50);

// ConcurrentPulseMap<K, V> (thread-safe)
map.insert_ttl(42u32, 100u64, 50);

// ShardedPulseMap<K, V> (16-shard)
map.insert_ttl(42u32, 100u64, 50);
}

Per-Entry Overrides Global

#![allow(unused)]
fn main() {
let mut map = PulseMap::new(64);
map.set_ttl(100); // global: 100 inserts

// Per-entry TTL = 2 (overrides global 100)
map.insert_ttl(b"short", b"val", 2);

// After 3 more inserts → short expired (age 3 > ttl 2)
// Even though global TTL is 100
}

API

PulseMap (raw &[u8])

#![allow(unused)]
fn main() {
map.set_ttl(n: u64)              // global TTL (0 = disabled)
map.get_ttl() -> u64             // current global TTL
map.current_epoch() -> u64       // total insertions
map.insert(key, value)           // uses global TTL
map.insert_ttl(key, value, ttl)  // per-entry TTL override
}

TypedPulseMap<K, V>

#![allow(unused)]
fn main() {
map.set_ttl(500u64);
map.insert_ttl(key, value, 50);  // per-entry TTL
map.get_ttl()                    // → 500
map.current_epoch()              // → total inserts
}

TTL = 0 → Disabled (Default)

By default, default_ttl = 0. The expiry check returns false immediately when both global and per-entry TTL are 0 — zero overhead.

Backward compatible — existing code works without any changes.

Update Refreshes Epoch

Re-inserting the same key resets its epoch and TTL:

#![allow(unused)]
fn main() {
cache.set_ttl(3);

cache.insert_ttl(b"key", b"v1", 3);  // epoch 1, TTL=3
cache.insert(b"a", b"x");             // epoch 2
cache.insert(b"b", b"y");             // epoch 3

// Re-insert refreshes both epoch AND TTL
cache.insert_ttl(b"key", b"v2", 3);  // epoch 4, TTL=3 (refreshed!)

cache.insert(b"c", b"z");             // epoch 5 → key age = 1 (alive)
assert_eq!(cache.get(b"key"), Some(&b"v2"[..]));
}

This is useful for session stores — each access or heartbeat refreshes the TTL.

Lazy Eviction

Expired slots are not eagerly removed. They are reclaimed lazily:

1. get() / peek() — returns None for expired entries (no cleanup)
2. insert() — when searching for a free slot, expired slots are treated as available

This means no background thread, no periodic scan, no latency spikes.

Choosing a TTL Value

TTL is measured in insertions, not wall-clock time. To convert:

ttl_epochs = expected_inserts_per_second × desired_ttl_seconds

Example:
  Server: 10,000 inserts/sec
  Desired TTL: 60 seconds
  → set_ttl(600_000)

This makes TTL workload-proportional — a busier server expires entries faster.

Comparison with Redis TTL

PulseMap TTL is ideal for in-process hot caches. Use Redis when you need cross-process TTL or millisecond precision.

Implementation Details

#![allow(unused)]
fn main() {
// PulseMapRaw fields (raw.rs) — v0.6.1
#[derive(Clone, Copy, Default)]
pub(crate) struct SlotTTL {
    epoch: u64,  // insertion epoch
    ttl: u64,    // 0 = use default, u64::MAX = never
}

slots_ttl: Vec<SlotTTL>,  // one per slot
current_epoch: u64,        // global counter
default_ttl: u64,          // set via set_ttl()

// On every insert:
self.current_epoch = self.current_epoch.wrapping_add(1);
self.slots_ttl[idx] = SlotTTL { epoch: self.current_epoch, ttl };

// On get():
fn is_expired(&self, bucket_idx: usize, slot_idx: u8) -> bool {
    let entry = self.slots_ttl[bucket_idx * 4 + slot_idx as usize];
    let effective_ttl = if entry.ttl == 0 { self.default_ttl } else { entry.ttl };
    if effective_ttl == 0 || effective_ttl == u64::MAX { return false; }
    self.current_epoch.wrapping_sub(entry.epoch) > effective_ttl
}
}

Memory overhead: num_buckets × 4 × 16 bytes (one SlotTTL per slot). For 1024 buckets: 1024 × 4 × 16 = 64 KB — negligible.

Concurrency Model

PulseMap offers two concurrent map implementations:

• ConcurrentPulseMap — single map with per-bucket spinlocks (good for 1–2 threads)
• ShardedPulseMap — 16 independent shards (optimal for 3+ threads, 2.4–3.1x faster)

Lock Architecture

Level 1: RwLock (global)
  ├── Read lock: normal operations (get, insert, remove)
  └── Write lock: resize only (rare, stop-the-world)

Level 2: Per-Bucket Spinlock (AtomicU8)
  └── One lock per bucket — only contention is same-bucket access

Why This Works

• Lock-free reads: MetaWord uses AtomicU64 for lock-free reads, and get() pushes to a deferred AccessBuffer without acquiring exclusive bucket spinlocks for metadata updates.
• Different buckets = zero contention. Two threads accessing different buckets for writes run fully in parallel.
• Same bucket = brief spinlock. Bucket write operations are ~10ns, so spin wait is negligible.
• RwLock read = cheap. Multiple threads hold read locks simultaneously.
• Resize = rare. Only triggered at 75% load with auto-resize enabled.

Spinlock Implementation

#![allow(unused)]
fn main() {
struct BucketLocks {
    locks: Vec<AtomicU8>,  // 1 byte per bucket
}

fn lock(&self, idx: usize) {
    while self.locks[idx]
        .compare_exchange_weak(0, 1, Acquire, Relaxed)
        .is_err()
    {
        std::hint::spin_loop();  // CPU hint: we're spinning
    }
}

fn unlock(&self, idx: usize) {
    self.locks[idx].store(0, Release);
}
}

RAII guard ensures unlock on all exit paths (including panics):

#![allow(unused)]
fn main() {
struct BucketGuard<'a> {
    locks: &'a BucketLocks,
    idx: usize,
}

impl Drop for BucketGuard<'_> {
    fn drop(&mut self) {
        self.locks.unlock(self.idx);
    }
}
}

&self API

All CRUD methods take &self, not &mut self:

#![allow(unused)]
fn main() {
// No Mutex needed — just Arc!
let map = Arc::new(ConcurrentPulseMap::<String, String>::new(1024));

// All these are &self calls:
map.insert("key".to_string(), "value".to_string());
map.get(&"key".to_string());
map.remove(&"key".to_string());
map.contains_key(&"key".to_string());
map.len();
}

This is possible because internal mutation is protected by the per-bucket spinlocks + UnsafeCell.

Resize Semantics

Resize uses a stop-the-world approach:

1. Acquire RwLock::write() — blocks ALL operations
2. Allocate new bucket array (2× size)
3. Rehash all entries from old → new buckets
4. Swap in new state
5. Release write lock — operations resume

Duration: ~1ms for 10K entries, ~10ms for 100K entries.

When it happens:

• Auto-resize: when load_factor > 0.75 during insert()
• Manual: when you call map.resize(new_num_buckets)

Thread Safety Guarantees

Note on UB Fix: PulseMapRaw is Send but NOT Sync. The concurrent wrappers handle all the necessary synchronization to safely share the map.

Memory Ordering

• Acquire on lock acquisition (load-after-lock sees latest writes)
• Release on lock release (store-before-unlock is visible to next acquirer)
• Relaxed for count and eviction_count (eventual consistency is fine for stats)

Best Practices

1. Use ShardedPulseMap for 3+ threads — 2.4–3.1x faster than ConcurrentPulseMap
2. Use Arc<ShardedPulseMap> or Arc<ConcurrentPulseMap> — never Mutex<PulseMap>
3. Pre-size for known workloads — avoids resize pauses
4. Use peek() for read-heavy paths — avoids spinlock on eviction metadata update
5. Monitor eviction_count() — high eviction = undersized map

ShardedPulseMap (v0.6.1+)

For high-concurrency workloads, ShardedPulseMap splits data across 16 independent shards:

ShardedPulseMap:
  ├── Shard 0:  ConcurrentPulseMap (own RwLock + spinlocks)
  ├── Shard 1:  ConcurrentPulseMap (own RwLock + spinlocks)
  ├── ...
  └── Shard 15: ConcurrentPulseMap (own RwLock + spinlocks)

Shard selection: h1 & 0xF (low-bits routing)

Result: Threads accessing different shards have zero lock contention.

#![allow(unused)]
fn main() {
use pulse_map::ShardedPulseMap;
use std::sync::Arc;

let map = Arc::new(ShardedPulseMap::<u32, u32>::new(4096));
// Same API as ConcurrentPulseMap — just faster under contention
}

resize_all() — Per-Shard Rehash

Unlike ConcurrentPulseMap’s stop-the-world resize, resize_all() rehashes one shard at a time. Other shards remain fully operational.

See ShardedPulseMap API for full details.

Architecture & Internals

Layer Architecture

Layer 5: sharded.rs     → ShardedPulseMap (16 × ConcurrentPulseMap, shard-per-key)
Layer 4: sync.rs        → ConcurrentPulseMap (thread-safe wrapper)
Layer 3: lib.rs         → TypedPulseMap<K,V>, PulseMap (user API)
Layer 2: raw.rs         → PulseMapRaw (hash table logic, per-entry TTL)
Layer 1: engine/        → Building blocks
           ├── meta.rs  → MetaWord (8-byte AtomicU64 eviction metadata)
           ├── access_buffer.rs → AccessBuffer (lock-free lossy ring buffer for deferred LRU/LFU)
           ├── slot.rs  → Slot (14-byte inline/slab storage)
           ├── bucket.rs→ Bucket (64-byte cache line unit)
           ├── hash.rs  → WyHash + HashResult decomposition
           └── slab.rs  → SlabPool arena allocator

File Map

Data Flow: Insert

insert("hello", "world")
  │
  ├── 1. Serialize: key.to_bytes() → [104,101,108,108,111]
  ├── 2. Hash: WyHash64 → {h1, h2, ext_fp_hi, ext_fp}
  ├── 3. Bucket: idx = h1 & bucket_mask
  ├── 4. Lock: spinlock[idx].acquire()
  ├── 5. Match: meta.match_mask(h2) → bitmask of matching slots
  │     ├── Hit? → Update value in-place, on_access()
  │     └── Miss? → Continue to step 6
  ├── 6. Find slot:
  │     ├── Free slot? → Use it
  │     └── All full? → Evict lowest-score slot
  ├── 7. Store:
  │     ├── key≤6B && val≤7B → Inline mode
  │     └── Otherwise → Slab mode (arena alloc)
  ├── 8. Update meta: state=Full, h2, on_insert()
  └── 9. Unlock: spinlock[idx].release()

Data Flow: Get

get("hello")
  │
  ├── 1. Serialize + Hash → {h1, h2}
  ├── 2. Bucket: idx = h1 & bucket_mask
  ├── 3. Lock: spinlock[idx].acquire()
  ├── 4. H2 filter: meta.match_mask(h2) → bitmask
  │     (rejects ~99.2% of non-matches without key comparison)
  ├── 5. For each matching slot:
  │     ├── Compare full key bytes
  │     ├── Match? → Push to AccessBuffer, return value
  │     └── No match? → Continue
  ├── 6. No match found → return None
  └── 7. Unlock: spinlock[idx].release()

Bucket Alignment

#![allow(unused)]
fn main() {
#[repr(C, align(64))]  // Force 64-byte alignment
pub struct Bucket {
    pub meta: MetaWord,    // 8 bytes
    pub slots: [Slot; 4],  // 4 × 14 = 56 bytes
}                          // Total: 64 bytes = 1 cache line

// Compile-time assertion
const _: () = assert!(std::mem::size_of::<Bucket>() == 64);
}

SlabPool Arena

For entries too large for inline storage (key > 6B or value > 7B):

SlabPool {
    entries: Vec<Box<SlabEntry>>
}

SlabEntry {
    key_len: u32,
    val_len: u32,
    data: *const u8,   // → heap allocation [key_bytes | value_bytes]
    layout: Layout,
}

Design trade-off: Individual slab entries are managed via a free-list reuse allocator. This is optimal for cache workloads where memory can be efficiently reused before the pool is periodically reset via resize.

Resize Strategy

Auto-resize triggers when: load_factor > 0.75

1. new_buckets = current_buckets × 2
2. Allocate new Vec<Bucket> + new SlabPool
3. For each old bucket, for each Full slot:
   a. Extract key/value bytes
   b. Rehash into new bucket array
   c. Re-allocate slab if needed
4. Swap old state → new state (atomic via RwLock)
5. Old state dropped (old SlabPool freed)

Performance & Benchmarks

Results from v0.6.2 · Criterion · Dell Latitude 7490 · i7-8650U · Linux

Single-Thread (100K ops)

Where PulseMap Wins

Eviction-heavy workloads — PulseMap’s core strength. Eviction metadata lives in the same 64-byte cache line as data slots, so eviction decisions cost zero additional cache misses.

• 1.7x faster than quick_cache on eviction
• 29x faster than moka on eviction
• 3.1x faster than lru on insert

Where PulseMap Loses

Pure lookup — PulseMap stores values as serialized bytes (enabling no_std + FFI bindings), which adds deserialization cost on read. Note: AtomicU64 lock-free reads and AccessBuffer narrowed the gap on concurrent lookups in v0.6.2.

• quick_cache lookup: 1.5x faster than PulseMap
• lru lookup: PulseMap is now faster (4.2 ms vs 5.4 ms)

Multi-Thread — 4 Threads, 100K ops

ShardedPulseMap Advantage

ShardedPulseMap uses 16 independent shards with separate locks. This eliminates the global RwLock bottleneck in ConcurrentPulseMap.

• 2.3–3.9x faster than ConcurrentPulseMap
• 6.5–12x faster than moka on concurrent workloads

vs std::HashMap (reference only)

HashMap has no eviction — it’s a different category entirely:

Memory Efficiency

Running Benchmarks

# All benchmarks
cargo bench

# Specific category
cargo bench -- insert
cargo bench -- "4t"        # 4-thread benchmarks
cargo bench -- moka        # moka comparison
cargo bench -- sharded     # ShardedPulseMap only
cargo bench -- eviction

# With SIMD (x86_64 only)
cargo bench --features simd

Cache Line Efficiency

L1 cache hit rate during lookup:

PulseMap:   ~98% (1 cache line per lookup)
HashMap:    ~60% (2-3 cache lines, pointer chasing)
BTreeMap:   ~40% (tree traversal, multiple lines)

Profiling Tips

# CPU cache analysis with perf
perf stat -e cache-misses,cache-references cargo bench

# Flamegraph
cargo install flamegraph
cargo flamegraph --bench benchmark

# Valgrind memory analysis
valgrind --tool=cachegrind target/release/examples/basic

Bottlenecks & Limits

Feature Flags

PulseMap uses Cargo feature flags to control optional functionality.

Available Features

Feature Details

std (default)

Enables:

• ConcurrentPulseMap (requires RwLock, Mutex, AtomicU8)
• ShardedPulseMap (16 shards, requires std)
• SlabPool (requires heap allocation)
• Display and Debug formatting

# With std (default) — v0.6.1
pulse_map = "0.6.1"

# Without std (no_std mode)
pulse_map = { version = "0.6.1", default-features = false }

no_std Mode

When std is disabled, only the core data structures are available:

• MetaWord — 8-byte metadata packing
• Slot — 14-byte inline/slab storage
• Bucket — 64-byte cache line unit
• PulseMapRaw — basic insert/get/remove/TTL

Use case: Embedded systems, OS kernels, WebAssembly.

simd

Enables SIMD-accelerated H2 fingerprint matching on x86_64:

pulse_map = { version = "0.6.1", features = ["simd"] }

Uses SSE2 _mm_cmpeq_epi8 to compare all 4 H2 fingerprints simultaneously:

#![allow(unused)]
fn main() {
// Without SIMD: sequential comparison
fn match_mask_scalar(h2: u8) -> u8 {
    let mut mask = 0;
    for i in 0..4 {
        if self.get_h2(i) == h2 { mask |= 1 << i; }
    }
    mask
}

// With SIMD: single instruction
fn match_mask_simd(h2: u8) -> u8 {
    let needle = _mm_set1_epi8(h2 as i8);
    let result = _mm_cmpeq_epi8(self.as_xmm(), needle);
    _mm_movemask_epi8(result) as u8 & 0x0F
}
}

Performance impact: ~15% faster lookups on x86_64 with high bucket occupancy.

Compile-Time Configuration

# Build with all features
cargo build --all-features

# Build for no_std
cargo build --no-default-features

# Build with SIMD only
cargo build --features simd

# Test specific feature combination
cargo test --no-default-features
cargo test --features simd

# Docs.rs (all features)
cargo doc --all-features --no-deps --open

FFI — C Bindings

PulseMap exposes a stable C ABI via the pulse_map_ffi crate. This is the only supported language binding — other languages should call through this C layer.

Architecture

                    ┌──────────────────────┐
                    │  pulse_map (Rust)     │ ← crates.io
                    │  ConcurrentPulseMap   │
                    └──────────┬───────────┘
                               │  Rust FFI (#[no_mangle])
                    ┌──────────┴───────────┐
                    │  pulse_map_ffi        │
                    │  libpulse_map.so/.dll │
                    └──────────┬───────────┘
                               │  C header (pulse_map.h)
                    ┌──────────┴───────────┐
                    │  C / C++ consumers    │
                    └───────────────────────┘

Build

# Build the shared library
cd pulse_map_ffi
cargo build --release

# Output:
#   target/release/libpulse_map.so      (Linux)
#   target/release/libpulse_map.dylib   (macOS)
#   target/release/pulse_map.dll        (Windows)
#   target/release/libpulse_map.a       (static)

C API

Uses an opaque handle pattern (PulseMapHandle*) — the Rust struct is never exposed directly to C.

#include "pulse_map.h"

int main(void) {
    // Create — 1024 buckets = 4096 slot capacity
    PulseMapHandle* map = pulse_map_new(1024);
    if (!map) return 1;  // allocation failed

    // Insert
    const uint8_t key[] = "session:abc";
    const uint8_t val[] = "user_data";
    pulse_map_insert(map, key, sizeof(key)-1, val, sizeof(val)-1);

    // Get
    uint8_t buf[4096];
    int32_t len = pulse_map_get(map, key, sizeof(key)-1, buf, sizeof(buf));
    if (len >= 0) {
        printf("Found: %.*s\n", len, buf);
    }

    // Remove
    int removed = pulse_map_remove(map, key, sizeof(key)-1);

    // Stats
    printf("Entries:   %zu\n", pulse_map_len(map));
    printf("Evictions: %zu\n", pulse_map_eviction_count(map));

    // Free — MUST call, no GC!
    pulse_map_free(map);
    return 0;
}

Full API Reference

// Lifecycle
PulseMapHandle* pulse_map_new(size_t num_buckets);
void            pulse_map_free(PulseMapHandle* map);

// CRUD
void    pulse_map_insert(PulseMapHandle* map,
                         const uint8_t* key, size_t key_len,
                         const uint8_t* val, size_t val_len);

int32_t pulse_map_get(PulseMapHandle* map,
                      const uint8_t* key, size_t key_len,
                      uint8_t* out_buf, size_t out_len);
// Returns: bytes written (≥0) on hit, -1 on miss, -2 if out_buf too small

int     pulse_map_remove(PulseMapHandle* map,
                         const uint8_t* key, size_t key_len);
// Returns: 1 if removed, 0 if not found

int     pulse_map_contains(PulseMapHandle* map,
                            const uint8_t* key, size_t key_len);

// Stats
size_t  pulse_map_len(const PulseMapHandle* map);
size_t  pulse_map_capacity(const PulseMapHandle* map);
size_t  pulse_map_eviction_count(const PulseMapHandle* map);

// TTL
void     pulse_map_set_ttl(PulseMapHandle* map, uint32_t ttl_epochs);
uint32_t pulse_map_get_ttl(const PulseMapHandle* map);
uint32_t pulse_map_current_epoch(const PulseMapHandle* map);

Null Safety

All functions check for null pointers before dereferencing:

// Safe — pulse_map_free() is a no-op on NULL
pulse_map_free(NULL);

// Safe — pulse_map_insert() checks map != NULL
pulse_map_insert(NULL, key, key_len, val, val_len);  // no-op

// Safe — pulse_map_get() returns -1 on NULL map
int32_t len = pulse_map_get(NULL, key, key_len, buf, sizeof(buf));  // -1

Memory Model

Critical: Always call pulse_map_free() when done. Forgetting it leaks the entire map including slab pool.

Linking

# Makefile example
CFLAGS  = -I./pulse_map_ffi/include
LDFLAGS = -L./target/release -lpulse_map -Wl,-rpath,./target/release

your_app: main.c
	$(CC) $(CFLAGS) -o $@ $< $(LDFLAGS)

Use Cases

💡 Use PulseMap anywhere you’d use HashMap but can’t afford unbounded memory growth.

DNS Cache

#![allow(unused)]
fn main() {
use pulse_map::ShardedPulseMap;

let dns_cache = ShardedPulseMap::<String, String>::new(65536);

// Hot domains stay, cold domains auto-evict
dns_cache.insert("google.com".to_string(), "142.250.80.46".to_string());

// Bounded memory — won't OOM on millions of unique queries
println!("Evictions: {}", dns_cache.eviction_count());
}

Why PulseMap: ISPs see millions of unique domains. HashMap grows forever → OOM. ShardedPulseMap keeps the hottest records in fixed memory, with 6.5–12x better throughput than moka under concurrent load.

API Rate Limiter with TTL

#![allow(unused)]
fn main() {
use pulse_map::ShardedPulseMap;
use std::sync::Arc;

let rate_limiter = Arc::new(ShardedPulseMap::<String, u64>::with_auto_resize(4096));
rate_limiter.set_ttl(100_000); // reset counts after 100K inserts

fn check_rate(limiter: &ShardedPulseMap<String, u64>, ip: &str) -> bool {
    let key = ip.to_string();
    let count = limiter.get(&key).unwrap_or(0);
    if count >= 100 {
        return false;  // rate limited
    }
    limiter.insert(key, count + 1);
    true
}
}

Why PulseMap: Per-IP counters in bounded memory. Old IPs auto-evict. Per-entry TTL lets short-burst IPs reset faster.

CDN Edge Cache

#![allow(unused)]
fn main() {
use pulse_map::ShardedPulseMap;

let edge_cache = ShardedPulseMap::<String, Vec<u8>>::new(16384);

// Serve from cache — ~5ns lookup on cache hit
if let Some(content) = edge_cache.get(&url) {
    return content;
}

// Cache miss — fetch from origin
let content = fetch_origin(&url);
edge_cache.insert(url, content);
}

Why PulseMap: Hot content stays in L1 (64-byte cache line). Cold content evicts automatically. No GC pauses — critical for sub-millisecond edge latency.

Session Store with Per-Entry TTL

#![allow(unused)]
fn main() {
use pulse_map::ShardedPulseMap;

let sessions = ShardedPulseMap::<String, String>::with_auto_resize(8192);
sessions.set_ttl(500_000); // global default: 500K inserts

// Premium users: longer TTL
sessions.insert_ttl("premium:abc".to_string(), user_json, 2_000_000);

// Regular users: global default
sessions.insert("user:xyz".to_string(), user_json);

// Admin tokens: never expire
sessions.insert_ttl("admin:root".to_string(), token, u32::MAX);
}

Why PulseMap: Per-entry TTL means different session policies without needing a separate cache per tier. No background cleanup thread needed.

Game Asset Cache

#![allow(unused)]
fn main() {
use pulse_map::ShardedPulseMap;

let texture_cache = ShardedPulseMap::<String, u64>::new(2048);

// Cache texture GPU handles — fixed VRAM budget
texture_cache.insert("hero_idle.png".to_string(), gpu_handle);

// When full, least-used textures auto-evict
println!("Evictions: {}", texture_cache.eviction_count());
}

Why PulseMap: Fixed memory = no frame drops from GC. Eviction metadata embedded in cache line = zero extra cost.

Log Deduplication

#![allow(unused)]
fn main() {
use pulse_map::ConcurrentPulseMap;

let seen_logs = ConcurrentPulseMap::<u64, u8>::new(32768);

fn should_log(seen: &ConcurrentPulseMap<u64, u8>, hash: u64) -> bool {
    if seen.contains_key(&hash) {
        return false;  // duplicate — skip
    }
    seen.insert(hash, 1);
    true
}
}

Why PulseMap: Dedup window is bounded. Old hashes auto-evict. Zero allocations during hot path.

Database Query Cache

#![allow(unused)]
fn main() {
use pulse_map::ShardedPulseMap;

let query_cache = ShardedPulseMap::<String, String>::new(4096);

fn cached_query(cache: &ShardedPulseMap<String, String>, sql: &str) -> String {
    let key = sql.to_string();
    if let Some(result) = cache.get(&key) {
        return result;  // cache hit — ~5ns
    }
    let result = execute_sql(sql);  // cache miss — ~1ms
    cache.insert(key, result.clone());
    result
}
}

Why PulseMap: Hot queries stay cached. Cold queries evict. 8-thread query dispatchers benefit from ShardedPulseMap’s near-zero lock contention.

Choosing the Right Map per Use Case

FAQ

General

Is PulseMap a HashMap replacement?

No. PulseMap is a bounded cache with automatic eviction. Use it when:

• You need fixed memory usage
• You can tolerate entries being evicted
• You want in-process caching without Redis

Use HashMap when you need to keep every entry forever.

What happens when PulseMap is full?

The least-useful entry in the target bucket is evicted (LFU+LRU hybrid). This is automatic and costs zero additional cache misses. Check eviction_count() to monitor.

Can I turn off eviction?

Not directly, but you can minimize it:

1. Use with_auto_resize(n) — the map doubles when 75% full
2. Start with a large initial size
3. Monitor eviction_count() — if it’s 0, you’re fine

What’s the maximum key/value size?

• Inline mode: key ≤ 6 bytes, value ≤ 7 bytes (fastest, zero allocation)
• Slab mode: unlimited size (heap allocated)

Both modes are transparent — PulseMap automatically chooses the optimal storage.

Performance

Why is PulseMap faster than HashMap?

Three reasons:

1. Cache efficiency: 1 cache line per lookup (vs 2-3 for HashMap)
2. No pointer chasing: Inline mode stores data directly in the bucket
3. H2 fingerprint: 99.2% of non-matches rejected without key comparison

When is PulseMap slower?

• Iteration — PulseMap doesn’t maintain insertion order
• Very large values — Slab allocation adds overhead
• 99%+ fill rate — Every insert causes an eviction

How does it compare to moka?

Single-thread: moka is significantly slower (161ms vs 6.1ms for 100K inserts). moka uses background maintenance threads and heavy synchronization.

Multi-thread (4T): ShardedPulseMap is 6.5–12x faster than moka across all concurrent workloads.

moka’s strength is its W-TinyLFU eviction policy (better hit rates on skewed workloads). PulseMap wins on raw throughput.

Memory

Does PulseMap leak memory?

No (since v0.6.0). Slab entries are returned to a free list on eviction/removal.

• Rust: Drop chains through SlabPool + free list
• C FFI: User must call pulse_map_free() (documented)

How much memory does PulseMap use?

Memory = num_buckets × 64 bytes + slab_overhead

For inline-only workloads (small KV pairs): exactly num_buckets × 64 bytes.

Can I use PulseMap in no_std?

Yes! Disable the std feature:

pulse_map = { version = "0.6", default-features = false }

Core data structures (MetaWord, Slot, Bucket) work without allocator.

Concurrency

Is PulseMap thread-safe?

• ConcurrentPulseMap — fully thread-safe, single-lock architecture
• ShardedPulseMap — fully thread-safe, 16-shard architecture (recommended for 3+ threads)
• TypedPulseMap and PulseMapRaw — single-threaded only

Can I set different TTLs for different keys?

Yes! Since v0.6.1, use insert_ttl(key, value, ttl):

#![allow(unused)]
fn main() {
cache.set_ttl(500);                              // global default
cache.insert_ttl(b"session", b"data", 50);       // expires after 50
cache.insert_ttl(b"config", b"val", u32::MAX);   // never expires
}

Can I use PulseMap with async/await?

Yes! ConcurrentPulseMap and ShardedPulseMap methods are non-blocking (spinlock, not mutex):

#![allow(unused)]
fn main() {
async fn handler(cache: &ShardedPulseMap<String, String>) {
    // Safe to call from async context — won't block the executor
    cache.insert("key".to_string(), "val".to_string());
}
}

What happens during resize?

• ConcurrentPulseMap: Stop-the-world (exclusive write lock). ~1ms per 10K entries.
• ShardedPulseMap: resize_all() rehashes one shard at a time — other shards remain operational.

FFI

Is the C API thread-safe?

Yes! The C API wraps ConcurrentPulseMap internally. You can call pulse_map_insert() from multiple threads simultaneously.

Changelog

See the full CHANGELOG.md in the repository root.

v0.6.2 (2026-08-11)

⚡ Lock-Free Reads + AccessBuffer + u64 TTL

8 PRs merged — correctness fixes, performance optimizations, and a breaking TTL type change.

Breaking Changes

• TTL types widened to u64: set_ttl(u64), get_ttl() -> u64, current_epoch() -> u64, insert_ttl(..., ttl: u64)
• Sentinel value for “never expire” is now u64::MAX (was u32::MAX)
• SlotTTL layout updated: { epoch: u64, ttl: u64 } (16 bytes per slot)

Added

• AccessBuffer module (engine/access_buffer.rs): Lock-free lossy ring buffer for deferred LRU/LFU priority updates
• Lock-free reads: MetaWord backed by AtomicU64, enabling relaxed atomic loads without dirtying cache lines
• Lazy slab lock: Inline keys skip slab_pool.lock() entirely during reads

Fixed

• UB Fix: Removed unsafe impl Sync from PulseMapRaw — now Send only
• Data loss during resize: Overflow retry loop ensures zero data loss during rehash
• TTL wipe during resize: Epoch/TTL metadata properly migrated
• Fingerprint entropy collapse: Shard routing no longer overlaps with h2 fingerprint bits

Performance (v0.6.1 → v0.6.2)

• GET p99: 1.244µs → 964ns (22.5% faster)
• Throughput: 5.99M → 7.47M ops/s (24.6% faster)
• Contention p99: 1.277µs → 1.134µs (11.2% faster)
• Memory: 34.0 B/entry (unchanged, zero overhead)

v0.6.1 (2026-08-03)

Added

• ShardedPulseMap — 16-shard concurrent map, 2.4–3.1x faster than ConcurrentPulseMap
• Per-entry TTL — insert_ttl(key, value, ttl) on all map types
  • ttl = 0: use global default, u32::MAX: never expire, N: expire after N inserts
• Zero-copy key borrow — PulseKey::with_key_bytes() for read-path optimization
• Competitor benchmarks — moka + quick_cache single-thread and 4-thread comparisons

Changed

• SlotTTL { epoch, ttl } replaces Vec<u32> epochs (8 bytes/slot)
• is_expired() now supports per-entry TTL with fallback to default

Tests

• 58 tests (up from 57)

v0.6.0 (2026-06-16)

Added

• TTL via epoch counter — set_ttl(n) expires entries after n insertions
• get_ttl(), current_epoch() — query TTL state
• Slab free list — evicted slab entries reused instead of leaked
• SlabEntry::rewrite() — in-place rewrite on free-list reuse

Changed

• peek() + remove() now use match_mask() — same branchless path as get()
• SlotState::Deleted removed — was never written, Tombstone is now value 2
• find_free_slot() simplified to != Full check

Fixed

• Memory leak: slab entries on eviction/remove now returned to free list
• Slot layout: slab slots store usize index instead of raw *const SlabEntry

Tests

• 57 tests (up from 50)

v0.5.0 (2026-05-26)

Added

• FFI bindings — C ABI
• ConcurrentPulseMap — thread-safe wrapper with per-bucket spinlocks
• Auto-resize support (with_auto_resize())
• peek() method — lookup without eviction priority update
• Null-safety checks across C bindings

Changed

• Workspace split: pulse_map (core) + pulse_map_bindings (FFI)
• Documentation URL: https://docs.rs/pulse_map
• MSRV declared: rust-version = "1.70.0"

v0.4.0 (2026-05-26)

Added

• Benchmark suite via Criterion
• SIMD H2 matching (optional, x86_64)
• TypedPulseMap<K, V> with PulseKey/PulseValue traits
• Iteration support (RawIter, TypedIter)

v0.3.0 (2026-05-26)

Added

• Dynamic resize support
• no_std compatibility
• Entry API improvements

v0.2.0 (2026-05-22)

Added

• LFU+LRU hybrid eviction (MetaWord)
• WyHash integration
• H2 fingerprint matching

v0.1.0 (2026-05-22)

Added

• Initial release
• 64-byte cache-line bucket architecture
• Inline + slab dual-mode storage

Contributing

See the full CONTRIBUTING.md in the repository root.

Quick Start

git clone https://github.com/ddsha441981/pulse_map.git
cd pulse_map
cargo build
cargo test

Before Submitting

cargo fmt               # Format
cargo clippy -- -D warnings  # Lint (zero warnings)
cargo test              # All tests pass
cargo doc --no-deps     # No doc warnings

Architecture

Layer 5: sharded.rs → ShardedPulseMap (16 shards)
Layer 4: sync.rs    → ConcurrentPulseMap
Layer 3: lib.rs     → User API (TypedPulseMap, PulseMap)
Layer 2: raw.rs     → Hash table logic + per-entry TTL
Layer 1: engine/    → MetaWord, Slot, Bucket, hash, slab

Key Rules

1. Every bucket = exactly 64 bytes
2. Eviction is zero-cost (metadata in cache line)
3. No heap allocation in hot path
4. Thread safety via &self (no &mut self for CRUD)

License

By contributing, you agree your contributions are licensed under MIT OR Apache-2.0.