Add sentinel-rooted replica ordering with a measured comparison - #162

Summary

Add experimental VirtualPermutation alongside the unchanged ConsistentPermutation. The latest revision replaces both earlier slot-based experimental variants with a single-cycle + permanent-sentinel traversal; it does not add a third alternative.

Both iterators now preserve complete survivor-list order: deleting the appended node from the larger complete order recovers the smaller order. Every requested replica count is a prefix containing distinct nodes. Membership remains consecutive IDs 0..N; replica ranks may shift on membership changes.

• Ordinary reversible Q is the strengthened, noncryptographic width-separated Feistel (24/16/8 rounds according to width).
• Conjugate modular increment, P = Q_inverse increment Q, guarantees a single full cycle. The normalized dyadic lift preserves single-cycle structure and cycle-deletion coherence.
• Internal label zero is a permanent sentinel; real node i is internal label i+1. Sequential iteration follows successors from the sentinel rather than evaluating independent rank inputs.
• Iterator state is 32 bytes, with no heap allocation, prebuilt ring/table, cached prefix or duplicate set. Supported real-node counts are 1..=u64::MAX - 1; invalid/overflowing counts panic explicitly.
• No direct-rank API remains. nth(r) replays successors. Earlier experimental mappings/APIs intentionally change; the existing iterator's source is byte-for-byte unchanged from the PR base.

Guarantees and qualifications

The design note derives uniform full cycles and rooted real-node orders under independent ideal uniform permutations per key and width. Adaptive sequential work is bounded by a pathwise inverse-charging argument followed by expected lower-label/padding counts—not by reusing a fixed-input proof. A conservative bound is fewer than 16 ordinary Q/Q_inverse calls per output in expectation over a fixed positive-length prefix, with constant-cost primitives.

This is expected O(k), not worst-case O(k). The bound covers cumulative work from the sentinel, not an arbitrary suffix conditioned on previous observations. The actual finite 64-bit Feistel family is an experimental noncryptographic approximation: no exact uniformity, proven independence, cryptographic security or adversarial-latency guarantee is claimed. Long walks have no mapping-changing retry limit. Mathematical review independently confirmed the adaptive-prefix accounting; expert review of this novel construction remains valuable.

Fresh final-construction measurements

Measured September 30, 2026 on Apple M4 Max, macOS 27.0, native release build, rustc 1.92.0. Same deterministic key corpus, hashing, output consumption and setup accounting for both methods. 905 estimates, including 177 N/k pairs each for fresh and prehashed queries, plus constructor, setup-excluded streaming, equal-width collection and honest rank-replay workloads. Powers of two, sentinel boundaries, nonpowers, large N, small k, proportional k and full bounded permutations are covered.

Mean fresh-key ns/query; ratio is new/existing:

The new implementation loses all 176 nontrivial fresh cases; only the degenerate N=1 case wins. Nontrivial ratios range from 3.51x to 53.45x (N=1024,k=16). At N=1000,k=3, bootstrap 95% intervals are [36.11,36.84] and [349.34,353.43] ns; costs per output are 12.16 and 117.09 ns. The committed report preserves confidence intervals, sample standard deviations, noisy cases and reproducible commands.

Single-cycle conjugation requires both Q and its inverse per primitive step, and consistent traversal retraces chains. Stronger mixing and padding contribute too; this is not a pure comparison of odd versus even Feistel halves. Avoiding heap counters does not compensate for the additional work. No obsolete direct-slot speedup remains in the report.

Randomness on the final construction

Each method was evaluated on 3,760,000 complete orders per corpus, using separate deterministic primary and held-out key corpora over 29 N values. Diagnostics cover first/middle/late ranks, adjacent and distant ordered pairs, first-three subsets, full permutations through N=7, consecutive application keys and related seeds. Larger-domain pairs use correctly weighted buckets; sparse triples are explicitly skipped. Every reported nonzero expected bin count is at least 11.834.

Representative primary / held-out chi-square statistics:

At N=9,rank=4, maximum relative cell deviations are 9.91%/7.94% for existing versus 0.90%/0.25% for sentinel. The unchanged baseline also shows repeatable distant-pair deviations. No comparably large repeatable deviations appeared for sentinel, but isolated fluctuations are retained and discussed. Diagnostics are correlated, include sampling noise, and do not prove independence or uniformity. The mixer was not tuned after viewing these results.

Untimed sequential operation counts cover 56 N/k cases with 10,000 seeds each: observed mean ordinary-PRP calls/output range from 2 to 11.8285. Tail counts and an explicit linear-work oracle demonstrate why this is not a worst-case bound.

Documentation and reproduction

• Construction, survivor-order contract, API/bounds and ideal-model derivation
• Final measured performance/randomness report, intervals, effect sizes and operation tails
• cargo bench -p consistent-choose-k-benchmarks --bench replica_comparison -- --noplot
• python3 crates/consistent-choose-k/benchmarks/summarize_replica_comparison.py target/criterion
• cargo run --release -p consistent-choose-k --example permutation_diagnostics (repeat with -- --held-out)
• cargo test --release -p consistent-choose-k operation_count_diagnostics -- --ignored --nocapture

Validation

Debug and release suites each pass 28 unit tests + 3 doctests, with the separate ignored operation-count diagnostic also run successfully. Coverage includes all 64 PRP/inverse widths, guaranteed single-cycle coverage, explicit lift/projection references, complete survivor restriction, k-prefixes, sequential nth/exhaustion, u64/sentinel boundaries, and deterministic per-level inverse charging. Exhaustive ideal tests cover all 24 size-four conjugators and 30,240 cycle families through internal size eight, with equal frequencies for every rooted order through seven real nodes.

All-target/all-feature builds, strict targeted Clippy, workspace formatting and whitespace checks pass. Rustdoc succeeds with the pre-existing private-link warning in the unchanged baseline.

All implementation and measurements ran in the isolated worktree. Local Cargo commands used the already-installed CLT via DEVELOPER_DIR=/Library/Developer/CommandLineTools; no Xcode license was accepted and no OS setting was changed. This updates the existing PR via a normal new commit, without force-pushing or merging.