AMD 250 manual Branches That Depend on Random Data, Signed Integer ABS Function x = labsx, 130

Software Optimization Guide for AMD64 Processors 25112 Rev. 3.06 September 2005

6.3Branches That Depend on Random Data

Optimization

Avoid conditional branches that depend on random data, as these branches are difficult to predict.

Application

This optimization applies to:

•32-bit software

•64-bit software

Rationale

Suppose a piece of code receives a random stream of characters “A” through “Z” and branches if the character is before “M” in the collating sequence. Data-dependent branches acting upon basically random data cause the branch-prediction logic to mispredict the branch about 50% of the time.

If possible, design branch-free alternative code sequences that result in shorter average execution time. This technique is especially important if the branch body is small.

Examples

The following examples illustrate this concept using the CMOVxx instruction.

Signed Integer ABS Function (x = labs(x))

mov	ecx, [x]	; Load value.
mov	ebx, ecx	; Save		value.
neg	ecx	; Negate value.
cmovs	ecx, ebx	;	If negated value is negative, select value.
mov	[x], ecx	;	Save	labs result.

Unsigned Integer min Function (z = x < y ? x : y)

mov	eax, [x]		; Load x			value.
mov	ebx, [y]		; Load y			value.
cmp	eax, ebx		; EBX		<=	EAX	? CF = 0 : CF	= 1
cmovnc eax,		ebx	;	EAX	= (EBX		<= EAX) ? EBX	: EAX
mov	[z],	eax	;	Save min(X,Y).

130 Branch Optimizations Chapter 6