Binary search performance regressed in 1.25

[Emerentius]

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, r8

1.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 

[Emerentius]

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-stable label?

[estebank]

@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]

@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]

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]

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]

Not sure why I previously removed I-slow; I'm putting it back now.

[pnkfelix]

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]

(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]

@pnkfelix

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 ?

That is exactly it