Post

It's a good day when the first item in your feed is your own work :) @rickbitloo.bsky.social was annoyed that scanning reads for all 96 rapid kit barcodes is bottleneck in Barbell, so he made Sassy2: 13x (150bp) to 4.6x (8kbp) faster than v1 by batch-searching patterns, and >100Gbp/s on 16 threads!

Just for reference, the tiling strategy in v1: the text is split into 4 chunks that are processed in parallel with 1 chunk per 64 bit SIMD lane. Each lane represents 64 adjacent *columns* of the DP matrix.

In v2, we filp the SIMD tiling and bitpacking direction: Each lane represents a separate *pattern*, and the bits are adjacent *rows* of the matrix. Basically the original 'pack multiple patterns in a word' of Hyyrö 2005, but on an AVX-512 SIMD level. So now we can search 16 32bp patterns at once!

Another cool trick, also by Hyyrö: if k=3 edits are allowed, then most of the time, this cost is exceeded after aligning around 6-10 characters. Thus, we first only find cost <=k candidate matches of the 16bp suffix of each pattern, so that we can double the SIMD parallellism to 32 x 16bp.