Help optimize out bounds checks in median_of_medians#144327
Draft
kornelski wants to merge 2 commits intorust-lang:mainfrom
Draft
Help optimize out bounds checks in median_of_medians#144327kornelski wants to merge 2 commits intorust-lang:mainfrom
kornelski wants to merge 2 commits intorust-lang:mainfrom
Conversation
Collaborator
rustbot
added
S-waiting-on-review
Contributor
|
Is this something that could get a codegen test to make sure we don't have a jump to a panic? Seems easy to accidentally regress. |
Contributor
Author
|
A codegen test would be valuable, but these functions are inlined into other functions that still need bounds checks fixed, so I can't realistically codegen tests until more of this work is done. |
rustbot
added
S-waiting-on-author
Member
|
@kornelski any updates on this? thanks |
Contributor
Author
|
I've implemented further refactorings that should eliminate further bounds checks in theory, but tracking of already-checked ranges of variables turned out to be too fickle in LLVM. I got stuck at ninther that has 9 variables to check, but LLVM gets amnesia after every I can't add codegen tests, because I can't make LLVM generate good code. |
bors
added a commit
that referenced
this pull request
Oct 15, 2025
Safer sort partition This reduces amount of `unsafe` code in `partition()`, while generating essentially the same code. ~~`partition()` and functions calling it can only run into out-of-bounds issues if the `is_less` function is buggy, so I've used cold `panic_on_ord_violation()` to replace various other panics/aborts. This slightly reduces code size, and gives a more relevant error message.~~ Related to #144327
bors
added a commit
that referenced
this pull request
Oct 15, 2025
Safer sort partition This reduces amount of `unsafe` code in `partition()`, while generating essentially the same code. ~~`partition()` and functions calling it can only run into out-of-bounds issues if the `is_less` function is buggy, so I've used cold `panic_on_ord_violation()` to replace various other panics/aborts. This slightly reduces code size, and gives a more relevant error message.~~ Related to #144327
bors
added a commit
that referenced
this pull request
Oct 16, 2025
Safer sort partition This reduces amount of `unsafe` code in `partition()`, while generating essentially the same code. ~~`partition()` and functions calling it can only run into out-of-bounds issues if the `is_less` function is buggy, so I've used cold `panic_on_ord_violation()` to replace various other panics/aborts. This slightly reduces code size, and gives a more relevant error message.~~ Related to #144327
Dylan-DPC
added
S-blocked
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
4 participants
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.
LLVM can't see that
assert!((v / 200) <= (v / 2))is always true, so it couldn't remove bounds inmedian_of_ninthers..unwrap()outside ofmin_index()was losing bounds information. I've even triedassume(index < slice.len()); return Some(index), but it didn't help. Only moving theunwrap()to inside the function seems to keep the range information (and doesn't needassume).Part of #144326
Currently blocked by #144522