# caps-sa 0.7 pre-release API and ruSTAR optimization audit
This audit was run on 2026-08-13 before publishing the 0.7 crate. The code
baseline was caps-sa `967a7b9`; the production-shaped workload was the saved
ruSTAR segmented/filter fixture derived from GENCODE Human v50:
- 6,557,611,930 text symbols;
- 6,176,694,310 retained ACGT-starting suffixes;
- STAR boundary ordering through a custom `LimitProvider`;
- `u64` indices, 8,192 partitions, and 32 pinned physical cores.
Every full run emitted hash `e81c8f9881e322148741a23c92ae2000`.
## Public API decisions
- `ExtMemOpts` is non-exhaustive. External callers start from `default()` or
`from_env()` and use builders, so a future option does not cause another
struct-literal break.
- `GeometricMemoizationConfig` is opaque and non-exhaustive. Read-only getters
and `with_*` methods expose the four measured controls without committing to
its field layout. Setters use `NonZeroUsize`, preserving the implementation's
invariants.
- `LcpMemoizationPolicy::geometric()` is the concise default-policy entry point.
A `From<GeometricMemoizationConfig>` conversion also lets callers pass a
tuned configuration directly to `ExtMemOpts::lcp_memoization`. The policy
enum is non-exhaustive so later memoization strategies can be added without
breaking exhaustive matches.
- Detailed memo counters are environment-only diagnostics rather than a public
boolean field. Their output is a profiling implementation detail, not a
stable result type.
- The crate-level generalized-SA documentation now recommends
`LimitProvider`/`SegmentedText`; it no longer incorrectly requires a distinct
terminal symbol per string.
- Documentation of automatic `subproblem_count` now matches the code: target
roughly 65,536 retained positions per subarray, bounded below by the Rayon
worker count and above by 8,192.
- `max_context` is documented as an ordering-context cap, not merely a scan
optimization. The merge previously read one extra symbol when the cap was
exhausted, disagreeing with pivot selection and `suffix_cmp_with`; the merge
now applies `boundary_order` at exactly the cap. A randomized finite-context
differential test and an 8,192-position external-memory probe both pass.
Memoization remains opt-in and phase-4-only. That is deliberate: generic inputs
do not universally benefit, while ruSTAR enables it explicitly for its repeated
genome-plus-splice-junction layout.
## Retained implementation changes
The first retained change keeps position and LCP arrays separate through
phase-1 routing and phase-4 bucket decode. The on-disk `(position, lcp)` format
is unchanged, but the build no longer constructs a transient record vector and
then copies it back into merge arrays.
The second retained change recognizes that automatic genome-scale construction
already has thousands of outer Rayon tasks. Its phase-1 subarray recursion is
therefore task-local and uses ping-pong source/destination buffers, eliminating
nested scheduler work and merge-level copy-back. If an explicit `p` provides
fewer tasks than workers, the old recursively parallel path is retained.
The third retained change accelerates `SegmentedText::lim_at`, which was the
largest remaining ruSTAR-specific cost. Large segment collections now get a
bounded two-level directory: a `u32` coarse entry identifies the small slice of
cumulative ends that can contain the next boundary, followed by a local binary
search. The directory is private, constructed automatically, capped at 8 MiB,
and omitted below 256 segments. It does not alter `LimitProvider` or the public
`SegmentedText` constructors.
| 0.7 baseline | 267.592 s | 7,622.88 s | 10,512,408 KiB | 106.847 s | 155.794 s |
| Direct SoA only | 267.763 s | 7,631.77 s | 9,932,420 KiB | 105.452 s | 157.191 s |
| SoA + task-local ping-pong | 260.338 s | 7,416.01 s | 9,136,716 KiB | 99.830 s | 155.462 s |
| + segmented-boundary directory | 172.953 s | 4,731.05 s | 9,169,892 KiB | 49.029 s | 118.743 s |
Relative to the already-optimized SoA + task-local candidate, the boundary
directory removes another 87.385 seconds (33.6%) and 2,684.96 user CPU-seconds
(36.2%) for 33,176 KiB (0.36%) additional peak RSS. Relative to the original
0.7 baseline, the complete candidate is 35.4% faster and uses 12.8% less peak
RSS. Temporary output volume is unchanged.
On the focused chromosome-21 backbone plus all annotation-derived flanks, the
directory reduced stable runs from 11.97–12.00 seconds to 7.77–7.80 seconds,
with the same 359,616,038-position hash. A directory-density sweep measured
7.90–7.91 seconds at one block per segment, 7.77–7.80 seconds at two, and
8.00–8.02 seconds at four; the middle setting was retained. The complete full
candidate emitted the baseline hash
`e81c8f9881e322148741a23c92ae2000`.
## Measured ideas not retained
- Extending geometric memoization into the now task-local phase-1 sort reduced
focused phase 1 by only about 0.5%, but perturbed the phase-4 kernel enough to
regress median end-to-end time from 11.838 to 11.937 seconds (0.84%). It was
removed.
- Focused sweeps of probe lengths 128/512, activation thresholds
16/32/128/256, exact-LCP admission thresholds 512/2,048, and a 2,048-entry
cap produced no repeatable improvement above noise over the existing
256/64/1,024/4,096 defaults. No default was changed.
- Earlier complete-GRCh38 measurements already found hash-per-diagonal table
layouts timing-neutral while adding roughly 648 MiB RSS. The flat sorted
vector remains the measured production choice.
The optimization pass therefore changes data movement, scheduler ownership,
and segment-limit lookup, not suffix ordering, filtering, segment limits,
boundary semantics, generic symbol support, or the public streaming contract.