Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Regression in binary_search_by #85773

Closed
brson opened this issue May 28, 2021 · 7 comments
Closed

Regression in binary_search_by #85773

brson opened this issue May 28, 2021 · 7 comments
Labels
C-discussion Category: Discussion or questions that doesn't represent real issues.

Comments

@brson
Copy link
Contributor

brson commented May 28, 2021

I don't see an issue for this.

The behavior of binary_search_by changed in #74024 such that the result of the function after the patch is not the same as before.

While not directly responsible for the downtime, Polkadot ran into this problem while trying to recover from a network failure this week: https://polkadot.network/a-polkadot-postmortem-24-05-2021/

@brson brson added the C-bug Category: This is a bug. label May 28, 2021
@bruxisma
Copy link

How is this a regression? The documentation for binary_search_by clearly states

If there are multiple matches, then any one of the matches could be returned.

@workingjubilee
Copy link
Member

workingjubilee commented May 28, 2021

It being valid for a binary search to return any element is a sufficiently well-known property of the underlying algorithm that even Wikipedia mentions it.

And from there we can find that C's bsearch does not specify which element should be returned.
java.util.Array.binarySearch also does not specify.
C#'s List.BinarySearch also does not specify.

Indeed, the cases where binary search methods do specify which value they would return are cases where the underlying algorithm is not required to be a binary search or when it returns the qualifying range. As already mentioned in the PR, if people really want to introduce determinism they can capture it with usage of partition_point.

@eddyb
Copy link
Member

eddyb commented May 28, 2021

The behavior of binary_search_by changed in #74024 such that the result of the function after the patch is not the same as before.

We make behavioral changes all the time, I don't understand why anyone is bringing "determinism" into all of this.

If you want the exact same behavior, you have to use the exact same standard library version.
We never guaranteed "cross-version reproducibility", except wherever documented as such (or in situations where only one behavior can be observed).

I don't want to unilaterally close this for now, but I am removing C-bug.

@eddyb eddyb added C-discussion Category: Discussion or questions that doesn't represent real issues. and removed C-bug Category: This is a bug. labels May 28, 2021
@jonas-schievink
Copy link
Contributor

jonas-schievink commented May 28, 2021

This specific behavior has been documented since 2018. Closing since this is not a bug.

@brson
Copy link
Contributor Author

brson commented May 28, 2021

Wow, the hostility in this thread is stunning.

@solson
Copy link
Member

solson commented May 28, 2021

Wow, the hostility in this thread is stunning.

Polkadot did lie by referring to this situation as a "compiler bug" in their tweet on the subject. To be honest, it might be a good idea to preemptively lock this thread, before it gets any more attention.

@rust-lang rust-lang locked as too heated and limited conversation to collaborators May 28, 2021
@nikomatsakis
Copy link
Contributor

My two cents:

I do indeed think that it's fair to change the details of which of many equal elements gets returned in a binary search, presuming that we have left this explicitly document as not specified. (That said, I think it'd potentially be useful to specify).

However, I agree with @brson that the general tenor of this thread felt hostile. We want to encourage people to file bugs when they see something that surprises them, even if they're not sure whether it's a bug or not. A more encouraging response might have been something like, "Thanks for filing the issue! However, even though the behavior changed, I don't think this is a bug. Binary search is documented as returning an arbitrary element when there are multiple equal elements, as is the case here. Therefore, I'm going to close as behaving as expected. Let me know if you think I've got this wrong."

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
C-discussion Category: Discussion or questions that doesn't represent real issues.
Projects
None yet
Development

No branches or pull requests

7 participants