CowVec

A vector-like container optimized for efficient cloning with copy-on-write semantics.

Motivation

In many algorithms, we need to clone a vector and then make small modifications to the clone. With a standard Vec, cloning is O(n) - every element must be copied. For large vectors with frequent cloning, this becomes a performance bottleneck.

CowVec solves this by:

1. Storing all values in a shared arena (via Arc)
2. Each instance maintains a vector of pointers into the arena (also via Arc)
3. Cloning is O(1) - just incrementing reference counts
4. The pointer vector is copied only on first mutation (copy-on-write)

This makes cloning O(1) regardless of vector size - the actual copying is deferred until (and only if) a mutation occurs.

Use Cases

• Backtracking algorithms: Clone state, explore a branch, discard or keep
• Undo/redo systems: Maintain history of states efficiently
• Parallel exploration: Share base state across threads, each making local modifications
• Immutable data structures: Build persistent vectors with structural sharing

API Overview

use cow_vec::CowVec;

// Create from Vec
let mut vec = CowVec::from(vec![1, 2, 3, 4, 5]);

// Clone is cheap - shares the arena
let mut clone = vec.clone();

// Modifications are independent (copy-on-write)
clone.set(0, 100);
assert_eq!(vec[0], 1);      // Original unchanged
assert_eq!(clone[0], 100);  // Clone has new value

// Standard vector operations
vec.push(6);
vec.pop();
vec.reverse();
let v: Vec<i32> = vec.to_vec();

// Introspection: check sharing status
let vec1 = CowVec::from(vec![1, 2, 3]);
let mut vec2 = vec1.clone();
assert!(vec1.is_structure_shared());  // Pointer vector is shared
assert!(vec1.is_storage_shared());    // Arena is shared

vec2.push(4);  // Triggers COW on structure
assert!(!vec2.is_structure_shared()); // vec2 now has its own pointer vector
assert!(vec2.is_storage_shared());    // Arena still shared

Limitations

No Element Removal from Arena

The arena is append-only. When you call pop(), remove(), clear(), or truncate(), the values remain allocated in the arena - only the pointers are removed from this instance's view.

let mut vec = CowVec::from(vec![1, 2, 3]);
vec.pop();  // Value 3 still exists in arena, just not accessible via `vec`

Implication: If you repeatedly push and pop elements, memory usage grows. This design is optimized for scenarios where you build up data and clone frequently, not for long-lived mutable collections.

Mitigation: Use clone_with_max_capacity(n) to compact the arena when cloning:

let mut vec = CowVec::from(vec![1, 2, 3]);

// Many operations accumulate garbage in the arena
for i in 0..100 {
    vec.set(0, i);
}
// Arena now has 103 allocations, but only 3 are live

// Clone with compaction if arena exceeds 10 allocations
let compacted = vec.clone_with_max_capacity(10);
// compacted has a fresh arena with only 3 allocations

No Mutable Access

You cannot get &mut T references to elements. The set() method allocates a new value in the arena rather than mutating in place.

// This won't compile:
// let x: &mut i32 = vec.get_mut(0);

// Instead, use set():
vec.set(0, new_value);  // Allocates new value, updates pointer

Clone Requires T: Clone for set()

The set() method requires T: Clone because it allocates a new copy in the arena.

Memory Overhead

Each CowVec instance stores:

• Arc<CowArena<T>> (pointer + reference count)
• Arc<Vec<*const T>> (shared pointer vector, pointer per element)

Clones share both the arena and the pointer vector until mutation. For very small types (e.g., u8), the pointer overhead may exceed the element size. Consider using standard Vec for small, cheap-to-copy types.

Implementation Details

Arena Storage

Values are stored in a typed_arena::Arena<T> wrapped in Mutex for thread-safe allocation:

struct CowArena<T> {
    arena: Mutex<Arena<T>>,
}

The arena guarantees that allocated values are never moved or deallocated until the arena itself is dropped. This allows us to store raw pointers safely.

Pointer Storage

Each CowVec instance maintains a shared vector of raw pointers:

pub struct CowVec<T> {
    arena: Arc<CowArena<T>>,
    items: Arc<Vec<*const T>>,
}

The items vector is wrapped in Arc for O(1) cloning. On mutation, Arc::make_mut() is used to clone the vector only if it's shared with other instances (copy-on-write for the structure itself).

Safety Invariants

The use of raw pointers is safe because:

1. Stable addresses: typed_arena guarantees values are never moved once allocated
2. Lifetime guarantee: Values are only dropped when the Arena drops, which only happens when all Arc references are gone
3. No dangling pointers: As long as a CowVec exists, it holds an Arc to the arena, keeping all values alive

Thread Safety

CowVec<T> implements Send and Sync when T: Send + Sync:

• Arena mutations (push) are protected by Mutex
• Reading via pointers requires no synchronization (immutable access)
• Each thread's CowVec instance has its own pointer vector

Copy-on-Write

Copy-on-write operates at two levels:

1. Structure level: The pointer vector is shared via Arc. On first mutation, if shared, the vector is cloned.
2. Value level: The set() method allocates a new value in the arena and updates only this instance's pointer.

pub fn set(&mut self, index: usize, value: T) {
    let ptr = self.arena.alloc(value);  // Allocate new value
    self.items_mut()[index] = ptr;      // COW: clone vec if shared, then update
}

Other clones continue pointing to the original values with their original structure.

Performance Characteristics

Note: "COW if shared" means the pointer vector is cloned only if this instance shares it with other clones. This is a one-time O(n) cost on first mutation.

Example: A vector of 42 million objects, where each element contains nested Vecs, HashMaps, and Strings:

• Regular Vec clone: Runs 42M Clone::clone() calls, each allocating memory, copying nested structures, updating reference counts, and potentially triggering the allocator
• CowVec clone: O(1) - just two atomic reference count increments, regardless of size
• First mutation after clone: A single memcpy of 42M × 8 = ~320 MB of pointers

The deferred copy is hardware-optimized on modern CPUs:

• x86 (Ivy Bridge+): Uses ERMSB (Enhanced REP MOVSB) with automatic vectorization
• ARM64: Uses optimized LDP/STP (load/store pair) sequences copying 16+ bytes per cycle

At ~50 GB/s memory bandwidth, copying 320 MB of pointers takes ~6ms - but only when you actually mutate.

Related Work: Persistent Data Structures

CowVec implements a form of persistent data structure with structural sharing - a well-known pattern in functional programming where data structures preserve previous versions when modified.

Terminology

• Persistent Data Structure: A data structure that always preserves the previous version of itself when modified.
• Structural Sharing: When copies share most of their memory, only allocating new memory for changed parts.
• Copy-on-Write (COW): The lazy copying strategy where clone is cheap and actual copying happens on modification.

Existing Rust Crates

Several mature crates implement persistent vectors with more sophisticated algorithms:

How CowVec Differs

CowVec is a simpler, specialized variant optimized for low-latency access and cheap cloning of large elements:

Key trade-offs:

• CowVec clone is O(1) - just two atomic reference count increments. The pointer vector is copied only on first mutation (if shared).
• CowVec has O(1) random access (direct pointer lookup) vs O(log n) for tree-based structures.
• CowVec uses arena allocation (bump pointer, no syscalls) vs tree-based structures that allocate O(log n) nodes per modification through the standard allocator.
• CowVec does not reclaim memory automatically; use clone_with_max_capacity() for compaction.
• CowVec is simpler with less overhead for small-to-medium sized vectors.

Cache locality and low-latency access:

• The pointer vector is contiguous in memory, enabling efficient CPU cache prefetching during iteration.
• Random access is a single pointer dereference with no tree traversal, ideal for latency-sensitive code.
• Tree-based structures like im require following multiple pointers through tree nodes, causing cache misses.
• For hot loops accessing elements by index, CowVec provides predictable, low-latency performance.

Choose CowVec when:

• You clone frequently but modify sparingly (or not at all).
• You need O(1) indexed access with minimal latency.
• Cache-friendly iteration performance matters.
• Vectors are short-lived or periodically compacted.
• Simplicity matters.

Choose im/rpds when:

• You perform many modifications across many clones.
• Automatic memory reclamation is important.
• You're building long-lived persistent data structures.

When to Use CowVec

Good fit:

• Large elements (structs, strings, nested containers)
• Frequent cloning with few modifications per clone
• Algorithms that explore multiple branches from a common state
• Short-lived instances where arena memory growth is acceptable

Poor fit:

• Small, cheap-to-copy types (use Vec)
• Long-lived mutable collections with many add/remove cycles
• Need for mutable element access (&mut T)
• Memory-constrained environments where arena growth is problematic