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

51–60 of 68 posts

Re: A history of branch prediction

#51

Post by innocenat »

redcalx wrote: post #45
SolarNet wrote: post #13

Earlier quoted context omitted.

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…

Unless you are targeting pre-SSE2 CPUs, no compiler should generate CMP+JMP for max operation on floating point. `maxsd` is in SSE2, along with all double precision operation. Before that double precision still run on x87. (SSE only has single-precision operation)

With AVX (Sandy Bridge and later), `vmaxpd` on `ymm` would allow you to operate on 4 double-precisions at once. If you observe 20x speed up, it would probably also come from memory access optimization.

Re: A history of branch prediction

#52

Post by SolarNet »

adrianN wrote: post #17
SolarNet wrote: post #13

Earlier quoted context omitted.

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…

Whether or not it's an early optimization depends on when you add the __builtin_expect, no? Perhaps you already have identified a very hot branch in your code that the compiler fails to treat correctly even though you provided it with profile data.

Except that anything newer than 1995 probably ignores the hint provided by __builtin_expect, and you'd probably have more luck changing the algorithm or vectorizing the code.

Re: A history of branch prediction

#53

Post by buildbot »

deepnotderp wrote: post #43
buildbot wrote: post #9

Earlier quoted context omitted.

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.

True, I was just reminded of it by the original poster’s idea.

Re: A history of branch prediction

#54

Post by deepnotderp »

ufo wrote: post #46
deepnotderp wrote: post #44

Earlier quoted context omitted.

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.

Ah , maybe they have a dedicated inner predictor?

Re: A history of branch prediction

#55

Post by deepnotderp »

buildbot wrote: post #53
deepnotderp wrote: post #43

Earlier quoted context omitted.

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

True, I was just reminded of it by the original poster’s idea.

Fair enough, runahead is a cool idea after all :)

Re: A history of branch prediction

#56

Post by ryangittins »

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 and no. I say yes because C and C++ both have likely() and unlikely() functions (well, technically It's part of a compiler extension rather than the language), which you wrap around the condition inside your if() statement like so:

  for(i=10000; i
I say no because most modern compilers simply ignore the functions. Compilers have become so sophisticated over the years that developers trying to help them along or optimize often make things worse, whether that's by getting in the compiler's way or just writing code that's harder to read and debug.

I say no (or at least probably not) to your second questions as well. No language I know if implements anything as sophisticated as a specification for regular intervals of branch switching. Many modern compilers have sophisticated branch prediction routines which can detect simple regular intervals like you describe.

To develop such a specification would optimize the branch prediction by a tiny margin which would be absolutely dwarfed by the overhead of learning the syntax for the specification, not messing it up, debugging it if you do mess it up, communicating the decision to other team members, and all of the other real-world stuff that gets in the way.

Computers are faster than ever and branch prediction algorithms are smarter than ever. Yes, you could help it along in theory but the portion of applications which really require you to do so is dwindling all the time.

Re: A history of branch prediction

#57

Post by sn9 »

legulere wrote: post #18

I really have problems reading this website. You don't have to make a website bloated to make it readable: http://bettermotherfuckingwebsite.com

It takes less than a second to Ctrl-+ a few times until the site becomes extremely readable.

Re: A history of branch prediction

#58

Post by Sniffnoy »

oshepherd wrote: post #38
Sniffnoy wrote: post #12

> PA 8000 (1996): actually implemented as a 3-bit shift register with majority vote This actually seems interestingly different from the two-bit saturating counter. Like, it's not just a different way of implementing it; you can't realize the saturating counter as a "quotient" of the shift/vote scheme.

It's the same just with redundant representations (the 2-bit repr is the count of ones in the 3-bit repr) '00' -> '000' '01' -> '001', '010', '100' '10' -> '011', '101', '110' '11' -> '111' this kind of transformation is truly bread & butter in hardware; we regularly numbers between binary counts, mask/number-of-set-bits and one-hot representations for optimisation purposes.

That's the obvious attempt at an equivalence one would come up with on being told that they're the same, but, as I stated, it doesn't work. As an example: In the 2-bit saturating counter, if you start at 00, if you see a 1 and then a 0 you're back to where you started. Whereas in the bit-shift register, if you start at 000 and see a 1 and then a 0, you're now at 010, which would correspond to 01 rather than 00.

Re: A history of branch prediction

#59

Post by 0xffff2 »

seedragons wrote: post #50

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

It's correct if you take "without branch prediction" to include any pipelining of instructions after a branch.

The very first branch prediction algorithm ("predict taken") is to simply enable pipelining by assuming the generally more likely branch.

>...this seems to be assuming that 100% of branches are guessed incorrectly...

Rather, it's assuming that 100% of branches are not guessed at all.

Re: A history of branch prediction

#60

Post by jasonwatkinspdx »

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…

> Also, since modern CPUs internally have many functional units to which operations can be dispatched, I wonder if, in the case that the "confidence" of a branch prediction is not high, "splitting" the execution stream and executing both branches in parallel until the result is known...

This is called disjoint eager execution: http://dl.acm.org/citation.cfm?id=225208

What killed the idea is that branch predictors are simply too good. You'd end up almost never speculating off the main spine the predictor gives you, and so all the other machinery needed doesn't provide nearly enough value for its cost.

Post reply on HN