perf: reduce interval arithmetic overhead before downstream adoption

[acgetchell]

Summary

Reduce the cost of outward-rounded interval arithmetic and determinant signs without weakening their scientific guarantees. Target v0.4.7 and unblock acgetchell/delaunay#577, deferred to Delaunay v0.8.3 pending a released fix and a successful downstream performance comparison.

The API introduced by #218 is available in v0.4.6. A downstream adoption candidate passed correctness checks but failed its no-material-performance-regression acceptance criterion. Tighter enclosures are valuable; they should be retained while eliminating redundant work and improving the implementation.

Current State

A candidate replaced Delaunay's private interval scalar and subset-DP determinant with Interval::try_from_subtraction, try_square, try_add, and IntervalMatrix::det_sign, using try_with_interval_matrix! for the concrete dimension. Geometric assembly, orientation interpretation, and exact rational fallback remained in Delaunay. Only positive/negative interval evidence returned early; zero, inconclusive results, and upstream errors retained the exact path.

Same-machine cold_path_predicates comparisons against Delaunay commit 7b2e610f0fa82ac998617f984def3593e42a8502, on aarch64-apple-darwin with Rust 1.98.1 and the perf profile, gave these central estimates:

Public in-sphere workload, 10,000 queries	Private Delaunay kernel	la-stack 0.4.6 candidate	Change
2D	1.0714 ms	1.9807 ms	+84.9%
3D	2.0857 ms	3.2095 ms	+53.9%
4D	9.3827 ms	11.235 ms	+19.7%
5D	17.485 ms	19.268 ms	+10.2%

These are short diagnostic measurements of complete predicates, including matrix construction and orientation, not isolated determinant timings or release benchmark evidence. Repeating after other validation finished confirmed the hot regressions. Known-boundary workloads changed much less, roughly 3–6% in their central estimates; the 4D boundary comparison was noisy and not statistically significant.

Correctness evidence for the candidate: 62 targeted tests passed, including exact absolute-lifted rational comparisons through geometric D=6, conclusive signs, boundary cases, cancellation, subnormals, underflow, and overflow. Existing legacy simplex-intersection agreement tests through D=5 and periodic-chart diagnostics also passed. just check and 10 SoS benchmark smoke cases through D=6 passed. The adoption candidate was removed from the downstream working tree because of the performance regression.

Proposed Changes

• Avoid evaluating the same endpoint square twice for a singleton interval [x, x]. Preserve identical bounds and error provenance. Consider zero/one cases within the same invariant-preserving arithmetic design.
• Profile and optimize exact product-bound comparisons and outward-rounded addition. Keep successful enclosures sound, endpoints finite and ordered, subnormal behavior correct, and range exhaustion explicit.
• Examine determinant workspace initialization and inner arithmetic call overhead where profiling justifies it.
• Extend the existing upstream interval benchmark to separate scalar arithmetic, lifted-matrix assembly, and determinant evaluation. Include the 3x3 determinant used by geometric 2D queries, plus representative larger dimensions, conclusive/inconclusive cases, and dense as well as sparse inputs.
• Preserve the public API and const-evaluation behavior where feasible. Do not introduce relaxed floating-point arithmetic or weaken error handling to improve timings.

Benefits

This enables downstream removal of a duplicate numerical kernel while retaining the stronger upstream interval contracts and avoiding a material regression in common predicate workloads.

Implementation Notes

The previous private Delaunay implementation expanded rounded floating-point results by adjacent representable values. la-stack computes tighter enclosures using exact u128 product comparisons and error-free sum residuals. Wider valid enclosures are not inherently incorrect; they can require more exact fallbacks. The goal here is to remove avoidable cost while retaining la-stack's guarantees.

Evidence narrowing the investigation:

• A five-second sampling profile of the candidate's hot 2D case collected 4,220 main-thread samples: 35.4% in rounded_product_bounds, 27.4% in Interval::try_add_for, 5.9% in Interval::try_mul_for, and 8.4% in memory clearing. These are runtime shares, not a decomposition of the entire regression; inlining limits attribution of the remaining frames.
• A disposable harness compared identical matrices assembled through checked IntervalMatrix::set calls and through trusted interval rows passed to IntervalMatrix::from_rows. Median construction-plus-determinant times were 172.8 ns versus 172.4 ns; a repeat gave 175.7 ns versus 174.8 ns. Per-entry setter checks therefore do not explain the large regression in this fixture.
• For singleton intervals, try_square took a median 14.5 ns versus 10.9 ns for multiplication by itself in that harness. Source inspection confirms that try_square evaluates both endpoint products even when the endpoints are equal. A downstream experiment choosing multiplication for singleton squares reduced, but did not eliminate, the hot regressions; that workaround was removed.

Relevant source: interval squaring, product rounding, and the existing interval benchmark.

Downstream comparison command, before and after applying the adoption:

cargo bench --profile perf --bench cold_path_predicates -- 'predicates/(hot|exact_fallback)/insphere_lifted_[2-5]d' --warm-up-time 0.2 --measurement-time 1 --sample-size 10 --nresamples 1000 --save-baseline interval-before
# Apply the interval API adoption, then repeat with the same settings:
cargo bench --profile perf --bench cold_path_predicates -- 'predicates/(hot|exact_fallback)/insphere_lifted_[2-5]d' --warm-up-time 0.2 --measurement-time 1 --sample-size 10 --nresamples 1000 --baseline interval-before

Acceptance:

• Independent exact-rational containment/sign tests continue to pass across supported dimensions, including cancellation, signed zero, subnormals, underflow, overflow, and inconclusive intervals.
• Focused upstream benchmarks document before/after costs with correctness checks outside measured loops.
• A downstream adoption comparison shows no material regression on representative filtered workloads, or any remaining blocker is explicitly resolved before adoption.
• The fix is released in v0.4.7 before Adopt la-stack interval determinant signs and retire local interval kernel delaunay#577 resumes adoption.