Skip to content

Development

Architecture

           Python (iheap.PQDict)                     Rust (iheap-core)
  ┌───────────────────────────────────┐   ┌─────────────────────────────────────┐
  │ _handles: dict[key -> handle]     │   │ 8-ary tournament tree               │
  │ _keys:    list[handle -> key]     │──▶│   leaves[h]  = priority of handle h │
  │ _values:  list[handle -> value]   │   │   node       = winner of 8 children │
  └───────────────────────────────────┘   └─────────────────────────────────────┘
                    only f64 priorities and u32 handles cross ▲

The design rests on these decisions:

  • Handles, not keys. The core gives out dense u32 handles and recycles them through a free list. Python keeps keys and values in lists indexed by handle. Rust never holds a Python object and never calls back into Python.
  • f64 priorities, stored as order-preserving u64 keys. The core compares native integers, never calling back into Python. The key encoding also gives a total order (-0.0 and +0.0 both round-trip) and a sentinel for vacant leaves that no real priority can collide with.
  • An 8-ary tournament tree. Leaf h holds the priority of handle h, so there is no position map. Each internal node holds the winner of a group of 8 children: a 64-byte line for leaves, 128 bytes for nodes. The node above leaf h on level l is h >> 3(l+1), independent of the tree's size, so growth only appends.
  • Latency first. pop replays the winner's path. The winner among the other siblings on each level doesn't depend on the replayed value, so all levels' reductions (NEON on aarch64) run in parallel. Updates use a two-phase replay with early exit. See the benchmark for the measurements behind each choice.
  • Atomic batch operations. push_many and update_many validate their whole input before changing anything, and rebuild in O(n) when k · log₂ n ≥ n.

Repository layout

crates/iheap-core/     pure-Rust core: no PyO3
  src/heap.rs          IndexedHeap (the tournament tree)
  src/group.rs         nodes, 8-wide groups, NEON/scalar reductions
  src/key.rs           order-preserving f64 -> u64 key encoding
  tests/model.rs       randomized differential test against a HashMap model
  examples/bench.rs    core-only micro-benchmark
crates/iheap-py/       thin PyO3 binding -> iheap._iheap (abi3-py310; free-threading safe)
python/iheap/          Python package
  _pqdict.py           PQDict mapping API
  _iheap.pyi           type stub + docs for the native module
tests/                 pytest suite (incl. differential tests vs dict and pqdict)
benchmarks/bench.py    end-to-end benchmark
docs/ + mkdocs.yml     this documentation

Keeping the core free of PyO3 means cargo test -p iheap-core runs without a Python interpreter, and the core could be published to crates.io unchanged.

Setup

You need Rust (1.88 or later) and Python ≥ 3.11.

uv venv
uv pip install maturin pytest pqdict "mkdocs>=1.6,<2" mkdocs-material "mkdocstrings[python]"
maturin develop --release        # builds the extension into python/iheap/

Re-run maturin develop --release after changing any Rust code.

Tests

cargo fmt --all --check
cargo clippy --all-targets -- -D warnings
cargo test -p iheap-core          # Rust: unit tests + randomized model test
pytest                            # Python: tests/, doctests, docs code blocks

The pytest suite includes:

  • docstring examples (--doctest-modules);
  • every python code block in docs/*.md, executed in order (tests/test_docs.py);
  • a randomized parity test against dict, covering results, iteration order and reversed;
  • a randomized differential test against pqdict.

Documentation

mkdocs serve                      # live preview at http://127.0.0.1:8000
mkdocs build --strict             # what CI runs

The API reference is generated by mkdocstrings from Google-style docstrings. The docs for the native IndexedHeap live in python/iheap/_iheap.pyi. Keep that stub in sync with crates/iheap-py/src/lib.rs.

Releasing

  1. Bump version in the root Cargo.toml. It is the single source of truth; the Python package version is derived from it.
  2. Commit, then tag and push: git tag v0.2.0 && git push origin v0.2.0.
  3. CI then runs, in order:
  4. Rust: fmt, clippy, tests, an MSRV (1.88) check, and the core's tests on i686, armv7, s390x and ppc64le under emulation.
  5. Python from source: CPython 3.11–3.15, 3.14t, 3.15t and PyPy 3.11 on Linux, and 3.11/3.15/3.15t on macOS and Windows.
  6. Wheels:
    • cp311-abi3 for 15 targets: Linux glibc (x86_64, i686, aarch64, armv7, ppc64le, s390x), Linux musl (x86_64, i686, aarch64, armv7), Windows (x64, x86, arm64), macOS (x86_64, arm64);
    • free-threaded cp314t and cp315-abi3t for the 64-bit targets;
    • PyPy pp311 for Linux x86_64/aarch64, macOS and Windows x64;
    • the sdist.
  7. Testing what ships: every wheel is installed the way pip would choose it and the suite is run, natively, under QEMU for the other architectures, and on PyPy. The sdist is built from source and tested.
  8. Publishing: only if all of that passes, and only if the tag matches the package version, everything goes to PyPI through Trusted Publishing (no API token is stored).

Docs are rebuilt with mkdocs build --strict on every push and deployed to GitHub Pages on every push to main.