Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

PulseMap

PulseMap is a fixed-capacity Rust cache with bucket-local LFU+LRU eviction. Every 64-byte aligned bucket holds four slots and their packed eviction metadata.

The eviction decision uses metadata in the bucket already fetched for lookup. This avoids an extra metadata cache-line fetch; it does not make operations free. TTL, slab storage and concurrency tracking require additional memory accesses.

Choose it when entries are disposable and compact keys/values make inline storage useful. Use an ordinary map when all entries must be retained. Evaluate scan resistance, hot-set changes, memory and concurrency separately.

Start with Getting Started, then Core Concepts and Benchmarks. Embedded support and its measured limits are in Embedded & no_std.

Getting Started

[dependencies]
pulse_map = "0.6"

Library MSRV: Rust 1.70. Benchmark/dev dependencies may require newer toolchains.

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

let mut cache = TypedPulseMap::<u32, u32>::new(16);
cache.insert(7, 70);
assert_eq!(cache.get(&7), Some(70));
assert!(cache.contains_key(&7));
assert!(cache.remove(&7));
}

Raw/typed constructors take buckets, rounded up to a power of two (minimum one). Capacity = buckets × 4. A raw/typed inline map needs 128 B/bucket for buckets and TTL storage: 16 buckets = 64 nominal slots = 2 KiB, before allocator overhead.

Concurrent types additionally allocate locks and access tracking. ShardedPulseMap takes buckets per shard; multiply by 16 shards and four slots. Local collisions can evict before the whole map is full. Headroom helps but is not a retention guarantee.

#![allow(unused)]
fn main() {
use pulse_map::ShardedPulseMap;
let cache = ShardedPulseMap::<u32, u32>::new(64);
assert_eq!(cache.capacity(), 16 * 64 * 4);
cache.insert_ttl(7, 70, u64::MAX); // immune to expiry, still subject to eviction
assert_eq!(cache.peek(&7), Some(70));
}

Raw/typed are fixed-size. Concurrent/sharded offer optional auto-growth above 75% occupied slots; that mode is not a fixed-memory cache. See the API pages for locking, TTL and resize semantics.

Core Concepts

Bucket layout

Bucket = 64 bytes, alignment 64
  MetaWord: 8 bytes
    states:     4 × 2 bits
    H2 hashes:  4 × 7 bits
    priorities: 4 × 7 bits
  Slots: 4 × 14 bytes

Inline: key ≤6 bytes and value ≤7 bytes. Larger keys or values store a slab index and extended fingerprint in the slot. u32/u32 is inline; u64/u64 is slab. Small typed numeric conversions use stack arrays, but slab storage still allocates.

WyHash with fixed seed 0 hashes the key bytes. Low bits select the bucket; high seven bits (57–63) form H2. Full key comparison follows a fingerprint match, so fingerprint collisions do not mean key equality. This fixed hash is not a HashDoS resistance guarantee for adversarial inputs.

Local eviction

Each bucket has four slots without chaining. An insert into a full bucket replaces its minimum-priority slot, even if a neighbouring bucket is empty. Priority is (frequency << 3) | recency: frequency dominates, recency breaks ties. See Eviction for aging and cold-start behaviour.

TTL records are outside the bucket: four × 16 bytes per bucket. Thus the fixed raw/typed allocation is 128 B/bucket, not 64. Slab storage grows with payload sizes.

Occupancy vs live lookup

Expiry is lazy: get/peek hide expired entries. len, is_empty, load_factor and iteration describe physically occupied slots, including expired unreclaimed ones. Iterating is not equivalent to repeatedly calling get on unexpired entries.

API Reference

TypeStorage APIThreading
PulseMap (alias of PulseMapRaw)&[u8] keys/values; borrowed lookup resultSend, not Sync
TypedPulseMap<K,V>Owned typed insert/result; iter/entry APIsSingle-owner mutation
ConcurrentPulseMap<K,V>Owned typed values; methods take &selfInternally locked
ShardedPulseMap<K,V>Concurrent API across 16 shardsInternally locked per shard

PulseKey: Sized and PulseValue: Sized provide associated Bytes: AsRef<[u8]>, to_bytes(&self) and from_bytes(&[u8]) -> Option<Self>. PulseKey also provides with_key_bytes, borrowing key bytes for reads where possible. It must encode the same bytes as to_bytes.

Both traits: u8/u16/u32/u64/i32/i64/String/Vec<u8>. Arrays implement PulseKey only; bool implements PulseValue only. Custom implementations define their own encoding.

All maps: new, insert, insert_ttl, get, peek, remove, len, is_empty, capacity, load_factor, eviction_count, set_ttl, get_ttl, current_epoch.

  • contains_key: typed/concurrent/sharded; raw uses peek(key).is_some().
  • iter, entry, Extend: typed. Raw iteration uses RawIter::new(&map).
  • num_buckets: raw and Concurrent; sharded capacity aggregates all shards.
  • with_auto_resize: Concurrent and Sharded only.
  • resize: Concurrent; resize_all: Sharded (growth only).

len() means occupied slots, including expired entries. See individual pages and TTL for lazy visibility. All insertion APIs may evict.

PulseMapRaw

PulseMap is its backwards-compatible alias. Keys/values are byte slices copied into inline/slab storage. Get/peek borrow value bytes from the map.

#![allow(unused)]
fn main() {
use pulse_map::{PulseMap, RawIter};
let mut map = PulseMap::new(16);
map.insert(b"hello", b"world");
assert_eq!(map.get(b"hello"), Some(&b"world"[..]));
assert!(map.peek(b"hello").is_some());
assert_eq!(RawIter::new(&map).count(), 1);
assert!(map.remove(b"hello"));
assert!(map.is_empty());
}

Fixed-size; no auto-resize or raw contains_key method. Empty keys and values are valid. Get updates priority, peek does not. Neither refreshes TTL.

set_ttl/insert_ttl use u64 insertion epochs. len/iteration include expired occupied slots; get/peek hide them. Raw insertion can reclaim expired slots. See TTL and Core Concepts.

TypedPulseMap<K,V>

A fixed-size wrapper around raw storage using PulseKey/PulseValue encodings. Lookups deserialize owned values. No Index or reference-to-V API is provided.

#![allow(unused)]
fn main() {
use pulse_map::TypedPulseMap;
let mut map = TypedPulseMap::<u32, u64>::new(16);
map.insert(42, 100);
assert_eq!(map.get(&42), Some(100));
assert!(map.contains_key(&42));
map.extend([(1, 10), (2, 20)]);
assert!(map.iter().any(|(k,v)| k == 42 && v == 100));
assert!(map.remove(&42));
}

This example’s u64 value uses slab storage; choose u32/u32 for inline mode. Keys must fit 6 bytes and values 7 bytes to avoid slab allocation. Strings/Vec values also allocate when deserialized.

Stats: len, is_empty, capacity, load_factor, eviction_count. There is no typed num_buckets or with_auto_resize. iter() includes expired occupied entries and skips values that fail custom deserialization. contains_key() tests raw presence with expiry, without decoding V.

From<HashMap> chooses a bucket count then inserts; collisions can evict entries during conversion. It is not a lossless HashMap conversion guarantee.

ConcurrentPulseMap

Thread-safe owned typed operations with &self. Share using Arc; get/peek take internal locks and copy value bytes before deserialization.

#![allow(unused)]
fn main() {
use pulse_map::ConcurrentPulseMap;
use std::sync::Arc;
let map = Arc::new(ConcurrentPulseMap::<String, u32>::new(16));
let writer = map.clone();
std::thread::spawn(move || writer.insert(String::new(), 42)).join().unwrap();
map.resize(32);
assert_eq!(map.get(&String::new()), Some(42));
assert!(map.remove(&String::new()));
}

New takes bucket count. with_auto_resize(n) enables growth above 75% occupied slots. Local collision eviction can still happen before that threshold.

Manual resize(n) rounds to a power of two, only grows, and blocks all operations while migrating resident entries, including empty keys and their TTL metadata. Buffered old-layout access hints and eviction priorities are reset during resize.

len()/eviction_count() read atomic counters. capacity()/num_buckets() acquire the map read lock. Counts across concurrent operations are not a consistent snapshot.

Get+insert is not an atomic read-modify-write. Concurrent counters/rate limiters need additional application synchronization or a purpose-built atomic-update API.

ShardedPulseMap

Sixteen independent ConcurrentPulseMaps. Constructor argument is buckets per shard. Each shard has its own locks, slab, access buffer, count and insertion epoch.

#![allow(unused)]
fn main() {
use pulse_map::ShardedPulseMap;
let map = ShardedPulseMap::<u32,u32>::new(16);
assert_eq!(map.capacity(), 16 * 16 * 4);
map.insert_ttl(1, 10, u64::MAX);
map.resize_all(32);
assert_eq!(map.peek(&1), Some(10));
}

Routing

shard = (hash >> 14) & 15
bucket_hash = (hash & 0x3fff) | ((hash >> 4) & !0x3fff)
bucket = bucket_hash & (buckets_per_shard - 1)

The shard’s four bits are removed before bucket indexing, preserving low-14-bit distribution while allowing larger shards to use independent hash bits. All CRUD and rehash operations use this same derivation. H2 uses the original hash’s high seven bits. Older versions failed to remove shard bits at larger capacities.

resize_all grows one shard at a time. Other shards remain usable; operations on the shard being migrated block. It is not a globally atomic snapshot operation.

TTL counts inserts into the entry’s own shard. current_epoch() is the maximum shard epoch, not total map-wide inserts. len() sums occupied slots; all aggregated stats are approximate snapshots under concurrent mutations.

Entry API

TypedPulseMap provides occupied/vacant entries through an exclusive mutable borrow. Unlike std HashMap’s entry API, or_insert/or_insert_with return unit, not &mut V.

#![allow(unused)]
fn main() {
use pulse_map::TypedPulseMap;
let mut map = TypedPulseMap::<u32,u32>::new(16);
map.entry(1).or_insert(10);
map.entry(1).and_modify(|v| *v += 1).or_insert(0);
assert_eq!(map.get(&1), Some(11));
map.entry(2).or_insert_with(|| 20);
assert_eq!(map.get(&2), Some(20));
}

OccupiedEntry exposes get/key/insert/remove; VacantEntry exposes key/insert. Writing a modified value re-inserts it, refreshing its epoch and using the default TTL. Entry lookup treats expired values as vacant.

Concurrent/sharded maps offer upsert through insert, but no atomic read-modify-write entry API. A separate get followed by insert can lose concurrent updates.

Eviction Strategy

The minimum-priority Full slot in the target bucket is evicted when no free slot is chosen. Raw insertion also reclaims expired slots; concurrent insertion currently chooses free slots or the policy victim, without an expired-first search.

priority = (frequency << 3) | recency
frequency: 0..15, saturating
recency:   0..7
new entry: frequency=0, recency=1
hit:       frequency += 1 (capped), recency=7
           other Full slots' recency -= 1 (floored at zero)

Frequency does not age. Recency decays on accesses to neighbours, not elapsed time. This protects established hot entries from scans, but can prevent adaptation to a new working set. Saturation caps counters; it does not guarantee old entries will become cold. Current traces measure both scan resistance and phase changes.

Raw/typed get updates the atomic MetaWord immediately. Concurrent get records a lossy access event, applied during insert in a bounded batch. Missed events can change policy accuracy; they do not change stored key/value bytes. Peek does not promote priority. Updating an existing key promotes it and refreshes its TTL.

Eviction is a local approximation, not exact global LRU or global LFU. Increasing capacity reduces collisions but does not guarantee every insertion survives. u64::MAX TTL only prevents expiry; it does not pin entries against eviction.

Insertion-Epoch TTL

TTL counts insertions, including updates. It does not count seconds or reads. Entries expire when current_epoch.wrapping_sub(insertion_epoch) > effective_ttl. At age equal to TTL they remain valid. Shards count their own inserts independently.

SettingMeaning
set_ttl(0)Disable global expiry (default)
insert_ttl(k,v,0)Use the current global default
insert_ttl(k,v,N)Override with N insertion epochs
insert_ttl(k,v,u64::MAX)Never expire; can still be evicted
#![allow(unused)]
fn main() {
use pulse_map::TypedPulseMap;
let mut cache = TypedPulseMap::<u32, u32>::new(16);
cache.set_ttl(100);
cache.insert_ttl(1, 10, 1);
cache.insert(2, 20);
assert_eq!(cache.peek(&1), Some(10)); // age == ttl
cache.insert(2, 21);
assert_eq!(cache.get(&1), None);     // age > ttl
assert_eq!(cache.len(), 2);          // occupied, not unexpired count
assert!(cache.iter().any(|(k, _)| k == 1));
}

Reinsert refreshes epoch and replaces the TTL override. get does neither. Changing global TTL changes the effective TTL of entries with override zero. Expiry is a lookup decision, not a permanent deletion; disabling/extending TTL can make an unreclaimed entry visible again. remove physically removes even expired entries and reports whether an occupied matching key was found.

Expired slots are not eagerly removed. Raw insertion can reuse them; concurrent insertion does not currently prefer them over policy victims. len() includes expired occupied entries; iter() includes them too. No wall-clock session/DNS lifetime can be guaranteed by converting an estimated request rate into epochs.

TTL metadata occupies 16 B/slot even when expiry is disabled. Concurrent hits take the epochs mutex before checking effective TTL, so disabled TTL is not zero overhead.

Concurrency Model

ConcurrentPulseMap shares a map with &self operations; ShardedPulseMap routes operations to 16 independent concurrent maps. Both require std.

Locks

  1. RwLock read guard for normal operations; exclusive write guard for resize.
  2. Per-bucket spinlock for get, peek, insert and remove on that bucket.
  3. Epochs mutex for TTL metadata, including hit lookups with global TTL disabled.
  4. Slab mutex for large entries. Inline get avoids this mutex, but not the others.

Different buckets can still contend on shared metadata/pool locks. Sharding narrows that contention to a shard. Same-key operations still route to the same shard/bucket. Lock waits and allocation mean these synchronous operations can block an async executor; no universal non-blocking/ISR-latency guarantee is provided.

Deferred priority updates

Get records bucket/slot access events rather than updating priority inline. Inserts drain up to 64 events before taking their own target bucket lock. Each callback takes one target bucket lock and releases it before the next event. Guards are not nested. The queue releases its slot before calling out.

The bounded MPMC buffer uses per-slot sequence numbers for publication/reuse and one reservation CAS attempt per push/pop. A full buffer, contention, or an unpublished head can cause tracking to be skipped. A stalled producer can delay consumption: try operations do not wait, but this is not a formally lock-free FIFO. Sequence tagging prevents duplicate delivery; lossy tracking remains an approximation.

Resize holds the exclusive map lock, clears queued old-layout events, migrates keys, values and TTL, and swaps the arrays. Policy history resets during rehash. Sharded resize processes one shard at a time; other shards can proceed.

Raw/typed maps have no shared concurrent writer API. Raw is Send, not Sync; use a concurrent map or application-level synchronization for shared mutation.

Architecture & Internals

FileResponsibility
lib.rsRaw alias, typed wrapper, serialization traits, entry API
raw.rsFixed-size byte cache, TTL, local eviction
sync.rsIndependently implemented concurrent operations, locks, growth
sharded.rs16-way routing and per-shard map ownership
engine/meta.rsAtomicU64 packed state/H2/priority
engine/access_buffer.rsBounded, sequence-tagged lossy deferred access queue
engine/slot.rs, bucket.rs14-byte slot, 64-byte aligned four-slot bucket
engine/hash.rsWyHash and fingerprint decomposition
engine/slab.rsHeap payload ownership and free-list index reuse
iter.rs, traits.rsIterators, Debug/Display/Extend/From<HashMap>

Bucket

#![allow(unused)]
fn main() {
use pulse_map::{Bucket, MetaWord, Slot};
assert_eq!(core::mem::size_of::<MetaWord>(), 8);
assert_eq!(core::mem::size_of::<Slot>(), 14);
assert_eq!(core::mem::size_of::<Bucket>(), 64);
assert_eq!(core::mem::align_of::<Bucket>(), 64);
}

Metadata selects fingerprint candidates before full key comparison. Inline slots own small bytes; slab slots contain an index and extended fingerprint. Freed slab indices are reusable; payload allocation/deallocation is still required for new slab entries, and vectors can retain their high-water capacity.

Concurrent paths

Normal CRUD takes an RwLock read guard then a bucket lock. TTL checking takes the epochs mutex. Get’s inline path avoids the pool lock; peek/remove can take it even for inline candidates. Slab reads need the pool lock. Owned value bytes are copied before deserialization. See Concurrency for lock ordering.

Insert drains up to 64 deferred accesses before taking its own target bucket lock. Publication/reuse sequence tags protect the ring slot until its consumer has copied the event. A callback runs after queue ownership is released.

Resize

Only concurrent maps grow. Under the exclusive map guard, discard buffered access hints, extract every Full entry (including empty keys and expired occupied slots), rehash into new bucket/slab/TTL arrays, and swap. TTL data is preserved; priorities reset. Requests do not shrink capacity. Sharded routing removes shard bits before bucket indexing, including during rehash.

Performance & Benchmarks

The authoritative current methodology and raw evidence live in evaluation/. It compares published v0.6.5 and the local correctness candidate in one optimized executable with pinned LRU, QuickCache and Moka dependencies.

Comparing fairly

  • Equal actual nominal capacity; bucket rounding is explicit.
  • Like-for-like u32/u32 (PulseMap inline) or u64/u64 (slab).
  • Shared seeded traces and operation choices, with independent read/write RNG.
  • Native single-thread LRU separately labelled from Mutex<LruCache>.
  • Fresh-process RSS per map; report both bytes/slot and bytes/resident.
  • Repeat timing trials and report spread. CPU scheduling and map policies vary.

These are host measurements. They are not physical-MCU timing results. TTL-disabled concurrent hits still take the epochs mutex, and slab/value-copy costs remain.

Historical results

Older v0.6.2 figures and cache-miss/ranking claims in this guide are superseded. Some old comparisons used a 10,000-entry competitor against PulseMap rounded to 16,384 slots; nominal memory denominators also hid occupancy differences. Historical outputs remain in repository history and labelled artifacts, not as current rankings.

Reproduce

cargo test --manifest-path evaluation/Cargo.toml --locked
python3 evaluation/capture.py my-unique-label
cargo bench --bench benchmark -- 'conc_|sharded_'

Capture labels must be new. See evaluation/README.md for workload and RSS limitations.

v0.6.6 correctness candidate

Full paired report includes three-seed means/ranges and all raw observations. At 65,536 slots and 2M cache-aside operations, candidate TypedPulseMap hit rate was 73.26% on Zipf .99, 23.05% on a repeated 3×capacity scan, and 90.58% on changing hot sets; LRU measured 71.69%, 0%, and 97.54% respectively. Scan resistance and adaptation are distinct.

All 63 paired deterministic hit-rate rows match v0.6.5. The separate large-shard probe retains 967,051 of 1M keys vs 821,839 before the routing fix. The buffer fix costs 48 KiB/Concurrent map on x86_64 (768 KiB over 16 shards). Measured u32 sharded RSS was 61.75 B/resident vs 48.12 before; QuickCache was 50.12. Inline typed remained 40.04 B/resident. RSS includes allocator/page effects; the queue allocation increase is structural.

Four-thread u64 sharded throughput was 9.56–9.75 Mops/s vs 10.52–11.03 for v0.6.5. This is a measured correctness/performance cost, not a speedup release. Several other timing rows show substantial host variance; no universal ranking follows.

Feature Flags

FeatureDefaultPurpose
stdyesConcurrent/sharded maps and From<HashMap>
simdnoSSE2 H2 matching on x86_64
critical-sectionnoportable-atomic fallback when native CAS is absent

Raw/typed maps, slab storage, iterators and formatting work without std, using alloc. The cache itself requires a heap allocator. Fixed-layout primitives MetaWord/Slot/Bucket can be used without creating a heap-backed map.

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

Targets without CAS additionally require the critical-section feature and a critical-section implementation supplied by the binary/HAL. See Embedded. SIMD uses multiple SSE2 operations plus state filtering; its benefit needs measurement, not a fixed percentage promise. Other architectures use scalar matching.

cargo test --all-features
cargo test --no-default-features
cargo test --features simd

Embedded & no_std

PulseMap runs on bare-metal microcontrollers — not just cargo check, but actually executed on emulated ARM hardware via QEMU.

Quick Start

# Most targets (Cortex-M3+, RISC-V with A extension, WASM)
pulse_map = { version = "0.6", default-features = false }

# Cortex-M0 / RP2040 / ESP32-C3 (no hardware atomic CAS)
pulse_map = { version = "0.6", default-features = false, features = ["critical-section"] }

What You Get in no_std

With default-features = false, PulseMap needs only alloc (a heap allocator). You get:

  • PulseMapRaw — insert / get / remove / peek / TTL
  • TypedPulseMap<K, V> — type-safe wrapper
  • MetaWord — 8-byte packed LFU+LRU metadata
  • Bucket — 64-byte cache-line-aligned storage

You do not get ConcurrentPulseMap or ShardedPulseMap (they need std for RwLock and threading).

Verified Targets

Every push runs cargo check in CI for all 8 targets. Two of them also execute on QEMU (marked with 🏃):

TargetChipsExtra FeatureTested
thumbv7m-none-eabiCortex-M3—🏃 QEMU
thumbv7em-none-eabihfCortex-M4F / M7F (STM32F4)—✅ build
thumbv8m.main-none-eabiCortex-M33 (nRF9160)—✅ build
thumbv6m-none-eabiCortex-M0 / M0+ (RP2040)critical-section🏃 QEMU
riscv32imac-unknown-none-elfRISC-V with A extension—✅ build
riscv32imc-unknown-none-elfESP32-C3critical-section✅ build
aarch64-unknown-none64-bit bare metal—✅ build
wasm32-unknown-unknownWebAssembly—✅ build

Why critical-section?

PulseMap’s MetaWord is an AtomicU64. On chips without hardware atomic CAS (Cortex-M0, RISC-V without the A extension), portable-atomic cannot build a 64-bit atomic at all. The critical-section feature solves this by masking interrupts around the update.

The critical-section implementation comes from your HAL, not from PulseMap:

# Cortex-M0 single-core — add to your binary crate
cortex-m = { version = "0.7", features = ["critical-section-single-core"] }

# ESP32-C3: use your HAL's supported critical-section implementation
esp-hal = { version = "...", features = ["critical-section"] }

Memory Footprint

On a Cortex-M with 16 KiB RAM, PulseMap fits comfortably:

ConfigBucketsSlotsHeap Used
16 buckets16642,048 bytes
4 buckets416512 bytes

Each bucket is exactly 128 bytes of heap (64B bucket + 64B slot TTL metadata). A 64-slot cache in 2 KiB of RAM is what makes PulseMap practical on parts where Moka and QuickCache cannot even compile.

Running the QEMU Tests Yourself

cd qemu-test

# Cortex-M3 (portable-atomic spinlock fallback)
cargo run --release --target thumbv7m-none-eabi

# Cortex-M0 (critical-section, interrupt masking)
cargo run --release --target thumbv6m-none-eabi --features m0

Requires qemu-system-arm installed (apt install qemu-system-arm).

The test inserts, gets, evicts, checks TTL, and removes — all on real ARM instructions, not a compile check. Output:

alloc: inline u32->u32 = 2 at new(), 0 across 256 insert+get+remove
alloc: slab u64->u64   = 2 at new(), 14 across 6 inserts
qemu-test: 16 buckets, 64 nominal slots, 4592 heap bytes used
qemu-test: all checks passed

The 4,592 covers all five maps and slab allocations in the test, including the added inline/slab allocation probes. It is not one map’s footprint. A lone 16-bucket inline map is 2 KiB, matching the table above. Older three-map output reported 3,072 B.

PulseMap vs LRU on Embedded

qemu-test/ compares PulseMap against lru 0.12, one no_std-compatible competitor; other no_std caches exist. At 64 resident inline u32/u32 entries, the historical probe measured 2,048 B heap for PulseMap and 4,520 B for LRU. It chooses keys that fill all slots, rather than assuming nominal capacity equals residency.

This does not imply the same hit rate on arbitrary keys. Bucket-local eviction can discard entries before global capacity is full. Numeric u64 payloads use slab storage and change allocation behaviour. Flash comparisons are toolchain-specific; the measured M3 build favoured LRU’s smaller code size.

MetaWord uses AtomicU64 even in raw/typed get. On Cortex-M0 the fallback can mask interrupts. QEMU validates instructions, results and allocations, not real-time latency. A multicore chip needs a cross-core-safe critical-section implementation; single-core interrupt masking alone is insufficient across cores.

Language Bindings

C, Python (PyO3), Java (Panama FFM) and Node.js bindings are maintained in the separate pulse_map_bindings repository. This Rust crate contains no C ABI or language-binding artifacts.

Use that repository’s versioned README, headers and examples for:

  • exact library/package names and supported runtime versions;
  • return codes, buffer sizes, TTL integer widths and thread-safety contracts;
  • handle ownership/freeing and platform build commands.

Bindings have independent version/dependency resolution. Preparing Rust v0.6.6 does not establish that a released binding already links it. Check the resolved core dependency when reproducing behaviour. Older guide examples describing C as the only binding and a u32 TTL ABI are historical, not the current Rust API.

Use Cases

Compact memoization

Use a typed cache when recomputing a missing result is acceptable. u32/u32 stays inline and does not allocate during insert/get/remove after map construction.

#![allow(unused)]
fn main() {
use pulse_map::TypedPulseMap;
fn squared(cache: &mut TypedPulseMap<u32,u32>, key: u32) -> u32 {
    if let Some(value) = cache.get(&key) { return value; }
    let value = key.saturating_mul(key);
    cache.insert(key, value);
    value
}
let mut cache = TypedPulseMap::new(16);
assert_eq!(squared(&mut cache, 7), 49);
}

Shared cache-aside data

#![allow(unused)]
fn main() {
use pulse_map::ShardedPulseMap;
fn cached_query(
    cache: &ShardedPulseMap<String,String>, key: String,
    fetch: impl FnOnce(&str) -> String,
) -> String {
    if let Some(value) = cache.get(&key) { return value; }
    let value = fetch(&key);
    cache.insert(key, value.clone());
    value
}
let cache = ShardedPulseMap::new(16);
assert_eq!(cached_query(&cache, "query".into(), |_| "result".into()), "result");
}

Concurrent misses may call fetch more than once. This does not provide request coalescing, an atomic read-modify-write, or a wall-clock freshness guarantee. String values use the slab and owned return values allocate.

Embedded sample cache

Small numeric sensor IDs and derived values are a good inline fit. Size the bucket and TTL allocations together and test collision pressure. See the embedded guide for QEMU allocation/footprint measurements; host timings do not establish ISR bounds.

Boundaries to account for

  • DNS/session lifetimes need actual time-based validation outside epoch TTL.
  • A concurrent get/increment/insert rate limiter can lose updates, refreshes TTL on each insert, and may forget counts through eviction.
  • Caching a numeric GPU handle does not release its external resource on eviction.
  • Deduplication is best-effort unless your application provides atomic coordination.
  • Fixed entry count does not cap bytes for arbitrarily large content.

These are cache semantics: choose application-level coordination and ownership according to the data being cached.

FAQ

Is this a HashMap replacement?

It is a bounded entry-count cache, not a lossless map. A full four-slot bucket evicts locally before global capacity is reached. Slab payload sizes can grow memory usage even with fixed entry count. Optional auto-resize on concurrent maps removes the fixed-capacity bound.

Is every operation one cache miss or allocation-free?

No. Bucket metadata is co-located with slots, but TTL and slab reads touch additional storage. Raw/typed inline operations avoid allocation after construction. Concurrent get/peek currently copy bytes into a temporary vector, even on inline hits.

Is it faster than LRU, QuickCache, Moka or HashMap?

Results depend on payload, occupancy, skew, hit rate and threads. HashMap has no eviction, so it is not an equivalent bounded-cache competitor. See the versioned benchmarks and compare actual resident counts as well as throughput.

Does expiry remove entries immediately?

No. Get/peek hide expired entries, while len and iter still count/include their occupied slots. TTL counts inserts, not wall-clock time. u64::MAX disables expiry for an entry but does not protect it from eviction.

Can I call it from async code?

Yes, as a synchronous operation that can block on locks and allocation. Reads use RwLock, bucket spinlock, and shared metadata/pool mutexes. A get followed by insert is not an atomic counter update. See Concurrency.

Does sharding remove same-key contention?

No. A key always maps to one shard and bucket. Sharding spreads unrelated keys; hot single-key traffic still contends. Resizing blocks the affected shard.

How much memory should I allocate?

Raw/typed: 128 B/bucket for bucket + TTL records, plus payload slab/allocator costs. Concurrent/sharded add locks and an access queue per map/shard. Inline key ≤6 bytes AND value ≤7 bytes. See Embedded and the measured RSS tables.

Are no_std and bindings supported?

Raw/typed maps support no_std with alloc and a suitable portable-atomic fallback. C/Python/Java/Node bindings are maintained in a separate repository with their own versions and lifetime/threading contracts: Bindings.

Changelog

See the full CHANGELOG.md in the repository root.

v0.6.6 (2026-10-10)

  • Preserve empty keys/TTL during resize; independent shard/bucket hash bits above the old growth boundary; sequence-tagged access events prevent overlapping-wrap duplicate delivery.
  • Precise TTL/occupancy/locking/allocation documentation and executable guide examples.
  • Pinned, paired in-repo evaluation with fair capacities, isolated memory and full timing spread. Correctness costs +48 KiB per Concurrent map on x86_64 and measurable throughput overhead on some traces; see Benchmarks.

Historical wording below describes old releases, not the current locking contract. Concurrent reads take locks; TTL’s never-expire sentinel is u64::MAX.

v0.6.5 (2026-09-28)

🧠 AccessBuffer Drain + Validation & Embedded Proofs

  • AccessBuffer drain: deferred LRU/LFU updates buffered by get() are now drained on the write path. ConcurrentPulseMap::get() ties TypedPulseMap at 95.372% hit rate (peek-only control: 94.456% — counting reads is worth +0.92 points). Read latency is untouched: the drain runs inside insert(). Ships with a BucketGuard fix so the drain is Miri-clean.
  • Validation: cargo-fuzz shadow-map oracle (5.46M executions clean under AddressSanitizer), Miri in CI for both engine and sync configs, loom models for the MetaWord CAS and AccessBuffer, multi-threaded soak at +0.0 MB RSS drift (147.9M ops).
  • Embedded: 8-target cargo check matrix in CI — thumbv6m (Cortex-M0) and riscv32imc (ESP32-C3) now compile via the opt-in critical-section feature. QEMU-executed tests on Cortex-M3 and Cortex-M0: 12 assertions, heap measured at 128 B per bucket (2 KiB for a 16-bucket map).

v0.6.4 (2026-08-19)

🌍 Portable AtomicU64 — Cross-Platform Compatibility

  • Replaced core::sync::atomic::AtomicU64 / std::sync::atomic::AtomicU64 with portable-atomic::AtomicU64 across meta.rs and sync.rs
  • Enables compilation on targets without native 64-bit atomics: WASM32, ARMv7-M, 32-bit embedded
  • No API changes — drop-in replacement

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 decisions reuse in-bucket metadata; additional TTL/slab accesses still cost work
  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.