Repository navigation
chaining: mb_chain_backtrack traverses the chain graph twice just to size u[] #24
Description
mb_chain_backtrack (lchain.c:43) walks the z[]/p[] chain graph twice with identical logic — lchain.c:60-72 ("precompute n_u") and lchain.c:75-87 ("populate u[]"). Both call mb_chain_bk_end and traverse every predecessor link, and both memset(t, 0, n * 4) first. The only thing between them is the allocation they exist to size:
u = Kmalloc(km, uint64_t, n_u);There is a third counting pass at lchain.c:51-53, precomputing n_z to size z[].
The second traversal is pointer-chasing over p[], so it is cache-unfriendly relative to its instruction count. A growable u[] (or an upper-bound allocation of n_z entries, trimmed after) would remove one full traversal.
Inherited verbatim from minimap2 (lchain.c:44 and :59 upstream), so this is not a minibwa regression — filing it because minibwa is free to diverge.
Expected impact
Small. In a sample profile on this machine (arm64, 8 threads, hg38), mb_lchain_dp — which inlines both mb_chain_backtrack and compact_a — is 6.2% of busy samples on HG002 HiFi 10k reads and 0.5% on HG002 WGS 1M pairs. The backtrack is a fraction of that, and this removes roughly half of the backtrack. Worth doing for long-read workloads only, and only if it stays simple.
Activity