Repository navigation
Conversation
… sorts The klib radix sort does one 8-bit pass per key byte, but every KRADIX_SORT_INIT in the tree declared an 8-byte key while the actual keys are narrower. Declaring the true width skips the passes over the always-zero high bytes. Two structural (not workload-dependent) bounds are exploited: - Genome coordinates -- seed SA/BWT positions (key_sai0), anchor target positions (key_anchor), and the chain/pair target-coordinate sorts in lchain and pe -- are bounded by the index length (< 2^40, i.e. references up to ~1 Tbp), so a 5-byte key suffices. - The chain-backtrack sort keys on f[i], a non-negative int32 score stored in a uint64, whose top 32 bits are structurally zero, so a 4-byte key suffices. The score<<32 sorts (mb_gen_hit, mb_hit_sort, mate rescue) are left at 8 bytes: their high-byte occupancy depends on read length rather than a structural bound. Output is unchanged: byte-identical SAM verified against stock across PE default, -u, -b MD, -b cs, single-end, and Hi-C (-5P). In isolation the narrowed sorts are 1.5-4.9x faster; end-to-end the effect is small because radix sorting is well under ~1% of map CPU time (dominated by the ksw2 DP kernels).
|
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. |
nh13
added a commit
that referenced
this pull request
Sep 7, 2026
Right-size klib radix key widths (5-byte genome coordinates, 4-byte int32 chain score). output = identical; byte-identity verified across PE default, -u, -b MD, -b cs, single-end and Hi-C. Kept downstream-only (upstreamable = false); fork PR #46.
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.
Downstream
identical-class perf feature. Not for upstream submission.What
Every
KRADIX_SORT_INITin the tree declares an 8-byte key, but klib radix does one 8-bit pass per key byte, so narrow keys pay for passes over always-zero high bytes. This declares the true width where the bound is structural (not workload-dependent):key_sai0), anchor target positions (key_anchor), and thelchain/petarget-coordinate sorts. Bounded by index length (< 2^40 ≈ references up to ~1 Tbp).mb_chain_backtracksorts onf[i], a non-negativeint32in auint64→ top 32 bits structurally zero.The
score<<32sorts (mb_gen_hit,mb_hit_sort, mate rescue) are left at 8 bytes on purpose — their high-byte occupancy depends on read length, not a structural bound.Correctness
Byte-identical SAM vs stock
f0e1174across PE default,-u,-b MD,-b cs, single-end, and Hi-C (-5P) on HG002 WGS-1M + HiFi-10k against hg38. Narrowing only removes provably-zero high bytes, so ordering (including the unstable radix tie-break) is unchanged.Performance
mapCPU time (dominated by the ksw2 DP kernels). Measured sort volume concentrates in anchor-tpos, chain-score, gen-hit, and compact_a. Shipped because it is free and byte-identical.Not a ksw2 kernel change, so the SW-kernel bench does not apply; validated by the byte-identity map gate above.