1

I have a have a few if statements in a performance critical loop that looks something like this

for(i = 0;;i = (i + 1) % n) {
    if (i == 3) {
        //...
    }
}

This opens up the possibility of branch prediction failure, which will slow my program. Fortunately, I know exactly how frequently the condition will be met, once every n iterations. (I will leave it as an abstract n because I have multiple similar conditions where n is different)

What I want to know is if there is any way to tell the branch predictor that this helpful information I have, or if I just have to hope it can find the pattern.

One solution I have considered is unrolling the loop so there is no branch. This is a fine solution, and what I was planning on using, but it has a few slightly unappealing side effects. In particular, it would break DRY and it would create a larger program size (memory is limited, though not that limited).

Can I tell the branch predictor the pattern I know without unrolling the loop?

rtpax
  • 1,687
  • 1
  • 18
  • 32
  • Not quite the same. I have an exact pattern for the predictor to match, rather than just a relative probability – rtpax Feb 23 '19 at 02:06
  • 1
    One of the answers there says “The processor can predict small repeating patterns (n~7) perfectly.” What is the range of your n? – Eric Postpischil Feb 23 '19 at 02:37
  • Branch prediction is a hardware feature. No C extension can provide it if the hardware does not. You should state the specific processor model you are targeting. – Eric Postpischil Feb 23 '19 at 02:38
  • I understand that it would be hardware dependent. I unfortunately don't have the information for the exact processor with me right now. The largest n, at least for now, is 6, so that actually works pretty well, though I would like a solution that extended to higher numbers out of curiosity. – rtpax Feb 23 '19 at 02:43
  • @EricPostpischil Though on a closer inspection, the processor says it can predict exact loops of up to 64 perfectly, which is more than I would ever need. I am going to flag my post as a duplicate of what user11087555 suggested – rtpax Feb 23 '19 at 02:47

0 Answers0