Posted Dec 16, 2010 5:09 UTC (Thu) by jzbiciak
(✭ supporter ✭
Parent article: Likely unlikely()s
Being wrong 39% of the time was pretty obviously too much and led to the removal of the annotation for that test.
What that's saying is that a 60:40 ratio is too close. So what is an appropriate threshold?
It seems like any notable bias in a particular direction should be reason enough. The main key is whether the bias is stable over a range of reasonable workloads. (Note I say "reasonable". If you have likely(doesn't segfault) and then run a workload full of segfaults, well that's just silly.)
Consider a simplified model: You have two costs, kcorrect and kincorrect. If you predict a branch is taken and the branch is in fact taken, then you get charged kcorrect, otherwise you get charged kincorrect. And, this whole exercise is only worthwhile if kcorrect < kincorrect. You also have two probabilities: pcorrect is the probability that your prediction matches what the computer did, and (1 - pcorrect) is the probability it didn't. In this model, then, overall performance should approach kcorrect * pcorrect + kincorrect * (1 - pcorrect) if you annotated your branch correctly. In the 60:40 example from the article, pcorrect would be 0.6.
In this model, you end up with a few possibilities:
- You annotated your branch correctly, and performance = kcorrect * pcorrect + kincorrect * (1 - pcorrect)
- You annotated your branch incorrectly, effectively switching kcorrect and kincorrect. performance = kincorrect * pcorrect + kcorrect * (1 - pcorrect)
- You left it up to the compiler to figure it out. Whether you get #1 or #2 above depends on how good/lucky your compiler is.
Now you're left weighing the quality of the compiler against your ability to get the annotation right and your desire to maintain that annotation. And that's just with this simplified model. In a more complex model, the probability a branch gets taken can vary on other factors, some of which may be discoverable by the CPU's branch prediction logic for example.
Given all that, I can see why you'd want a very clear signal for 'likely'/'unlikely'. But still, how clear?
to post comments)