Tracking Issue for `partition_point`

[VillSnow]

Feature gate: #![feature(partition_point)]

This is a tracking issue for [T]::partition_point.

See also rust-lang/rfcs#2184

Public API

impl<T> [T] {
    pub fn partition_point<P>(&self, mut pred: P) -> usize
    where
        P: FnMut(&T) -> bool;
}

Steps / History

• Implementation: Add partition_point #73577
• Final commenting period (FCP): Tracking Issue for partition_point #73831 (comment)
• Stabilization PR: Stabilize the partition_point feature #81012
• Update documentation of binary_search (and/or binary_search_by) to point out the existence of this function too.

Unresolved Questions

• Is there a better name? partition_point matches C++, but might be hard to recognize as a binary search.

[timvermeulen]

In order to deduplicate this code with binary_search_by's implementation, I think we can simply implement partition_point in terms of binary_search_by like so:

use crate::cmp::Ordering::{Less, Greater};

impl<T> [T] {
    pub fn partition_point<P>(&self, mut pred: P) -> usize
    where
        P: FnMut(&T) -> bool,
    {
        self.binary_search_by(|x| if pred(x) { Less } else { Greater })
            .unwrap_or_else(|i| i)
    }
}

[VillSnow]

@timvermeulen

I prefer my partition_point code than current binary_search_by code.
I found current binary_search_by has a problem that it usually calls one extra comparison.

I tried

• previous binary_search_by logic (=logic1),
• current binary_search_by logic (=logic2), and
• partition_point logic (=logic3).

In addition, I also tried to

• remove jump from partition_point (logic4).

I'm not sure succeeded to remove, or possibly already done from current code.

https://github.com/VillSnow/compare-binary-searches/blob/master/src/main.rs

You can find logic1, 3, 4 need 3 comparisons to find from 0..7, while logic2 needs 4 calls.
I think this causes significant cost more than optimization trick if users can pass their own predictions.

Here is a typical result of bench. Find 0 from 0..65536 and find 0 from 7 but inserted sleep(1ms) in comparison.
Logic2 is much slower than others in case of custom predication.

logic	[i32; 65536]	[Slow; 7]
logic1	30ns	5.4ms
logic2	9ns	7.2ms
logic3	10ns	5.6ms
logic4	10ns	5.6ms

[timvermeulen]

I found current binary_search_by has a problem that it usually calls one extra comparison.

I believe this is intended, it is not optimized for doing the minimum number of comparisons. Make sure to run the benchmarks in https://github.com/rust-lang/rust/blob/master/src/libcore/benches/slice.rs before drawing any conclusions.

And regardless of what the ideal implementation of binary_search_by looks like, partition_point should probably still be implemented in terms of it in the way I outlined above 🙂

[VillSnow]

@timvermeulen

I found current binary_search_by has a problem that it usually calls one extra comparison.

I believe this is intended, it is not optimized for doing the minimum number of comparisons. Make sure to run the benchmarks in https://github.com/rust-lang/rust/blob/master/src/libcore/benches/slice.rs before drawing any conclusions.

AFAIK, this bench is written when logic1 is replaced into logic2, not after logic3. The bench tries to find random element from usize slice, not user type which needs large cost to compare.
If it does not optimize for minimum number of comparisons, itself is a problem, I think.
If user need 1ns faster binary search, they can write by themselves or use 3rd party crate, as well as HashMap.

And regardless of what the ideal implementation of binary_search_by looks like, partition_point should probably still be implemented in terms of it in the way I outlined above 🙂

Is it means partition_point should call binary_search_by instead of binary_search_by calls partition_point?
I agree because binary_search_by has more information and the cost would be small.

[scottmcm]

I noticed in passing that this is using FnMut. That seems strange to me, since there's no guarantee which items will be looked at or in which order by this API, so actually mutating in the closure would seem an anti-pattern. Should it maybe use Fn instead? (People could always use interior mutability if they really really really want to update things in the closure, but this would discourage it.)

Though I guess sort_by takes FnMut...

[VillSnow]

@scottmcm memoization or exterior (web/DB) API access using mut handle?

[matklad]

@VillSnow this has been baking in the nightly for a while, I think this is ready for stabilization. Would like to send a stabilization PR?

[VillSnow]

If the team think all right, I'm glad.

I still concern about code duplication, and I'm watching this PR #74024.
However, how predicate is called is not documented, so even if the algorithm was changed, it never change the stable branch.

I have no objection to merge this.

[matklad]

If the team think all right, I'm glad.

Submitting a stabilization PR is a way to figure that out! I am not on the libs team, but this seems stabilization-worthy to me.

I wouldn't worry about impl details -- they can be adjusted after stabilization.