improve sketching performance

[kloetzl]

Mash has recently integrated some changes making it faster. I think sourmash could also benefit from them. However, my Rust isn't good enough for an actual pull request. So instead I will just point out the issues and suggest solutions.

In minhash.rs#L684 _checkdna is repeatedly called on the same characters. Mash achieved a 30% performance boost by adding just one more counter.

The function _checkdna uses a match statement which compiles to a chain of cmp and jumps. Using a lookup table will give you much better performance.

Best,
Fabian

[ctb]

thank you!! stuff like this is red meat to @luizirber I think :)

[kloetzl]

No problem. I think this should get you about 12% of performance. Maybe more. See the profile below.

[luizirber]

Mash has recently integrated some changes making it faster. I think sourmash could also benefit from them. However, my Rust isn't good enough for an actual pull request. So instead I will just point out the issues and suggest solutions.

This is what I suggest if you want to try it:

curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh
git clone https://github.com/dib-lab/sourmash.git
cd sourmash
cargo bench -- add_sequence

There are 4 benchmarks for add_sequence, and (I think) they cover most cases in the add_sequence method.

In minhash.rs#L684 _checkdna is repeatedly called on the same characters. Mash achieved a 30% performance boost by adding just one more counter.

Nice, I'll try it out! I'm also looking into the faster revcomp discussion, which can also help us.

The function _checkdna uses a match statement which compiles to a chain of cmp and jumps. Using a lookup table will give you much better performance.

@camillescott has suggestions too, for keeping track of valid/invalid positions (using a deque).

There was also a PR for the ntHash crate with similar suggestions (lookup vs match), and it was way faster.

Thanks for the great suggestions!

[luizirber]

Oh, another point: @kloetzl, did you run your tests with sourmash installed from pip, or from latest master? #845 brings some improvements and avoids _checkdna calls for each k-mer if the sequence is valid (only calls it once for the full sequence)

[kloetzl]

I used the current master (aka a601b4a). But I can't remember whether my profile was done on a clean bacterial genome, or if it did contain some characters other than ACGT. It was probably a clean bacterial genome with only ACGTs. So my performance boost estimate are off, but still you will see an effect.

[kloetzl]

There was also a PR for the ntHash crate with similar suggestions (lookup vs match), and it was way faster.

I am trying to assemble a number of these super fast DNA processing routines into a project I call libdna. It will take some time and/or help until its finished, though.

[luizirber]

Fixed in #861, thanks @kloetzl!

[kloetzl]

I am glad that I could help.