PhD on high troughput bioinformatics @ ETH Zurich; IMO, ICPC, Xoogler, Rust, road-cycling, hiking, wild camping, photography bsky.app/profile/curiouscod
Zurich
- Tweets 1,855
- Following 81
- Followers 1,171
- Likes 4,732
To all folks dealing with biological data:
do you ever need to check if your reads contain barcodes/adapters/primers/...? Or off-target matches?
Sassy is the tool to use! A super fast implementation of "approximate string matching" with a grep-like CLI.
curiouscoding.nl/posts/sassy…
1
9
24
3,441
With AVX-512, the SimdQuickHeap is consistently 2x faster than the radix heap and other engineered heaps that are I/O-efficient, and up to 10x faster than the binary heap and other tree-based heaps.
ALT Log-log time-per-operation plots for different workloads. The x-ax has increasing input sizes, and the y-ax has the normalized time per push-pop pair of operations divided by lg n. The binary heap, d-ary heap, and weak heap all slow down as n increases, while the I/O-efficient heaps all get faster. The SimdQuickHeap is 2x faster than the radix heap and up to 10x faster than the binary heap.
1
4
145
The data structure has some similarities to QuickSelect and is pretty simple: repeatedly partition the list of values using random pivots until the smallest is left, and store each part in its own array.
New elements are compared to the pivots and pushed to the right layer.
ALT Overview of the SimdQuickHeap data structure: a list (vector) of pivots is stored, and the elements between consecutive pivots are stored in their own bucket (also a vector). The elements in a bucket are in between the two pivots surrounding it.
1
2
117
Sassy, a tool for fast approximate string matching (eg searching short DNA strings) is out now!
Conceptually simple but very nice work with Rick Beeloo.
Sassy: Searching Short DNA Strings in the 2020s biorxiv.org/content/10.1101/… #biorxiv_bioinfo
2
6
24
1,873
Meanwhile, the paper with @BKille , Todd, and others on a lower bound on the density of sampling/minimizer schemes was published!
For k = 1 (mod w), the precise version (red) is the first to *exactly* match the density of optimal schemes found by ILP.
doi.org/10.1093/bioinformati…
1
8
639
OMG YES I CAN 😍
Definitely one to remember.
I run into this semi-regularly, and never knew of a workaround before.
1
2
5
726
I'm extra annoyed because the same happened last year for my 1BRC post and the video @theo made about it.
I think around half of the 40 minute video is on my blog, yet it wasn't linked in the description either.
piped.video/watch?v=e_9ziFKc…
1
3
308
Also, the BY part means a link must be shared. The link was not in the description when I was 4h into the stream, and live comments asked for it multiple times.
Stream started between 2pm and 3pm CET, and from my server logs, I get the first referrals from YT at 17:17.
1
1
100
Well great, watching live worked but now it's subscribers only. Not ideal😞
Also, my blog is CC-BY-SA, which _does_ allow others to make money off of it (since I get paid a salary anyway), as long as it's under the same licence. Private videos don't exactly feel share-alike? 🤔
Prime is streaming my blog!
Watch live now!
(I'm out, will have to rewatch tonight lol)
piped.video/live/OSN-nkxGUXU…
1
5
967
Was featured in programmingdigest.net.
Turns out that even changing my twitter handle and blog frontpage to {Groot Koerkamp} is not sufficient.
(it remains fun to trace back all traffic spikes I'm getting :)
4
469
Hmmm, can someone explain me why this test fails?
The closure to initialize A is called twice, once for A itself and once while initializing B.
(The fix is to use static instead of const and LazyLock instead of LazyCell.)
1
1
407
Scratch that. #1 now.
Hug of death incoming.... The plots total 5MB or so, so I uploaded 10GB of data in the past half hour 😅
5
38
2,532
#2 on hackernews 🤯
I did a project on making an optimized implementation of the S+ tree. The result is 40x speedup over plain binary search!
It builds on Algorithmica's post on S-trees and the famous paper "Array layouts for comparison based searching" by @pkhuong. 🧵
curiouscoding.nl/posts/stati…
ALT Example of a static search three with elements 0..17 and a 3-layer tree on top of it, with B=2 elements per node and branching factor 3.
1
11
125
9,022
The S+ trees of Algorithmica are a static, inline variant of classic B+ trees, so, 'static search trees'. Algorithmica gets 6x speedup over plain binary search. We get additional gains from batching queries, heavily optimizing the code, and cleverly interleaving queries.
ALT Some results of various improvements. First binary search, then eytzinger layout, and then a number of iterations on the S+ tree search.
1
9
1,573
I did a project on making an optimized implementation of the S+ tree. The result is 40x speedup over plain binary search!
It builds on Algorithmica's post on S-trees and the famous paper "Array layouts for comparison based searching" by @pkhuong. 🧵
curiouscoding.nl/posts/stati…
ALT Example of a static search three with elements 0..17 and a 3-layer tree on top of it, with B=2 elements per node and branching factor 3.
5
83
425
33,110
I gave a talk recently at Ben Langmead's group on my post on fast computation of random minimizers.
Was super fun!
Blogpost: curiouscoding.nl/posts/fast-…
Recording: curiouscoding.nl/talks/minim…
2
10
46
4,033
Happy to have recently rediscovered this 'non-overlapping' words scheme that was already rediscovered before by Chee (2013), and Levenshtein (1970), after the original from 1960.
Anyway, it works really great for generating near-optimal density minimizers when k<w/6.
ALT Screenshot of 'Non-overlapping codes' (2015) by Simon Blackburn
1
7
433
Slightly simplified:
1. Hash all s-mers (blue).
2. Find all open syncmers (black): t-mers that have the minimal s-mer in the middle.
3. Hash the open syncmers.
4. Let the minimal one be at position x.
5. Return the k-mer (red) at position x%w.
3/
1
3
66
To highlight simple: The open-closed minimizer is just 2 lines on top of miniception, which is a few lines on top of the random minimizer. And the mod-minimizer is 3 lines on top of that. 2/
1
2
46
The open-closed mod-minimizer is officially out, with @daniel_c0deb0t and @giulio_pibiri :D
A single simple & practical & efficient scheme that is best in class for k>w (closing ~half the remaining gap to optimal), and close to the best there currently is for k<w.
1/5
This new paper is a follow up of the WABI'24 paper featuring the mod-minimizer: it introduces the "open-closed" mod-minimizer scheme. Fantastic collaboration with @curious_coding and @daniel_c0deb0t! (A bioRxiv preprint is forthcoming.)
jermp.github.io/assets/pdf/p… 1/16
1
7
23
2,644
The results especially excite me since my 'threshold' scheme is near-optimal for k<w/6, while nothing is near-optimal for k just below w.
Understanding both may lead to some combination that gets even closer to that bottom-left corner.
5/5
1
177
Bedtime figure.
It's really cool how the red SusAnchorALex line is so good for small k and k=w+eps, and exactly when it drops off, the grey Threshold scheme takes over, perfectly continuing the curve.
Surely there must be some scheme covering the remaining ground...
1
246
Found two new schemes, so here's an updated gif.
The last one completely changes everything... the current lower bound may be almost tight after all 🤯
Really, it's hard to understate how HYPED I am 😆
2
1
12
1,698
Number of times I've wanted to click any of these tabs: 0
Number of times I've wanted to click settings: many
1
170
Here's another one of a seemingly super-close-to-optimal 'selection scheme' that can select any position in the window (so always has k=1).
3
1,181
In practice, the mod-minimizer that @giulio_pibiri and I recently introduced has near-optimal density when k ≡ 1 (mod w) and the alphabet is large (256). In fact, we prove that the mod-minizer becomes optimal as the alphabet goes to infinity!
1
4
98
Consider the De Bruijn graph of order w+k=ℓ+1 (b). Each pure cycle of length c|w+k must contain at least ⌈c/w⌉ distinct sampled positions, and hence at least as many charged edges in the order ℓ DBg (a).
ALT (a) A De Bruijn graph B3 corresponding to a minimum-density (2, k=2)-forward scheme. The underlined position in each vertex labels represents the 2-mer that is selected for that window. The solid edges represent the charged contexts and the edge colors represent the pure cycles in B4 (not B3 itself). For characters ci, each edge (c0c1c2, c′ 0c′ 1c′ 2) in B3 corresponds to the vertex c0c1c2c′ 2 in B4. (b) The corresponding (2, ℓ=4)-UHS in B4. The vertices are partitioned by color, representing the pure-cycles. The vertices with a double border represent the charged edges in B3 in (a) and the corresponding (2, 4)-UHS. Each pure cycle c has at least ⌈|c|/w⌉vertices in the UHS.
2
4
309
For large alphabet of size 256 (up from 4), the figure is actually much prettier:
we can interpolate the red lower bound, and the new scheme very closely matches it for k>w.
4
230
We had the mod-minimizer (blue) and very soon the lower bound preprint will be up (lower red function).
Iterating a bit on @daniel_c0deb0t's idea (thanks PyO3 😆), I found this new scheme (dotted red), which halves the gap towards the lower bound, and may well be near-optimal.
1
3
16
2,174
From the PLA-index paper by @pashadag:
That big flat in the middle around (2e12, 1e8) indicates a complete lack of k-mers starting with CG in chromosome 1. Why is that?
The 4 smaller flats are xCG for each option of x, and more generally, all underrepresented kmers contain CG.
1
4
689
FYI: Don't let LLMs write your Bioinformatics paper!
(I agree, but wasn't aware it's a hard rule.)
3
2
592
Just listened to a wonderful talk on suffix array construction by Paolo Ferragina (*not* the F of FM-index ;)
Turns out their SA-construction code from 2002 was still 3rd fastest on real-world text when benchmarked 5y ago! Surely it can be optimized!
github.com/acubeLab/Deep-Sha…
ALT Screenshot from the SACAbench paper by Bahne et al, showing that Deep-Shallow (3rd col, green) is only up to 2x slower than divsufsort, the state of the art.
1
8
694
Spot the bug.
This produces random numbers, but all vector elements end up having the same value.
1
197
ah it's just a sway (/wayland?) setting actually. But either way I've been using lenovo x1 keyboards ever since I started at google 7y ago
1
42
Ever write an if statement, and then directly after write the same if statement just in case radiation hit your hardware?
Here RCX and R9 are compared for inequality at the end of the loop, and then the very first thing in the next iteration is to panic if they are equal?!?!?
1
175
More questions:
On line 6 there is a useless mov to %ecx, since the first time that register is used again is when line 10 overwrites it.
Why is line 6 there? What purpose does the compiler think it has that I do not see?
3
1
5
1,265
Below, the (0..len).collect() works, but when wrapping it, it needs the TrustedLen impl to avoid the grow_one call, even though all code seems inlined.
But the goal was not to do unsafe 😅
Probably I just do vec![default(); len] and overwrite that.
1
1
41
I've been staring at this for 2-3 hours now.. Plz send help 🥺
The code on the left makes a Vec with capacity. The push will always fit.
The assemly on the right nevertheless has a `cmp` to call `grow_one` if needed. Why???
That also prevents inlining the vector address %rax
4
1
3
471
Yes neat! Reminds me of some massive undergraduate physics textbook.
I'm at this now, when the screen is wide enough. (Otherwise it's a popup and at the bottom of the page.)
2
302
Working on the CSS of my blog, but chrome has some weird rendering bug when:
1) using rounded corners, and
2) using different border widths, and
3) the content is wide enough to trigger a scroll bar.
I was so happy with how cute the borders look, but this makes me sad.
2
196
Isn't the entire point of 2FA codes to store them not with the password itself? My password manager explicitly recommends against it anyway.
Or have we decided that random passwords in a password manager are good enough, in which case, why bother with 2FA in the first place?
1
197
When you finally get the compiler to generate gather instructions, and now your code is twice as slow
1
8
650
