Repository navigation
Conversation
Optimize the Farrar striped mate-rescue kernel (ksw_ll_u8_core / ksw_ll_i16_core)
on arm64, building on the affine-gap reassociation. All changes are arm64-gated and
bit-identical to the baseline; the x86 path is unchanged.
- Hybrid recurrence: E' reads the reduced H' (classic), F' reads max(M,E), dropping
one max off the loop-carried chain.
- USQADD with an unshifted signed query profile: one saturating op for the match add
instead of uqadd+uqsub. Exact -- any divergence is past the score ceiling, where the
existing gmax+shift>=255 early exit already fires.
- Pair-lookahead in the lazy-F correction (F'(j+2) folded), halving that chain, with a
cheaper exit test (cmhi/shrn/fmov) and stripe-pair umaxp reduction; the block is
skipped when F'(i,slen)==0.
- Interleaved {H,E} ping-pong buffers with one paired store per stripe (last pair peeled
so the next row's diagonal input is not delayed). The widened qinit layout that feeds
this is gated on __ARM_NEON, so non-ARM builds keep the original allocation.
- Row max taken from max(M,E); deferred Hmax copy; hoisted invariants; register carry of
H'(i,slen-1) across rows.
The reassociation fast path is gated on gapo>0 (verbatim baseline otherwise), so the
gapo>=0 precondition holds by construction (mate rescue calls with gapo=(q+a-1)/a >= 0).
Validated: sw_bench --check --mode rescue PASS (120k pairs); a differential harness over
both cores comparing every ksw_llrst_t field (score/te/qe/score2/te2) across many
gap-parameter sets incl. o=0 and the pe.c-derived gapo, 0 mismatches; full-aligner SAM
byte-identity on real WGS PE reads. +30% on Graviton4 (1.36/1.29/1.29x at qlen
100/150/250; 1.5-1.9x at production rescue hit-rates); neutral/byte-identical on x86.
|
Note Reviews pausedUse the following commands to manage reviews:
Use the checkboxes below for quick actions:
Important Draft PR not reviewedDraft PRs are not automatically reviewed by default.
To automatically review draft PRs, update your CodeRabbit configuration: reviews:
auto_review:
drafts: trueThanks for using CodeRabbit! It's free for OSS, and your support helps us grow. If you like it, consider giving us a shout-out. Comment |
Owner
Author
|
@coderabbitai pause |
✅ Action performedReviews paused. |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
What
Speeds up minibwa's #2 short-read hotspot — the Farrar striped mate-rescue Smith-Waterman kernel (
ksw_ll_u8_core/ksw_ll_i16_core) — on arm64/NEON only, on top of the existingperf/ll-sse-affine-reassoc-armfeature. Every change is#if defined(__ARM_NEON)-gated; the x86 path is byte-identical to the prior kernel.E'reads the reducedH'(classic),F'readsmax(M,E)— one max off the loop-carried chain.uqadd+uqsub. Exact — any divergence is past the score ceiling, where the existinggmax+shift>=255early exit already fires.F'(j+2)folded), halving that chain, with a cheaper exit test (cmhi/shrn/fmov) and stripe-pairumaxpreduction; the block is skipped whenF'(i,slen)==0.ksw_ll_qinitlayout that feeds this is gated on__ARM_NEON, so non-ARM builds keep the original allocation.max(M,E); deferredHmaxcopy; hoisted invariants; register carry ofH'(i,slen-1)across rows.The reassociation fast path is gated on
gapo>0(verbatim baseline otherwise), so thegapo>=0precondition holds by construction — mate rescue calls withgapo=(q+a-1)/a >= 0.Performance (
bwa-bsw-bench, arm64 Graviton4 c8g, best-of-7 ×2)At production-like rescue hit-rates the gain is larger (1.5–1.9×), since the lazy-F work is a smaller share there. x86 (c6a): neutral (1.00×), byte-identical — the guard leaves the x86 path unchanged.
Correctness
./sw_bench --check --mode rescue: PASS — 120,000 pairs identical in score and CIGAR.ksw_llrst_t(score/te/qe/score2/te2, not just score) between baseline and candidate, both cores, across many gap-parameter sets includingo=0and thepe.c-derivedgapo, plus small-slenboundary cases — 0 mismatches.Draft,
feature-labeled review vehicle — installation is the manifest's job, not this PR.