introduce cmovcc instruction to speed up certain simple "if" blocks #6224
Description
Original bug ID: 6224
Reporter: vbrankov
Status: acknowledged (set by @damiendoligez on 2014-07-16T11:55:31Z)
Resolution: open
Priority: normal
Severity: feature
Version: 4.01.0
Target version: undecided
Category: back end (clambda to assembly)
Tags: patch
Monitored by: @gasche meurer @diml @chambart @hcarty @yakobowski
Bug description
(on behalf of pdenys who worked on this)
Using cmovcc instruction is a way to avoid branch mispredictions. This change translates "if" statements of the form [if cond then var1 else var2] and similar to use "cmovcc".
Steps to reproduce
Do [if cond then var1 else var2] with [cond] hard to predict. The penalty of misprediction is about 24 cycles. On the other hand [cmovcc] takes just 2 cycles. In the case of 50% mispredictions, the speedup should be 6 times.
Additional information
The effect is visible in [Map]. For instance [Map.find] has [if cond then l else r] to select left and right subtree. The benchmark shows that [Map.find] got 1.6 times faster.
The data structures where this should be noticeable are [Map], [Set], various implementations of heap and others which use ordered types.