branchless binary search is not branchless since rust 1.25

[fulmicoton]

The std binary search implementation is supposed to rely on a branchless implementation.
The implementation rely on the idea that the idiom

   let base = if cond { base } else { something_else }; 

compiles as a conditional move.

Until rust < 1.25, rustc was very aggressively relying on conditional moves to avoid branches.
With rust >= 1..25, rustc seem to consistently compile the expression above with conditional jump.

I haven't benchmarked it, but this should have resulted in a performance regression.

Example code

pub fn binary_search(arr: &[u32], mut base: usize, mut len: usize, target: u32) -> usize {
    while len > 1 {
        let half = len / 2;
        let mid = base + half;
        let pivot = *unsafe { arr.get_unchecked(mid) };
        let cmp = pivot>target;
        base = if cmp { base } else { mid };
        len -= half;
    }
    base + ((*unsafe { arr.get_unchecked(base) } < target) as usize)
}

Assembly on 1.24

Godbolt

example::binary_search:
        push    rbp
        mov     rbp, rsp
        cmp     rcx, 2
        jb      .LBB0_1
.LBB0_3:
        mov     rsi, rcx
        shr     rsi
        lea     rax, [rdx + rsi]
        cmp     dword ptr [rdi + 4*rax], r8d
        cmova   rax, rdx
        sub     rcx, rsi
        cmp     rcx, 1
        mov     rdx, rax
        ja      .LBB0_3
        jmp     .LBB0_2
.LBB0_1:
        mov     rax, rdx
.LBB0_2:
        cmp     dword ptr [rdi + 4*rax], r8d
        adc     rax, 0
        pop     rbp
        ret

Assembly on 1.25

Godbolt

example::binary_search:
        push    rbp
        mov     rbp, rsp
        cmp     rcx, 2
        jb      .LBB0_4
.LBB0_1:
        mov     rax, rcx
        shr     rax
        lea     rsi, [rdx + rax]
        cmp     dword ptr [rdi + 4*rsi], r8d
        ja      .LBB0_3
        mov     rdx, rsi
.LBB0_3:
        sub     rcx, rax
        cmp     rcx, 1
        ja      .LBB0_1
.LBB0_4:
        cmp     dword ptr [rdi + 4*rdx], r8d
        adc     rdx, 0
        mov     rax, rdx
        pop     rbp
        ret

[jonas-schievink]

There's no guarantee that binary_search is actually branchless, and branches aren't necessarily slow since modern CPUs are very good at predicting them, so a benchmark demonstrating that it's actually slower would be appreciated.

[nikic]

Duplicate of #53823. TL;DR is that this is caused by x86 cmov conversion and there is no way to (selectively) disable it yet.