cow_vec

Clone a vector in constant time. When that clone starts writing, you copy pointers — never the elements themselves.

You get two types that behave the same from the outside and disagree about what happens the first time a clone writes:

	CowVec<T>	PagedVec<T>
Layout	one flat pointer array	pointer pages behind a small root table
clone()	O(1)	O(1)
First mutation after clone	copies the whole pointer array	copies the root table + touched pages
Diverge 50 elements of 4M	~32 MB copied	~0.4 MB copied
Indexed access	1 pointer hop	2 pointer hops (root stays in cache)
pop / truncate after clone	copies the kept prefix (clear: nothing)	copies nothing
Extras	sort/dedup/binary_search, append, split_off, splice, as_slice	sort, append (shares whole pages), insert/remove/splice, swap

CowVec is the one you want when clones rarely write — or they rewrite everything at once — and most of the time you are just reading. PagedVec is for the other life: you keep deriving new versions from old ones. Version chains, undo history, branch-and-discard search. Code that does not want to decide can be generic over the CowVector trait, which names the API the two have in common.

Quick start

use cow_vec::CowVec;

let base = CowVec::from(vec![
    String::from("alpha"),
    String::from("beta"),
    String::from("gamma"),
]);

// Instant. Shares storage and structure with `base`.
let mut branch = base.clone();

// Only `branch` sees this. The Strings in `base` are never cloned.
branch.set(1, String::from("BETA"));
branch.make_mut(2).push_str("!");

assert_eq!(base.to_vec(), ["alpha", "beta", "gamma"]);
assert_eq!(branch.to_vec(), ["alpha", "BETA", "gamma!"]);

PagedVec has the same API. It starts earning its keep once versions chain:

use cow_vec::PagedVec;

let mut versions: Vec<PagedVec<u64>> = vec![(0..100_000).collect()];

// Each generation: clone the last version, poke a couple of elements.
// You pay for the root table plus one 8 KB page per page you touch —
// not the whole vector.
for gen in 1..10 {
    let mut next = versions.last().unwrap().clone();
    next.set(50_000, gen);
    next.set(99_999, gen);
    versions.push(next);
}

assert_eq!(versions[0][50_000], 50_000); // every version is still intact
assert_eq!(versions[9][50_000], 9);

A nice side effect of the pointer representation: sorting a CowVec of megabyte-sized structs shuffles 8-byte pointers. The structs stay put.

use cow_vec::CowVec;

let mut vec = CowVec::from(vec![
    String::from("pear"),
    String::from("apple"),
    String::from("plum"),
]);
vec.sort_by(|a, b| a.cmp(b)); // permutes pointers only
assert_eq!(vec.to_vec(), ["apple", "pear", "plum"]);

Concatenation is the same story — pointers move, elements don't:

use cow_vec::CowVec;

let mut a = CowVec::from(vec![1, 2]);
let b = CowVec::from(vec![3, 4]);
a.append(&b); // b's storage stays alive; nothing is cloned
assert_eq!(a, vec![1, 2, 3, 4]);

Choosing a container (including someone else's)

You clone a lot and mutate a little. Here is the honest lineup:

	clone	diverge k of n elements	access	reclaims memory	unsafe-free
Vec<T>	deep copy	(clone is the cost)	contiguous, fastest	yes	yes
Arc<Vec<T>> + make_mut	O(1)	clones all n elements	contiguous, fastest	yes	yes
Arc<Vec<Arc<T>>> + make_mut	O(1)	n Arc bumps + k allocs	1 hop	per element	yes
imbl::Vector<T>	O(1)	O(k log n) node copies	~5 hops at 4M	automatic	yes
CowVec<T>	O(1)	n pointer memcpy, once	1 hop	via compaction	no
PagedVec<T>	O(1)	root + touched pages	2 hops	via compaction	no

• If T is cheap to clone — numbers, small structs — use Arc<Vec<T>> and stop reading. Element clones are the cost this crate exists to avoid, and yours are free.
• If you want automatic reclamation and you edit heavily across many versions, imbl is excellent. The trade is tree-depth access.
• This crate's niche is expensive-to-clone elements + snapshot-style work + flat, predictable access. Divergence costs pointer copies. Access stays a fixed number of pointer hops. (A "hop" here is one dependent pointer dereference beyond the container's own header: what Vec<T> pays none of and Vec<Arc<T>> pays one of.)

How it works

Both types split structure from storage:

CowVec                                PagedVec
------                                --------
items: Arc<Vec<*const T>>             pages: Arc<Vec<Arc<Page>>>
            |                                    |         Page = [*const T; 1024]
            v                                    v
       +---------------------- storage ----------------------+
       |  active bump arena  <-  frozen keep-alive chain     |
       +-----------------------------------------------------+

Structure is the pointer table. It is shared through Arc and copied on first write (Arc::make_mut). CowVec copies the whole thing; PagedVec copies the root table and whichever 8 KB pages you actually touch.

Storage is bump arenas, append-only for as long as they are shared. An instance only allocates into an arena it uniquely owns. The first allocation after a clone freezes the now-shared arena onto an Arc keep-alive chain and starts a fresh one. That is why push/set never take a lock: clones on different threads never fight over the same arena. Values never move, so the raw pointers in the structure stay valid as long as any descendant is still holding the chain.

Performance characteristics

Operation	CowVec	PagedVec
clone()	O(1)	O(1)
first mutation after clone	O(n) pointer memcpy	O(PAGE_SIZE) per touched page
get() / [i]	O(1), 1 hop	O(1), 2 hops
push()	O(1) amortized, no lock	O(1) amortized, no lock
set()	O(1) + COW	O(1) + page COW
pop() / truncate(k) / clear()	O(1); O(k) prefix copy if shared	O(1), copies nothing
insert(i) / remove(i)	O(n - i) pointer memmove	O(n - i) pointer copies, rewrites pages after i
sort_*()	O(n log n) pointer swaps	O(n log n) pointer swaps, rewrites every page
append()	O(m) pointer copies	O(m) pointer copies; O(m / PAGE_SIZE) if page-aligned
bulk build (from/collect)	one allocation batch, values contiguous	same

Benchmarks

Median criterion times on an Apple M1 Pro. Elements are structs that own a String, so cloning one actually allocates — the world these containers are built for. "50 edits" replaces 50 scattered elements after a clone. "chained" derives 32 such generations from each other and keeps every version around.

Scenario	Vec	Arc<Vec>	Arc<Vec<Arc>>	imbl	CowVec	PagedVec
clone, 100k	2.5 ms	9.5 ns	—	19 ns	12 ns	12 ns
clone + 50 edits, 100k	1.3 ms	1.3 ms	253 µs	55 µs	17 µs	15 µs
clone + 50 edits, 1M	13.3 ms	13.5 ms	2.5 ms	63 µs	194 µs	24 µs
32 chained generations, 1M	—	—	81 ms	2.5 ms	8.2 ms	1.1 ms
10k random reads, 1M	7.8 µs	—	15.8 µs¹	330 µs	16.9 µs	17.2 µs
full iteration, 1M	0.53 ms	—	1.00 ms¹	2.7 ms	0.67 ms	0.71 ms
build from Vec, 100k	—	—	—	923 µs	14 µs	55 µs

¹ measured as Vec<Arc<T>> (the read path is identical).

What the numbers actually mean:

• Divergence is where this crate lives. A 50-edit version of a 1M-element vector: PagedVec 24 µs, imbl 63 µs, CowVec 194 µs, and the usual Arc<Vec<Arc<T>>> at 2.5 ms. Arc<Vec<T>> just pays the full 13.5 ms element-clone bill — the one O(1)-clone types exist to spare you.
• Access stays flat. Random reads through CowVec/PagedVec cost about the same as through a plain Vec<Arc<T>> (one pointer chase) and ~20× less than walking imbl's tree. Iteration lands within about a third of a plain Vec, and ahead of Vec<Arc<T>>.
• Those read numbers are for a freshly built vector, whose values sit in one chunk in index order. After every element has been replaced in scattered order (cargo bench -- dirty), random reads are unchanged (17 µs), but full iteration of 1M elements takes 2.2 ms for both types: still ahead of an equally scattered Vec<Arc<T>> at 3.0 ms, and compact brings it back to 0.67 ms.
• Chained generations are why PagedVec exists. That workload runs 7× faster than CowVec (which recopies the whole pointer table every generation) and 2.2× faster than imbl.

Time is the weaker half of the chained-generation story. Keeping 32 versions of a 1M-element vector alive costs this much memory beyond the base vector (cargo run --release --example memory):

	Arc<Vec<Arc>>	imbl	CowVec	PagedVec
extra memory, 32 live versions	244 MB	7.5 MB	244 MB	12.6 MB
per version	7.6 MB	0.24 MB	7.6 MB	0.39 MB

Every CowVec version keeps its own 8 MB pointer table, exactly like Arc<Vec<Arc<T>>>; a PagedVec version shares every page it did not touch, so 50 edits cost about 50 pages plus a root table.

Reproduce with cargo bench. Hardware moves the numbers; the ratios are the point.

Memory model and compaction

Storage is append-only while anything else can see it. set, pop, remove, and clear on a vector with live clones leave the old values in place, because a clone might still be pointing at them, and the arenas hand out pointers that cannot move.

Once a vector is the sole owner of its storage (never cloned, or every clone and ancestor is gone) it behaves like Vec again: pop and remove move values out, set and truncate drop the replaced values on the spot, make_mut hands out the slot itself, and freed slots are reused by later writes, so mutating in a loop does not grow the storage.

Garbage accumulates only for values a clone can still see. A version history is the typical case, and two tools deal with it:

use cow_vec::CowVec;

let mut vec = CowVec::from(vec![1, 2, 3]);
let history: Vec<CowVec<i32>> = (0..100)
    .map(|i| {
        let snapshot = vec.clone();
        vec.set(0, i); // the snapshot still sees the old value
        snapshot
    })
    .collect();
assert_eq!(vec.storage_allocations(), 103); // 3 live + 100 kept for history

// Rebuild in place once you are past a threshold. With the history gone,
// nothing else shares the storage, so the elements are moved, not cloned:
drop(history);
vec.compact(50);
assert_eq!(vec.storage_allocations(), 3);

// Or build a compacted copy and keep the original as it is:
let copy = vec.clone_compacted(0);
assert_eq!(copy, vec);

Drop every clone of a lineage and all of its arenas go with it. A vector that outlives its clones takes their arenas back on its next mutation. Keep-alive chains drop iteratively, so a version chain hundreds of thousands of generations deep unwinds without blowing the stack.

Limitations

• &mut T costs a clone while the storage is shared. make_mut hands out the slot directly only when nothing else references the storage; otherwise it clones into a fresh slot first. There is no in-place mutation that other clones could see — that is the point.
• pop/remove/splice need T: Clone because, while the storage is shared, the original has to stay put for everyone else. They move the value out when it is not. truncate works for any T.
• History is garbage until you compact, as above. A sole owner reuses its slots, but every value a live clone can still see stays allocated, and so does its slot after that clone is gone, until the next compact.
• Small cheap elements do not belong here. The pointer hop and per-element allocation are pure overhead — use Vec or Arc<Vec<T>>.

Safety and testing

This crate is raw pointers into arenas that never move a value while anything else can see it, so verification is part of the product:

• The entire test suite runs under Miri (Stacked Borrows) in CI — concurrency tests included. Pointer provenance is preserved through every allocation path.
• Both types share one behavior suite (the parity contract). PagedVec runs it at page sizes 1024 and 8, so page-boundary logic is hammered.
• Page-granularity tests check which pages diverge on a mutation, not just that the values come out right.

Migration from 1.x

1.x	2.0
vec[i] = x (via IndexMut)	vec.set(i, x)
vec[i] += 1	*vec.make_mut(i) += 1
vec.pop() → Option<&T>	vec.pop() → Option<T> (T: Clone)
vec.remove(i) → &T	vec.remove(i) → T (T: Clone)
vec.splice(..) → Vec<&T>	vec.splice(..) → Vec<T>
vec.position(p)	vec.iter().position(p)
vec.clone_with_max_capacity(n)	vec.clone_compacted(n)

1.x also had a soundness bug in IndexMut: a write through a pointer that had lost write provenance — undefined behavior, found by Miri. 2.0 fixes the provenance handling everywhere and takes the footgun API out.

License

MIT