code optimization- Removing if .. else conditions in for loops

[Kunal]

Hello,

I need help in removing if ..else conditions inside for loops. I have
used the following method but I am not sure whether it has actually
helped.
Below is an example to illustrate what I have used.
Original code :

c= 0 ;
for (i=0; i<999; i++)
{
if (a > B)
c++ ;
}

Modified code for speed optimization

c= 0 ;
for (i=0; i<999; i++)
{
c += (a > B) ;
}

As per my reasoning, the logical expression is evaluated but no
conditional branching instructions should be generated. This should
avoid any pipeline stalls.
However, I havent found any document confirming my belief !
Any comments, suggestions or references will be a big help !

Thanks & Regards

 

[Ben Pfaff]

I need help in removing if ..else conditions inside for loops. I have
used the following method but I am not sure whether it has actually
helped.
Below is an example to illustrate what I have used.
Original code :

c= 0 ;
for (i=0; i<999; i++)
{
if (a > B)
c++ ;
}

Modified code for speed optimization

c= 0 ;
for (i=0; i<999; i++)
{
c += (a > B) ;
}

The only way you can find out whether this makes a difference is
by measuring. My guess is that it will make no difference with
most compilers.

Note that the evaluation of `a > b' may itself require a branch.

 

[Keith Thompson]

I need help in removing if ..else conditions inside for loops. I have
used the following method but I am not sure whether it has actually
helped.
Below is an example to illustrate what I have used.
Original code :

c= 0 ;
for (i=0; i<999; i++)
{
if (a > B)
c++ ;
}

Modified code for speed optimization

c= 0 ;
for (i=0; i<999; i++)
{
c += (a > B) ;
}

As per my reasoning, the logical expression is evaluated but no
conditional branching instructions should be generated. This should
avoid any pipeline stalls.
However, I havent found any document confirming my belief !
Any comments, suggestions or references will be a big help !

You're assuming that the code generated for (a > B) won't involve any
conditional branches.

Any decent compiler is likely to generate similar or identical code
for both forms.

It's usually best to write your code as clearly as possible and let
the compiler worry about micro-optimization. Attempting to do
low-level optimization yourself is likely to make the compiler's job
more difficult.

First rule of optimization: Don't do it.
Second rule of optimization (advanced users only): Don't do it yet.

If you really need to do this kind of micro-optimization, perhaps
because the loop is in a performance-critical part of your program
(because you've measured it), you can probably examine the assembly
language generated by your compiler -- or you can write the code in
assembly language yourself.

 

[Christian Bau]

Hello,

I need help in removing if ..else conditions inside for loops. I have
used the following method but I am not sure whether it has actually
helped.
Below is an example to illustrate what I have used.
Original code :

c= 0 ;
for (i=0; i<999; i++)
{
if (a > B)
c++ ;
}

Modified code for speed optimization

c= 0 ;
for (i=0; i<999; i++)
{
c += (a > B) ;
}

As per my reasoning, the logical expression is evaluated but no
conditional branching instructions should be generated. This should
avoid any pipeline stalls.

Did you measure how long it takes?

The most important rule of optimisation: Don't optimise until you have
measured it.

(There are several most important rules of optimisation, this is just
one of them. I bet some more will be posted. This one always applies:
Never, ever optimise without measuring. )

 

[Eric Sosman]

Kunal wrote On 12/05/05 17:02,:

Hello,

I need help in removing if ..else conditions inside for loops. I have
used the following method but I am not sure whether it has actually
helped.
Below is an example to illustrate what I have used.
Original code :

c= 0 ;
for (i=0; i<999; i++)
{
if (a > B)
c++ ;
}

Modified code for speed optimization

c= 0 ;
for (i=0; i<999; i++)
{
c += (a > B) ;
}

Even faster (probably):

c = (a > B) ? 999 : 0;
i = 999;

As per my reasoning, the logical expression is evaluated but no
conditional branching instructions should be generated. This should
avoid any pipeline stalls.
However, I havent found any document confirming my belief !
Any comments, suggestions or references will be a big help !

See Ben Pfaff's response.

 

[Jordan Abel]

Kunal wrote On 12/05/05 17:02,:

Even faster (probably):

c = (a > B) ? 999 : 0;
i = 999;

Though presumably he was doing more in the loop, you're correct.

 

[Flash Gordon]

Hello,

I need help in removing if ..else conditions inside for loops. I have
used the following method but I am not sure whether it has actually
helped.

Have you tested the code to see if it is too slow? Have you done
profiling to see where the code is spending its time? Have you made sure
that you are using an efficient algorithm? All these things should come
before spending time on a question like this.

Below is an example to illustrate what I have used.
Original code :

c= 0 ;
for (i=0; i<999; i++)
{
if (a > B)
c++ ;
}

Modified code for speed optimization

c= 0 ;
for (i=0; i<999; i++)
{
c += (a > B) ;
}

As per my reasoning, the logical expression is evaluated but no
conditional branching instructions should be generated. This should
avoid any pipeline stalls.

Anything like that is highly specific to the processor, compiler,
specific version of the compiler, the settings of the compiler and the
surrounding code.

However, I havent found any document confirming my belief !

It is very unlikely there is *any* documentation that will tell you
which is faster, since it might depend on a hole host of things.

Any comments, suggestions or references will be a big help !

Rule one of optimisation:
Don't do it.

Write the code to do the right thing in an understandable (to a human)
manner and let the optimiser that is almost certainly part of your
compiler package do its job.

 

[Eric Sosman]

Jordan Abel wrote On 12/05/05 18:00,:

Though presumably he was doing more in the loop, you're correct.

That was the point I was trying to make, indirectly:
It's silly to micro-optimize pseudocode. If the O.P.
responds to my tongue-in-cheek suggestion by showing us
what's actually going on in the loop, we might have some
better ideas about how to optimize it -- or whether it's
even worth the bother.

 

[Mark McIntyre]

Hello,

I need help in removing if ..else conditions inside for loops.

Why - have you proved that they're inefficient?

c += (a > B) ;

As per my reasoning, the logical expression is evaluated but no
conditional branching instructions should be generated. This should
avoid any pipeline stalls.

This would be /highly/ hardware specific, and depend very very much on
your compiler's efficiency.

As a general rule its a bad idea to try to outsmart your compiler,
until and unless you can prove its inefficient. You may end up simply
making your code slower. A good compiler might realise it could unroll
the loop and discard a whole bunch of the ifs, and your 'improvement'
might prevent that for some reason.

 

[Chris Dollin]

Hello,

I need help in removing if ..else conditions inside for loops. I have
used the following method but I am not sure whether it has actually
helped.
Below is an example to illustrate what I have used.
Original code :

c= 0 ;
for (i=0; i<999; i++)
{
if (a > B)
c++ ;
}

Modified code for speed optimization

c= 0 ;
for (i=0; i<999; i++)
{
c += (a > B) ;
}

As per my reasoning, the logical expression is evaluated but no
conditional branching instructions should be generated. This should
avoid any pipeline stalls.

On the ARM, a natural way to compile the if (assuming variables in
registers, which is plausible here) is:

CMP a, B
ADDEQ c, c, #1

Two instructions, no pipeline break. I can't see a compiler generating
better code for your `c += (a > B)` statement, and it would be easy for
it to generate much /worse/ code.

Morals: (a) measure before you consider optimising; (b) straightforward
code plays to the compiler's strengths.

 

[Kunal]

Hello,
Thanks for all your responses.

The example I had given is a typical (but not exact) one which I have
encountered during the development of the code.
I am working on development of video compression algorithm and have
encountered deep nested loops with embedded if ... else conditions,
typically like the one I have given in the example.

I have a stiff target to meet on fps (frame per second) front and hence
I am trying to remove such conditions where there may be pipeline
stalls. So optimization is inevitable.

I am still not clear why would the compiler generate a branch condition
if only a boolean expression is to be solved.

 

[Ben Pfaff]

I am still not clear why would the compiler generate a branch condition
if only a boolean expression is to be solved.

Because, given the machine's instruction set, that may be the
fastest or shortest way to evaluate the boolean expression. Many
machines provide "jump if <condition>" instructions, but not "set
0/1 based on <condition>" instructions.

 

[Joe Wright]

Hello,
Thanks for all your responses.

The example I had given is a typical (but not exact) one which I have
encountered during the development of the code.
I am working on development of video compression algorithm and have
encountered deep nested loops with embedded if ... else conditions,
typically like the one I have given in the example.

I have a stiff target to meet on fps (frame per second) front and hence
I am trying to remove such conditions where there may be pipeline
stalls. So optimization is inevitable.

I am still not clear why would the compiler generate a branch condition
if only a boolean expression is to be solved.

Because that's what computers do. Solving a boolean results in a
conditional branch (or jump or call, whatever).

C's if/else constructs are not expensive as a rule. Deeply nested loops,
poorly designed, can drag you to a stop. Algorithm failure.

As programmers we should concern ourselves with the algorithms which
solve our problems. It is a waste of our time, and rather arrogant of
most of us, to try to optimize lagnuage constructs like if, else, while,
etc. because the guys and girls who wrote the compiler know that stuff
better than we do. We design and code the algorithm. Leave code
optimization to the compiler.

 

[Skarmander]

Because, given the machine's instruction set, that may be the
fastest or shortest way to evaluate the boolean expression. Many
machines provide "jump if <condition>" instructions, but not "set
0/1 based on <condition>" instructions.

And even those that do might have to allocate a new register to store the
evaluated result in, which could be costlier overall.

S.

 

[Keith Thompson]

Thanks for all your responses.

To what? Please read <http://cfaj.freeshell.org/google/>.

[...]

I am still not clear why would the compiler generate a branch condition
if only a boolean expression is to be solved.

As in
c += (a > B);
as opposed to the equivalent
if (a > B)
c++;
}

If you're familiar with the assembly language of whatever CPU you
happen to be using, try writing your own code to implement the first
assignment. If the CPU provides an instruction that compares two
values and stores a 0 or 1 depending on the result, the compiler is
likely to use it. If not, a conditional branch may well be the best
way to accomplish it, even if it might cause a pipeline stall.

If the CPU has an instruction that could do the job efficiently and
it's not using it (when you specify the maximum level of
optimization), you might consider complaining to the compiler vendor.

It's really not a C language issue. As long as the generated code
gets the right answer, the C standard is happy.

Note that the results of equality and relational operators are
*usually* used as conditions rather than to produce an actual 0 or 1
value. Because of this, the authors of your compiler might reasonably
not have bothered spending much time on optimizing this kind of thing.

 

[Christian Bau]

Hello,
Thanks for all your responses.

The example I had given is a typical (but not exact) one which I have
encountered during the development of the code.
I am working on development of video compression algorithm and have
encountered deep nested loops with embedded if ... else conditions,
typically like the one I have given in the example.

I have a stiff target to meet on fps (frame per second) front and hence
I am trying to remove such conditions where there may be pipeline
stalls. So optimization is inevitable.

I am still not clear why would the compiler generate a branch condition
if only a boolean expression is to be solved.

Just curious: You do that just for entertainment or for the learning
experience, or is someone actually employing programmers who try to
learn about optimisation by posting on comp.lang.c to implement video
compression algorithms?

 

[Carl R. Davies]

c= 0 ;
for (i=0; i<999; i++)
{
if (a > B)
c++ ;
}

Could you remove the if from the loop:

loop( condition )
if( something )
stuff
else
other stuff
end loop


if( something )
loop (condition)
stuff
end loop
else
loop( condition )
stuff
end loop
endif

 

[Eric Sosman]

Because that's what computers do. Solving a boolean results in a
conditional branch (or jump or call, whatever).

C's if/else constructs are not expensive as a rule. Deeply nested loops,
poorly designed, can drag you to a stop. Algorithm failure.

As programmers we should concern ourselves with the algorithms which
solve our problems. It is a waste of our time, and rather arrogant of
most of us, to try to optimize lagnuage constructs like if, else, while,
etc. because the guys and girls who wrote the compiler know that stuff
better than we do. We design and code the algorithm. Leave code
optimization to the compiler.

Kunal did mention that he's subject to tight performance
requirements. If good algorithms have been chosen and the
unaided compiler still can't meet the performance specs, it
may well be time to micro-optimize.

Two important points, though: First, he MUST measure to
isolate the cause(s) of the failure to perform fast enough.
If the loop takes one percent of the total time and he gets
it to run ten thousand times faster than it does now, he'll
have made less than a one percent improvement in the program
as a whole. Second, the gains from micro-optimization are
usually rather modest: You can seldom expect to get dramatic
speedups from the kind of transformation Kunal is considering.
If Kunal's program is just a whisker too slow, fiddling with
the `if' has a chance of boosting the speed just enough --
but if the program is now running at only half the required
speed, this sort of thing is surpassingly unlikely to help.

Sure, counter-examples to the second point exist -- but the
big gains usually stem from things like arranging the data in
ways that are friendly to the machine's caches, issuing pre-
fetches for data that'll be needed several instructions further
along, and a lot of other such implementation-specific techniques
that really have no "image" in the C language as such. If such
shenanigans are needed, Kunal needs to consult people who are
experts on his system.

 

[Richard Tobin]

I am still not clear why would the compiler generate a branch condition
if only a boolean expression is to be solved.

As you know, "A > B" means "1 if A > B and 0 otherwise". It may well
be that to get the right one of those values - 1 or 0 - the quickest
way is to test and branch.

Of course, it may not be. Depending on the instruction set, there may
be a direct way to get 1 or 0 in a register according to the result of
the comparison. But if you can see a simple transformation of your
code that allows this, then very likely the compiler can too.

The only way is to try it and see, and remember that it won't
necessarily be better on other processors.

-- Richard

 

[Ed Prochak]

Thanks for all your responses.

To what? Please read <http://cfaj.freeshell.org/google/>.

[...]

I am still not clear why would the compiler generate a branch condition
if only a boolean expression is to be solved.

As in
c += (a > B);
as opposed to the equivalent
if (a > B)
c++;
}

If you're familiar with the assembly language of whatever CPU you
happen to be using, try writing your own code to implement the first
assignment. If the CPU provides an instruction that compares two
values and stores a 0 or 1 depending on the result, the compiler is
likely to use it. If not, a conditional branch may well be the best
way to accomplish it, even if it might cause a pipeline stall.

If the CPU has an instruction that could do the job efficiently and
it's not using it (when you specify the maximum level of
optimization), you might consider complaining to the compiler vendor.

It's really not a C language issue. As long as the generated code
gets the right answer, the C standard is happy.

Actually, does the C standard now require a true expression result to
be 1?
(sorry, but I still think of C in terms of the original K&R, where 0 is
false and anything else is true. And I've done enough assembler
programming to know the compare doesn't simply result in a 1 in a
usable register.)

Ed