perf: reduce certified linear-form overhead before downstream adoption

[acgetchell]

Summary

Reduce certified dot-product/linear-form cost and measure downstream vector-construction overhead separately. Target v0.4.7 to unblock acgetchell/delaunay#579, deferred to Delaunay v0.8.3 pending a released fix and a successful downstream performance comparison.

The API from #220 is present in la-stack 0.4.6 and passes the targeted scientific checks. However, replacing Delaunay's local reduction with it materially slows the Level 4 simplex-intersection fast path. Reusing the shared vertex's projection helps, but the repeated comparison still shows roughly 8–30% slower public intersection checks in 2D–5D and 13% slower whole-triangulation Level 4 validation in the 2D fixture.

This is distinct from #246's triangular rational-solve work. It is related to #247 because interval arithmetic and certified vector reductions share rounding::compare_product_with_rounded; an optimization to that helper may benefit both. Neither an exact-solve fix nor an interval determinant-specific fix establishes parity for these workloads.

Downstream comparison

Local aarch64-apple-darwin, Rust 1.98.1 (48a229cea, LLVM 22.1.8), la-stack 0.4.6 with default features disabled and exact enabled. Delaunay base: 7b2e610f0fa82ac998617f984def3593e42a8502, with pre-existing test/tooling changes. Timings use the repository's perf profile and identical fixture definitions; they are short diagnostic measurements, not release-suite claims.

Two candidates were evaluated:

1. Replace certified_dot_difference_lower_bound with Vector::dot_difference_with_errbound. Parse the scaled axis/common vertex once and accept only a certified lower_bound() > 1.0.
2. Compute the common vertex's dot_with_errbound result once, then reuse it for every other vertex. Bound each subtraction with Interval::try_from_subtraction(vertex.lower_bound(), shared.upper_bound()), reversing operands for the other simplex. Accept only a resulting lower endpoint greater than 1.0.

Both keep Delaunay's geometric axis construction, labels, common-coordinate identity checks, witnesses, and exact fallback. Neither reconstructs the upstream proof locally or treats errors/missing certificates as separation. Both remove the old generic certified reduction in the trial patch; neither candidate remains active because of the regression.

Public workload	Original local reduction	Direct upstream difference	Reused common projection	Reused projection, isolated repeat
Single shared vertex, 2D	101.48 ns	149.46 ns	131.55 ns	132.28 ns
Single shared vertex, 3D	168.40 ns	269.44 ns	212.79 ns	215.00 ns
Single shared vertex, 4D	1.2539 µs	1.5293 µs	1.3943 µs	1.4454 µs
Single shared vertex, 5D	2.0759 µs	2.5018 µs	2.2097 µs	2.2317 µs
Whole Level 4, 2D / 500 vertices	6.5811 ms	7.6840 ms	7.3455 ms	7.4622 ms

Times are Criterion's printed central estimates. All five isolated repeat cases reported statistically significant regressions. Whole 3D validation with the reused-projection candidate showed no statistically detected change; whole 4D and 5D were within the noise threshold. The first candidate's whole 3D result was noisier/slower and is not used to establish the blocker.

The focused public intersection fixture is reproducible without triangulation construction: first simplex coordinates [0, e1, ..., eD], labels [0, 1, ..., D]; second coordinates [0, -e1, ..., -eD], labels [0, D+1, ..., 2D]. The intersection is exactly the common origin. Validate fixture correctness outside timing. Delaunay's realization_validation benchmark also retains near-degenerate shared-face cases and whole-triangulation controls. Four new single_shared_vertex cases and 18 additional correctness tests are currently retained in the downstream worktree, pending publication.

Downstream command, before and after adoption:

cargo bench --profile perf --bench realization_validation -- \
  --warm-up-time 0.2 --measurement-time 1 --sample-size 10 --nresamples 1000 \
  --save-baseline issue-579-before
# After applying the adoption, use the same settings with:
# --baseline issue-579-before

The isolated repeat ran the already-built candidate with the filter single_shared_vertex|realization_validation/2d after other validation finished.

Construction versus certified arithmetic

The performance gap must not be attributed entirely to upstream arithmetic. Delaunay already owns finite coordinate rows but constructs checked Vector values at the boundary. That conversion/validation has measurable cost, and the first adapter also repeated the common projection unnecessarily.

A disposable upstream-only harness compared the same reused-projection batch with all Vector::try_new calls inside timing versus all vectors constructed beforehand. Both versions retained the same certified dot products and outward-rounded subtractions. Axis scaling and geometric label handling were excluded from both. No local numerical reduction or unchecked constructor was substituted.

Reproducer: use a pre-scaled axis [2048.0; D], common vertex s = [0; D], and non-shared vertices s + ei and s - ei. Repeat with the exactly representable translation s[i] = (i+1)/8. Compute the common projection once; certify the D differences on each side against margin 1. Construct every input normally and assert the expected successful certificates outside timing.

The harness links la-stack 0.4.6 with optimization level 3, thin LTO, and one codegen unit. Each entry below is a median of nine batches of 150,000 iterations with timing order alternated. The second invocation checks repeatability.

Origin-centered batch	With construction	Preconstructed	Repeat with construction	Repeat preconstructed
D=2	55.239 ns	48.546 ns	55.714 ns	49.237 ns
D=3	110.673 ns	88.338 ns	110.357 ns	85.971 ns
D=4	154.806 ns	149.208 ns	152.589 ns	147.468 ns
D=5	207.078 ns	199.371 ns	207.796 ns	200.988 ns

Construction savings are approximately 6–7 ns, 22–24 ns, 5–6 ns, and 7–8 ns respectively. Translated fixtures show a similar ordering. These isolated measurements are not an additive decomposition of the public benchmark's regression and do not demonstrate end-to-end parity after removing construction cost.

A five-second sampling profile of the reused-projection candidate's 3D public case also finds substantial execution in CertifiedReduction::add_product_magnitude_upper and ScalarWithErrorBound::try_new. The latter computes outward error-bound endpoints; it is not Vector::try_new input validation. The sample includes fixture setup and inlined code, so whole-process sample percentages are not used to partition the regression.

Relevant sources: certified reduction, magnitude bound, certificate endpoints, and shared exact product comparison.

Scope and acceptance

• Add upstream benchmarks separating vector construction, prepared-vector dot_with_errbound and dot_difference_with_errbound, and repeated projections against a common vertex. Include 2D–6D, sparse/dense operands, nonzero translations, cancellation, and range-sensitive cases. Keep fixture construction and correctness assertions outside timing except in explicitly named construction measurements.
• Profile and optimize certified magnitude accumulation, product-rounding comparisons, certificate endpoint construction, and repeated-reference workflows where evidence supports it. Measure boundary-conversion costs separately and coordinate any needed downstream reuse; do not simply remove finite-input validation or expose unchecked storage.
• Preserve the proven arithmetic tree/error relationship, finite ordered outward endpoints, typed range failures, and Ok(None) when proof is unavailable. Preserve true-zero, signed-zero, cancellation, subnormal, underflow, and overflow semantics. Do not introduce relaxed floating-point arithmetic or weaken correctness to meet timings.
• Retain independent exact-rational containment/sign tests for successful certificates and adversarial cases. Downstream exact intersection agreement and known shared-face/overlap fixtures must continue to pass through D=6.
• Rerun representative downstream Level 4 comparisons with the same toolchain/profile/features/fixtures and no overlapping validation jobs; demonstrate no material regression before resuming Adopt la-stack certified linear-form bounds and retire local filter delaunay#579. A construction-only improvement or a fix to perf: avoid unnecessary exact elimination for triangular rational systems #246/perf: reduce interval arithmetic overhead before downstream adoption #247 alone is not sufficient evidence.
• Release the accepted fix in v0.4.7. Reaching that version number alone does not unblock adoption: the released implementation must pass the downstream correctness and performance checks.

Existing downstream evidence: the reused-projection candidate passed 54 focused debug tests. After restoration, the existing implementation plus the new tests passed 55 focused debug tests, all 18 new tests in release mode, and just check. No full CI run was performed, per the maintainer's requested validation scope.