Benchmarks in readme

[RagnarGrootKoerkamp]

Could you add some benchmarks to the readme comparing the performance of this crate to eg libdivsufsort and libsais (and any other SACA's that appear high on crates.io), for example for constructing the suffix array of a human genome.

It's very hard to know how useful this crate (and most other suffix array construction crates) are without having at least some easily available numbers.

Ideally you'd also include a quick sentence on all of the methods and how they differ / why you are better. Some are linear, some log-linear, and it's unclear how your method differs.

PS: the first link in the readme is broken ;)

[traviswheeler]

Thanks for the interest @RagnarGrootKoerkamp. We're in the process right now of building a benchmarking system that will evaluate sufr, libdivsufsort, libsais, and others. We don't want to muddy this repository with that evaluation code, so we'll create a 2nd repo (sufr-benchmark) and point to it when it's complete.

We'll also get to the other suggestion (describing alternative methods) in an soon-to-appear manuscript. The simplest description of how this method differs is that it follows the core ideas of CaPS-SA (merge sort with help from on-the-fly LCP array construction), then introduces ideas to dramatically reduce RAM requirement during construction, enables creation of a spaced seed SA, and provides search functions. More details to come.

(Fixed the 1st link in the README - thanks)

Finally: in a bit of synchronicity, we've just been discussing your recent static search tree post - it's a really lovely exploration of the idea. I'm toying with how to bring that approach into SA search. If you're interested in discussing, let me know.

[RagnarGrootKoerkamp]

We're in the process right now of building a benchmarking system that will evaluate sufr, libdivsufsort, libsais, and others. We don't want to muddy this repository with that evaluation code

Yeah that's reasonable

so we'll create a 2nd repo (sufr-benchmark) and point to it when it's complete.

Sounds great

We'll also get to the other suggestion (describing alternative methods) in an soon-to-appear manuscript. The simplest description of how this method differs is that it follows the core ideas of CaPS-SA (merge sort with help from on-the-fly LCP array construction), then introduces ideas to dramatically reduce RAM requirement during construction, enables creation of a spaced seed SA, and provides search functions. More details to come.

👍
I think I had the framing of expecting this to be completed work since I found it via crates.io. There's the programmer perspective where some quick info in the readme is very helpful, and then there's the academic perspective of writing a nice paper, and they slightly conflict with each other.

[traviswheeler]

I think I had the framing of expecting this to be completed work since I found it via crates.io. There's the programmer perspective where some quick info in the readme is very helpful, and then there's the academic perspective of writing a nice paper, and they slightly conflict with each other.

That's fair. You can expect some useful text to appear in the next week or two. Things slowed down in the last half of December, just after we wrapped up the final planned feature. We want to kick off a robust benchmarking run asap ... then will get back to expanding documentation to (a) discuss relative merits/performance and (b) better describe the API.

[feldroop]

Hey, I just came across this and wanted to let you know that I created a benchmark of crates.io SACAs, you can find it here.

It's only a rough benchmark and sufr is not yet included. I'd be happy to add it, but I was a bit unsure about the configuration of the algorithm. Maybe sufr does not really fit into the comparison, because the other algorithms in the benchmark simply construct the suffix array in memory. sufr seems to be more focused on creating a suffix array file and querying it, or am I mistaken?

[traviswheeler]

Sorry for the slow reply.

Briefly, I think it makes sense to include sufr. In the end: suffix array construction is usually an offline action, intended to produce an artifact that's stored in a file for later use, so the fact the sufr does this directly isn't inconsistent with the goals of SA construction. And the fact that sufr does other things (like ... search the SA) doesn't change the fact that it builds SAs

The bigger problem is that the algorithm implemented in sufr (extending the ideas CaPS-SA) gets seriously bogged down in genomic sequence that contains long repeats (like centromeres). My guess is that this will cause sufr to perform poorly on the test unless it's run with the --max-query-len flag (for something <128, for example; for most of my use cases, I'd be looking at 32 or less).

We have a solution for this repetitiveness problem designed and ready to implement, and are (still) planning to add an in-memory option for construction ... but we ended up needing to take a hiatus from the project for a bit. I expect us to be back on this within a month or so. (It's been astonishing how long a "short hiatus" became a long one...)

[feldroop]

Thank you for the reply, I agree with everything you said. I added sufr to the benchmark with max-query-len 128 (32 was very similar for me). I believe this is the most useful comparison for users at the moment, even though it is not entirely fair. I added some notes to the README that explain the background of sufr. If you want you could take a look at it and give me feedback (link). The configuration I used for sufr is here.

Unrelated to this issue, I think being able to construct a suffix array in chunks is very useful. As the author of an FM-Index library, I would be interested in the ability to generate a sampled suffix array and BWT without materializing the whole suffix array in memory. Maybe an API to iterate over the chunks would be cool to have:

SuffixArray::iter_suffix_array_chunks(builder_args).for_each(|chunk_offset: usize, suffix_array_chunk: &[u32]| {
    // ... use chunk_offset and suffix_array_chunk to construct a chunk of the BWT or sampled suffix array
}