In https://github.com/fjall-rs/lsm-tree I am heavily using partition_point for various binary searches.
I found the std implementation to be somewhat slow.
As you can see below, the performance regression happens between rustc 1.81 and 1.82.
Comparing std between rustc versions:
git clone https://github.com/fjall-rs/lsm-tree && cd lsm-tree
cargo +1.81 bench --bench tli
cargo +1.82 bench --bench tli
The std implementation performs much worse in rustc 1.82 compared to 1.81.
As a sanity check, I wrote a simple alternative and found it performed much better (comparable to how partition_point used to be):
https://github.com/fjall-rs/lsm-tree/blob/0dca39eb54690beee2481cc3e31c9fc78d9e3fca/src/binary_search.rs#L9-L35
Reproduce (using monkey patch):
git clone https://github.com/fjall-rs/lsm-tree && cd lsm-tree
cargo +1.85 bench --bench tli
git checkout perf/replace-partition-point
cargo +1.85 bench --bench tli
The hand-written binary search performs much better in 1.82+.
Looking at flame graphs, you can see a whole chunk of PartialOrd that only occurs when using the std implementation in 1.85:
In https://github.com/fjall-rs/lsm-tree I am heavily using
partition_pointfor various binary searches.I found the std implementation to be somewhat slow.
As you can see below, the performance regression happens between rustc 1.81 and 1.82.
Comparing std between rustc versions:
The std implementation performs much worse in rustc 1.82 compared to 1.81.
As a sanity check, I wrote a simple alternative and found it performed much better (comparable to how
partition_pointused to be):https://github.com/fjall-rs/lsm-tree/blob/0dca39eb54690beee2481cc3e31c9fc78d9e3fca/src/binary_search.rs#L9-L35
Reproduce (using monkey patch):
The hand-written binary search performs much better in 1.82+.
Looking at flame graphs, you can see a whole chunk of
PartialOrdthat only occurs when using the std implementation in 1.85: