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

11–20 of 68 posts

Re: A history of branch prediction

#11

Post by buildbot »

filereaper wrote: post #3

Ryzen has rolled out a Neural-Net based branch predictor, would be curious to see its accuracy compared to the listed approaches.

It’s actually a fairly old technique, which has been applied in other processors before! I recall and arm processor used the technique as well as AMD’s piledriver.

https://www.cs.utexas.edu/~lin/papers/tocs02.pdf https://www.cs.utexas.edu/~lin/papers/hpca01.pdf

Re: A history of branch prediction

#12

Post by Sniffnoy »

> 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.

Re: A history of branch prediction

#13

Post by SolarNet »

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 manufactures ignore the classic hints, and don't really have information on how to tune branch predictors. So while GCC/Clang does have a special intrinsic (`__builtin_expect`) for it in c/c++ - most other languages are too high level for it to matter - it probably won't do much and is an insanely early optimization to consider making.

Re: A history of branch prediction

#14

Post by irishsultan »

I seem to be missing something when the two bit scheme is introduced it's said that it's the same as the one bit scheme except for storing two bits (seems logical), but then the index in the lookup table seems to involve both the branch index (already the case in the one bit scheme) and the branch history (as far as I can see never introduced).

Re: A history of branch prediction

#15

Post by Sniffnoy »

irishsultan wrote: post #14

I seem to be missing something when the two bit scheme is introduced it's said that it's the same as the one bit scheme except for storing two bits (seems logical), but then the index in the lookup table seems to involve both the branch index (already the case in the one bit scheme) and the branch history (as far as I can see never introduced).

Looks like he just used the wrong picture -- used the picture from "two-level adaptive, global" instead.

Re: A history of branch prediction

#16

Post by jlebrech »

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...

the BC made no sense to me and there's no reference to it.

If he made an illustration about hunters tracking their prey and there was a fork in the road and they split into 2 groups that could allude to branch prediction, I don't know

Re: A history of branch prediction

#17

Post by adrianN »

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…

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.

Re: A history of branch prediction

#19

Post by suprfnk »

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

This is even better, in my opinion: https://bestmotherfucking.website/

Anyway, I agree. Text should always have a max width. Long lines of text aren't really readable.

I use this in my SurfingKeys settings, and use it on a lot of sites to make them more readable:

  mapkey('', 'Centers the current page', function() {
    document.body.style.cssText = "font-family: sans-serif !important";
    document.body.style.cssText += "color: black !important";
    document.body.style.cssText += "line-height: 1.4 !important";
    document.body.style.cssText += "margin: 0 auto !important";
    document.body.style.cssText += "max-width: 60em !important";
    document.body.style.cssText += "background: none !important";
    document.body.style.cssText += "background-color: #FEFEFE !important";
    
    return true;
  });
Post reply on HN