Github Instruct LLVM that binary_search returns a valid index by SkiFire13 · Pul...
source link: https://github.com/rust-lang/rust/pull/81354
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Conversation
This allows removing bound checks when the return value of binary_search
is used to index into the slice it was call on. I also added a codegen test for this, not sure if it's the right thing to do (I didn't find anything on the dev guide), but it felt so.
(rust-highfive has picked a reviewer for you, use r? to override)
This seems like the wrong way of fixing the issue. get_unchecked
requires that the index be in bounds - if LLVM can't remove the bounds check, then get_unchecked
itself should be fixed instead of trying to work around the issue at a particular callsite.
I assume that the get unchecked doesn't emit a bounds check, but for some reason isn't propagating the information to outside the function, whereas the assume does - note that the test case checks for the lack of problems indexing with the returned usize.
I do agree that it may be worth considering the assume being inlined into get unchecked instead.
This seems like the wrong way of fixing the issue. get_unchecked requires that the index be in bounds - if LLVM can't remove the bounds check, then get_unchecked itself should be fixed instead of trying to work around the issue at a particular callsite.
get_unchecked
requires the index to be in bounds, however that is a check the programmer has to do, otherwise the result is UB. This check was already done in the implementation of binary_search
, in fact there aren't bound checks in its implementation. However if that, index after being returned, is used to safely index the slice on which binary_search
was called, you'll get a bound check that isn't optimized away. The problem is that this bound check is useless because the index has been proved by us to be valid, but LLVM has no way to know that. That assume
tells LLVM just that and allows that bound check to be optimized.
I do agree that it may be worth considering the assume being inlined into get unchecked instead.
I didn't thought of that, I based this on the implementation of Iterator::position
for slice::Iter
which however doesn't use get_unchecked
. Still, it looks like a good idea to me.
Well, in theory, LLVM could see that the access through get unchecked guarantees that the index is valid, but I imagine it would be quite difficult to demonstrate that.
Cc @nagisa @cuviper @nikic - IIRC, in the past assume in common methods like get_unchecked has actually been rather unhelpful, but I don't recall if we've specifically tried it with get_unchecked.
in the past assume in common methods like get_unchecked has actually been rather unhelpful
That's correct – in the past any attempts to add assume
would only help with very handpicked samples and not others. Furthermore assume
often has a nasty side-effect of preventing other optimisations from occurring, so we have refrained from adding assume
s to the standard library implementation where the intent is, like done here, to improve certain very specific examples.
Well, in theory, LLVM could see that the access through get unchecked guarantees that the index is valid, but I imagine it would be quite difficult to demonstrate that.
Aren't bound checks basically if
s? I don't think they be elided just by knowing a certain memory access is valid.
That's correct – in the past any attempts to add
assume
would only help with very handpicked samples and not others. Furthermoreassume
often has a nasty side-effect of preventing other optimisations from occurring, so we have refrained from addingassume
s to the standard library implementation where the intent is, like done here, to improve certain very specific examples.
Is this about adding assume
to general purpose methods, like get_unchecked
, or to specific ones like position
or binary_search
? I guess with general methods it's pretty rare that that condition is later used, however with more specific ones I would expect it to be used more often.
This works as an alternative to assume.
if base < ary.len() { if cmp == Equal { Ok(base) } else { Err(base + (cmp == Less) as usize) } } else { unsafe { std::hint::unreachable_unchecked() } }
https://rust.godbolt.org/z/9o9oq8
Edit: nevermind, this also boils down to assume
in the IR.
This seems related to what I see when using the newly introduced unwrap_unchecked()
at #81383.
I have filled https://bugs.llvm.org/show_bug.cgi?id=48975 with the IR reduction and an analysis of why manually integrating the function (e.g. via a macro) helps sometimes. If solved, it may solve also this one as well as others like:
The latest upstream changes (presumably #74024) made this pull request unmergeable. Please resolve the merge conflicts.
Triage:
@SkiFire13 - thanks for resolving, setting this to waiting on review.
@rustbot label: +S-waiting-on-review -S-waiting-on-author
Going to re-assign to @nagisa who can better judge whether we should do this, but past experience hints to me that this is likely to hurt more than help in the common case.
#80836 comes to mind as a counterexample to usefulness of this kind of optimisation. Basically, it really matters In this particular case what the implementation of the len
method is. Given this is a slice
the len
method is going to be fairly trivial (a field read). Thus an assume like this one does have a fair chance of improving other code that does not directly rely on the len()
method, but otherwise interacts with the metadata portion of the slice's fat pointer.
@bors r+ with that in mind, but happy to revert if anybody pinpoints this to cause any kind of regression in their code.
Commit c9d04c2 has been approved by nagisa
@bors rollup=never
Test successful - checks-actions
Approved by: nagisa
Pushing 1df2056 to master...
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK