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.
mb_chain_backtrack(lchain.c:43) walks thez[]/p[]chain graph twice with identical logic —lchain.c:60-72("precompute n_u") andlchain.c:75-87("populate u[]"). Both callmb_chain_bk_endand traverse every predecessor link, and bothmemset(t, 0, n * 4)first. The only thing between them is the allocation they exist to size:There is a third counting pass at
lchain.c:51-53, precomputingn_zto sizez[].The second traversal is pointer-chasing over
p[], so it is cache-unfriendly relative to its instruction count. A growableu[](or an upper-bound allocation ofn_zentries, trimmed after) would remove one full traversal.Inherited verbatim from minimap2 (
lchain.c:44and:59upstream), so this is not a minibwa regression — filing it because minibwa is free to diverge.Expected impact
Small. In a
sampleprofile on this machine (arm64, 8 threads, hg38),mb_lchain_dp— which inlines bothmb_chain_backtrackandcompact_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.