fix: improve perf of count with smarter handling of half-open range #25
Conversation
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
b8e3b88 to
9cc7957
Compare
There was a problem hiding this comment.
Pull Request Overview
This PR refactors the interval counting logic to remove an extra cursor-advancing loop, replaces the traditional binary search with a branchless version, and bumps the crate version to 1.2.0.
- Remove mutable
topbinding and simplify stack handling - Introduce branchless
bsearch_seq, eliminate inclusive-range loop incount - Bump
rust-lapperversion from 1.1.0 to 1.2.0
Reviewed Changes
Copilot reviewed 2 out of 3 changed files in this pull request and generated no comments.
| File | Description |
|---|---|
| src/lib.rs | Simplified stack pop, replaced binary search with branchless variant, adjusted half-open logic in count, and left a debug println! in tests |
| Cargo.toml | Updated package version to 1.2.0 |
Comments suppressed due to low confidence (3)
src/lib.rs:431
- [nitpick] The variable name
cursoris ambiguous in the context of a search index; consider renaming to something likeindexorposition, and likewise renamelengthtoremainingorspanfor clarity.
let mut cursor = 0;
src/lib.rs:587
- [nitpick] It would be helpful to add unit tests targeting edge cases around the
start + one::<I>()adjustment to ensure the half-open interval logic remains correct under all boundary conditions.
let first = Self::bsearch_seq(start + one::<I>(), &self.stops);
src/lib.rs:1009
- This debug
println!in the test appears to be leftover and will clutter test output; consider removing it.
println!("{:?}",lapper);
The BITS paper uses fully inclusive ranges. When this was written I'm not sure I understood that. To get things to match the naive version of count (find -> count) I had a while loop in the bits count method to advance the cursor past the matched start/stop index. This change was found while porting mojo-lapper and removes the while loop. It also has a more effecient branchless binary search. Benchmarks for count improve 24-30% (see PR).
9cc7957 to
6f55829
Compare
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.
The BITS paper uses fully inclusive ranges. When this was written I'm not sure I understood that. To get things to match the naive version of count (find -> count) I had a while loop in the bits count method to advance the cursor past the matched start/stop index.
This change was found while porting mojo-lapper and removes the while loop. It also has a more effecient branchless binary search.
Benchmarks for count improve 24-30% (see PR).
Bakeoff/rust-lapper: count with 100% hit rate time: [14.742 us 14.773 us 14.811 us] change: [-24.448% -24.164% -23.869%] (p = 0.00 < 0.05) Performance has improved. Found 18 outliers among 100 measurements (18.00%) 18 (18.00%) high severe Bakeoff/rust-lapper: count with below 100% hit rate time: [2.1958 us 2.2019 us 2.2076 us] change: [-30.391% -29.790% -29.274%] (p = 0.00 < 0.05) Performance has improved. Found 6 outliers among 100 measurements (6.00%) 6 (6.00%) low mild Benchmarking Bakeoff/rust-lapper: count with below 100% hit rate - chromosome spanning interval: Collecting 100 samples in estimated 5.0080 s (2.3M ite Bakeoff/rust-lapper: count with below 100% hit rate - chromosome spanning interval time: [2.1989 us 2.2070 us 2.2148 us] change: [-32.616% -30.807% -29.536%] (p = 0.00 < 0.05) Performance has improved. Found 6 outliers among 100 measurements (6.00%) 5 (5.00%) low mild 1 (1.00%) high severe