Re: [boost] non-branching min()

Subject: Re: [boost] non-branching min()
From: Giovanni Piero Deretta (gpderetta_at_[hidden])
Date: 2009-09-11 13:21:32

On 9/11/09, Bo Persson <bop_at_[hidden]> wrote:
> DE wrote:
>> on 11.09.2009 at 3:19
>> Cory Nelson wrote :
>>> I'm curious, have you actually tried to look at the generated
>>> instructions?
>> of course
>>
>>> Because on a 686+ this should compile this into two
>>> non-branching instructions for min():
>>> cmp a, b
>>> cmova a, b
>>> And the same thing but with cmovb for max().
>> neither icc11 nor msvc80 generate such instructions
>> msvc generates a conditional jump and icc generates code "without
>> branches but with the sbb asm instruction" (c) Joel Falcou
>>
>
> I believe the conditional move introduces a dependency that is about
> as bad as a conditional jump.

Conditional jumps actually break dependencies, as the processor can
speculate beyond them and execute code at the jump target even before
computing the condition.

Conditional moves do introduce dependencies as any other
if-conversions, including an indexed load, thus an if-conversion
should only be used if the CPU has no chance to predict the jump as it
otherwise limit any out-of-order capabilities of the CPU.

Cmov and other predicated instructions should be as fast or faster
than if-conversions done with bitwise instructions or other
instruction combinations.

> It also limits the code to the latest
> processor models.
>
> The compilers generally try to avoid this situation.  :-)
>

cmov on x86 has been available since the first pentium pro, which has
been launched almost 15 years ago. It is guaranteed to exist on
x86_64. By default, some compiles still produce code compatible with
the original 386, so you might need to use appropriate compiler flags.

HTH,

-- 
gpd