Recent Features
| |||||||||||||
Likely unlikely()sLikely unlikely()sPosted Dec 19, 2010 3:39 UTC (Sun) by quotemstr (subscriber, #45331)In reply to: Likely unlikely()s by jzbiciak Parent article: Likely unlikely()s You're assuming that pcorrect and pincorrect are constant over time, and they're often not. CPUs these days have large global branch prediction buffers and can detect fairly complex patterns (e.g., branch every third time) automatically. The overall result of this dynamic prediction may be superior to a purely static assertion, even if that assertion is correct on average. Think of a branch that goes one way during the day and another way at night. If we suppose that activity is twice as high during the day, then we'll see a 2:1 branch bias in favor of the daylight path. But over smaller intervals of time (say, an hour), the branch bias will be almost totally in favor of one path or the other. Unlike static assertions, the CPU's automatic prediction can look at the specific circumstances of the system and make predictions based on recent behavior and specific circumstances. Using static branch prediction could actually hurt.
(Log in to post comments)
Likely unlikely()s Posted Dec 20, 2010 20:35 UTC (Mon) by jzbiciak (✭ supporter ✭, #5246) [Link] I did state my model was simplified, and did allow for the fact that branch prediction could change the cost over time and that that wasn't included in my model. My understanding is that static prediction mainly involves either putting a hint on a branch opcode (on architectures that support it) and/or changing which path is the "fall through" path versus the "branch taken" path, overlaid with a rule such as "predict backward branches as taken; forward branches not-taken". In the presence of dynamic prediction, a branch hint should be just that: a hint. A strong prediction signal from the predictor ought to override a hint. The main purpose of branch hinting is to help the cold-predictor case. This article describes one such scheme. Basically, if your branch isn't in the Branch History Table (BHT), then it falls back to the static prediction. This puts an upper bound on how much damage the static prediction can do, as well as an upper bound on how much it can help. For static branch prediction to hurt, you'd need to have a large enough working set that the branch in question isn't in the BHT (to use the P4's scheme above), but still hit often enough to make a measurable performance difference. For your bimodal case (day/night shifting patterns), which ever way you schedule your code, you'll penalize one or the other. If you have accurate long-term branch statistics, though, you can still pick the one that occurs less often and penalize that. So, if daytime has twice the load as nighttime, it should show up in the statistics and you can put likely/unlikely on the conditional to favor daytime. Really, the argument that makes the most sense to me against likely/unlikely in marginal cases is that different users could have completely different workloads with wildly different statistics (multimodal across all users, even though each user might be unimodal), and so there's no good training set, so just let the compiler guess. There's no way to avoid penalizing someone, so let the compiler do it. Only put likely/unlikely where it's clear that it's right across the vast majority of workloads. Otherwise, there's a good chance it could be wrong for more than half the users out there, and it's also not worth the maintenance burden. So, that leaves the question: What's the criteria for figuring that out? Taken vs. not-taken ratio seems like a shaky heuristic to me.
Likely unlikely()s Posted Dec 21, 2010 13:58 UTC (Tue) by vonbrand (subscriber, #4458) [Link] It has been observed that programmers are terrible at guessing where their programs spend most of their time... and that should be much easier than predicting the frequency of some critical branch going one way or the other. Best leave it alone, or only annotate when extensive measurements show a high bias (and the compiler gets it wrong).
Likely unlikely()s Posted Dec 27, 2010 11:00 UTC (Mon) by tesarik (guest, #52705) [Link]
*the* compiler? which compiler?
Surely, gcc heuristic decisions change with the version...
|
|||||||||||||