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

How many branches can your CPU predict?

lemire.me

Post reply on HN
Print view View original

61–66 of 66 posts

Re: How many branches can your CPU predict?

#61

Post by throawayonthe »

OskarS wrote: post #6

Hmm, that's interesting. The code as written only has one branch, the if statement (well, two, the while loop exit clause as well). My mental model of the branch predictor was that for each branch, the CPU maintained some internal state like "probably taken/not taken" or "indeterminate", and it "learned" by executing the branch many times. But that's clearly not right, because apparently the specific data it's branch…

relevant video: https://youtu.be/nczJ58WvtYo How Branch Prediction Works in CPUs - Matt Godbolt with Computerphile

Re: How many branches can your CPU predict?

#62

Post by mcdeltat »

fc417fc802 wrote: post #39
rayiner wrote: post #17

Earlier quoted context omitted.

Your mental model is close. Predictors generally work by having some sort of table of predictions and indexing into that table (usually using some sort of hashing) to obtain the predictions. The simplest thing to do is use the address of the branch instruction as the index into the table. That way, each branch instruction maps onto a (not necessarily unique) entry in the table. Those entries will usually be a two-bit…

It seems like that would struggle with detecting how many layers of branching to pay attention to. Imagine the two nested loops surrounded by a randomized one. Wouldn't that implementation keep hitting patterns it hadn't seen before? Obviously that must be a solved problem; I'd be curious to know what the solution is.

Can you walk through why you think the random outer loop would interfere?

If the inner loop's behaviour is predictable no matter the outer loop, then because the branch predictor is keyed by instruction address, it can be predicted. Only the inner loop's history is considered.

Or maybe I'm misunderstanding what code you're imagining?

Re: How many branches can your CPU predict?

#63

Post by fc417fc802 »

mcdeltat wrote: post #62
fc417fc802 wrote: post #39

Earlier quoted context omitted.

It seems like that would struggle with detecting how many layers of branching to pay attention to. Imagine the two nested loops surrounded by a randomized one. Wouldn't that implementation keep hitting patterns it hadn't seen before? Obviously that must be a solved problem; I'd be curious to know what the solution is.

Can you walk through why you think the random outer loop would interfere? If the inner loop's behaviour is predictable no matter the outer loop, then because the branch predictor is keyed by instruction address, it can be predicted. Only the inner loop's history is considered. Or maybe I'm misunderstanding what code you're imagining?

It seems likely I've fundamentally misunderstood gselect or some other aspect here.

If you only look at the history of a single address independently then don't shallow nested loops with dependent behavior completely break the entire scheme?

Whereas with global history I think it mostly works. Maybe? But in that case what happens when the inner branch is trivially predictable but shallow and enclosed by ones that aren't?

In the linked article the branch always has the same address. AMD starts gradually degrading at 30k. Doesn't that indicate 16 bits of history? So for a single trivially predictable inner branch wouldn't you expect an initial 14 mispredictions? That seems like a lot.

My (I suspect very flawed) mental model here is global branch history with a 16 bit shift register and a 16 bit table, the latter keyed on hash( register ) ^ hash( address ) to explain the observed behavior.

Re: How many branches can your CPU predict?

#65

Post by mcdeltat »

fc417fc802 wrote: post #63
mcdeltat wrote: post #62

Earlier quoted context omitted.

Can you walk through why you think the random outer loop would interfere? If the inner loop's behaviour is predictable no matter the outer loop, then because the branch predictor is keyed by instruction address, it can be predicted. Only the inner loop's history is considered. Or maybe I'm misunderstanding what code you're imagining?

It seems likely I've fundamentally misunderstood gselect or some other aspect here. If you only look at the history of a single address independently then don't shallow nested loops with dependent behavior completely break the entire scheme? Whereas with global history I think it mostly works. Maybe? But in that case what happens when the inner branch is trivially predictable but shallow and enclosed by ones that are…

Ahh maybe I am the one who is misunderstanding... I'm by no means an expert on this (and it is quite complex)

Re: How many branches can your CPU predict?

#66

Post by fc417fc802 »

mcdeltat wrote: post #65
fc417fc802 wrote: post #63

Earlier quoted context omitted.

It seems likely I've fundamentally misunderstood gselect or some other aspect here. If you only look at the history of a single address independently then don't shallow nested loops with dependent behavior completely break the entire scheme? Whereas with global history I think it mostly works. Maybe? But in that case what happens when the inner branch is trivially predictable but shallow and enclosed by ones that are…

Ahh maybe I am the one who is misunderstanding... I'm by no means an expert on this (and it is quite complex)

Looking at the linked slides again my mental model is what it refers to as "gshare". A tournament predictor between that and "local" addresses the two scenarios I posed but still has obvious failure modes.

Local: if( rng() ){ if( true ){ ... }}

Global: if( f ){} if( !f ){}

Trashed state: if( rng() ){} if( f ){} if( !f ){}

But notice that the third happens naturally (ie no need for an RNG) any time the history depth doesn't match up nicely with the looping pattern. Hence my initial question about how real world implementations determine how many layers to pay attention to. You could solve it with a tree structure but do hardware implementers go that far?

Post reply on HN