caps-sa

caps-sa

A pure-Rust implementation of CaPS-SA — a cache-friendly, parallel, sample-sort-based suffix array constructor (Khan et al., WABI 2023).

Generic over the symbol type (u8, u16, … any Symbol) and index width. Scales to human-genome inputs (≈ 6 × 10⁹ symbols) on commodity hardware via an external-memory path that streams the SA out as positions are emitted.

DocumentationGitHub ↗

Genome-scale, on commodity hardware.

Complete ruSTAR-shaped GRCh38 + GENCODE Human v50: 6.56 billion symbols, 1.40 million segments, ACGT-start filtering, and STAR boundary ordering. Measured with 32 physical cores on an AMD EPYC 9555.

2.88 min

6.18 billion emitted suffixes

caps-sa 0.7.0 completes the generalized, filtered construction in 172.953 s with 8.75 GiB peak RSS.

35.4%

Faster than the pre-pass 0.7 baseline

Task-local phase 1, direct SoA data flow, and indexed segment boundaries also reduce peak RSS by 12.8%.

What it does.

01

Generic over symbols

Sort u8, u16, u32, u64, [u8; N] — anything implementing Symbol. Index width is u32, u64, or usize.

02

In-memory & external-memory

A parallel merge-sort and an in-memory sample-sort for RAM-rich hosts; a disk-spilling sample-sort when the SA can’t fit. Same SA, same kernel.

03

LCP-enhanced merge

Carried LCP arrays decide most merge comparisons in O(1), with a SIMD LCP fast path (AVX-512BW → AVX2 → NEON → scalar) selected once per build.

04

Streaming output

The external-memory path emits SA positions in lex order through a caller closure. Peak RAM stays bounded at ~O(text + n/p) — the SA is never fully materialised.

05

Sort a subset

The *_for_positions entry points sort only the positions you hand them. Filtered positions (N’s, spacers) never enter the sort.

06

Generalized-SA ready

A SegmentedText limit-provider stops LCP scans at segment boundaries — the hook STAR-style genome+junction indexes build on.

07

Optional long-LCP reuse

Bounded, partition-local geometric memoization reuses exact long matching intervals without taxing ordinary short comparisons. It remains opt-in and improved the complete ruSTAR-shaped build by 8.4% in isolation.

Two faces, one kernel.

Embed it, or run it

caps-sa ships as a library for embedding in larger tools (it backs the genome indexer in rustar-aligner) and as a small CLI example for standalone suffix-array construction and benchmarking.

Add the crate from crates.io, or build the CLI from source.

installquick startthe algorithm

# Library · add to your crate
$ cargo add caps-sa

# CLI · build the example binary
$ cargo build --release --example caps_sa

# construct a suffix array, streaming from disk
$ ./target/release/examples/caps_sa input.bin sa.bin \
    --ext-mem --threads 16

The 0.7 production path.

Complete ruSTAR-shaped GRCh38 + GENCODE v50 construction. All rows emit the same 6,176,694,310 positions and output hash. See the performance page for the workload definition and separate upstream comparison.

Implementation	Wall	User CPU	Peak RSS
Pre-pass 0.7 baseline	267.592 s	7,622.88 s	10,512,408 KiB
caps-sa 0.7.0	172.953 s	4,731.05 s	9,169,892 KiB