Dependency discussion: libsais (vendored C via cc) for suffix-array construction

[BenjaminDEMAILLE]

CONTRIBUTING.md asks for a new dependency, especially a non-Rust one, to be raised in an issue before the PR. #109 predates that rule and adds one, so here are the facts and the trade-offs. The decision is yours; I am not arguing for it here, only laying it out.

What it is

Crate	libsais 0.2.0, wrapping libsais-sys 0.2.0
Upstream	https://github.com/feldroop/libsais-rs, wrapping IlyaGrebnov/libsais
Licence	MIT OR Apache-2.0, both crates
New transitive deps	bytemuck, either, and cc as a build dependency
Declared as	libsais = { version = "0.2.0", default-features = false }

What it does to the build

The C is vendored in libsais-sys (libsais/src/*.c, libsais/include/*.h) and compiled by cc. There is no system library to install, no bindgen, no libclang, and no pkg-config probe. cc pulls in find-msvc-tools on Windows, which is how it locates MSVC.

default-features = false matters: the crate's default feature is openmp, which would add an OpenMP toolchain requirement. It is off, so the C is built single-threaded and nothing outside the vendored sources is needed.

The five-platform CI matrix on #109 is green, windows-x86_64 included.

What it buys

Suffix-array construction time, on this branch, --runThreadN 8, same machine, warm cache. Both builders produce byte-identical SA and SAindex, because the suffix array of a text is unique.

genome	size	libsais	caps-sa	ratio
yeast R64-1-1	12 Mb	1.0 s / 0.39 GB	1.7 s / 0.22 GB	1.6x
human chr1	249 Mb	27.4 s / 6.5 GB	47.2 s / 5.6 GB	1.7x
GRCh38 primary	3.1 Gb	641.6 s / 86.8 GB	1040.4 s / 14.4 GB	1.6x

--runThreadN 8, same machine, warm cache. The ratio holds across three orders of magnitude. libsais is single-threaded here, because default-features = false turns off its OpenMP feature; it still wins because caps-sa spends about six times the total CPU work for the same array (on GRCh38: 726 s of user time against 6135 s).

What it costs

• A C compiler in the build. Today the crate graph is pure Rust; this changes that for everyone who builds from source, including crates.io consumers.
• Supply chain. Two more crates and a vendored C library to track for advisories. cargo audit is clean today.
• Memory. libsais is in-memory. Its peak is roughly 17 × 2N bytes, so a mammalian genome needs on the order of 100 GB where the external-memory builder needs a few. genomeGenerate: libsais suffix-array builder, selected by --limitGenomeGenerateRAM #109 gates the choice on --limitGenomeGenerateRAM for exactly that reason, and at the 31 GB default a human genome takes the caps-sa path, not this one.

That last point is the honest summary of the scope: the win lands on genomes up to roughly chromosome scale, which is where most of the test and development loop sits, and the default declines it above that.

Alternatives

• Do nothing. caps-sa already builds correct indices, and genomeGenerate on GRCh38 is already faster than STAR 2.7.11b on this branch's predecessor work (7:36 against 11:26 wall, 32 threads). The gain here is on smaller genomes.
• Pure-Rust SA-IS in tree. No new dependency and no C, at the cost of writing and maintaining a construction algorithm that libsais has spent years tuning. It would also have to be re-validated for byte-identity.
• Optional feature. Put libsais behind a non-default Cargo feature so the default build stays pure Rust and packagers opt in. This costs a CI dimension and means the fast path is not what most users get.

If the answer is no, #109 closes and nothing is lost but the branch. If it is "yes, but behind a feature", say so and I will restructure it that way.