im (Rust)Archived

Persistent collections for Rust: an RRB-tree Vector, a hash array mapped trie HashMap and B-tree OrdMap, with O(1) cloning and copy-on-write updates. Unmaintained since 2022.

What it is: Purely functional data structures (rrb vectors)
Type: Open source
Made by: Bodil Stokke
License: MPL-2.0 (LGPL-3.0 before version 10)
Status: Archived since 29 April 2022
Facts checked: 9 October 2026

What it is

The im crate offers immutable versions of the standard collections: Vector (an RRB tree), HashMap and HashSet (hash array mapped tries) and OrdMap and OrdSet (B-trees). Each tree node holds up to 64 values. Cloning a collection only bumps the reference count on its root; nodes are copied lazily, when one of the clones changes them, and then only the changed node and its parents. Values must implement Clone, so expensive values are best wrapped in Rc or Arc.

Rust’s ownership rules let im skip the usual price of immutability. If a node’s reference count says nobody else shares it, an update changes it in place, about an order of magnitude faster than copying and close to the standard collections, so there is no need for Clojure-style transients. The API follows std::collections, with mutating methods such as push_back and insert by default. im uses thread-safe Arc counters; the twin crate im-rc uses Rc and is about 20 to 25 percent faster but can’t be shared between threads. Vector acts like a plain array until it outgrows one chunk, then adds O(log n) concatenation and splitting, which Vec and VecDeque can’t do.

Bodil Stokke published the crate in April 2017. Version 11.0.0 (July 2018) rewrote Vector as an RRB tree and moved to a std-style API, and 12.0.0 split it into im and im-rc. The last release, 15.1.0, came out in April 2022 and the repository has since been archived. imbl, a fork that keeps the API and fixes bugs, carries the design on.

Why teams pick it

O(1) clone and structural sharing make snapshots, undo history and sharing data between threads cheap
Copy-on-write in place when a node isn’t shared, so code that never clones runs almost as fast as with std::collections
Vector concatenates, splits and inserts in the middle in O(log n), which Vec and VecDeque can’t
An API close to std::collections, so HashMap and BTreeMap code ports with few changes

Watch out for

Unmaintained: no release since 15.1.0 in April 2022 and the repository is archived; new projects should use the imbl fork
Slower than the standard collections at what they do best: Vec wins below several hundred elements, and OrdMap runs 2 to 3 times slower than BTreeMap
Values must be Clone; expensive values need wrapping in Rc or Arc to avoid deep copies

Alternatives, recommended first

What all rrb vectors have in common →

imblOpen sourceThe maintained fork of Rust’s `im` crate: persistent collections with an RRB-tree `Vector`, a hash array mapped trie `HashMap` and a B+ tree `OrdMap`, with O(1) cloning and copy-on-write updates.immerOpen sourceA header-only C++ library of persistent, immutable containers, including an RRB-tree `flex_vector` with O(log n) concatenation and slicing and policy-based memory management.

How it fits with other technologies

What im (Rust) uses

im (Rust)is a collections crate forRustProgramming languages

O(1) clones, copy-on-write updates and RRB concatenation (`im = "15.1.0"`) · rust

use im::{HashMap, Vector};

fn main() {
    let v1: Vector<u32> = (0..100_000).collect();

    // clone is O(1): it only bumps the root's reference count
    let mut v2 = v1.clone();
    v2.set(0, 42); // copies the changed chunk and its path to the root
    println!("{} {}", v1[0], v2[0]); // 0 42

    // RRB trees concatenate and split in O(log n)
    let mut joined = v1.clone();
    joined.append(v2.clone());
    let tail = joined.split_off(150_000);
    println!("{} {}", joined.len(), tail.len()); // 150000 50000
    println!("{:?}", tail.head()); // Some(50000)

    // HashMap is a hash array mapped trie; update returns a new map
    let prices = HashMap::unit("tea", 3);
    let more = prices.update("cake", 5);
    println!("{} {}", prices.len(), more.len()); // 1 2
}

See it in a real stack

No architecture uses im (Rust) yet. Drop it into the playground and wire it up yourself.Open playground →

Where it came from2017–2022

Bodil Stokke published im on crates.io on 17 April 2017. Stokke’s argument was unusual for Rust: the type system already prevents accidental mutation, so the selling point of immutable collections is structural sharing, making a copy as cheap as copying a pointer, and a single default collection with no slow operations to trip over.

Version 11.0.0 (July 2018) was a rewrite. Vector became an RRB tree with head and tail chunks, following the ICFP 2015 RRB vector paper, replacing a Clojure-style vector trie; values were stored directly in nodes instead of behind an Arc; and the API was aligned with std::collections, mutable by default. Version 12.0.0 (August 2018) split the crate into im (thread-safe Arc) and im-rc (faster Rc). Releases continued to 15.0.0 (May 2020) and 15.1.0 (April 2022), after which development stopped. Joe Neeman forked it as imbl in August 2021, and that fork is still released.

Why it’s built this way

An RRB tree as the only list type: It is never much worse than iterating over the data: O(log n) split and join on top of fast indexing, so users don’t have to pick a specialised list per task.
Copy-on-write instead of transients: Reference counts show whether a node is shared, so unshared nodes are updated in place automatically, without a separate mutable mode.
Values stored directly in nodes: From 11.0.0, values of any Clone type live inside the nodes instead of behind an Arc each, at least doubling speed for Copy values and improving cache locality.
Two crates: im and im-rc: Atomic reference counts make collections Send and Sync but cost speed, so the same code is published twice, with Arc and with Rc.

Timeline

2017
Bodil Stokke publishes the first versions of im (April)
2018
10.0.0, the first release called stable (March); 11.0.0 rewrites Vector as an RRB tree (July)
2020
15.0.0 (May)
2021
Joe Neeman forks it as imbl
2022
15.1.0, the last release (April); the repository is later archived

Sources5 · facts checked 9 October 2026

Improve this page on GitHub