Re: Branch prediction
20 May 2000 13:20:51 -0400

          From comp.compilers

Related articles
Re: Branch prediction (2000-05-20)
Re: Branch prediction (2000-05-21)
Re: Branch prediction (2000-05-21)
Re: Branch prediction (Andi Kleen) (2000-05-21)
Re: Branch prediction (2000-05-28)
Re: Branch prediction (2000-05-31)
Re: Branch prediction (2000-06-03)
[1 later articles]
| List of all articles for this month |

Newsgroups: comp.compilers
Date: 20 May 2000 13:20:51 -0400
Organization: Mailgate.ORG Server - http://www.Mailgate.ORG
Keywords: architecture, optimize
Mail-From: at []

>There are two sides to the branch prediction story: static
>(compile-time) prediction and dynamic prediction done by the

The x86 does not allow AFAIK static prediction. The PPC does.

>that). Of course, this means that your predictor should be really
>smart: these CPUs expect prediction accuracy well into the 90% range.

The scheme used by P6s and on (maybe Pentium MMX too? I don't
remember) is exceptionally smart. It works by bucketing jumps into 16
bins, according to a taken/not-taken bit pattern. E.g. bin 13 (1101)
means Taken, Taken, Not-Taken, Taken; it is actually able to guess all
pattern with periods up to six, a few longer patterns (up to 16), and
even to learn irregularities.

There's a description of it in Agner Fog's Pentium and Pentium Pro
optimization paper (

There's a fundamental problem with every branch prediction system I
ran over. They do not work with indirect jump. Most processors
remember where the last jump landed, which might be decent for a lexer
but absolutely impractical for a bytecode interpreter; the solution
might be to tell the processor "hey, trust me, the jump is going to
land there" with a special instruction.

Paolo Bonzini

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.