Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A history of branch prediction

danluu.com

Post reply on HN
Print view View original

41–50 of 68 posts

Re: A history of branch prediction

#41

Post by deepnotderp »

userbinator wrote: post #5

The use of previous branch history and branch address as a "context" for prediction reminds me of the very similar technique used for prediction in arithmetic compression as used in e.g. JBIG2, JPEG2000, etc. --- the goal being that, if an event X happens several times in context C, then whenever context C occurs, the probability of X is more likely. Also, since modern CPUs internally have many functional units to wh…

You're thinking of predication, also sometimes called "if- conversion" or more loosely, speculation

It's very useful for getting rid of small control flow that doesn't really change the path of execution much, but doing it for too long is impossible due to the exponential complexity.

Re: A history of branch prediction

#42

Post by deepnotderp »

mjevans wrote: post #10
userbinator wrote: post #5

The use of previous branch history and branch address as a "context" for prediction reminds me of the very similar technique used for prediction in arithmetic compression as used in e.g. JBIG2, JPEG2000, etc. --- the goal being that, if an event X happens several times in context C, then whenever context C occurs, the probability of X is more likely. Also, since modern CPUs internally have many functional units to wh…

You could do it, but 'work' produces heat. From that point of view a branch predictor /saves/ you from spending the heat of the cases you /don't/ need to have processed. The performance per watt of such a design would probably leave it on the back of a napkin as an educated guess of how costly that would be.

Yes, but functional units are only around ~6% of the power consumption of a modern superscalar processor. And with Moore's law squeaking out its last few iterations, that number will get even smaller. If you can remove a good part of that by using predication, then you actually win out on power and heat as well.

Re: A history of branch prediction

#43

Post by deepnotderp »

buildbot wrote: post #9
userbinator wrote: post #5

The use of previous branch history and branch address as a "context" for prediction reminds me of the very similar technique used for prediction in arithmetic compression as used in e.g. JBIG2, JPEG2000, etc. --- the goal being that, if an event X happens several times in context C, then whenever context C occurs, the probability of X is more likely. Also, since modern CPUs internally have many functional units to wh…

People has tried this but as other have pointed out, it doesn’t get you very far. Along the same lines is runahead execution which is not directly related to branch prediction, but follows the similar idea you had that if you have all these functional units , you might as well try to figure out what you should start prefetching by speculatly executing the most likely sequence of instructions- even if you are waiting…

Runahead is a totally different concept though, it attempts to extract MLP and throws away all the work even if it was valid.

Re: A history of branch prediction

#44

Post by deepnotderp »

ufo wrote: post #36

One surprising thing that I discovered recently is that after Haswell, Intel processors got much much better at predicting "interpreter loops", which are basically a while true loop with a very large seemingly unpredictable switch statement. It lead to a dramatic improvement in micro benchmarks and made some traditional optimizations involving computed goto and " indirect threading" obsolete. Does anyone know how it…

perhaps they have a dedicated loop length predictor? Iirc, loop exits account for a majority of branch mispredicts nowadays, so it makes sense.

Re: A history of branch prediction

#45

Post by redcalx »

SolarNet wrote: post #13
lordnacho wrote: post #8

Top quality article. Now we need one with specifics of how to write code that's aware of this. For instance when do use what compiler hints. Anyone have links or books?

The compiler is (probably) smarter than you. Generally speaking, it will automatically decide which branches are most likely and arrange them accordingly (e.g. for things like for loops and while loops especially, where the biggest gains are). You'd likely gain more performance out of algorithmic changes, and then a number of other processor optimizations (like vectorization and pre-fetch hints) first. Also, CPU manu…

I noticed recently that there are conditional select vector instructions, so e.g. you can implement max(x,y) with an instruction instead of doing a CMP and JMP. When I tried it it was substantially faster than the CMP/JMP approach, like 20 times faster (on an Intel Skylake i7) even though the vector had only 4 values (4 * 64 bit double precision floats) - hence I was expecting 4x speedup at most.

I figured as far as the brnach predictor is concerned this is not a branch and therefore branch mispredictions are totally avoided.

Re: A history of branch prediction

#46

Post by ufo »

deepnotderp wrote: post #44
ufo wrote: post #36

One surprising thing that I discovered recently is that after Haswell, Intel processors got much much better at predicting "interpreter loops", which are basically a while true loop with a very large seemingly unpredictable switch statement. It lead to a dramatic improvement in micro benchmarks and made some traditional optimizations involving computed goto and " indirect threading" obsolete. Does anyone know how it…

perhaps they have a dedicated loop length predictor? Iirc, loop exits account for a majority of branch mispredicts nowadays, so it makes sense.

It must have been something else. I was talking about VM loops, which never exit.

Re: A history of branch prediction

#47

Post by ajkjk »

Is there any system out there that supports branch 'annotations', of a sort, so that the programmer or the compiler can just tell the CPU what the branch behavior is going to be?

Like -- it seems kinda silly for the CPU to do so much work to figure out if a loop is going to be repeated frequently, when the code could just explicitly say "fyi, this branch is going to be taken 99 times out of 100".

Or, if there's a loop that is always taken 3 times and then passed once, that could be expressed explicitly, with a "predict this branch if i%4 != 0" annotation.

Re: A history of branch prediction

#48

Post by to3m »

ufo wrote: post #36

One surprising thing that I discovered recently is that after Haswell, Intel processors got much much better at predicting "interpreter loops", which are basically a while true loop with a very large seemingly unpredictable switch statement. It lead to a dramatic improvement in micro benchmarks and made some traditional optimizations involving computed goto and " indirect threading" obsolete. Does anyone know how it…

https://hal.inria.fr/hal-01100647 suggests it might use an improved version of the TAGE scheme referred to in the article.

Re: A history of branch prediction

#49

Post by _chris_ »

ajkjk wrote: post #47

Is there any system out there that supports branch 'annotations', of a sort, so that the programmer or the compiler can just tell the CPU what the branch behavior is going to be? Like -- it seems kinda silly for the CPU to do so much work to figure out if a loop is going to be repeated frequently, when the code could just explicitly say "fyi, this branch is going to be taken 99 times out of 100". Or, if there's a loo…

Yes, a few ISAs have things like "branch.likely", but the CPU will just ignore it because it will do a better job anyways (the compiler is only as good as the test program used to guide its analysis).

GCC allows the programmer to guide "unlikely" branches too. I assume that means GCC moves that code away so it doesn't pollute the I$ and static predictors can predict them correctly.

There are some (usually small, embedded) processors that have "loop count" instructions. They are typically stateful and hard to make work in high-performance pipelines.

Re: A history of branch prediction

#50

Post by seedragons »

Is this correct? "Without branch prediction, we then expect the “average” instruction to take branch_pct * 1 + non_branch_pct * 20 = 0.8 * 1 + 0.2 * 20 = 0.8 + 4 = 4.8 cycles"

other than branch_pct and non_branch_pct being reversed, this seems to be assuming that 100% of branches are guessed incorrectly. Shouldn't something like 50% be used, to assume a random guess? ie 0.8 * 1 + 0.2 * (0.5 * 20 + 0.8 * 1)=2.96

Post reply on HN