Skip to content

[X86] cmov conversion hurts binary search performance #39374

Open
@nikic

Description

@nikic
Bugzilla Link 40027
Version trunk
OS All
CC @adibiagio,@chandlerc,@topperc,@Dushistov,@ot,@jdm,@LebedevRI,@RKSimon,@rnk,@rotateright

Extended Description

Originally reported at: rust-lang/rust#53823

The cmov conversion pass converts a cmov in Rust's binary search implementation into a branch. As binary search branches are badly predicted, this significantly hurts performance. For small data sets, which are not dominated by cache performance, the slowdown is around 2-3x.

https://gist.github.com/nikic/13e907d7097f74a92d082fcc61bc212c has the LLVM IR for the function, as well as generated assembly with cmov conversion enabled (default) and disabled (-x86-cmov-converter=false).

It would be great if the cmov conversion heuristics could be adjusted in some way to avoid converting this case.

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions