Uses a lookup table instead of match to convert nucleotides to 2 bits

[natir]

A lookup table is faster than a match to convert nucleotides to 2-bit representation but requires the use of a 256 bytes lookup table.

In red are the results of the Bitkmer benchmark with the master version and in blue the results after my modification.

We can use unsafe get_uncheck because u8 range match in the size of the lookup table.

Another drawback of my PR is how cargo fmt format the table declaration, I can move the lookup table in a specific module.

[Keats]

I'm a bit sad the match version is not in the same ballpark :( What are you using to do the graphs? Is there a noticeable difference between get and get_unchecked?

[natir]

I'm a bit sad the match version is not in the same ballpark :(

I'm sorry but match made many tests (probably more than you think)

What are you using to do the graphs?

This graph is produced by Criterion. If you launch:

git checkout master
cargo bench --  Bitkmer
git checkout natir/faster_2bt
cargo bench -- Bitkmer

The page needletail/target/criterion/Kmerizing/Bitkmer/report/index.html contains this graph. You can probably get similar stuff with the Criterion baseline system.

Is there a noticeable difference between get and get_unchecked?

When I check asm code produce by godbolt we can see get_unchecked avoid a test. I use NUC2BIT_LOOKUP[nuc as usize] in place of *NUC2BIT_LOOKUP.get(nuc as usize) because get return an Option not the value directly

In Bitkmer benchmark we can see unchecked is a little bit faster than checked

red is unchecked, blue is checked

But the main argument to use get_unchecked for me is we didn't need this test, u8 can't be larger than 255.

[Keats]

Thanks!

[luizirber]

If you want to shorten your code, you can also do like this, using a const array.

There is a nice discussion about it in https://github.com/luizirber/nthash/pull/2, https://github.com/luizirber/nthash/pull/6 and https://github.com/luizirber/nthash/pull/8

[Keats]

Oh that's a nicer array. I'll have a look at that when I get back from holiday

[natir]

Oops I already did it in #49