A. Sarid A. Sarid - 1 year ago 98
C Question

Call a function when counter reaches some value without if statement

Lets say I have a function named

. In this
I increment a counter

I have few functions,
, etc.

I want to call each one of these functions when the counter reaches some value (different for every function).
My current code looks like:

static unsigned int count = 0;
void loop(){
if (count == VALUE_ONE)
if (count == VALUE_TWO)
if (count == VALUE_THREE)
..... //more cases

if (count == MAX_VAL)
count = 0;

s so they are not being changed during the program.

Right now I am using regular
statements to check the counter value. But I want to avoid using the
statement to avoid branch mispredictions.

Is there a better way to do this? Something that will actually avoid branch mispredictions etc?


The goal here is to optimize this part of code in order to make it in faster, as for now it sometimes doesn't finish until the time it should. I am aware that there might be a problem with function
, etc, but for now I am asking about this specific case.

To make it clear,
, etc might be very large values and not increasing by
. For example it might be:

#define VALUE_ONE 20
#define VALUE_TWO 1500
#define VALUE_THREE 99777

My compiler version is: gcc (GCC) 4.4.7

Answer Source

Why in the world are you worried about branch misprediction? Do you have a working program? Does it run too slowly? Have you narrowed the problem to branch misprediction in the code you present? Unless the answer to each of those questions is "yes", you are engaging in premature optimization.

Moreover, the conditional branches in the code you present appear to be highly predictable, at least if the counter is expected routinely to reach values in the tens or hundreds of thousands or more, as the updated example code seems to indicate. A misprediction rate on the order of 0.00001 or less -- which is about what you could expect -- will not have a measurable performance impact. Indeed, handling code such as you've presented is the bread and butter of branch prediction. You could hardly ask for a case more friendly to a branch-prediction unit.

In any event, since you are concerned about branch misprediction, your question must be not so much about avoiding the if statements in particular, but about avoiding conditional logic in general. As such, a switch construct probably is not better, at least not for the situation you describe, wherein you want to call functions only for a handful of the large number of distinct values the function will see, sprinkled across a wide range. Although the compiler could, in principle, implement such a switch via a jump table, it is unlikely to do so in your case because of how large the needed table would be, and how few of the elements would differ from the one for the default case.

A hash table has also been discussed, but that's no better, because then either you need conditional logic to distinguish between cache hits and cache misses, or else your hash table must for every input provide a function (pointer) to be called. Calling a function on every iteration would be far more costly than what you are doing now.

Additionally, you need a perfect hash function to avoid conditional logic in the HT implementation. If the possible values of your counter are bounded by a small enough number that a hash table / perfect hash could be used to avoid conditional logic, then a plain array of function pointers would be lighter-weight than a hash table, and could serve the same purpose. It would still have the same problem with function-call overhead, however. If you insist on avoiding conditional logic then this would probably be the best way to go for your particular problem. But don't.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download