Repository navigation
Binary search performance regressed in 1.25 #53823
Description
The speedup obtained by the optimizations from #45333 which hit stable in 1.23 were mostly lost again from 1.25 onwards, because the compiler started emitting a branch instead of a cmov.
1.24
14 cmp qword ptr [rsi + 8*rax], rcx
15 cmova rax, r81.25
18 cmp qword ptr [rsi + 8*r9], rcx
19 ja .LBB0_7
20 mov r8, r9
21 .LBB0_7:From godbolt: https://godbolt.org/z/DUDl-T
Bench comparison with 1.23 nightly (2017-11-20, 9 days after PR merge)
name old_1.23 ns/iter new_1.23 ns/iter diff ns/iter diff % speedup
binary_search_l1 70 28 -42 -60.00% x 2.50
binary_search_l1_with_dups 46 28 -18 -39.13% x 1.64
binary_search_l2 94 42 -52 -55.32% x 2.24
binary_search_l2_with_dups 68 42 -26 -38.24% x 1.62
binary_search_l3 267 234 -33 -12.36% x 1.14
binary_search_l3_with_dups 198 236 38 19.19% x 0.84
and status quo with 1.30 nightly (2018-08-15)
name old_1.30 ns/iter new_1.30 ns/iter diff ns/iter diff % speedup
binary_search_l1 75 68 -7 -9.33% x 1.10
binary_search_l1_with_dups 46 61 15 32.61% x 0.75
binary_search_l2 99 89 -10 -10.10% x 1.11
binary_search_l2_with_dups 71 89 18 25.35% x 0.80
binary_search_l3 272 245 -27 -9.93% x 1.11
binary_search_l3_with_dups 212 256 44 20.75% x 0.83
Reacted by Tyler Neely, q2p, EFanZh, Markus Laire, Vihan, Bryan Hitchcock, Kornel, Elichai Turkel, Ragland Asir, Felipe S. S. Schneider and 4 more
Activity
Emerentius commentedon Aug 31, 2018
The likely culprit is the upgrade from LLVM 4 to 6. The upgrade was merged on the 10th of Feb. The binary search was fast on the 9th and slow on the 12th.
@estebank The optimization did hit stable (if only for 2 releases), so does it not need the
regression-from-stable-to-stablelabel?estebank commentedon Aug 31, 2018
@Emerentius what do you mean for only 2 releases? Isn't the slowdown present in stable through nightly? Reading the assembly from godbolt it seems to me like there have been some changes but the code causing the slowdown presented in this issue is still there. If that is the case, then it would need that label, but if it was fixed in current stable, then we can close the ticket, as I do not believe we cut point releases for previous stable releases.
Emerentius commentedon Aug 31, 2018
@estebank I mean it was fast in 1.23 stable and slow from 1.25 stable on, so fast for 2 stable releases, then regressed.
pnkfelix commentedon Nov 29, 2018
triage: P-medium, since I don't think investigating this takes priority over other things currently being juggled. but also self-assigning since I'm curious and I think I can do some bisection as a background task, assuming I can reproduce the perf regression locally.
pnkfelix commentedon Nov 29, 2018
discussed in T-compiler meeting. Re-prioritizing as P-high just for evaluating the scope of the regression (though some good work on that is already evident in this comment thread).
pnkfelix commentedon Dec 12, 2018
Not sure why I previously removed I-slow; I'm putting it back now.
pnkfelix commentedon Dec 12, 2018
Hey @Emerentius, what is the distinction you are making in the columns with the prefix "old_" and "new_" in the tables you present?
That is, I would have thought that "old_" somehow corresponds to the state prior to the changes from PR #45333 and "new_" corresponds to after PR #45333 landed; but you already established that PR #45333 landed in between the two versions that each have "old_" and "new_" labels applied to them.
So I don't understand what difference has been applied to either the code or the benchmark in between the two columns there. (Hypothesis: Is "old_" testing the binary search implementation prior to PR #45333, and "new_" testing the binary search implementation that was added by PR #45333 ?)
pnkfelix commentedon Dec 12, 2018
(In any case I definitely am able to reproduce a regression on my Linux desktop on benches/slice between nightly-2018-02-09 and 2018-02-12, as anticipated/noted by #53823 (comment) ; there's a fair amount of noise between runs when looking at binary_search_l3 in my own machine, but binary_search_l1 is much more consistent in illustrating a 2x regression for me.)
Emerentius commentedon Dec 12, 2018
@pnkfelix
That is exactly it
34 remaining items
yaahc commentedon Jul 22, 2021
What Josh said, I've gone ahead and removed the
T-libslabel, thanks for the confirmation @pnkfelix ^_^.vlovich commentedon Sep 1, 2023
Could something like https://docs.rs/cmov/latest/cmov/ be used in the interim to force the usage of cmov to recover the performance?
mohe2015 commentedon Sep 1, 2023
Is profile guided optimization able to do anything in this case maybe?
nikic commentedon Sep 14, 2023
The x86 backend should now respect
__builtin_unpredicatefor cmov conversion, so if we can expose that in rustc in some way, we can use that.the8472 commentedon Sep 14, 2023
There's a discussion what to do about
likely()/unlikely()on IRLO. Adding anunpredictable()was mentioned too.Rewrite binary search implementation
Amanieu commentedon Jul 26, 2024
See #128254 for a potential fix.
Rewrite binary search implementation
Rewrite binary search implementation
Rewrite binary search implementation
Rewrite binary search implementation
Rewrite binary search implementation
Auto merge of rust-lang#128254 - Amanieu:orig-binary-search, r=<try>
Auto merge of rust-lang#128254 - Amanieu:orig-binary-search, r=tgross35