Skip to content

v2.0.0-alpha

Choose a tag to compare

View all tags
@cmarschner cmarschner released this 07 Jan 09:08
· 28 commits to main since this release
v2.0.0-alpha
581fb4e

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
  1. 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]
  1. 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()
  1. 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

Assets 2
Loading