std::slice::partition_point performance regression when using rustc 1.82+

[marvin-j97]

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:

[moxian]

Could you try bisecting the regression with cargo-bisect-rustc to better understand what exactly led to this slowdown? (As a guess, it's probably llvm bump 18.1.7->19.1.1, but it would be useful to confirm)
@rustbot label: +E-needs-bisection +I-slow

[marvin-j97]

Using

cargo bisect-rustc --start 2024-08-01 --end 2024-08-30 --prompt -- bench --bench tli

********************************************************************************
Regression in nightly-2024-08-03
********************************************************************************

get_commits_between returning commits, len: 8
commit[0] 2024-08-01: Auto merge of #127276 - aDotInTheVoid:no-opaque, r=camelid
commit[1] 2024-08-02: Auto merge of #127624 - Oneirical:a-test-of-lime, r=jieyouxu
commit[2] 2024-08-02: Auto merge of #128147 - lolbinarycat:fmt-write-bloat-rmake, r=jieyouxu
commit[3] 2024-08-02: Auto merge of #128529 - matthiaskrgr:rollup-gzq2slo, r=matthiaskrgr
commit[4] 2024-08-02: Auto merge of #128254 - Amanieu:orig-binary-search, r=tgross35
commit[5] 2024-08-02: Auto merge of #128352 - Oneirical:daLTOnist-vision, r=jieyouxu
commit[6] 2024-08-02: Auto merge of #127926 - Oneirical:classical-orctestra, r=jieyouxu
commit[7] 2024-08-02: Auto merge of #128361 - Oneirical:testle-deforestation, r=jieyouxu

[moxian]

that would be

• Rewrite binary search implementation #128254

@rustbot labels: +S-has-bisection -E-needs-bisection +T-libs -needs-triage -regression-untriaged +regression-from-stable-to-stable