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

• Spinlock-free metadata on reads: MetaWord uses AtomicU64, and get() records LRU/LFU updates into a deferred AccessBuffer without taking a bucket spinlock. The value read itself is not lock-free for slab-mode entries (keys/values past the 6B/7B inline window, including every u64 key) — those take the slab pool lock.
• Drain on the write path: queued access events are applied by insert() — each insert drains up to 64 events into its eviction decision before taking the bucket spinlock. Reads therefore carry eviction weight without any lock on the read path.
• 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.