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

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

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.

--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. #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.

Start with CONTRIBUTING.md and the dependency changes described in #109. Review the reported CI matrix, libsais memory trade-offs, and benchmark results before deciding whether the dependency should be accepted, made optional, or rejected. Done means the dependency policy decision is recorded and #109 is either restructured accordingly or closed.