33

Once pipelined CPUs became common, a common issue arrived as a result of taking the wrong branch of a conditional jump, and thus needing to flush the pipeline. As a result branch prediction mechanisms were introduced to help mitigate the issue.

Older processors also allowed you to hint the direction of the branch via prefix (documented here), allowing the branch predictor to learn faster, but this technology was later scrapped, and I can't find out why (or even when) but I know modern processors are not affected by the hint prefixes.

11
  • 1
    Modern branch prediction seems to do even better than hints in the code, b/c it can predict the next-pc earlier in the pipeline, based on current-pc, so without even seeing and decoding the instruction at current-pc, which has the hint.
    – Erik Eidt
    Oct 25 at 15:06
  • 2
    @ErikEidt Do you have official sources for this?
    – Badasahog
    Oct 25 at 15:17
  • 3
    @tofro works fine in C (e.g. gcc __builtin_expect), other languages could do similar if they were interested. x86 gcc uses those hints to emit code that the static branch predictor will do the right thing with (e.g. putting the body of an "unlikely" if behind a forward branch that will be predicted not-taken).
    – hobbs
    Oct 25 at 21:14
  • 8
    Itanium had an interesting variant on this -- you'd evaluate the condition and store the result into a (boolean) predicate register, then a later branch instruction would use the value of the predicate register to determine which branch to follow. Zero mispredictions, but the cost is that you need a minimum distance between condition and branch that is difficult to fill with useful instructions in real-world applications, so compilers would often generate a lot of NOPs and unroll loops to generate efficient code. Oct 26 at 4:47
  • 1
    C++20 introduced the likely & unlikely attributes: en.cppreference.com/w/cpp/language/attributes/likely. So some form of hinting seems to still be working...
    – thkala
    Oct 26 at 15:20
22

Implicit forward-not-taken, backward-taken hinting is almost as effective as an explicit indicator. (A backward branch that is usually not taken — single pass loop — could not be encoded and a simple if conditional that is false often enough to prefer forward taken but not false often enough justify extraction, which would typically require an additional jump back, could not be optimized.)

Detecting the hint requires some degree of decoding, delaying the availability of the information. This reduces the benefit. While direction hint determination would be faster than target address calculation for relative branches, a taken branch still needs a target.

For microarchitectures with a branch target buffer (BTB), a BTB miss would typically be assumed to indicate a never-taken branch, in that case a not-taken hint would be useless.

The fraction of cases when an explicit static prediction will be provided and be more accurate than a dynamic prediction is likely to be small. Much software will not include the hints (profile-guided optimization is still not common and has issues with non-representative samples and standard languages often lack the means to indicate such hints [and assembly coding declined in popularity]). Programmers can also make mistakes either misunderstanding the semantics or mispredicting the common case (or having the common case differ for some uses or new versions of a program).

If most branches need to be predicted dynamically anyway, the benefit of providing a hint is reduced but the cost of managing the hint remains. The hardware will also have to decide whether to override a dynamic prediction with the hint; with a partially tagged BTB entry this could be driven by whether the target address matches the later calculated target address, but accurate branch direction predictions can easily exist for branches where the BTB entry was evicted and a BTB alias exists that is recognizable by target mismatch.

High transition rate branches (flipping directions frequently) are one cause of high per-address dynamic branch misprediction that would not be helped much if at all with a taken/not-taken static hint.

While persistently caching branch (and other) metadata — which is ideally what branch direction hints would do — has some attraction, one must also, as with any kind of memoization/caching, consider the communication and storage overhead relative to recomputation cost. (Of course, caching a global per-address branch history could also introduce a side channel. Fixed hints avoid this at the cost of not changing when behavior changes.)


A static prediction directive might be useful for avoiding timing variability (to facilitate deadline guarantees — mispredicting the more common case might result in a tighter worst-case execution time), but branch direction annotations are typically (always?) architected as hints.

Inclusion of other branch metadata has been proposed (e.g., "Static Methods in Hybrid Branch Prediction", Dirk Grunwald et al., 1998 {PDF}, which proposed a hint to select the table/predictor type, "Boolean Formula-based Branch Prediction for Future Technologies", Daniel Jiménez et al., 2001 {PDF}, which proposed providing a formula to derive a prediction from a global history string, and "Wish Branches: Combining Conditional Branching and Predication for Adaptive Predicated Execution", Hyesoon Kim et al., 2005 {PDF}, where special hammock branches are proposed to facilitate dynamic predication) and the HP PA-RISC 8500 used an agree mechanism (mentioned in "The Hewlett Packard PA-RISC 8500 Processor", Catherine Freeburn, 1998 {PDF}, where the dynamic predictor tracked whether the past behavior agreed with the hint.

1
  • 3
    In most cases, "forward-not-taken" misses can be avoided by the compiler by rearranging blocks so that the more likely path directly follows the conditional branch. Oct 26 at 4:36
27

I can speak from experience of having tried using the manual hinting. I work on a large mathematical modeller and when the Intel IA-32 hinting system described in the reference appeared, my management was keen to try it.

The codebase is far too large for manual hinting of every if/then/else to be practical, and there is no single "core algorithm" to hand-optimise. So I applied the hinting system to the model traverse operators in the domain-specific language used to write the modeller.

The results were very disappointing. The most obvious effect was an increase in code size; some operation speeded up by small amounts, and others got slower. There was no overall gain in performance. My best hypothesis is that the increased code size reduced the gains from the instruction cache sufficiently to cancel out the gains in data cache misses. Simpler code ran just as fast, so adding complexity seemed pointless, given that the bottleneck in programming is normally human comprehension of code.

14
  • 1
    I've used one processor with branch delay slots, and they seemed like a good approach. The TI compiler I had seemed to manage to fill delay slots most of the time, and since the CPU had both delayed and undelayed branches in the architecture that seemed like a win. The TI C2xx dropped the delayed branch instructions, so later versions of our product couldn't exploit them, but they seemed a good concept.
    – supercat
    Oct 25 at 14:49
  • 5
    I recall reading, in the rationale for why DEC Alpha did not have delay slots, that fixing the slot size now (say at 1 instruction deep) constrained future implementations with respect to how the pipeline could operate. Oct 25 at 19:09
  • 3
    @supercat: Branch delay slots do constrain am implementation. There were reasons why TI dropped them, and MIPS, which made a big thing of them, dropped out of performance competition fairly early. Oct 25 at 19:24
  • 3
    Seems to be a nice confirmation of Patterson & Hennessy's "Make the default case fast". If that is the case, added complexity will only make it slower, or at the least do nothing.
    – chthon
    Oct 26 at 5:24
  • @supercat: Ever put a branch in a branch delay slot?
    – Joshua
    Oct 27 at 20:27
14

TL;DR:

It was a limited solution to bridge a gap in chip development.

There was a small window of usefulness between the time chip technology was capable to support a CPU with pipelines long enough to create a failed prediction penalty (i.e. the wrong sequence fetched) but not providing sophisticated branch prediction units (and data storage) and the time this got solved.

In addition it's only really useful if the penalty for a miss is a very hefty one, like with the extreme long pipeline of a Pentium 4 - which is exactly where Intel introduced the 2E/3E branch hint prefixes. The same that later got dropped when instruction preparation and execution got complete redesigned and pipelines shortened (together with bigger and better branch prediction).


Points to think about:

  1. Hint prefixes will increase code size, which in turn will lower performance overall, as it means fetching an additional byte from memory (and cache), taking up bandwidth (*1).

  2. There will be only a one-time gain as it only pays out if the hint is true and if that branch is only encountered once. If executed a second time, a branch prediction will be as effective.

  3. It carries always maximum penalty in cases where the hint is incorrect.

  4. A BTFN (*2) algorithm will already improve most cases of branches where static hints have a high success chance: loops.

But most importantly:

  • Any Branch Prediction will usually outperform static hints.

Implementing branch prediction is not just always a good idea, but a real must to support code without hints (or worse, bad hints). So as soon as there is a branch prediction, branch hints turn into a burden.


So the question might be rather:

Why was branch hinting considered in the first place?

As so often in (chip) development, it's a matter of resources. A hint based system can be implemented very easy with extrem low hardware effort within the fetching logic:

(situation when hitting a hinted branch)

  • fetch hint opcode
  • fetch the branch
  • decode hint (can be done in parallel)
  • depending on hint
    • continue fetching following instruction, or
    • fetch starting with branch target. (whenever the condition is checked)
  • if branch condition test does not support hint
    • flush pipeline and start fetching the other way.

When comparing this with the way fetching works without, it becomes obvious that the difference is only in how a (hinted) branch is handled.

An operation is treated as

  • a sequential operation without any hint
  • a sequential operation if there's a 'usually not taken' hint
  • a jump (unconditional branch) if there's a 'usually taken' hint

Any sufficient complex pipeline will already handle both cases accordingly, so it's really just a small addition to switch for either according to the hint. Hardware cost for hinting is very low (*3,*4). Thus an implementation of hinting was easy to achieve at a time before large (and fast) prediction tables became affordable. But as soon as chip real estate provided them, hinting became a (mostly) useless burden.


Practical Use

Last, but for sure not least, a look at use cases for hinting might help as well, as there is essentially only one:

  • extreme one sided data sets with known tilt

Which comes in 3 flavors:

  • uneven user data
  • looping/list processing
  • error checks (think if (read(...) == -1) {...} clauses)

Of these

  • the first is hard to predict
  • the second is again rather likely covered by a BTFN

leaving only

  • the last as generic use case where a BTFN will usually fail and a hint would be helpful.

Not much of a use case that is.


*1 - This could be mitigated by using 3 sets of branches (taken/not taken/no hint) - of course at cost of code space.

*2 - Back Taken/Forward Not - which means any branch to a lower address (back) is assumed to be taken, while a higher target address is assumed to be not taken.

*3 - A FF for the hint (a few if more complex) plus maybe an address register and a few logic gates. seriously not much to think about if this is already a CPU with pipelining (one without doesn't need hints at all).

*4 - Then again, adding a BTFN logic is as simple while catching quite many cases, although slower as it needs to check the branch target address first.

10
  • 1
    I haven't had a close look at any real-world ISAs, but as for your first point, about increased code size, it's basically one bit per branch. Isn't it? Or were there actual machines having full instructions words as prefixes? If that's what we're talking about, it's the encoding that's inefficient. Not the branch hint itself.
    – OmarL
    Oct 26 at 13:00
  • @OmarL There were both variants. Intel e.g. introduced the 2E/3E prefixes as branch hint with the Netburst architecture (P4). No basic difference from adding 'just' a bit, as this triples the code space use (used encoding within all available encoding) for branches by needing three versions of each branch (regular, taken-hint, not-taken-hint) - resulting in less possible instructions or a larger instruction word. I'm not really sure what your point is. Any encoding is always information to be transported (stored, fetched). No matter if bit or byte, thus eating bandwidth - aka performance.
    – Raffzahn
    Oct 26 at 14:00
  • 1
    Why would BTFN fail for error checks? Isn't the compiler smart enough to optimize the order so that BTFN will work for this cases too? In C code error checks are one of the most common branches. Oct 26 at 21:02
  • @12431234123412341234123 well, error checks like with If(error){...} are (usually) a test (like compare with -1) followed by a forward jump if no error. Assuming no error as default, the FN part of BTFN will result in the wrong assumption. Of course one could (nowadays) think of compilers optimizing this, but to do so, they need a way to see that this is a rare case - and by doing so, how to organize the code otherwise? This isn't a trivial issue.
    – Raffzahn
    Oct 26 at 21:13
  • 1
    @PaulA.Clayton I see. Yes, if the hint isn't a prefix but embedded within the branch, then BTFN has no speed penalty. As well true, if it's a PC relative branch with simple encoding then the top bit can be used without further decoding. Regarding instruction encoding: The point to be made is that adding hints it never will produce a reduction in code size. O course, depending on a particular ISA it may run at zero cost. I'm starting to like the question as it leads deep into the jungle of optimization being only valid in certain configurations.
    – Raffzahn
    Oct 27 at 19:22
0
  1. Branch prediction is based on estimated behavior. The statistics gathered at run-time becomes more accurate, and more adaptive to whatever actual data the program is currently handling, than any compile time estimates based on previous data sets.

  2. Compiled hints target a specific ISA implementation, and, if portable, quickly become inappropriate for more newer advanced microarchitectures targeting the same ISA (more renaming registers, deeper pipelines, and etc.)

  3. Run-time branch prediction hardware can use far more advanced logic (neural nets trained at run-time to infer complex branching sequences and behavior. An instruction set doesn't have anywhere near enough bits to upload a machine learning model for each branch.)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.