Tracking: suffix array construction performance (10x in-memory, 15x external-memory on chr21)

[BenjaminDEMAILLE]

Tracking issue for the four-PR performance stack #3 #4 #5 #6.

What prompted it

A report that caps-sa was ~18x slower than libsais on chr21. Reproducing it
turned up something more useful: the two numbers had been measured on
different inputs, and the gap was one specific pathology rather than general
slowness.

Dividing CPU time by n log2 n merge steps, same kernel, same machine:

chr21.0123 (N-free, 80 MB)     28.1 s / 2.11e9 steps =  13 ns/step
chr21.fa   (raw FASTA, 47 MB) 283.5 s / 1.21e9 steps = 222 ns/step

16x apart, entirely scan length. Every leaf merge starts with m = 0, so a
tied comparison scans the whole shared prefix of two suffixes. Genome FASTA
carries ~6.6 Mb of N, and once 60-column line wrapping is included that is a
period-61 repeat, not a homopolymer. One comparison can scan millions of bytes.

On the N-free input caps-sa was never 18x off. That framing is worth keeping in
mind when reading the older numbers in bench/README.md.

Result

Apple M4 Max (12 P-cores), 12 threads. All outputs verified byte-identical to
the original merge kernel, on both the in-memory and external-memory paths.

input	in-memory	external-memory
chr21 fwd ++ revcomp, coded 0..3, 80 MB	6.08 s → 0.57 s	3.49 s → 1.69 s
same, ASCII ACGT, 80 MB	6.08 s → 0.61 s	3.49 s → 1.82 s
chr21 FASTA, 47.5 MB, 6.6 Mb of N	27.8 s → 1.12 s	24.19 s → 1.56 s

CPU time on the FASTA input drops from 283.5 s to ~5 s in memory and from 268 s
to ~17.5 s externally. Peak RSS for the external path goes from 214 MB to
285 MB, still an order of magnitude under the in-memory path, so the bound that
path exists to provide holds.

The stack

Merge in order. I do not have write access here, so the parts cannot use each
other as base branches and all four target main; every diff collapses to just
its own work as soon as the part before it merges.

• 1/4 perf: radix-seeded prefix doubling for the in-memory suffix array #3 — 1/4 in-memory fast path: radix-seeded prefix doubling, verify_sa, LCP-array tests, Rust CI (8 commits)
• 2/4 perf: MSD counting-sort seed, and cover subsets + in-memory sample sort #4 — 2/4 MSD counting-sort seed; subsets and in-memory sample sort (3 commits)
• 3/4 perf: external memory, 24.2 s -> 1.56 s on chr21 FASTA #5 — 3/4 external memory: run skipping, prefetch, phase-1 seeding, parallel cascade, pipelined emit (11 commits)
• 4/4 perf: alphabet ranking, SWAR key packing, and doubling-round overhead #6 — 4/4 alphabet ranking, SWAR key packing, doubling-round overhead (6 commits)

Two pre-existing problems fixed along the way

• No test covered the LCP array. The public entry points discard it, but the
  next merge level consumes it in the three-case decision, so a single wrong
  entry silently reorders suffixes one level up. Fixed first, in 1/4 perf: radix-seeded prefix doubling for the in-memory suffix array #3, before any
  kernel change.
• bench/README.md credited lto = "fat" to a parent workspace that is not
  in this repository. From the commit that made the crate standalone until 1/4 perf: radix-seeded prefix doubling for the in-memory suffix array #3,
  every build made here used lto = false, codegen-units = 16, so numbers taken
  in that window are not comparable with numbers taken now.

Verification

• 87 unit tests (was 62), run in debug as well as release. Debug is not
  incidental: it caught a u64 shift-by-64 in the SWAR key packing that release
  masks to zero and silently gets right.
• src/radix.rs checks every binary text to length 10 and every ternary text to
  length 6 against brute force, so each key width is exercised at every
  alignment and tail length.
• verify_sa, added in 1/4 perf: radix-seeded prefix doubling for the in-memory suffix array #3, checks a candidate in O(n) without re-running any
  construction algorithm and without depending on LCP length — usable at genome
  scale on exactly the repetitive inputs that are hardest to trust.
• Cross-check: the suffix array of the ASCII ACGT text is identical to that of
  the 0..3-coded text, as it must be, the encodings being order-isomorphic.

Negative results, recorded so they are not retried

• Grain-size threshold on parallel cascade levels measured worse on both
  inputs (2.22 s and 1.63 s against 2.02 s and 1.55 s). Every level goes
  parallel.
• Unconditional partition re-sort by key regressed the N-heavy input badly
  (1.45 s → 2.23 s): a long run is exactly where a fixed-depth key resolves
  nothing. It is gated on the run table being empty.
• Key-accelerated phase-3 pivot search was tried twice, including after the
  key became ~5x cheaper, and gained nothing (0.402 s → 0.378 s, within noise).
  Phase 3 is bound by the cache miss on records[mid] in the binary search, not
  by the comparison. Reverted rather than kept.

Known limits

• build_ext_mem keeps the merge kernel deliberately: prefix doubling needs a
  rank for every text position, which would defeat its memory bound. It gets the
  pathology fixed in the comparator instead (3/4 perf: external memory, 24.2 s -> 1.56 s on chr21 FASTA #5).
• Run detection handles periods up to 64. A repeat whose shortest period exceeds
  that is still scanned; the bound is a constant.
• Segmented texts, custom boundary_order, finite max_context, and symbols
  wider than u8 all stay on the merge kernel for ordering. Each is a soundness
  condition, and each defaults to declining, so existing and third-party
  LimitProvider implementations are unaffected without changing a line.

Beyond this

The remaining step is a linear-time construction (SA-IS or DC3), which replaces
CaPS-SA rather than optimising it. Within the current algorithm the per-round
group-size distribution — now logged behind CAPS_SA_PROFILE — is the first
thing to look at.

🤖 Generated with Claude Code

[rob-p]

Hi @BenjaminDEMAILLE — thanks for assembling this stack. I reviewed #3–#6 individually and cumulatively against the current ruSTAR suffix-array path, then ran a focused GENCODE v50 benchmark and an adapted libsais comparison.

Short version

I do not think the four PRs should merge as one stack yet.

The raw-FASTA 10–15× result in this issue is real for that input, but most of the new fast paths do not apply to ruSTAR's production comparator. On a realistic annotation-shaped ruSTAR fixture, #3/#4 are neutral and #5/#6 are about 8% slower than main at 32 physical cores, although #5/#6 reduce RSS by about 22%. There is also a generic correctness blocker in #5/#6 for negative i8 symbols.

Run skipping itself is excellent and worth preserving as a separate change. It gives 5.8–6.9× on synthetic periods through 64, but no benefit at periods 65 or 171.

I also implemented a complete STAR-compatible libsais adapter on the same annotated fixture. Native libsais GSA matches every caps-sa output position and is about 4× faster than caps-sa main here, at 1.41× RSS and with no temp disk. The legacy distinct-terminal form also matches, but is much less attractive: only 1.17× faster than caps-sa and 2.08× its RSS. For a complete human index, however, native libsais64 still needs a roughly 60.7 GB lower-bound working set (about 67.3 GB if ruSTAR's original genome remains resident), so it is not an equivalent replacement for the external-memory path.

Pinned state

• caps-sa main: eae37143b3aa0adb894095dafdb1cc40e311dc87
• 1/4 perf: radix-seeded prefix doubling for the in-memory suffix array #3: 72db16541f936486fc58bdf52aad2898925bac4c
• 2/4 perf: MSD counting-sort seed, and cover subsets + in-memory sample sort #4: 31c1bb4d7afc5811cb560178521bc62f3b39ed80
• 3/4 perf: external memory, 24.2 s -> 1.56 s on chr21 FASTA #5: b1fd8fbf9dd3fe3a41011d9cec38da6ef1ad35b2
• 4/4 perf: alphabet ranking, SWAR key packing, and doubling-round overhead #6: 3ef11f29244410736e2c00cce1213b884d38c259
• rustar-aligner main: cf4683a941ed8dbac7dc1853d5d2697c21081f26
• libsais: b6e52ef33fe14f9d5c14c580d162b6fd2c27f2a8 (2.10.4)
• GENCODE human v50, GRCh38 primary-assembly FASTA and comprehensive primary-assembly GTF
• host: AMD EPYC 9555, 64 physical/128 logical cores, 376 GiB RAM, one NUMA node
• rustc/cargo 1.97.1; native CPU code generation; fat LTO; one codegen unit

Why the issue's raw-FASTA benchmark is not ruSTAR-shaped

The current ruSTAR constructor:

• parses away FASTA headers and line wrapping;
• encodes A/C/G/T/N/spacer as 0..5;
• uses StarSegmentedText with boundary_order = lim_b.cmp(&lim_a).then(p_a.cmp(&p_b));
• filters to ACGT-starting suffixes (text[p] < 4);
• calls try_build_ext_mem_for_filter_with for realistic inputs;
• streams output rather than retaining the final SA; and
• uses u64 positions for a complete human forward/RC index.

This means the raw FASTA's 60-N-plus-newline period-61 structure is removed before construction; it becomes a period-1 N run. More importantly, the prefix-doubling paths in #3/#4/#6 and the packed phase-1 seed/final key re-sort in #5 correctly decline StarSegmentedText, because plain_lex_len() is None and the custom boundary order is not plain lexicographic order.

The #5 changes that do reach ruSTAR are run skipping, prefetch, the 64 Ki → 128 Ki partition target, parallel cascade merging, and pipelined emit.

Why the long-N benchmark pathology does not carry over to ruSTAR

The raw/synthetic N benchmark and ruSTAR sort different suffix populations. On raw FASTA, every byte position is a candidate suffix, including millions of suffixes that begin at different offsets inside the same long N block. Those suffixes have enormous shared prefixes. Line wrapping makes the raw file a period-61 repeat (N × 60 plus newline), so even a homopolymer-only shortcut would miss the representation used by that benchmark.

ruSTAR removes FASTA headers, newlines, and wrapping before construction, turning such regions into ordinary period-1 N runs. More importantly, its filter admits only ACGT starts, so no suffix beginning inside an N block enters phase 1 at all. Increasing an N block by another million bases therefore does not create another million records to sort. A retained ACGT-starting suffix can still encounter an N later, but a costly scan requires two retained suffixes to match up to suitably aligned N runs; ordinary genomic differences generally terminate the comparison first.

I isolated this effect on the parsed 93,419,968-symbol chr21 no-annotation control at 32 cores. I replaced only comparison-time N symbols with deterministic pseudo-random ACGT while preserving the original ACGT-start filter, so both cases sorted the same 80,177,238 positions. Immediately before the run-skipping commit, the original input averaged 1.801 s and the masked-N control 1.776 s: only a 1.4% difference. By contrast, the run-skipping commit alone took 2.724 s on the original filtered input, because once a run exists its current implementation adds run-table lookups to every LCP call, most of which mismatch in ordinary sequence before reaching an N run.

Thus the large speedup on the raw/synthetic N case solves a real generic caps-sa pathology, but it is not evidence of a corresponding ruSTAR bottleneck. For ruSTAR, run skipping is best treated as inexpensive insurance: do an ordinary bounded SIMD probe first and consult the run table only after a long match survives that probe. That retains exact LimitProvider, custom boundary-order, finite-context, filtered-subset, and external-memory semantics without taxing the overwhelmingly common short comparison.

Focused GENCODE fixture

I used ruSTAR's pinned FASTA parser, GTF parser, junction extraction, motif/shift preparation, coordinate/strand deduplication, and build_gsj, with default sjdbOverhang=100.

The fixture is the true chr21 sequence plus every distinct splice-junction flank generated from the complete GENCODE v50 primary-assembly annotation, followed by ruSTAR's forward/reverse-complement layout:

• 5,087,789 parsed exon records
• 698,600 raw junctions
• 698,597 prepared/deduplicated junctions
• 140,417,997 forward Gsj bytes
• 374,255,962 total text symbols
• 359,616,038 retained ACGT-starting suffixes
• 1,397,196 logical forward/RC segments
• 1,397,194 segments of length 200 and two chr21 segments of length 46,709,983
• alphabet counts: A 93,067,139; C 86,740,880; G 86,740,880; T 93,067,139; N 13,242,728; spacer 1,397,196

The no-annotation control has 93,419,968 symbols, 80,177,238 retained suffixes, and two 46,709,983-base segments.

The focused fixture uses u32 internally because it is below 2^32, but exercises ruSTAR's real external/filter/custom-boundary API. A full human index dispatches u64, so these timings should not be presented as full-human genomeGenerate results.

caps-sa results

At 32 physical cores, with one warm-up and three measured runs:

cumulative tip	partitions	mean wall	vs main	mean CPU	peak RSS	temp peak/writes	result
main	5,488	14.429 s	—	387.0 s	1.564 GiB	5.359 GiB	baseline
#3	5,488	14.382 s	-0.3%	386.6 s	1.538 GiB	5.359 GiB	exact match
#4	5,488	14.408 s	-0.2%	387.1 s	1.556 GiB	5.359 GiB	exact match
#5	2,744	15.588 s	+8.0%	414.2 s	1.225 GiB	5.359 GiB	exact match
#6	2,744	15.530 s	+7.6%	416.5 s	1.217 GiB	5.359 GiB	exact match

I wrote the full main output as 359,616,038 little-endian u64 positions (2,876,928,304 bytes), then compared every emitted value from #3–#6 against it. All four tips matched byte-for-byte; this is stronger than the diagnostic hash comparison.

The phase tradeoff in #5/#6 is clear:

tip	phase 1 sort/sample/spill	phase 2	phase 3 distribute	phase 4 merge/emit
main	4.752 s	0.087 s	1.055 s	8.195 s
#5	6.577 s	0.050 s	0.452 s	7.363 s
#6	6.600 s	0.048 s	0.450 s	7.357 s

Halving the partition count saves memory, distribution, and final-merge time, but costs about 1.83 s in phase 1. On a complete human retained count, both the old and new target hit the 8,192-partition cap, so the target-size change should have no effect there.

On the no-annotation control, main averaged 1.815 s; #5 and #6 averaged 2.086 and 2.089 s, regressions of 14.9% and 15.1%, without a meaningful RSS reduction.

Scaling on the annotated fixture:

tip	1 core	32 cores	64 cores
main	305.724 s	14.429 s	8.502 s
#5	365.184 s	15.588 s	9.333 s
#6	366.149 s	15.530 s	9.252 s

#5/#6 scale slightly better but remain slower in absolute time at every measured thread count.

Run skipping

This is the strongest part of the stack.

The exact #5 detector finds 60 period-1 N runs in the parsed input, covering 13,240,000 bytes. That is 14.1726% of the no-annotation text and 3.5377% after the junction library is appended. N-starting suffixes are filtered, so this is text coverage, not a direct count of comparisons skipped.

Three-run means on 1 MiB periodic segmented inputs:

shortest period	main	#5	speedup	detected coverage
1	0.1672 s	0.0243 s	6.89×	100%
2	0.1664 s	0.0257 s	6.47×	100%
61	0.1794 s	0.0307 s	5.83×	100%
64	0.1800 s	0.0262 s	6.88×	100%
65	0.1862 s	0.1874 s	0.99×	none
171	0.1842 s	0.1856 s	0.99×	none

So I agree with the core idea, but the README statement that periods through 64 also cover satellite arrays is too broad. The canonical alpha-satellite monomer length 171 is outside the detector, and the 4,096-window sampling stage can also miss localized runs.

Correctness blocker in #5/#6

seed_params<S> accepts any Symbol with size_of::<S>() == 1, reinterprets it as u8, and uses unsigned packed-key order. Symbol includes i8, so this is not sound for negative values.

For [-1, 0, -1, 1, -2, 0, 1, -1, 0, -2, 1, 0]:

• direct order, main, 1/4 perf: radix-seeded prefix doubling for the in-memory suffix array #3, 2/4 perf: MSD counting-sort seed, and cover subsets + in-memory sample sort #4: [4, 9, 7, 0, 2, 11, 8, 1, 5, 3, 6, 10]
• 3/4 perf: external memory, 24.2 s -> 1.56 s on chr21 FASTA #5/4/4 perf: alphabet ranking, SWAR key packing, and doubling-round overhead #6: [5, 1, 3, 6, 4, 7, 0, 2, 11, 8, 10, 9]

The packed-key guard should require exact u8 (as the in-memory doubling guard already does), or perform an order-preserving signed mapping. This needs external-memory and sample-sort negative-i8 regression tests before merge.

#6 also constructs Packer::new(text) before it knows whether packed sorting is allowed. On a 64 MiB gapped-alphabet segmented input, the ranked copy cannot be used but is still allocated: RSS rises from about 778 MB on #5 to 846 MB on #6. The packer should be constructed only after the plain_lex_len and finite-context guards succeed.

Full STAR-compatible libsais comparison

Current libsais has a native GSA API using a common zero separator, so it does not require one explicit alphabet symbol per string. However, direct native GSA ordering is not STAR's ordering.

The compatible native adapter I tested does the following:

1. Identify ruSTAR's logical strings from spacer boundaries.
2. Reverse logical-string order.
3. Map A/C/G/T/N to order-reversed nonzero bytes 5/4/3/2/1 and append zero separators.
4. Run libsais_gsa_omp.
5. Translate the resident SA back to original coordinates in parallel, mark N/separator starts, traverse the SA in reverse, and emit only ACGT starts.

Reversing both alphabet and output changes libsais's boundary-smallest order into STAR's boundary-largest order. Reversing input string order repairs the equal-string position tie. A targeted semantic probe covered proper prefixes and duplicate strings, and the complete fixture then matched every one of caps-sa's 359,616,038 positions exactly.

I also implemented the legacy form using libsais_int_omp: original 0..4 symbols plus ordered distinct terminals 5..1,397,200, alphabet size 1,397,201. That output also matches every caps-sa position.

The adapter includes segment scanning, transformation, a 110,330,344-byte coordinate rank/index, libsais construction, in-place parallel coordinate translation, ACGT filtering, and output hashing. It does not time only the C function.

32 physical cores, one warm-up and three measured runs:

constructor	mean total	libsais call	mean CPU	peak RSS	temp disk	vs caps main	exact output
caps-sa main	14.429 s	—	387.0 s	1.564 GiB	5.359 GiB	1.00×	baseline
caps-sa #5	15.588 s	—	414.2 s	1.225 GiB	5.359 GiB	0.93×	yes
libsais native GSA adapter	3.629 s	2.564 s	72.9 s	2.200 GiB	0	3.98×	yes
libsais distinct terminals	12.338 s	11.247 s	216.6 s	3.250 GiB	0	1.17×	yes

Mean native phase breakdown is 0.342 s scan, 0.142 s transform, 0.045 s rank index, 2.564 s GSA construction, 0.208 s coordinate translation, and 0.328 s filter/hash.

The native process retains the 374.3 MB original ruSTAR text, a 374.3 MB transformed byte input, a 1,497.0 MB i32 SA, and the 110.3 MB adapter index. The distinct path replaces the byte transform with a 1,497.0 MB i32 text. Neither uses temporary files.

Thread sweep:

cores	native total / call	distinct total / call
1	13.178 / 6.884 s	21.761 / 15.891 s
8	4.669 / 3.119 s	13.186 / 11.658 s
16	3.970 / 2.762 s	12.983 / 11.694 s
32	3.629 / 2.564 s	12.338 / 11.247 s
64	3.752 / 2.783 s	12.335 / 11.242 s

Native saturates around 32 cores. The integer path gains little beyond eight. Importantly, the 1.397M-symbol alphabet completed successfully, so the legacy concern is a width/time/RSS problem here rather than a failure to construct.

For a complete GENCODE v50 primary-assembly ruSTAR index, the exact padded forward genome is 3,138,387,968 bytes; after the 140,417,997-byte Gsj and reverse complement, n=6,557,611,930. This requires libsais64 and 64-bit SA entries.

Lower-bound full-human working sets before exceptional library allocation/output are:

• native GSA: 6.56 GB transformed text + 52.46 GB SA + about 1.67 GB coordinate adapter = 60.69 GB (56.5 GiB); about 67.25 GB (62.6 GiB) if ruSTAR's original genome stays resident;
• legacy distinct terminals: 52.46 GB i64 text + 52.46 GB SA + about 1.67 GB adapter = 106.6 GB; about 113.2 GB (105.4 GiB) with the original genome.

So native libsais is a serious high-memory speed option and a useful comparator. It is not equivalent to caps-sa's bounded-memory construction: libsais must retain a complete SA and cannot directly stream only the filtered subset.

Suggested dispositions

• 1/4 perf: radix-seeded prefix doubling for the in-memory suffix array #3 — accept after revision. The LCP tests, verify_sa, release-profile fix, CI, and guarded plain-u8 path are useful. Correct the stale statement that ruSTAR has not migrated to SegmentedText, clarify that the verifier is for complete plain SAs, and make sure the advertised Actions jobs actually run (the API showed no check runs at these tips).
• 2/4 perf: MSD counting-sort seed, and cover subsets + in-memory sample sort #4 — split/rework. Separate the MSD seed from the dense-subset heuristic. At m >= n/8, that heuristic silently constructs the complete SA plus an n-element membership structure and full rank arrays. Make that resource change explicit/opt-in or memory-budgeted, and benchmark RSS immediately below/above the threshold. It does not apply to current ruSTAR.
• 3/4 perf: external memory, 24.2 s -> 1.56 s on chr21 FASTA #5 — split/rework; do not merge as-is. Extract run skipping into its own PR. Fix the signed-i8 bug. Keep partition sizing, prefetch, packed seed, parallel cascade, pipelining, and final key re-sort separately bisectable. Re-evaluate the 128 Ki partition target on segmented/filter workloads.
• 4/4 perf: alphabet ranking, SWAR key packing, and doubling-round overhead #6 — split/rework and defer. Fix/inherit the exact-u8 eligibility issue and move packer/ranked-text construction behind all eligibility guards. Present this as a plain-text optimization unless/until a segmented-safe key design exists.

Local checks passed for all tips: debug and release tests (62/73/76/85/87 tests for main/#3/#4/#5/#6), doc tests, fmt, Clippy with warnings denied, and rustdoc on the PR tips. Five ruSTAR segmented-vs-sentinel byte-oracle tests passed, as did a deterministic randomized segmented/filter direct-comparator probe. I did not have Rust 1.89 installed locally, and GitHub exposed no actual check runs at the pinned PR tips.

I have the complete harness, phase data, and exact-output oracle locally if useful for follow-up or for turning the GENCODE-shaped fixture into a smaller reproducible benchmark.

[rob-p]

2026-08-13 update: caps-sa 0.7.0, current ruSTAR numbers, and remaining PRs

This is a follow-up to my earlier review now that the independent proposals have been evaluated, geometric LCP memoization has been designed and measured, and the resulting code has shipped as caps-sa 0.7.0.

The released main/v0.7.0 commit is 7d1858c. The corresponding ruSTAR integration is scverse/rustar-aligner#228; it now uses the registry release, adopts the final policy API, and its Linux x86-64/v3/Arm64, macOS Arm64, Windows, fmt, Clippy, MSRV, audit, and aggregate checks are green.

What landed

The independently reviewed follow-ups had clear dispositions:

proposal	full annotated-GRCh38 result	disposition
#9: choose pivots before phase 1 and fuse sorting/distribution	397.295 s -> 365.903 s mean, -7.90%; temp writes ~193 GB -> 96.5 GB	clean implementation landed as ac0a911/ba29c3b; contributor PR closed as superseded because its head included the whole unreviewed stack
#10: lazy run skipping after a 256-symbol ordinary probe	373.800 s -> 408.053 s, +9.16%; +457,704 KiB RSS	correct, but closed without merge
#11: LCP-oracle tests, rustdoc fix, Rust CI	no ruSTAR runtime-code change	accepted and merged as cf71aaa
#12: prefetch upcoming merge candidates	373.521 s -> 293.552 s, -21.41%; phase 4 -30.99%	accepted and merged as 2b527c9
#13: parallelize merge-cascade pairs	374.029 s -> 394.635 s, +5.51%; +7.32% RSS	correct, but closed without merge

All full runs above used the actual ruSTAR-shaped GENCODE Human v50 input: GRCh38 primary-assembly FASTA plus comprehensive primary-assembly GTF, sjdbOverhang=100, 698,597 deduplicated junctions, forward/reverse-complement layout, 1,397,582 segments, STAR boundary ordering, ACGT-start filtering, external-memory u64, 8,192 partitions, and 32 pinned physical cores. Every run emitted 6,176,694,310 positions with hash e81c8f9881e322148741a23c92ae2000.

Geometric LCP memoization also landed, but deliberately as an opt-in policy, not an unconditional behavior. On the earlier complete ruSTAR fixture it reduced wall time from 291.710 s to 267.128 s (-8.43%), user CPU from 8,029.81 to 7,607.24 s, and peak RSS from 10,672,468 to 9,696,720 KiB, with identical output. The retained defaults are a 256-symbol ordinary probe, activation after 64 qualifying comparisons, admission only for exact LCPs of at least 1,024 symbols, and a 4,096-entry cap. Threshold sweeps did not find a repeatable better setting; hash-table variants were timing-neutral and added about 648 MiB, so the measured flat sorted-vector representation remains.

The public 0.7 API reflects that evidence:

• ExtMemOpts and LcpMemoizationPolicy are non-exhaustive and configured through builders;
• LcpMemoizationPolicy::geometric() is the concise ruSTAR entry point;
• GeometricMemoizationConfig is opaque, preserves nonzero invariants, and exposes getters plus with_* tuning methods;
• memoization remains phase-4-only and off unless the caller selects it;
• diagnostic counters remain private/environment-controlled rather than becoming a stable public result type.

The final pre-release optimization pass then found a larger ruSTAR-specific cost: repeated SegmentedText::lim_at searches over ~1.4 million boundaries. The release adds a small, bounded, private two-level boundary directory, keeps phase-1 positions/LCPs in structure-of-arrays form, and uses task-local ping-pong sorting when genome-scale construction already supplies abundant outer parallelism.

full ruSTAR-shaped build	wall	user CPU	peak RSS	phase 1	phase 4
pre-pass 0.7 baseline	267.592 s	7,622.88 s	10,512,408 KiB	106.847 s	155.794 s
direct SoA	267.763 s	7,631.77 s	9,932,420 KiB	105.452 s	157.191 s
+ task-local ping-pong	260.338 s	7,416.01 s	9,136,716 KiB	99.830 s	155.462 s
+ segmented-boundary directory (v0.7.0)	172.953 s	4,731.05 s	9,169,892 KiB	49.029 s	118.743 s

Thus the released result is 35.4% faster and uses 12.8% less peak RSS than the pre-pass 0.7 baseline. This table already includes the memoization work; its percentage should not be added to the earlier isolated memo-only percentage. On the focused chr21 backbone plus all GENCODE junction flanks, repeated measurements fell from 11.97–12.00 s to 7.77–7.80 s. Full and focused output hashes remained unchanged.

The pass also fixed a finite-max_context correctness issue: merge comparison had read one symbol beyond the cap before applying boundary_order. Randomized differential and external-memory regression tests now cover the exact cap.

Current status of the not-yet-accepted open PRs

As of this update the open PRs are #3, #4, #5, #6, and #8. All five are CONFLICTING/DIRTY against current main and have no current check rollup. More importantly, they overlap work already accepted or rejected through isolated PRs, so they are not a merge queue in their present form.

• 1/4 perf: radix-seeded prefix doubling for the in-memory suffix array #3 — core optimization not accepted; useful support work superseded. The LCP-array tests, CI, and rustdoc repair reached main through test+build+ci: LCP-array coverage, release profile, and a Rust workflow (independent) #11. The remaining radix-seeded prefix-doubling path and verify_sa are potentially useful for a complete, unsegmented, plain-u8 SA, but they do not reach ruSTAR's segmented/filter/external-memory path. If pursued, they should be extracted onto current main and evaluated as a generic in-memory feature, with no ruSTAR speed claim.

• 2/4 perf: MSD counting-sort seed, and cover subsets + in-memory sample sort #4 — not accepted; split/rework remains appropriate. Its MSD seed and dense-subset/full-SA strategy remain tied to the in-memory doubling path, not the production ruSTAR path. Review fixes: signed-u8 guard, dense-subset byte budget, and lcp_array #8 improves the resource semantics by replacing the implicit m >= n/8 allocation decision with an explicit byte budget, which is the right direction, but that API is buried in a large stacked branch. It needs an isolated PR and memory-threshold tests if it is still desired.

• 3/4 perf: external memory, 24.2 s -> 1.56 s on chr21 FASTA #5 — do not merge as a stack. Its two strongest ideas are already represented by the clean perf: choose pivots before sorting, and fuse phase 3 into phase 1 #9 integration and merged perf: prefetch the next candidates' text in the merge loop (independent) #12 prefetch. The run-skipping component was independently tested in its requested lazy form in perf: skip long periodic runs instead of scanning them (independent) #10 and regressed the complete ruSTAR build by 9.16%; the parallel-cascade component was isolated in perf: merge cascade run pairs in parallel (no measurable effect at 12 cores — needs your machine) #13 and regressed it by 5.51%. The original 3/4 perf: external memory, 24.2 s -> 1.56 s on chr21 FASTA #5 tip was also about 8% slower than the then-current main on the focused annotated fixture. Its negative-i8 packed-key bug is fixed in Review fixes: signed-u8 guard, dense-subset byte budget, and lcp_array #8, but that fix only becomes relevant if the guarded packed path is separately proposed again. Any remaining pipelining/key/partition ideas need isolated diffs against current main.

• 4/4 perf: alphabet ranking, SWAR key packing, and doubling-round overhead #6 — not accepted. Alphabet ranking, SWAR key packing, and doubling-round changes primarily accelerate the complete plain-text path and originally declined STAR's segmented boundary semantics. Review fixes: signed-u8 guard, dense-subset byte budget, and lcp_array #8 fixes the eager-packer allocation and signed-i8 eligibility problems and proposes segmented-safe keys, but 4/4 perf: alphabet ranking, SWAR key packing, and doubling-round overhead #6 itself is stale and should not merge.

• Review fixes: signed-u8 guard, dense-subset byte budget, and lcp_array #8 — promising pieces, but do not merge as-is. This is a 40-commit, ~3.8-KLOC follow-up stack, now conflicting with main. Its exact-u8 guard, lazy packer construction, corrected satellite documentation, and explicit dense-subset budget are sound fixes to paths that have not otherwise landed. Its lazy run-skipping policy has now been rejected for the measured ruSTAR default through perf: skip long periodic runs instead of scanning them (independent) #10. The genuinely interesting remaining performance idea is boundary_rank plus segmented-safe packed keys: on Ben's 372.9M-symbol splice-junction-shaped fixture, corrected interleaved results were about 23.5–24.0 s without keys versus 15.8–16.2 s with keys, with no repeatable RSS increase. That is encouraging evidence, but it predates the new boundary directory, is not the complete current GENCODE/GRCh38 build, and comes bundled with the rest of 1/4 perf: radix-seeded prefix doubling for the in-memory suffix array #3–4/4 perf: alphabet ranking, SWAR key packing, and doubling-round overhead #6. Because v0.7.0 has materially changed both phase 1 and phase 4, this needs extraction onto current main, an API review of the new LimitProvider capability, and a fresh full-fixture A/B before acceptance.

My recommendation is therefore to close #3–#6 as superseded by the isolated accepted/rejected results, unless their remaining generic in-memory work is going to be rebased into narrowly scoped PRs. Keep #8 open only if it will be reduced to the segmented-key proposal (and any independently useful API/resource fixes); the current aggregate branch should not merge.

The practical ruSTAR conclusion is now stronger than in the original review: the synthetic long-N pathology remains irrelevant to ruSTAR's filtered, parsed input; run skipping is useful for genuinely periodic unfiltered inputs but is a measured loss here; prefetch, fused distribution, opt-in geometric memoization, and especially faster segmented-boundary lookup all produce real gains on the actual genome-plus-annotation construction.

[BenjaminDEMAILLE]

Negative result: a wider NEON LCP body, recorded so it is not retried

Tested against 0.7.0 on the ruSTAR-shaped fixtures described in #14, Apple M4
Max, 12 threads.

The change. The 16-byte NEON step needs a vector-to-general-register
transfer (the shrn + fmov movemask emulation) to test for a mismatch, and
that transfer sits on the loop's critical path. The candidate compared four
vectors, anded the four equality masks, and tested the conjunction with a
single uminv: one transfer per 64 bytes instead of four, behind a 16-byte
head so the short-LCP regime kept the narrow path's cost. x86_64 untouched.

In isolation it works. Replaying 1,898,584 (p, q, max_ctx) triples
sampled from a real segmented build, single-threaded with the text hot:
8.0 ns per call against 6.7 ns, a 16% improvement, identical results.

On the real build it regresses. GRCh38 primary plus GENCODE comprehensive,
6,432,142,906 symbols, 773,358 segments:

	wall
main (0.7.0)	450.9 s
wider NEON body	483.9 s (+7.3%)

Both emitted 6,046,292,134 positions with identical checksums.

Why the isolated win does not transfer. The replay is single-threaded
against a hot text; the build at 12 threads is memory-bandwidth-bound, and the
wide body issues eight loads per iteration where the narrow one issues two. The
LCP kernel is not the constraint on this workload, the memory system is. The
call-length distribution says the same thing from the other side: 98.3% of LCP
calls resolve inside 16 bytes, so the wide body engages on 0.24% of calls.

Not opened as a PR.