Closed
Description
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):
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:
