Dependency discussion per CONTRIBUTING.md ("New dependencies need prior discussion"). Sibling of
#162 (libsais), same subsystem, different candidate.
Incumbent
caps-sa 0.6 drives src/index/sa_build.rs: the segmented arm (caps_sa::SegmentedText +
StarSegmentedText), build_ext_mem for production-scale genomes with build_in_memory below the
16 MB threshold, streaming filter+pack into the PackedArray so the full SA is never materialized
twice. Byte-for-byte STAR-compatible, verified by the
segmented_arm_matches_sentinel_arm_byte_for_byte_* differential tests.
Candidate
| Crate |
Version |
License |
Last release |
sufr / libsufr |
0.7.12 |
BSD-3-Clause |
2025-02-27 |
Wheeler Lab. Parallel SA + LCP construction, explicitly "inspired by CaPS-SA" and the C++ CaPS-SA
implementation, i.e. the same algorithm family as the incumbent. Extras it advertises:
low-memory and very-low-memory modes (suffixes from disk, then text from disk too), a DNA mode
with softmask/ambiguity handling, configurable sequence delimiters, an LCP array, and a
count/locate/extract search API over its own .sufr file format.
Why this probably ends in "declined", and what would change that
Almost every sufr differentiator is either already solved here or unwanted:
- Ext-mem —
caps_sa::build_ext_mem already bounds peak RAM at ~O(text + n/p).
- DNA mode, delimiters, sentinels — the sentinel/segmented transform in
sa_build.rs exists
precisely because STAR's generalized-SA order is not the naive DNA-mode order. A crate's own
DNA handling is a liability here, not a feature.
- LCP array,
.sufr format, search API — unused; we need the permutation only.
- Maintenance — last release 2025-02-27, ~18 months ago.
What would flip the verdict: a measured win on genomeGenerate wall time or peak RSS versus
caps-sa on a real genome, at equal output bytes. Nothing else.
Checklist
Dependency discussion per
CONTRIBUTING.md("New dependencies need prior discussion"). Sibling of#162 (
libsais), same subsystem, different candidate.Incumbent
caps-sa 0.6drivessrc/index/sa_build.rs: the segmented arm (caps_sa::SegmentedText+StarSegmentedText),build_ext_memfor production-scale genomes withbuild_in_memorybelow the16 MB threshold, streaming filter+pack into the
PackedArrayso the full SA is never materializedtwice. Byte-for-byte STAR-compatible, verified by the
segmented_arm_matches_sentinel_arm_byte_for_byte_*differential tests.Candidate
sufr/libsufr0.7.12Wheeler Lab. Parallel SA + LCP construction, explicitly "inspired by CaPS-SA" and the C++ CaPS-SA
implementation, i.e. the same algorithm family as the incumbent. Extras it advertises:
low-memory and very-low-memory modes (suffixes from disk, then text from disk too), a DNA mode
with softmask/ambiguity handling, configurable sequence delimiters, an LCP array, and a
count/locate/extract search API over its own
.sufrfile format.Why this probably ends in "declined", and what would change that
Almost every
sufrdifferentiator is either already solved here or unwanted:caps_sa::build_ext_memalready bounds peak RAM at ~O(text + n/p).sa_build.rsexistsprecisely because STAR's generalized-SA order is not the naive DNA-mode order. A crate's own
DNA handling is a liability here, not a feature.
.sufrformat, search API — unused; we need the permutation only.What would flip the verdict: a measured win on
genomeGeneratewall time or peak RSS versuscaps-sa on a real genome, at equal output bytes. Nothing else.
Checklist
spacer-as-largest convention is the crux, same question as for any external SACA)
caps-saext-mem and in-mem on a real genome: wall time and peak RSSrather than pairwise