pds

Persistent data structures with structural sharing for Rust.

Forked from imbl (itself a fork of im) with different design priorities: performance over compatibility, Merkle hashing for O(1) equality checks, SIMD-accelerated HAMT nodes, and no_std support.

Add to your Cargo.toml:

[dependencies]
pds = "1.0"

Optional features can be enabled as needed:

[dependencies]
pds = { version = "1.0", features = ["serde", "rayon"] }

See Feature flags for the full list.

All collections use structural sharing: cloning is O(1) and modified copies share unchanged subtrees with the original.

*Amortised O(1) push; O(log n) split/concat.

All collection types implement Display for human-readable output. Debug is also implemented on all types for use in format strings and test assertions.

Vector exposes VectorRange — a borrowed, range-bounded view with O(1) construction. OrdMap and OrdSet will gain equivalent view types (OrdMapRange, OrdSetRange) following the same design.

A VectorRange holds a reference to the original vector plus two integer bounds. Construction records only those three values — no tree walk, no element copy:

The view borrows the original. Both the view and the vector share the same backing tree — no extra memory is allocated.

Most operations work directly on the view:

let data: Vector<i32> = (0..1000).collect();

// Iterate — O(n) work, O(1) view construction.
for x in data.take(100) { /* ... */ }

// Check length — O(1).
assert_eq!(data.skip(900).len(), 100);

// Chain narrowing operations — all O(1).
let middle = data.skip(200).take(600); // elements 200..800
println!("{}", middle.len());          // 600

Call .to_vector() when you need an owned copy:

// Materialise — O(log n) two-split on the underlying tree.
let owned: Vector<i32> = data.take(100).to_vector();

Before range views, working with a prefix meant clone-and-split:

// O(log n): clone is O(1) but split_off walks the tree.
let mut prefix = data.clone();
let _rest = prefix.split_off(100);

VectorRange costs strictly less: take(100) is pure integer arithmetic. Views are the right default for any operation that reads a subrange without needing to own it.

The standard library provides HashMap, BTreeMap, and Vec as mutable, owned containers. Every clone() allocates fresh memory and copies every element — O(n) in both time and space. pds collections use structural sharing: clone is always O(1), and a modification touches only the path from the root to the changed node.

† Merkle hash fast-path — same-lineage maps with equal length and equal Merkle hash compare in O(1).
‡ Cached content hash (ord-hash feature, on by default) — O(1) when the hash is valid.

The trade-off is clone cost versus point-lookup speed. std::HashMap wins on random lookups (roughly 2× faster than pds::HashMap). pds wins on any operation that involves copying: every clone that would cost O(n) with a standard map becomes O(1).

When a single thread owns a map and mutates it in a tight loop with no snapshotting, std::HashMap is the right tool. When you need snapshots, undo/redo, versioning, or shared state between threads — pds collections win.

std::Vec is unbeatable for purely sequential workloads: appending and reading by index in a tight loop. pds::Vector trades a constant factor on random access (the RRB tree depth) for dramatically cheaper structural operations — split and concat are O(log n) rather than O(n), and clone is O(1). Use pds::Vector when you need to branch on a sequence: taking a snapshot before a speculative edit, passing an independent view to another thread, or producing multiple output variants from a single input.

Rust's ownership model prevents data races at compile time. pds extends this advantage: because clone is O(1), you can hand a complete, independent snapshot to another thread with no synchronisation overhead.

With a standard library map:

// Every reader must acquire the lock — even for read-only access.
let shared: Arc<Mutex<std::collections::HashMap<K, V>>> = ...;
let guard = shared.lock().unwrap();
let value = guard.get(&key);

With a pds map:

// Clone the current snapshot in O(1) — no lock held during processing.
let snapshot: pds::HashMap<K, V> = current_state.clone();
let value = snapshot.get(&key);

Because each modification produces a new root without touching the old one, multiple threads can hold snapshots at different points in time — all sharing structure, all independent, none blocking the others. Common patterns:

• Worker pools — distribute independent snapshots to workers; merge results back with par_union.
• Speculative execution — clone before a tentative operation; discard the clone on rollback, keep it on commit.
• Event sourcing — each state transition produces a new snapshot; prior states are retained cheaply because unchanged subtrees are shared.
• Read scale-out — any number of readers hold the latest snapshot with zero contention; the writer atomically publishes a new root.

The Hash-backed and Ord-backed variants of every collection type share the same persistent semantics, the same structural-sharing clone model, and the same API shape. The choice between them is driven first by key constraints, then by which operations dominate your workload.

This section covers the primary HashMap / OrdMap pair. The same reasoning applies to every derived type: Bag / OrdBag, HashMultiMap / OrdMultiMap, BiMap / OrdBiMap, SymMap / OrdSymMap, Trie / OrdTrie, InsertionOrderMap / OrdInsertionOrderMap, and InsertionOrderSet / OrdInsertionOrderSet.

These are hard constraints, not preferences:

If you need sorted iteration, range queries, or access to the minimum/maximum key, OrdMap is the only option. If your keys lack Ord, HashMap is the only option. When both constraints are satisfied the choice is a performance question.

All numbers from cargo bench --bench compare --features rayon (release profile). Full results in docs/baselines.md.

HAMT gives O(1) amortised lookup (fixed trie depth). OrdMap is O(log n) with a small constant from B+ node binary search. HashMap is consistently ~2× faster for random point queries, and this is the only operation where HashMap wins.

OrdMap wins under sole-owner writes: copy-on-write detects the sole reference and mutates in-place without allocating. HashMap rewrites HAMT nodes on every insert regardless of ownership. The same pattern holds for from_iter (OrdMap ×1.4–2.0× faster) and remove_mut at small sizes (OrdMap ×1.7–2.2× faster at ≤1K).

B+ tree leaves are contiguous arrays; iterating a leaf scans cache-linearly. HAMT traversal follows pointer chains through bitmapped nodes — poor spatial locality. The gap widens with size as the HAMT grows deeper.

OrdMap uses the O(m log(n/m)) parallel join algorithm (split → recurse → concat); HashMap uses filter+reduce, which has a sequential O(n) bottleneck. The gap grows with size and is the dominant reason to choose OrdMap for any set-merge workload.

From cargo bench --bench memory (dhat, 100,000 i64 entries):

OrdMap packs up to 16 key-value pairs per leaf allocation. HAMT nodes are per-trie-level and multiply with tree depth.

Use HashMap / Hash variants when:

• Keys are not Ord (e.g. unordered tuples, custom types without a natural order).
• Your workload is dominated by random point lookups and writes are infrequent. The ~2× lookup advantage compounds when lookups are the overwhelming majority of operations.
• You rely on ptr_eq structural-sharing fast-paths: HashMap::par_union short-circuits to O(1) when both operands share the same root (common after clone() with no mutation). This benefits patterns like "start from a common snapshot, make one change, union back".
• You accumulate incremental Merkle hashes without rescan. HAMT root hashes update atomically on each insert; OrdMap (ord-hash) recomputes lazily. If you clone a map, mutate it once, and compare it immediately, HAMT avoids the deferred rescan.

Use OrdMap / Ord variants when:

• You need sorted order at any point — sorted output, priority processing, stable serialisation, or deterministic comparison. Iteration is sorted by definition and ×2–4× faster than HashMap at large sizes.
• You need range queries: "all keys between X and Y", "everything from key K onwards". This is only available on OrdMap.
• You need minimum / maximum access without a full scan (get_min, get_max, without_min, without_max). These are O(log n).
• You perform parallel set operations (par_union, par_intersection, etc.). At 100K entries OrdMap's join algorithm is ~15× faster than HashMap's filter+reduce.
• Your workload is write-heavy or bulk-construction-heavy. Sole-owner in-place mutation gives OrdMap a consistent ×1.5–2× advantage over HashMap for inserts, removes, and from_iter.
• You are in a no_std environment without the foldhash feature. OrdMap requires no hasher.
• You want lower memory pressure. At 100K entries OrdMap uses 4.5× fewer allocations and 3.9× less memory than HashMap.
• Keys are expensive to hash. Ord comparison is often cheaper than hashing for numeric or short-string keys, and OrdMap's B+ tree stops as soon as a comparison resolves the branch.

Use either when:

• Immutable snapshots / structural sharing: both types share subtrees on clone and write only the changed path.
• Serde round-trips: both implement Serialize/Deserialize (behind serde feature).
• Rayon parallel iteration: both support par_iter() and FromParallelIterator.
• As a key in another map: both implement Hash (via ord-hash for OrdMap; built-in for HashMap) and can be used as keys in HashMap<OrdMap<_,_>, _> etc.

Every Hash-variant / Ord-variant pair follows the same pattern:

For each pair: the Hash variant requires Hash + Eq, the Ord variant requires only Ord. Performance characteristics mirror the HashMap / OrdMap comparison above: the Ord variant is faster for writes, iteration, and parallel ops; the Hash variant is faster for random point lookups on large collections. The OrdInsertionOrder* types have no Hash variant analogue for the iteration-order guarantee when keys lack Hash.

dhat measures exact heap allocation counts per operation. The table below is from cargo bench --bench memory on an M5 Max (Rust 1.95.0, release profile).

from_iter allocations and bytes — HashMap<i64,i64> vs OrdMap<i64,i64>:

from_iter allocations — HashSet<i64> vs OrdSet<i64>:

The gap opens with scale because HAMT promotes nodes through three tiers (SmallSimdNode → LargeSimdNode → HamtNode) and each trie level adds allocations. OrdMap's B+ tree is bounded by the tree height: at 100,000 entries, roughly one allocation per 15 entries (100,000 / 16 ≈ 6,250 leaves; 6,641 includes internal branch nodes).

Small-map behaviour: for ≤ 16 entries, HashMap uses a SmallSimdNode — a single flat allocation with SIMD lookup. For ≤ 32 entries it promotes to LargeSimdNode. At these sizes HashMap's allocation count is comparable to OrdMap.

For your own workload, run cargo bench --bench memory or instrument with:

#[global_allocator]
static ALLOC: dhat::Alloc = dhat::Alloc;

let _profiler = dhat::Profiler::new_heap();
// ... operations under test ...

Full results are in docs/baselines.md.

pds is forked from imbl, which is itself a fork of the unmaintained im. The API is largely compatible with imbl 7.x, but pds prioritises performance and capability over strict backward compatibility.

rpds is an independent implementation with a different collection set and design philosophy.

†par_union, par_intersection, par_difference, par_symmetric_difference are available on all Hash-backed types and on OrdMap/OrdSet. Trie, InsertionOrderMap, InsertionOrderSet, and all Ord-derived types (OrdBag, OrdMultiMap, OrdBiMap, OrdSymMap, OrdTrie, OrdInsertionOrderMap, OrdInsertionOrderSet) do not have parallel set operations.

Key differences from imbl:

• Merkle hashing on all collections for O(1) structural equality checks
• Fifteen additional collection types: Bag, OrdBag, HashMultiMap, OrdMultiMap, InsertionOrderMap, InsertionOrderSet, OrdInsertionOrderMap, OrdInsertionOrderSet, BiMap, OrdBiMap, SymMap, OrdSymMap, Trie, OrdTrie, UniqueVector
• Hash consing via InternPool — deduplicates identical HAMT subtrees across collections
• Structural-sharing-preserving serialisation via HashMapPool — serialises/deserialises trees with node deduplication and cross-session interning
• no_std support via default-features = false; foldhash feature provides type aliases in no_std environments
• triomphe::Arc support (no weak count, 8 bytes smaller per node)
• Deprecated API aliases removed; breaking changes for correctness accepted

• API docs — build locally with rm -rf rustdocs && cargo doc --no-deps --all-features --target-dir rustdocs --open
• Architecture — internal data structure design
• Decision log — architectural choices and rationale
• Glossary — project terminology
• Implementation plan — phased improvement roadmap
• References — papers and external resources

The core types and their Hash-backed derived types gain parallel capabilities under the rayon feature flag. Ord-backed derived types (OrdBag, OrdMultiMap, OrdBiMap, OrdSymMap, OrdTrie, OrdInsertionOrderMap, OrdInsertionOrderSet) do not currently have rayon support — only sequential operations.

Every collection type that exposes union, intersection, difference, and symmetric_difference also has parallel counterparts named with the par_ prefix. These work identically to the sequential versions but use rayon to parallelise the computation.

All Ord-backed derived types (OrdBag, OrdMultiMap, OrdBiMap, OrdSymMap, OrdTrie, OrdInsertionOrderMap, OrdInsertionOrderSet): no parallel set operations.

† par_union delegates to the sequential implementation for these types. BiMap and SymMap maintain bijection/symmetry invariants that require sequential conflict resolution on each insert; HashMultiMap value-set merging has the same constraint. The other three par ops are fully parallelised via parallel filter + collect.

Fast paths for HashMap / HashSet: The HAMT-backed types also exploit structural sharing for O(1) short-circuits:

• ptr_eq — if both collections share the same root pointer they are identical; union returns one copy, difference returns empty, intersection returns one copy.
• Merkle hash — same-lineage maps with equal length and equal Merkle hash are definitively equal; the fast-path fires without comparing individual entries.

Join algorithm for OrdMap / OrdSet (B+ tree): These types use a fundamentally different parallel strategy based on Blelloch et al., "Joinable Parallel Balanced Binary Trees" (ACM TOPC 2022) and "PaC-trees" (PLDI 2022). A single structural split at the root's median key divides both inputs into independent halves, which are merged recursively in parallel via rayon::join, then concatenated with a height-aware concat. This gives:

• Work: O(m log(n/m + 2)) — optimal for set operations on inputs of size m ≤ n
• Span: O(log² n) — polylogarithmic, scales with thread count

Both the split and concat are O(log n) structural operations on the B+ tree spine — no per-entry hashing or re-insertion required. This is believed to be the first implementation of the Blelloch join algorithm on a blocked-leaf persistent B+ tree in any language. No other Rust persistent map library implements join-based parallel set operations.

Rayon-join parallelism for symmetric_difference: par_symmetric_difference on all types uses rayon::join to compute the two halves (self \ other and other \ self) simultaneously on separate threads.

use pds::{Bag, HashMap, HashSet};
use rayon::iter::ParallelIterator;

// Parallel iteration
let map: HashMap<i32, &str> = (0..10_000).map(|i| (i, "x")).collect();
let sum: i32 = map.par_iter().map(|(&k, _)| k).sum();

// Parallel set operations
let mut a = Bag::new();
let mut b = Bag::new();
a.insert_many("apple", 5);
a.insert_many("banana", 3);
b.insert_many("banana", 7);
b.insert_many("cherry", 2);

let union = a.par_union(&b);          // apple:5, banana:10, cherry:2
let intersection = a.par_intersection(&b);  // banana:3
let difference = a.par_difference(&b);     // apple:5

# Development (requires Nix)
nix develop              # enter devShell with stable Rust + sccache
bash test.sh             # run full quality gate (tests + clippy + doc)
bash bench.sh            # run criterion benchmarks
bash bench.sh vector     # run a single benchmark suite

# Nightly tools (miri, fuzzing)
nix develop .#nightly    # enter nightly devShell
cargo miri test          # run tests under miri
cd fuzz && cargo fuzz list  # list fuzz targets

This crate supports Rust 1.85 and later.

Copyright 2017–2021 Bodil Stokke Copyright 2021 Joe Neeman

This software is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/.