PyPersistent

A high-performance collection of persistent (immutable) data structures for Python, written in C++.

Features

• Immutable: All operations return new collections, leaving originals unchanged
• Structural Sharing: New versions share most structure (O(log n) changes instead of O(n) copies)
• Fast: 3-5x faster than pyrsistent, with merge operations up to 176x faster
• Thread-Safe: Immutability makes concurrent access safe without locks
• Python 3.13+ Free-Threading Ready: Lock-free design with atomic reference counting for true parallelism
• Memory Efficient: Structural sharing minimizes memory overhead
• Dual Interface: Both functional (Clojure-style) and Pythonic APIs
• Pickle Support: Native serialization for all data structures

Data Structures

PyPersistent provides five core persistent data structures:

PersistentDict

Unordered key-value map based on Hash Array Mapped Trie (HAMT).

• Use for: General-purpose dictionary needs with immutability
• Time complexity: O(log₃₂ n) ≈ 6 steps for 1M elements
• Features: Fast lookups, structural sharing, bulk merge operations
• Example:

  from pypersistent import PersistentDict
  
  m = PersistentDict.create(name='Alice', age=30)
  m2 = m.set('city', 'NYC')
  m3 = m | {'role': 'developer'}  # Merge
  

PersistentSortedDict

Sorted key-value map based on Left-Leaning Red-Black Tree.

• Use for: Ordered data, range queries, min/max operations
• Time complexity: O(log₂ n) for all operations
• Features: Sorted iteration, range queries (subseq/rsubseq), first/last
• Example:

  from pypersistent import PersistentSortedDict
  
  m = PersistentSortedDict.from_dict({3: 'c', 1: 'a', 2: 'b'})
  list(m.keys())  # [1, 2, 3] - always sorted
  
  # Range queries [start, end) - start inclusive, end exclusive
  sub = m.subseq(1, 3)  # or m[1:3]
  list(sub.keys())  # [1, 2]
  
  # Min/max
  m.first()  # (1, 'a')
  m.last()   # (3, 'c')
  

PersistentList

Indexed sequence based on bit-partitioned vector trie (RRB-Tree variant).

• Use for: Ordered sequences with efficient random access and append
• Time complexity: O(log₃₂ n) for get/set, O(1) for append
• Features: Fast indexed access, efficient append, slicing
• Example:

  from pypersistent import PersistentList
  
  v = PersistentList.create(1, 2, 3)
  v2 = v.conj(4)  # Append
  v3 = v2.assoc(0, 10)  # Update index 0
  v[1]  # 2 - indexed access
  

PersistentSet

Unordered set based on HAMT (same as PersistentDict).

• Use for: Unique collection of items, set operations
• Time complexity: O(log₃₂ n) for add/remove/contains
• Features: Fast membership testing, set operations (union, intersection, difference)
• Example:

  from pypersistent import PersistentSet
  
  s = PersistentSet.create(1, 2, 3)
  s2 = s.conj(4)  # Add
  s3 = s.disj(2)  # Remove
  2 in s  # True
  

PersistentArrayMap

Small map optimization using array of key-value pairs.

• Use for: Maps with < 8 entries (automatic optimization)
• Time complexity: O(n) linear scan, but faster than HAMT for tiny maps
• Features: Lower memory overhead, faster for very small maps
• Note: Typically used internally; PersistentDict automatically uses this for small maps

Choosing the Right Data Structure

Performance

Why Use Persistent Data Structures?

The key advantage of persistent data structures is structural sharing: when you create a modified version, the new and old versions share most of their internal structure rather than duplicating everything.

Example:

# Python dict - must copy everything
d1 = {i: f'val{i}' for i in range(10000)}
d2 = d1.copy()  # Copies all 10,000 entries
d2['new_key'] = 'new_value'

# PersistentDict - shares structure
from pypersistent import PersistentDict
m1 = PersistentDict.from_dict({i: f'val{i}' for i in range(10000)})
m2 = m1.set('new_key', 'new_value')  # Shares 99.99% of structure with m1

When to Use pypersistent

✅ Use pypersistent when:

• Creating multiple versions - Undo/redo, snapshots, version history
• Concurrent access - Multiple threads safely reading shared data without locks
• Functional programming - Immutable data flow, pure functions
• Building up collections incrementally - Each addition shares structure with previous version

❌ Use standard Python dict/list when:

• You only need one mutable version
• Maximum raw construction speed is critical
• Extremely memory-constrained environments

Performance vs Python Standard Library

PersistentDict vs dict

Key insight: Creating multiple versions through structural sharing is 24-3271x faster than copying dicts, with the advantage growing dramatically for larger collections.

PersistentList vs list

Key insight: If you need multiple versions (undo, history), PersistentList is dramatically faster.

Performance vs pyrsistent

pyrsistent is a mature pure-Python library with similar persistent data structures. pypersistent offers better performance through its C++ implementation, but with a smaller feature set.

PersistentDict Performance Comparison

Why the difference? pypersistent's C++ implementation provides:

• Optimized tree traversal and node allocation
• Cache-friendly memory layout
• Specialized bulk merge algorithms
• Direct memory manipulation without Python object overhead

Feature Comparison

Summary: Choose pypersistent for performance-critical applications with the core data structures. Choose pyrsistent for a richer feature set and pure-Python portability.

Performance by Map Size

Fast Iteration Methods

For complete iteration over small-medium dicts, use materialized list methods:

m = PersistentDict.from_dict({...})

# Fast methods (1.7-3x faster for dicts < 100K)
items = m.items_list()   # Returns list of (key, value) tuples
keys = m.keys_list()     # Returns list of keys
values = m.values_list() # Returns list of values

# Lazy iterators (better for very large dicts or early exit)
for k, v in m.items():   # Generator, O(log n) memory
    ...

Performance:

• Dicts ≤ 10K: 3x faster with items_list()
• Dicts ≤ 100K: 1.7x faster with items_list()
• Dicts > 100K: Use iterator (lazy, memory-efficient)

Technical Details

Implementation: C++ HAMT (Hash Array Mapped Trie) with:

• Bottom-up bulk construction for from_dict()
• Arena allocator for fast node allocation
• Structural tree merging for merge()
• COW semantics for collision nodes
• Fast iteration with pre-allocated lists

Time Complexity: O(log₃₂ n) ≈ 6 steps for 1M elements Space Complexity: O(n) with structural sharing across versions

For detailed performance analysis and benchmarking methodology, see docs/.

Installation

pip install pypersistent

Or build from source:

git clone https://github.com/cmarschner/pypersistent.git
cd pypersistent
python setup.py install

Use Cases

Use persistent data structures when:

• Creating multiple versions of data (undo/redo, time-travel, version history)
• Sharing data across threads without locks or defensive copying
• Functional programming patterns (immutability, pure functions)
• Creating modified copies is frequent (structural sharing makes this fast)
• Python 3.13+ free-threading for true parallelism

Use mutable collections when:

• Single mutable instance is sufficient
• Maximum raw construction speed is critical
• Memory per entry is highly constrained

Specific use cases:

• Config management: Share base config, each thread creates customized version
• Event sourcing: Maintain history of all states efficiently
• Reactive programming: Pass immutable state between components
• Concurrent caching: Multiple threads read/update cache without locks
• Functional data pipelines: Transform data through pipeline stages

How It Works

PyPersistent implements multiple classic persistent data structures:

PersistentDict - Hash Array Mapped Trie (HAMT)

Based on the HAMT data structure used by Clojure, Scala, and Haskell:

• 32-way branching tree indexed by hash bits
• Path copying for immutability
• Structural sharing between versions
• std::shared_ptr for entry sharing (44x fewer INCREF/DECREF)
• Inline storage with std::variant for cache-friendly access

PersistentSortedDict - Left-Leaning Red-Black Tree

Self-balancing binary search tree with:

• Path copying for immutability
• Sorted order maintenance (O(log₂ n))
• Atomic reference counting for node sharing
• Range query support via tree traversal

PersistentList - Bit-Partitioned Trie

32-way branching tree for indexed access:

• Path copying for updates
• Tail optimization for fast append
• O(log₃₂ n) random access (~6 steps for 1M elements)
• Efficient slicing via structural sharing

PersistentSet - HAMT-based Set

Uses PersistentDict internally with:

• Keys as set elements
• Same O(log₃₂ n) complexity
• Set algebra operations

PersistentArrayMap - Simple Array

Linear array for tiny dicts (< 8 entries):

• Lower overhead than HAMT for small sizes
• O(n) operations but faster than tree for n < 8
• Automatically used by PersistentDict when beneficial

Technical Details

Complexity:

• PersistentDict/HashSet: O(log₃₂ n) ≈ 6 steps for 1M elements
• PersistentSortedDict: O(log₂ n) for all operations
• PersistentList: O(log₃₂ n) get/set, O(1) append
• PersistentArrayMap: O(n) but fast for n < 8

Implementation:

• C++ with pybind11 bindings
• Atomic reference counting (std::atomic<int>)
• Structural sharing for memory efficiency
• Thread-safe reads (fully immutable)

Python 3.13+ Free-Threading Support

PyPersistent is fully compatible with Python 3.13's experimental free-threading mode (nogil), making it ideal for parallel workloads:

Why It Works

1. Lock-Free Reads: Immutable data structure allows concurrent reads without synchronization
2. Atomic Reference Counting: Internal C++ reference counting uses std::atomic operations
3. Thread-Safe Entry Storage: Uses std::shared_ptr with built-in thread-safe reference counting
4. Independent Updates: Each thread can create new versions without blocking others

Usage with Free-Threading

# Python 3.13+ with --disable-gil or PYTHON_GIL=0
import threading
from pypersistent import PersistentDict

# Shared base dict
base_config = PersistentDict.create(
    api_url='https://api.example.com',
    timeout=30,
    retries=3
)

def process_request(thread_id, data):
    # Each thread creates its own version - no locks needed!
    my_config = base_config.set('thread_id', thread_id)
    my_config = my_config.set('request_data', data)

    # Concurrent reads are completely lock-free
    url = my_config['api_url']
    timeout = my_config['timeout']

    # Do work...
    return my_config

# Spawn threads - true parallelism without GIL!
threads = []
for i in range(100):
    t = threading.Thread(target=process_request, args=(i, f'data_{i}'))
    threads.append(t)
    t.start()

for t in threads:
    t.join()

Performance Benefits

Without the GIL:

• Parallel reads: Multiple threads read simultaneously without contention
• Parallel updates: Each thread creates new versions independently
• No lock overhead: Zero synchronization cost for immutable operations
• Structural sharing shines: Creating 100 thread-local variants is 3000x faster than copying dicts

Enable Free-Threading

# Python 3.13+
python3.13 --disable-gil your_script.py

# Or set environment variable
export PYTHON_GIL=0
python3.13 your_script.py

Note: Free-threading is experimental in Python 3.13. Some packages may not be compatible yet.

Development

# Install development dependencies
pip install pytest pybind11

# Build extension
python setup.py build_ext --inplace

# Run all tests
pytest -v

# Run specific data structure tests
pytest test_persistent_dict.py -v
pytest test_persistent_sorted_dict.py -v
pytest test_persistent_list.py -v
pytest test_persistent_set.py -v

# Run performance benchmarks
python performance_test.py
python performance_vector.py

License

MIT License - see LICENSE file for details

Credits

Inspired by Clojure's persistent data structures and the HAMT paper by Bagwell (2001).

Implementation by Clemens Marschner.