Skip to content

v0.4.0: High-Performance Algorithmic Optimizations

Choose a tag to compare

View all tags
@Routhleck Routhleck released this 23 Aug 12:51
· 60 commits to master since this release
v0.4.0
a12c46a

🚀 CANNS-Ripser v0.4.0: High-Performance Release

This major release implements comprehensive performance optimizations inspired by the highly optimized C++ ripser implementation, achieving significant speedups while maintaining 100% numerical accuracy.

📊 Performance Results

  • Median speedup: 1.01x | Mean: 1.13x
  • Top speedups: Up to 1.82x on certain datasets
  • Memory efficiency: Stable 1.01x memory ratio
  • Accuracy: 100% match across all test cases (6/6 pass)
  • Benchmarks: Tested on 54 dataset/parameter combinations

🏆 Top Performance Improvements

  • Random N(0,I) d=2, n=500 → 1.82x speedup
  • Two moons n=400, noise=0.08 → 1.77x speedup
  • Random N(0,I) d=2, n=200 → 1.72x speedup

🔧 Major Optimizations Implemented

Phase 1: Hot Path Optimizations

  • Dense edge generation: Row-by-row generation eliminates O(n²×n) vertex decoding overhead
  • Sparse matrix queries: Binary search reduces O(k) to O(log k) for distance lookups
  • Binomial coefficient table: K-major (transposed) layout improves cache locality
  • k=2 fast path: Closed-form sqrt solution for most common edge operations

Phase 2: Algorithmic Improvements

  • Sparse coboundary enumeration: Neighbor intersection algorithm dramatically reduces cofacet generation for sparse graphs
  • Zero-apparent pairs: Boundary/coboundary pivot detection skips redundant column reductions

Phase 3: Memory & Data Structure Optimizations

  • Structure of Arrays (SoA): Improved cache performance in reduction matrix operations
  • Memory pooling: Thread-local buffer pools reduce allocation overhead
  • Intelligent capacity management: Growth strategies minimize costly reallocations

Phase 4: Compilation & Runtime Optimizations

  • Global allocator: mimalloc for superior performance with frequent small allocations
  • Link-time optimization: LTO, optimized codegen units, panic=abort
  • Aggressive inlining: #[inline(always)] on profiler-identified hot functions

🔬 Technical Implementation

All optimizations maintain full algorithmic compatibility with the original ripser while implementing performance strategies from the C++ reference implementation. Changes span from micro-optimizations (memory layout, inlining) to macro-optimizations (algorithmic improvements, data structure redesign).

Key implementation highlights:

  • Cache-friendly access patterns through data layout optimization
  • Reduced algorithmic complexity in critical paths
  • Memory allocation optimization with pooling and reuse strategies
  • Compiler optimization leveraging with profile-guided optimizations

✅ Quality Assurance

  • Accuracy validation: 100% match with original ripser.py across comprehensive test suite
  • Cross-platform testing: macOS, Linux compatibility verified
  • Memory profiling: Stable resource consumption confirmed
  • API compatibility: Zero breaking changes, full backward compatibility

🛠 Installation

pip install canns-ripser==0.4.0

Or build from source:

git clone https://github.com/Routhleck/canns-ripser.git
cd canns-ripser
git checkout v0.4.0
maturin develop --release

📈 When to Upgrade

This release is recommended for all users, especially those working with:

  • Large point clouds (n > 200)
  • High-dimensional persistent homology computations
  • Performance-critical applications
  • Batch processing workflows

The optimizations provide the most benefit on datasets where ripser spends significant time in edge enumeration and matrix reduction phases.

Full Changelog: v0.3.2...v0.4.0

Assets 2
Loading