Xbox One Family CPU: Branch Prediction

Xbox Advanced Technology Group

Updated May 15th 2017

In this topic

Introduction

Branch predictor units

Test: Branch pattern learning speed

Test: Performance of sparse vs. dense predictors

Test: Function pointers and virtual functions

Test: Branch vs. ?: operator and isel

Test: If test replacement by integer mask

Using SSE to remove branches

Test: Loop unrolling

CPU hardware performance counters

Xbox One X

Recommendations

References

Introduction

The Xbox One CPU features speculative out-of-order execution, which means that each core can speculatively execute instructions before the address of a jump target has been resolved. The branch predictor is responsible for supplying the address at which to start speculative execution. Without speculative execution, the CPU would have to stall, waiting for the resolution of the address at which to continue execution. The branch predictor is responsible for predicting all jumps, not just branches, and this includes function pointers and virtual function calls.

If the branch predictor mispredicts the address, all speculative instructions are discarded and never retired. A branch misprediction on an Xbox One core costs a minimum of 14 cycles for an unconditional jump or 20 cycles for an indirect jump (such as a virtual function). Because the cores may retire 2 micro-operations per cycle, even the minimum cost represents a heavy penalty.

Optimizing your code for the branch predictor is a key optimization strategy for the Xbox One platform.

Branch predictor units

The branch predictor consists of multiple units with differing performance characteristics.

The fastest unit is the sparse predictor. For each 64-byte L1 instruction cache line there is a corresponding array of marker data for the sparse predictor. The sparse predictor and associated marker data can only handle the first two branches in each L1 cache line. Any additional branches in a cache line are handled by the dense predictor. For flexibility, the dense predictor employs a 4K set-associative cache of prediction information.

For indirect branches (function pointers and virtual functions), an indirect branch target predictor is used. The indirect branch target predictor maintains 512 addresses with a history for each entry. (Unlike conditional statements, there can be more than two outcomes) The type of branch, direct or indirect, is recorded in the branch prediction marker data.

  1. Simple instructions produced by the compiler usually equate to a single micro operation, and instructions that are more complex are broken down by the CPU into multiple micro instructions. This breaking down can help reduce CPU complexity and increase parallelism at the instruction level, which is especially good for out-of-order execution.

The sparse and dense predictors behave differently if the address of the branch target is outside of the 4K memory page that contains the branch. In such a case, the sparse predictor falls back to the out-of-page target array. This array is 32 elements large, each containing 16 bits, this extends the address range from 11 bits to 27 bits. If the address offset is 28 bits or larger, the sparse predictor falls back to the indirect branch target predictor. In this instance, the indirect branch target predictor is only being used for a full width address, not for its history of indirect branches.

The dense predictor does not use the out-of-page target array and always falls back to the branch target address calculator.

The branch target address calculator obtains the full 64-bit address; this requires that all operands are fetched and decoded. For direct jumps, the address is fetched from the executable.

There is extra hardware that maintains a 16-entry call/return stack; this means that return calls do not need prediction.

Branch prediction process

A branch not yet encountered is predicted to be not taken. No branch prediction entry is created until a branch instruction is retired as taken, and a branch that is never taken will never generate any entries in either sparse or dense predictors.

A branch that is taken is added to the branch predictor and flagged as always taken. It is not until a branch flagged as always taken is not taken that it is promoted to dynamic. Dynamic branch prediction relies on a system of self-modifying weights to learn patterns—the precise scheme implemented is not discussed in this paper.

There is an important point here: You may need to check the disassembly code to see what path taken and not taken correspond to. For example:

if(condition)
// true block
else
// false block

The compiler is likely to produce a comparison with zero and a conditional jump that, when taken, sends the program counter to the false block. Otherwise, the program counter falls through to the true block; following execution of the true block, the false block will be skipped by an unconditional jump.

Executing the true block requires that the CPU process an additional jump instruction to skip the false block. The relative address for the jump is fixed when the program is linked. The branch predictor will still be invoked, but because the address never changes, the branch predictor will always successfully predict the jump address. Executing the extra jump instruction may be effectively free if the CPU is waiting on memory to load or for the results of other calculations; however, this additional invisible jump instruction should be accounted for when deciding whether code is likely to invoke the dense predictor. If the number of instructions in the true block is small and both the conditional and invisible jump are contained on the same cache line, these can consume both entries in the sparse predictor. You may wish to avoid invoking the dense predictor by rearranging code so as not to immediately follow the true block with another conditional or an indirect function call.

Branches are ordered by address. The first two branches in a cache line that are retired as taken are assigned entries in the sparse predictor. If a third branch is retired as taken, then either it follows the first two—in which case it is assigned directly to the dense predictor—or a shuffle must take place with the earlier entries in the sparse predictor. When a shuffle takes place, the second of the earlier targets in the sparse predictor is moved to the dense predictor.

When the branch target address calculator resolves the correct address, it is checked to see if it matched the predicted address. If it does not match, the CPU rolls back all speculatively executed instructions. A branch that was speculatively executed but rewound will not be retired, and the branch predictor will not update its entries for this branch (or create a new one).

The L2 silo

When an instruction cache line is retired from the L1 cache, the significant part of the sparse predictor data is saved to the L2 silo. If the cache line is reloaded to the L1 cache, this data is restored. The L2 silo allows branch weights that are learnt on one core to be reloaded to a different core. When a cache line of code is retired from the L2 cache, the corresponding L2 silo data is wiped; if the cache line is reloaded, the sparse predicted branches are re-learnt from scratch.

The dense predictor does not use the L2 silo. The retention of data in its set-associative cache is dependent the number of dense branches that intervening code retired, and which cache lines these mapped.

Performance

The sparse predictor can predict two branches per cycle only if the two branches are in the same high or low 32 bytes of the 64-byte cache line; otherwise, the maximum rate of prediction is one branch per cycle.

The dense predictor cannot be invoked on the same cycle as the sparse predictor. The first invocation of the dense predictor takes two cycles, each subsequent invocation consumes an additional cycle. Invoking the dense predictor stalls instruction fetch, instead of fetching instructions the core is fetching dense predictor data. As described, jump target addresses handled by the sparse predictor that have large offsets require invoking additional hardware units to extend the address; these invocations add additional latency in obtaining the address.

A branch misprediction on an Xbox One core costs a minimum of 14 cycles for an unconditional jump or 20 cycles for an indirect branch (such as a function pointer).

Test: Branch pattern learning speed

We packed the L1 instruction cache (32K) with a loop containing 1024 unique branch instructions, and then timed the execution of short branching patterns over increasing iteration counts.

We timed all patterns that were 8 branches long, but removed those patterns that were rotations of others. We also timed execution of always taken and never taken branches, but primed them with the opposite condition. Our objective was to see how fast these timings converged with always taken and never taken.

Because the times involved are very small, for short iteration counts the timer produces lumpy results—that is, roughly +/- 1 μs. Over very long iteration counts; this fluctuation diminishes as expected.

To remove the L1 fetch of the code from the time taken, we made a single extra iteration in which the first taken/not taken condition was repeated but not timed.

Observations

We timed longer patterns by expanding the pattern sequence; for example, “011” expanded to “00001111111111”. This produced exactly the same pattern of results.

We timed increasingly large iteration counts on a logarithmic scale. A small selection of those studied are graphed in the following figure.

Observations

Conclusions

The best performance, by far, comes from not taken or always taken branches. Only for very low iteration counts should engineers be concerned that some patterns might be better than others. If possible, it is better to order data so that all not taken items are processed first, followed by all taken. Avoid alternating taken and not taken, which is the worst pattern.

Test: Performance of sparse vs. dense predictors

We constructed two pieces of code to test the relative performance of the sparse and dense predictors.

To test the dense predictor, we crammed a large number of conditional jumps into a single cache line. This was followed by enough non-branching arithmetic to fill a second cache line.

To test the sparse predictor performance, we rearranged the test code for the dense predictor, spreading the conditional jumps over the two cache lines instead of packing them all into one.

The dense predictor code had the following form:

if(condition) 
       // true block
else
       // false block
// do work

Where the true block and false block contained more packed conditions.

For the sparse predictor, we broke up the logic like this:

if(condition) 
       	// true block

// do the first half of work
if(!condition) 
// false block
// do the second half of work

The code targeting the sparse predictor was 2% larger than the code targeting the dense predictor. We unrolled each code block to consume nearly the entire 32K of the L1 instruction cache.

The code for the sparse predictor, despite being larger, produced a speed increase of around 6% when presented with a random branching pattern. At best, we saw a performance increase of 17% for good branching patterns. Experiences will vary, the alignment of code over cache line boundaries may shift due to unrelated changes elsewhere in your executable.

Conclusion

Reducing the number of conditional jumps in a given cache line, particularly when the number can be reduced to as low as 2, should always produce a healthy performance improvement.

Test: Function pointers and virtual functions

Like branches, function pointers invoke the branch predictor to enable speculative execution of a target function. For this test, we created a large array of function pointers, each pointed to one of four trivial functions. Each function featured in the array an equal number of times. We timed execution of the array ordered by function pointer, and randomly ordered. The sorted array executed 226% faster.

As with functions pointers, we created an array of 4 different derived classes, each with a different virtual function. The virtual functions executed the same four trivial math operations we used with the function pointer test. We timed execution of the array both with ordered objects and with a randomized order. The sorted array executed 188% faster.

As expected, function pointers performed slightly faster overall due to not having the indirection of a vtable lookup.

Test: Branch vs. ?: operator and isel

Unlike the Xbox 360 CPU, based on the PowerPC architecture, the Xbox One’s x64-based CPU cores have no _fsel intrinsic. _fsel was implemented as:

(a >= 0.0f) ? x : y;

It is possible to implement an integer selection without branches. The key feature is how arithmetic right shift of signed integers extends the most significant bit; that is:

char(0x7f) >> 7 == 0x0
char(0x80) >> 7 == 0xff

A negative number can, therefore, easily be manipulated to produce a mask of all bits set, whereas a zero or a positive number will have no bits set.

// if c >= 0, return x, else y
template <class UT>
__forceinline int isel(int c, UT x, UT y)
{
    UT mask = (UT)(c >> ((sizeof(int) * 8) - 1));  
    
    return x + ((y - x) & mask);
}

We timed if-then-else branches versus the following:

The results, shown in the following figure, represent good branching behavior and random branching behavior for both tests.

We can see that isel performed better in all cases: 220% faster than a branch misprediction and 120% faster than a correct branch prediction. We can also see that the compiler produced the same code for if-then-else as it did for the ternary operation with a floating-point comparison.

However, take care with optimized code built with Visual Studio 2015 or Visual Studio 2017. Their optimizer is very aggressive in using the conditional move operation with integer operations. In these cases, performance will be the same as using isel. The generated code is also branchless.

The situation changes when we add math operations that are dependent on the outcome of the selection. The following figure shows the results of inserting integer-only math after the isel operation and floating-point-only math after the floating-point branch.

With dependent math operations, isel is 150% faster than a branch misprediction and 110% slower than a branch hit. However, as with the previous test, do investigate the generated code. When the optimizer can use the conditional move instruction, the performance between the **isel and branching code is identical.

Conclusions

Using an isel operation can be an attractive technique for optimization. isel scores very well when the branch predictor mispredicts. When the branch predictor performance is near perfect, and the integer pipeline is heavily saturated, isel is only slightly slower. Unless the branch condition is always taken or never taken, isel could be a useful method of optimization. However, be sure to investigate the code generated by the optimizer; it could be using the conditional move operation, which means it is also branchless and you won’t see any performance gain from switching to isel.

Test: If test replacement by integer mask

On Xbox One, the result of an integer or floating-point comparison is either 0 or 1, which means that this result cannot be directly used with isel. There is an integer selection technique* that can convert any non-zero integer to all bits set, which can then be used as a mask to select between two integer results; in our testing, this code was faster than a branch misprediction but fractionally slower than a branch hit.

* This technique is described in Using masks to accelerate integer performance, a blog post by Mike Acton, Engine Director at Insomniac Games.

We created a new routine with fewer instructions but one that is less general. One shift operation is all that is needed to shift the least significant bit to the most significant bit, changing the result from a positive number to a negative—and this can then be used with isel. This code works only if the least significant bit is set, it does not handle the general case of any bit that is set producing a non-zero mask.

// if c & 1, return x, else y
template <class UT>
__forceinline UT IntegerSelect(int c, UT x, UT y)
{
    assert((c & 1) || !(c));

    int msb = c << ((sizeof(int) * 8) - 1);

    return isel<UT>(msb, y, x);
}

This can be used by any conditional operation, like the following example:

// equivalent to: result = (fValue > 0.5f) ? 0xc : 0x3;
unsigned int result = IntegerSelect<unsigned int>(fValue > 0.5f, 0xc, 0x3);

We timed real branches with both random branching behavior and highly predictable branching behavior against our integer mask technique.

Using an integer mask can produce a significant speed increase when the branch predictor is presented with random inputs. When the branch predictor faces highly predictable conditions, a branch is the same speed for floating-point conditions but still slower for integer conditions.

It is interesting to note that ideal branching behavior on a floating-point condition was faster than branching on an integer condition. For both loops, the compiler generated exactly 8 instructions; however, the floating-point version could co-issue instructions.

For our next test, we timed the same conditional operation but preceded the branch instruction with several non-dependent math operations of opposite type to the branch condition (that is, for an integer branch, non-dependent floating-point work) to saturate the opposite pipeline. The results, shown in the following graph, are perhaps more as you might expect with floating-point branches being consistently more expensive than integer branches.

We then changed from non-dependent work of a different type to non-dependent work of the same type, heavily saturating either the floating-point or integer pipelines with the same data type that we were branching on.

This showed that when pipelines are heavily saturated, a floating-point comparison is faster than an integer comparison. In all these tests, with the CPU performing other non-dependent work, an integer mask is as effective as ideal branching behavior and much better than random.

We also timed the case where there are many math operations dependent on the branch result.

Here, the integer pipeline was over saturated already, and adding dependent integer instructions meant that integer comparison became slower than both a perfectly predicted branch and the random branching pattern. For floating point branches, integer comparison continues to perform as well as a predictable branching pattern and much better than random branching.

Conclusions

While your experience will vary, in general, out-of-order execution on the Xbox One CPU cores means that the performance of any specific branch is affected by what other work the CPU core can find to do and how heavily saturated the integer or floating-point pipelines are.

The Visual Studio 2015 and Visual Studio 2017 compilers are aggressive in their use of the conditional move operation. Whenever they are able to use this optimization technique, the performance of the code will be the same as the previous branchless techniques. In this case, the generated code is also branchless.

Using SSE to remove branches

Very much the same as the integer mask method, streaming SIMD extensions (SSE) comparison instructions return a mask value with either all bits or no bit set. An extremely useful instruction after a mask value is generated is _mm_and_ps, which performs a bitwise AND on floating-point registers. It is therefore trivial to select between the existing value and zero as the result of a comparison without using a branch, as shown in the following example:

static const __m128 g_one = {1.0f, 1.0f, 1.0f, 1.0f};

// maskResult = (a != b) ? 0xffffffff : 0;
__m128 maskResult = _mm_cmpneq_ps(a, b);	
	
// zeroOrOne = (a != b) ? 1.0f : 0.0f;
__m128 zeroOrOne = _mm_and_ps(g_one, maskResult);

You can use SSE instructions to remove branches that only affect SSE registers; however, if the branch also affects an integer register, it may often be faster to allow branching to occur rather than transferring the value from the SIMD register to an integer register.

Test: Loop unrolling

Unrolling a loop can be worthwhile, but performance does not increase linearly with the number of iterations unrolled. Better performance gains are had from unrolling loops with fewer instructions, the reason being that a loop’s branch instruction represents proportionally more of the instruction count. As the looped instruction count increases, so the speed increase due to unrolling that loop approaches zero. Even worse, if the number of iterations is small, the time required to fetch instructions from memory can dominate timings.

We unrolled, by a factor of eight, a simple loop that contained only a load and two add instructions. This produced a speed increase of 197%. Simply inserting another add instruction per iteration reduced the performance increase to by 143%.

Duff’s device allows you to unroll an arbitrary number of iterations. The alternative is two loops, one to handle large multiples and one to catch the remainder. In our testing, Duff’s device improved execution time by as much as 107% for very short iterations only. For larger iterations, performance approaches—but is not appreciably worse than—the two-loop alternative.

There is a potentially huge advantage to loop unrolling. The worst branching pattern measured is alternating taken and not taken. If this pattern is encountered by a conditional statement inside a loop, then unrolling the loop by a factor of two will result in branches that instead exhibit the best-case behavior, always taken and never taken.

CPU hardware performance counters

The Xbox One CPU exposes hardware performance counters that measure the number of branches:

The Xbox One console can be configured to capture simultaneously four hardware counters at once. For more information about capturing these counters, see ConfigurePMCs and GetPMCValue in the PIX API reference in the Xbox One XDK documentation. For an overview of using the performance monitoring counters, see “Performance Monitoring” in “Processor Core Allocation and Performance Monitoring” in the XDK documentation.

Xbox One X

Xbox One X includes a faster processor than Xbox One; its speed has been increased to 2.3 GHz. All tests described in this paper were also run on a Xbox One X dev kit. However, the branch predictor works entirely within the processor and benefits directly from the increased clock speed. In all cases the code will execute approximately 30% faster. Because of this, for the sake of brevity, we’ve left the numbers out of this part of the paper. The relative differences between patterns will be the same on Xbox One X as they are on Xbox One.

Recommendations

Optimizing for the branch predictor is important to keep cores fully utilized. Implementing some or all of the following recommendations will help to improve the performance of your code.

Order by target address

For function pointers and virtual functions, ordering by target address significantly improves performance.

Order data

Branches that are always taken or never taken are, by far, the fastest patterns. The worst branching pattern is alternating taken and not taken. Other branching patterns are usually better than random, but there are no other obviously good patterns. It is better to order the data so that all not taken items are processed first, followed by all taken.

Order nested branches

If possible, arrange nested branches so that branches with more predictable branching behavior are the outer branches. If an outer branch is mispredicts, it will rewind the speculatively executed inner branch.

Keep jumps within the same page

Jumps to branch targets that are in the same 4K memory page as the jump instruction are faster than jumps to targets that are further away.

Spread out branches to avoid invoking the dense predictor

The sparse predictor is faster than the dense predictor. By spreading out branches, you can reduce the chance of invoking the dense predictor. Consider also virtual function or function pointer calls and invisible jumps used to skip false blocks.

Aim for two branches per cache line, both in the same high or low 32 byes

The sparse predictor can predict two branches per cycle only if both branches are in the same high or low 32 bytes of the cache line.

Consider alternatives to branching

Consider alternatives to branching, particularly when branching behavior is poor or to avoid invoking the dense predictor. The integer-based techniques presented in this paper work especially well when the integer pipeline isn’t saturated. Also for SSE, a comparison followed by _mm_and_ps is a cheap alternative to branching.

Consider unrolling loops

Loop conditions are probably of least concern when looking for a place to optimize your code. However, consider unrolling loops with very small numbers of instructions per iteration. Consider using Duff’s device only for small numbers of instructions and for small, but variable, iteration counts. Also, consider what loop unrolling will do to the branching pattern of conditional statements.

References

Software Optimization Guide for AMD Family 16h Processors on AMD Developer Central

CellPerformance, a blog by Mike Acton, Engine Director at Insomniac Games

Posts about intrinsics on Some Assembly Required, a blog by Elan Ruskin, a developer at Valve

Duff’s device described on Wikipedia. Also, Re: Explanation, please!, a posting on Usenet in which Tom Duff explains Duff’s device.