Prefer `partition_point` to look up assoc items by JohnTitor · Pull Request #863...
source link: https://github.com/rust-lang/rust/pull/86392
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
(rust-highfive has picked a reviewer for you, use r? to override)
Awaiting bors try build completion.
@rustbot label: +S-waiting-on-perf
Trying commit 
Try build successful - checks-actions
Build commit: 05fd6aa (05fd6aaa737fb22c7a1029b309aa3709bad95d72)
Finished benchmarking try commit (05fd6aa): comparison url.
Benchmarking this pull request likely means that it is perf-sensitive, so we're automatically marking it as not fit for rolling up. Please note that if the perf results are neutral, you should likely undo the rollup=never given below by specifying rollup- to bors.
Importantly, though, if the results of this run are non-neutral do not roll this PR up -- it will mask other regressions or improvements in the roll up.
@bors rollup=never
@rustbot label: +S-waiting-on-review -S-waiting-on-perf
Some small wins up to ~0.6% and the worst regression is regex-opt's 0.3%, I guess it's acceptable?
@bors r+
Commit c0efd2a has been approved by petrochenkov
// FIXME: This should be in the standard library as `equal_range`. See rust-lang/rfcs#2184.
match self.binary_search_idx(key) {
Err(_) => self.idxs_to_items_enumerated(&[]),
Ok(idx) => {
let start = self.find_lower_bound(key, idx);
let end = self.find_upper_bound(key, idx);
let start = self.idx_sorted_by_item_key[..idx]
.partition_point(|&i| self.items[i].0.borrow() != key);
let end = idx
+ self.idx_sorted_by_item_key[idx..]
.partition_point(|&i| self.items[i].0.borrow() == key);
self.idxs_to_items_enumerated(&self.idx_sorted_by_item_key[start..end])
Comment on lines
-97 to 106
m-ou-se 14 days ago
Member
If I understand correctly, this is now doing a binary_search_by to use a binary search to find any matching key, and then does two more binary searches (left and right of the item that was found), to find the first one. Why not just use a partition_point(|| .. < ..) to find the first key directly?
That is, if you just remove the match and the Err case, and change the != to <, it still works and does the same thing, right?
m-ou-se 14 days ago •
Member
(And unless there's tons of duplicated keys, it can be a lot faster to only use partition_point for finding the lower bound, and just search linearly for the upper bound. See also the comment on line 128 before the change.
Edit: Oh, since this just returns an impl Iterator, it can just not look for the upper_bound at all and return .take_while(..) on the slice starting at the lower bound.)
JohnTitor 13 days ago •
Author
Member
Oh neat, indeed we could improve it more. I'll open a PR to follow up it, it'd be great if you could review it, thanks!
Test successful - checks-actions
Approved by: petrochenkov
Pushing 149f483 to master...
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK