Problem encountered while benchmarking: AWRY gets stuck

[feldroop]

Hello, I am currently creating a little benchmark of all FM-Index libraries in Rust. It is incomplete, but you can find it here. Of course, I included AWRY in the list of competitors. The benchmark code for AWRY is here.

I implemented the functionality to the best of my ability, but I encountered an issue. When the FM-Index of AWRY has to locate search results, it seems to end up in an infinite loop. I believe there might be a bug in the sampled suffix array implementation.

[Sawwave]

Hi Feldroop, thanks for looking into this, and for working on these speed comparisons. I look forward to seeing them when you're done.

Firstly, do you have input data I could look at, or have you gone through with a debugger to see where the application gets into the loop? If it's during suffix array creation, that's using code from the Travis Wheeler Lab at https://github.com/TravisWheelerLab/sufr. I can bring it to their attention, but it would be likely up to them to fix. If it's post suffix array creation, that'd be something that I could look into and fix. If I'm understanding your code correctly, the issue arises during Locate, not Search? If that's the case, it would be an issue on my side.

A few thoughts on the test code you gave:
I think you're likely right on the un-idiomatic nature of a few of the elements in the codebase. Coming from a C++ background, AWRY was a great learning experience for rust, but shows in a few blemishes, certainly.

AWRY requires the suffix array to be made on disk because that's what sufr required. I see looking their git blame that since writing this library they've implemented in-memory suffix array usage. I'll add that to the todo list, but unfortunately working on this software has gone from my job to a side-hobby.

I see your comment about &String. The inputs to the locate and count functions take &str, not &String, right? Is there somewhere I'm missing that takes a &String?

[feldroop]

I linked the input data here. The index creation succeeds, so its not an issue of sufr. The count function also works, and even the locate function works as long as there are no results to actually locate. I didn't investigate further, but I saw a while loop in the code, so it likely gets stuck there.

I actually forgot that those comments were still there! I thought about also creating an API comparison of the librarires, but decided against it. Sorry if they sounded a bit harsh.

I think constructing a suffix array in a file can make sense, if you're heaviliy trading off speed for low memory usage. However, the memory usage of AWRY so far does not seem to be lower than what one could achieve with a fully in-memory suffix array construction algorithm.

Yes, the (parallel) count/locate functions are the only places where I found a &String. I believe that in this case, a &[u8] might actually be more appropriate than a &str. Because unlike the std::string in C++, the Rust String and str require the data to be UTF-8 encoded. Since you're only searching for a specific set of ASCII symbols, just using a Vec<u8>/&[u8] seems to be a better fit and even removes the overhead of checking whether the input is valid UTF-8.

[Sawwave]

Thanks for the input, data, I'll take a look into it after work tonight.

You're comments weren't harsh, they were honest and constructive, and I appreciate them. When I release a new version that fixes this issue, I'll look into supporting the in-memory suffix array construction and using &[u8] for the input types, these are all great suggestions. I'll let you know how my progress goes.

[feldroop]

Hey there, just as a heads up: I just ran into further trouble using AWRY. I got a segmentation fault when building the index. I already investigated it and it happens in the sufr library. I opened an issue with them, you can find it here. I have to exclude AWRY from the benchmark until the issue is fixed.

[Sawwave]

Hey @feldroop , just wanted to post to say that I'm watching the github issue in SUFR, and as soon as they have a fix, I'll update AWRY to include the changes.

[RagnarGrootKoerkamp]

Hey both,

I'm also working on a fast FM-index currently (targeting only 2-bit encoded DNA), see quadrank.
I'm also interested in comparing against AWRY, but running into different issues, that may well be caused by the same underlying issue:

When I use a 1MB prefix of a fasta file containing viral genomes (ie multiple records), and then query simulated 150bp reads with 1% error rate, I get a bunch of matches. (Not for every read since some have errors, but still many match.)
When I then bump to a 3MB prefix or anything larger, nearly none of the reads match anymore.

The reference file I'm using is rsviruses17900.fa.gz from this zenodo link, and the reads are the rsviruses17900.r1.fastq.gz. (I've transformed both to plain fasta before feeding them to AWRY.)