v2.0.0

⏺ Summary of Changes: v1.0.0 → v2.0.0

Breaking Changes 🔴

Pythonic Class Names

• PersistentMap → PersistentDict
• PersistentVector → PersistentList
• PersistentHashSet → PersistentSet
• PersistentTreeMap → PersistentSortedDict

Dual API Introduction

Both functional (Clojure-style) and Pythonic methods now available:

• Pythonic: .set(), .delete()
• Functional: .assoc(), .dissoc()

New Data Structures 🎉

v1.0.0 only had PersistentMap. v2.0.0 adds:

• ✨ PersistentList - Indexed sequence (bit-partitioned trie)
• ✨ PersistentSet - Unique elements collection (HAMT-based)
• ✨ PersistentSortedDict - Sorted map with range queries (Red-Black Tree)
• ✨ PersistentArrayMap - Optimized for small maps (<8 entries)

Total: 1 → 5 data structures

New Features ✨

1. Native Pickle Support
   - All data structures fully serializable
   - pickle.dumps() / pickle.loads() work out of the box
2. Slice Notation for Range Queries
   - PersistentSortedDict: scores[20:50] as alias for subseq(20, 50)
   - More Pythonic range query syntax
3. Comprehensive Documentation
   - Interactive Jupyter notebook with 8 sections
   - Google Colab ready
   - Performance comparisons
   - Real-world use cases
4. Operator Overloads
   - Merge operator | for all dict types
   - Set operators &, -, ^ for PersistentSet

Bug Fixes 🐛

1. Fixed PersistentSortedDict reference counting
   - Resolved segfaults during garbage collection
   - Fixed iterator dangling pointer bug
   - All 50 tests now passing (was 17/50)
2. Fixed merge operations
   - No more crashes on large merges
   - Correct count tracking
3. Windows Build Support
   - Replaced ssize_t with Py_ssize_t
4. Iterator Safety
   - Fixed dangling pointer causing segfault

Code Quality Improvements 🔧

1. Zero Compiler Warnings
   - Fixed deprecated get_type() → py::type::of()
   - Marked unused parameters
   - Removed dead code
2. Better Test Coverage
   - Comprehensive tests for all data structures
   - Pickle tests (17 new tests)
   - Edge case coverage
3. Organized Project Structure
   - Tests moved to tests/ directory
   - Python scripts to scripts/ directory
   - C++ files renamed to match Python classes

Performance 🚀

(Same as v1.0.0, but now across more data structures)

• 3-5x faster than pyrsistent
• 24-3271x faster for structural sharing
• Merge operations up to 176x faster

Documentation 📚

1. Updated README
   - Corrected examples for all APIs
   - Added pickle documentation
   - Clear breaking changes section
   - Performance benchmarks
2. New Jupyter Notebook
   - 32 interactive cells
   - Covers all 4 main data structures
   - Performance demos
   - Real-world examples (undo/redo, thread safety)

Commits Summary

• 42 commits between v1.0.0 and v2.0.0
• 4 new data structures implemented
• Multiple critical bugs fixed
• Complete API overhaul for Pythonic conventions

v2.0.0b3

Bump version

v2.0.0b2

Add support for pickle.

Full Changelog: v2.0.0a3...v2.0.0b2

v2.0.0b1

Renamed classes to be more pythonic.

v2.0.0-a3

Hotfix

v2.0.0-a2

Fill up missing standard functions for the new classes

v2.0.0-a1

Hotfix

v2.0.0-alpha

---

Release 2.0.0 Alpha - Major Feature Expansion

Overview

This is a major alpha release that expands PyPersistent from a single data structure (PersistentMap) to a complete suite of five persistent data structures. This represents a 5,700+ line addition with comprehensive tests and documentation.

⚠️ Alpha Release Notice: This is a pre-release for testing. While all tests pass, we recommend thorough evaluation before production use.

New Data Structures (4)

1. PersistentTreeMap - Sorted Map

• Implementation: Left-Leaning Red-Black Tree
• Use case: Sorted key-value storage with range queries
• Time complexity: O(log₂ n) for all operations
• Key features:
  • Maintains sorted order of keys
  • Range queries: subseq(), rsubseq()
  • Min/max operations: first(), last()
  • Full test coverage: 50/50 tests passing
  • Fixed: 9 critical reference counting bugs discovered and resolved

2. PersistentVector - Indexed Sequence

• Implementation: 32-way bit-partitioned trie with tail optimization
• Use case: Indexed sequences with fast append and random access
• Time complexity: O(log₃₂ n) for get/set, O(1) for append
• Key features:
  • Fast indexed access: v[idx]
  • Efficient append: conj(item)
  • Slicing support: v[start:end]
  • Negative indexing: v[-1]

3. PersistentHashSet - Unordered Set

• Implementation: HAMT-based (same as PersistentMap)
• Use case: Unique collections with set operations
• Time complexity: O(log₃₂ n) for add/remove/contains
• Key features:
  • Set algebra: union (|), intersection (&), difference (-)
  • Membership testing: item in s
  • Functional operations: conj(), disj()

4. PersistentArrayMap - Small Map Optimization

• Implementation: Linear array of key-value pairs
• Use case: Tiny maps (< 8 entries) with lower overhead
• Time complexity: O(n) but faster than HAMT for small n
• Key features:
  • Lower memory overhead
  • Faster than tree-based structures for tiny maps
  • Can be used directly or as internal optimization

Major Changes
Documentation

• Comprehensive README rewrite (375 lines changed)
  • Added "Data Structures" section with detailed descriptions
  • Added "Choosing the Right Data Structure" comparison table
  • Complete usage examples for all five data structures
  • Updated API reference covering all types
  • Expanded "How It Works" with implementation details

Bug Fixes

• Windows build compatibility: Fixed ssize_t → Py_ssize_t for MSVC compatibility
• PersistentTreeMap reference counting: Fixed 9 critical bugs causing segfaults
  • Fixed rotateLeft() and rotateRight() reference counting
  • Fixed flipColors() double-counting children
  • Fixed balance() releasing refcount=0 nodes
  • Fixed insert() and remove() child reference handling

Testing

• 1,734 new test lines across 4 new test files:
  • test_persistent_tree_map.py - 50 tests (100% passing)
  • test_persistent_vector.py - comprehensive coverage
  • test_persistent_hash_set.py - set operations and edge cases
  • test_persistent_array_map.py - small map behavior

Performance

• New performance_vector.py benchmark suite (514 lines)
• Vector operations benchmarked against lists

Code Statistics

17 files changed, 5,739 insertions(+), 85 deletions(-)

New files:

• src/persistent_tree_map.{cpp,hpp} - 932 lines
• src/persistent_vector.{cpp,hpp} - 595 lines
• src/persistent_hash_set.{cpp,hpp} - 340 lines
• src/persistent_array_map.{cpp,hpp} - 433 lines
• Test files - 1,734 lines
• Performance benchmarks - 514 lines

Breaking Changes

None - all v1.x API remains compatible.

Migration from v1.0.1

No code changes required. v2.0.0a0 is fully backward compatible with v1.0.1. Simply upgrade and start using the new data structures:

from pypersistent import (
PersistentMap, # Existing
PersistentTreeMap, # NEW
PersistentVector, # NEW
PersistentHashSet, # NEW
PersistentArrayMap, # NEW
)

Platform Support

• Linux: x86_64, ARM64 (aarch64)
• macOS: Intel (x86_64), Apple Silicon (arm64)
• Windows: x86_64 (AMD64)
• Python: 3.10, 3.11, 3.12, 3.13, 3.14

Known Issues

None currently identified. This is an alpha release - please report any issues at https://github.com/cmarschner/pypersistent/issues

What's Next (v2.0.0 final)

• Real-world testing feedback
• Performance optimization based on usage patterns
• Additional examples and documentation

---

Full Changelog: v1.0.1...v2.0.0alpha

v1.0.1

Hotfix: Memory refcounting issue

v1.0.0

Initial Release of PersistentMap