A rating system for theoretical computer scientists. The more logarithms there are (i.e. the more “\(\log\)” before your variables), the higher your reputation will be. No-log theoretical computer scientists are virtually non-existent, as virtually all non-trivial algorithms require use of logarithms. Most are one-log scientists. In the old times (well, I’m young, so these look like old times to me at least), one would occasionally find a piece of code done by a three-log scientist and ...| Posts on CuriousCoding
Table of Contents 1Minimizing critical sections 2RabbitFx: chunking 3Different chunking 4Experiments 5Outlook This is a quick note on some thoughts & experiments on fasta parsing, alongside github:RagnarGrootKoerkamp/fasta-parsing-playground. It’s a common complaint these days that Fasta parsing is slow. A common parser is Needletail (github), which builds on seq_io (github). Another recent one is paraseq (github). Paraseq helps the user by providing an interface for parallel processing of ...| Posts on CuriousCoding
Table of Contents External links The problem Initial solution: 105s First flamegraph Bytes instead of strings: 72s Manual parsing: 61s Inline hash keys: 50s Faster hash function: 41s A new flame graph Perf it is Something simple: allocating the right size: 41s memchr for scanning: 47s memchr crate: 29s get_unchecked: 28s Manual SIMD: 29s Profiling Revisiting the key function: 23s PtrHash perfect hash function: 17s Larger masks: 15s Reduce pattern matching: 14s Memory map: 12s Parallelization:...| CuriousCoding
Table of Contents GreedyMini Results A first look Comparison with optimal ILP values Large alphabets Analysing GreedyMini at \(w=3\) \(w=3\), \(k=3\) \(w=7\), \(k=3\) \(w=3\), \(k=4\) \(w=3\), \(k=5\) \(w=3\), \(k=6\) \(w=3\), \(k=7\) Looking at fixed \(k=5\) \(k=5\), \(w=4\) \(k=5\), \(w=5\) \(k=5\), \(w=6\) \(k=5\), \(w=7\) \(k=5\), \(w=8\) \(k=5\), \(w=12\) Investigating \(w=5\) \(w=5\), \(k=8\) What about \(k = w+1\)? In this post, we will look at the minimizer schemes generated by the gr...| CuriousCoding
Table of Contents 1Early idea: Bottom-up match-merging (aka BUMMer?)1.1Some previous ideas 1.2Divide & conquer 1.3Bottom-up match merging (BUMMer) 1 Early idea: Bottom-up match-merging (aka BUMMer?) Link to heading TODO: Move to separate post. One thing that becomes clear with mapping is that we don’t quite know where exactly to start the semi-global alignments. This can be fixed by adding some buffer/padding, but this remains slightly ugly and iffy.| Posts on CuriousCoding
Table of Contents 1Variants of semi-global alignment 2Fast text searching2.1Skip-cost for overlap alignments 2.2Results 3Mapping using A*Map3.1Seeding 3.2Chaining 3.3Aligning 3.4A*Map 3.5Results This is Chapter 5 of my thesis. --- Summary So far, we have considered only algorithms for global alignment. In this chapter, we consider semi-global alignment and its variants instead, where a pattern (query) is searched in a longer string (reference). There are many flavours of semi-global alignment...| Posts on CuriousCoding
Table of Contents 1Introduction1.1Results 2Random minimizers 3Algorithms3.1Problem statementProblem A: Only the set of minimizers Problem B: The minimizer of each window Problem C: Super-k-mers Which problem to solve Canonical k-mers 3.2The naive algorithmPerformance characteristics 3.3Rephrasing as sliding window minimum 3.4The queuePerformance characteristics 3.5Jumping: Away with the queuePerformance characteristics 3.6Re-scanPerformance characteristics 3.7Split windowsPerformance characte...| Posts on CuriousCoding
\[ \newcommand{\sketch}{\mathsf{sketch}} \] This is a small survey on MinHash-based sketching methods, to go along with my simd-sketch crate (github, crates.io, docs.rs). See also Cohen (2014) for a previous small survey. Goal. SimdSketch should be fast. It is and should remain a conceptually simple tool, that prefers fast implementations of simple ideas over complex ideas. For now, it works well for the simple case of relatively high identity sequences. I may implement more algorithmic varia...| Posts on CuriousCoding
1 De Bruijn graph Consider an edge-centric De Bruijn graph, where each edge corresponds to a k-mer, and nodes are the \(k-1\) overlaps between adjacent k-mers. In the figures, all edges are directed towards the right. 2 k-mers The goal is now to store all edges / k-mers of the graph efficiently. A spectrum preserving string set (SPSS) is a set of strings whose k-mers are the k-mers of the input graph, that does not contain duplicate k-mers (Rahman and Medvedev 2020).| Posts on CuriousCoding
Table of Contents Latex Code highlighting: minted Rust Cargo.toml workspace Release profile List exported functions Read human genome using needletail Prevent auto-vectorization Python Export org table Pretty plots These are some common libraries and code snippets for various tasks. Latex Code highlighting: minted 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 \usepackage[newfloat=true]{minted} \newmintedfile{rust}{ linenos, numbersep=5pt, frame=lines, baselinestretch=1.05, fontsize=\footnotesize, } \be...| CuriousCoding
Table of Contents 1Abstract 2Introduction2.1Objectives 2.2Challenges 2.3List of papers 2.4Thesis structure and contributions 2.5Personal note 3Discussion and conclusion3.1Overview 3.2Future directions 3.3Concluding remarks 4Bibliography 1 Abstract 2 Introduction Summary. 2.1 Objectives 2.2 Challenges 2.3 List of papers Pairwise alignment. A*PA, Bioinformatics 24. Groot Koerkamp, Ragnar, and Pesho Ivanov. 2024. “Exact Global Alignment Using A* with Chaining Seed Heuristic and Match Pruning....| Posts on CuriousCoding
Table of Contents 1Introduction1.1Overview 2A history of pairwise alignment 3Problem statement 4Variations on pairwise alignment4.1Alignment types 4.2Cost Models 4.3Minimizing Cost versus Maximizing Score 5The classic quadratic DP algorithms 6Linear Memory using Divide and Conquer 7Dijkstra’s algorithm and A* 8Computational volumes and band doubling 9Diagonal transition 10Subquadratic methods and lower bounds 11Parallelism 12LCS and Contours 13Some tools 14Summary 15TODO15.1A*PA2Summary/ove...| Posts on CuriousCoding
Table of Contents 1Optimizing Compute Bound Code: Random Minimizers1.1Avoiding Branch Misses 1.2SIMD: Processing In Parallel 1.3Instruction Level Parallelism 1.4Input Format 2Optimizing Memory Bound Code: Minimal Perfect Hashing2.1Using Less Memory 2.2Reducing Memory Accesses 2.3Interleaving Memory Accesses 2.4Batching, Streaming, and Prefetching 3TODO Writing High Performance Code3.1TODO Benchmarking 3.2Writing and Optimizing High Performance Code 3.3DROP? Performance Metrics Attribution Thi...| Posts on CuriousCoding
Table of Contents 1Overview 2Introduction - Previous reviews 3Theory of sampling schemes3.1Questions 3.2Types of schemes 3.3Parameter regimes 3.4Different perspectives 3.5UHS vs minimizer scheme 3.6(Asymptotic) bounds 3.7Lower bounds 4Minimizer schemes4.1Orders 4.2UHS-based and search-based schemes 4.3Pure schemes 4.4Other variantsSelection schemes Canonical minimizers 4.5Non-overlapping string sets This post is simply a list of brief comments on many papers related to minimizers, and forms t...| Posts on CuriousCoding
Table of Contents Questions and remarks on PTHash paper Ideas for improvement Parameters Align packed vectors to cachelines Prefetching Faster modulo operations Store dictionary \(D\) sorted using Elias-Fano coding How many bits of \(n\) and hash entropy do we need? Ideas for faster construction Implementation log Hashing function Bitpacking crates Construction Fastmod TODO Try out fastdivide and reciprocal crates First benchmark Faster bucket computation Branchless, for real now! (aka the tr...| CuriousCoding
Table of Contents 1Optimizing Binary Search And Interpolation Search1.1Problem statement 1.2Inspiration and background 1.3Benchmarking setup 2Baseline2.1A note on power-of-two array sizes 3Alternative memory layout3.1Naive implementation 3.2Prefetching 3.3Branchless Eytzinger 3.4Batched Eytzinger3.4.1Non-prefetched 3.4.2Prefetched 4Eytzinger or BinSearch? 5Memory efficiency – parallel search and comparison to B-trees 6Interpolation search 7Comparing everything on the human genome 1 Optimizi...| Posts on CuriousCoding
Table of Contents 1 Consensus 1.1 Consensus-RecSplit 2 IDEA: Consensus-PtrHash 3 Tiny pointers and optimal open addressing hash tables These are some thoughts on the Consensus-based MPHF presented in Lehmann et al. (2025), and how this could be applied to PtrHash: Lehmann, Hans-Peter, Peter Sanders, Stefan Walzer, and Jonatan Ziegler. 2025. “Combined Search and Encoding for Seeds, with an Application to Minimal Perfect Hashing.” arXiv. https://doi.org/10.48550/ARXIV.2502.05613. Below are ...| CuriousCoding
Table of Contents 1 Nginx setup 2 GoAccess configuration 3 Systemd setup 4 Serving the static file 5 Serving live statistics 6 GeoIP database GoAccess (goaccess.io, github) is a tool that analyses server logs and gives real-time statistics on network traffic. It took me some time to figure out exactly how to get the real-time websocket server working through Nginx, so I’m just sharing my configuration here. Install via your package manager, e.g. sudo pacman -S goaccess on Arch.| CuriousCoding