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

61–68 of 68 posts

Re: A history of branch prediction

#61

Post by simcop2387 »

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

This is talking about the case where there is no branch prediction. So every branch incurs the penalty of a bad prediction because it never tries to do the favorable action, instead it stalls and waits on the result to do the branch.

Re: A history of branch prediction

#62

Post by seedragons »

0xffff2 wrote: post #59
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.

Ah I see, I assumed it was a penalty for only mis-guessed, not the number of cycles required to evaluate the statement. Thanks!

Re: A history of branch prediction

#63

Post by redcalx »

innocenat wrote: post #51
redcalx wrote: post #45

Earlier quoted context omitted.

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 proba…

I'm playing with the new(ish) C#/dotnet vector/SIMD support e.g. Vector.Max() generates a vmaxpd instruction, whereas Math.Max() generates a method call.

That method is implemented like so:

if (val1 > val2) { return val1; } if (double.IsNaN(val1)) { return val1; } return val2;

This appears to not have an optimized implementation in the CLR (the dotnet VM) and the presence of 'if' statements is likely the reason why this was not inlined. So I think the 20x speedup is genuine, it's because the baseline version is horribly slow!

Re: A history of branch prediction

#64

Post by deepnotderp »

fulafel wrote: post #37
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…

It doesn't look like a series of comparisons from the CPU point of view. Normally switch statements are compiled like a series of "if" statements, but the interpreter loop style switch gets compiled into a table of jump targets that is indexed by bytecode. Same kind of indirect branch prediction features that were previously designed to help C++ "virtual" functions help here - a branch target buffer, etc. The VM inte…

Longer switches are usually compiled into binary search trees.

Re: A history of branch prediction

#65

Post by fulafel »

deepnotderp wrote: post #64
fulafel wrote: post #37

Earlier quoted context omitted.

It doesn't look like a series of comparisons from the CPU point of view. Normally switch statements are compiled like a series of "if" statements, but the interpreter loop style switch gets compiled into a table of jump targets that is indexed by bytecode. Same kind of indirect branch prediction features that were previously designed to help C++ "virtual" functions help here - a branch target buffer, etc. The VM inte…

Longer switches are usually compiled into binary search trees.

It depends on whether the switched-on values are sparse. Contiguous ranges of bytecodes are more efficiently compiled to straight jump tables (and enable indirect branch prediction mechanisms in CPUs to work).

For another boost to leveraging indirect branch prediction, threaded code is still a little better since each VM instruction has a unique jump call site: http://eli.thegreenplace.net/2012/07/12/computed-goto-for-ef...

Re: A history of branch prediction

#66

Post by redraga »

deepnotderp wrote: post #40

TAGE and perceptron combined are the SOTA right now, right?

Yes. TAGE still does better than perceptron, but combining the two is likely to give you the best performance currently. Of course, all this is dependent on area allocated to the predictor and the workloads being run.

Re: A history of branch prediction

#67

Post by josch »

ramshorns wrote: post #4

Very informative. I missed the part about 1500000 BC though – a time when our ancestors lived in the branches of trees? Another beginner-friendly explanation of the effects of branch prediction is this Stack Overflow post which compares a processor to a train: https://stackoverflow.com/questions/11227809/why-is-it-faste...

You might be interested in this note by Oleg Kiselyov which talks about branch prediction in the context of one of the 1st computers: http://okmij.org/ftp/Computation/Zuse-accolades.txt

Re: A history of branch prediction

#68

Post by ufo »

fulafel wrote: post #65
deepnotderp wrote: post #64

Earlier quoted context omitted.

Longer switches are usually compiled into binary search trees.

It depends on whether the switched-on values are sparse. Contiguous ranges of bytecodes are more efficiently compiled to straight jump tables (and enable indirect branch prediction mechanisms in CPUs to work). For another boost to leveraging indirect branch prediction, threaded code is still a little better since each VM instruction has a unique jump call site: http://eli.thegreenplace.net/2012/07/12/computed-goto-fo…

That blog post is from 2012. What I observed is that with the more recent processors threaded code doesn't make much of a difference.
Post reply on HN