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

[Jordan Abel]

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.)

the "as if" rule will let you weasel out of it in most cases for a real
implementation, but if you assign the result of a relational/equality
comparison expression to an integer variable, it must be 1 for true, 0
for false.

 

[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.

Actually, does the C standard now require a true expression result to
be 1?

It depends on the expression.

The result of any operator that yields a boolean result is required to
be 0 for false, 1 for true; this applies to relational operators,
equality operators, unary "!", and probably others I haven't thought
of. The statement
c += (a > B);
is guaranteed to add either 0 or 1 to c; if it adds 2, the compiler is
broken (or you've invoked undefined behavior somewhere).

The is*() functions in <ctype.h> may return any non-zero value if the
corresponding condition is true. The statement
c += isdigit(x);
is unlikely to do what you want it to. If you specifically want to
add 0 or 1, you can do
c += !!isdigit(x);
or any of a number of other workarounds.

If an expression is used as a condition, it's treated as false if it
compares equal to 0, true otherwise.

(sorry, but I still think of C in terms of the original K&R, where 0 is
false and anything else is true.

That hasn't changed -- nor has the fact that *some* boolean
expressions are guaranteed to evaluate to either 0 or 1. (I *think*
K&R1 guaranteed this, but I don't have my copy here.)

And I've done enough assembler
programming to know the compare doesn't simply result in a 1 in a
usable register.)

That depends on the CPU. If a comparison doesn't result in a 0 or 1
in a usable register, the compiler will have to go to some extra
effort to generate the 0 or 1 value, unless it can legally optimize
out the result. For example, given

if (x == y) { ... } else { ... }

the expression "x == y" yields a value of 0 or 1, but the generated
code doesn't have to store this value anywhere as long as executes the
correct block of code.

 

[websnarf]

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) ;
}

For most compilers the two are exactly the same.

But a more importantly real savings come from doing more serious
optimizations like this:

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

which is equivalent to:

c += 999 * (a > B);

Of course if your compiler is good enough, it can figure all this out
as well.

Seriously though, if you want to remove branched from the inside of a
loop, hoisting is usually the best way, when it is available. If a
and/or B is really a macro that makes it a function of i, or itself, or
something like that, then it will depend on how they expand out.

Unfortunately the ANSI C standard is basically broken on the right
shift operator, but on most compilers, if you know a and B are signed
ints and positive you have certain functional tricks like:

(a > B)

is the same as:

- ((B - a) >> (sizeof (int) * CHAR_BIT - 1))

which does remove the branch pretty much for sure. But as I said, the
ANSI C standard doesn't allow you to assume that the two are same when
a and B are positive (they are on > 99.999% of compilers deployed.)

 

[Kunal]

like I said in my earlier post, the if conditions are embedded deep
inside multiple for loops. Hence such an opportunity has rarely
occurred .... and whenever it has, this technique has been used.

 

[Naren]

Elementary optimizations like this should be left to compiler only and
should not be done at the cost of code clarity and readability.
Moreover original code seems to be more optimized than the modified
code if compiler optimization is kept aside. Original code increments
only if condition is satisfied while modified code does both operations
(checking condition and doing addition) and always. One more
optimization can be done by doing a pre-increment both inside for loop
as well as inside the block if post increment is not really required.

thanks
--naren