Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   Optimization of if (http://www.velocityreviews.com/forums/t446110-optimization-of-if.html)

 Rajen 02-01-2007 01:45 PM

Optimization of if

Hi all,
I have a code like this.
if(X)
{
return retVal1;
}

if(Y)
{
return retVal2;
}

if(Z)
{
return retVal3;
}

The above if can be written like this
int retVal = 0;
if(X)
{
retVal=retVal1;
}

if( retVal == 0)
{
if( Y)
retVal=retVal2;
}

if( retVal == 0 )
{
if(Z)
retVal=retVal3;
}

return retVal;
which has only one exit point. But it has more If's

How do i Optimize this? Please give me some suggestions.

 Chris Dollin 02-01-2007 01:53 PM

Re: Optimization of if

Rajen wrote:

> Hi all,
> I have a code like this.
> if(X)
> {
> return retVal1;
> }
>
> if(Y)
> {
> return retVal2;
> }
>
> if(Z)
> {
> return retVal3;
> }
>
>
> The above if can be written like this
> int retVal = 0;
> if(X)
> {
> retVal=retVal1;
> }
>
> if( retVal == 0)
> {
> if( Y)
> retVal=retVal2;
> }
>
> if( retVal == 0 )
> {
> if(Z)
> retVal=retVal3;
> }
>
> return retVal;
> which has only one exit point. But it has more If's
>
> How do i Optimize this? Please give me some suggestions.

Optimise? What's to optimise? I didn't see anything non-optimal
with the first one. (There's a missing case for when none of
X, Y, and Z are true.) The second form seems to assume that
neither `retVal1` nor `retVal2` are 0. Maybe that's true but
it seems to be asking for trouble to rely on it. And that second
form is clumsier and harder to understand.

Myself I prefer the form:

return
X ? retVal1
: Y ? retVal2
: Z ? retVal3
: whateverYouWantForNoneOfXYZ
;

laid out in whatever way fits your coding style.

Optimisation? This is really the bottleneck in your code? Colour
me gobsmacked.

--
Chris "green/purple hedgehog" Dollin
"We live for the One, you die for the One." Unsaid /Babylon 5/.

 Richard Tobin 02-01-2007 02:14 PM

Re: Optimization of if

Rajen <rajenpn@gmail.com> wrote:

> I have a code like this.
> if(X)
> {
> return retVal1;
> }
>
> if(Y)
> {
> return retVal2;
> }
>
> if(Z)
> {
> return retVal3;
> }
>
>
>The above if can be written like this
> int retVal = 0;
> if(X)
> {
> retVal=retVal1;
> }
>
> if( retVal == 0)
> {
> if( Y)
> retVal=retVal2;
> }
>
> if( retVal == 0 )
> {
> if(Z)
> retVal=retVal3;
> }
>
> return retVal;
>which has only one exit point. But it has more If's

Your first form is much clearer, so use that. If your employer insists on
less clear code to satisfy some rules, find another employer.

-- Richard
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.

 Laurent Deniau 02-01-2007 02:16 PM

Re: Optimization of if

Rajen wrote:
> Hi all,
> I have a code like this.
> if(X)
> {
> return retVal1;
> }
>
> if(Y)
> {
> return retVal2;
> }
>
> if(Z)
> {
> return retVal3;
> }
>

> which has only one exit point. But it has more If's
>
> How do i Optimize this? Please give me some suggestions.

Nothing says the first case generate more than one exit point of your
function. BTW some compilers will effectively generate only one exit
point and jump to it from each return point, so it far from obvious that
first case will not be optimal. Clarity is much more important than
implementation dependant low-level assumption.

a+, ld.

 Eric Sosman 02-01-2007 02:18 PM

Re: Optimization of if

Rajen wrote:
> Hi all,
> I have a code like this.
> if(X)
> {
> return retVal1;
> }
>
> if(Y)
> {
> return retVal2;
> }
>
> if(Z)
> {
> return retVal3;
> }
>
>
> The above if can be written like this
> int retVal = 0;
> if(X)
> {
> retVal=retVal1;
> }
>
> if( retVal == 0)
> {
> if( Y)
> retVal=retVal2;
> }
>
> if( retVal == 0 )
> {
> if(Z)
> retVal=retVal3;
> }
>
> return retVal;
> which has only one exit point. But it has more If's
>
> How do i Optimize this? Please give me some suggestions.

First, it's extremely unlikely that any optimization
is needed.

Second, learn about the `else' keyword.

--
Eric Sosman
esosman@acm-dot-org.invalid

 Chris Dollin 02-01-2007 02:23 PM

Re: Optimization of if

Laurent Deniau wrote:

> Rajen wrote:
>> Hi all,
>> I have a code like this.
>> if(X)
>> {
>> return retVal1;
>> }
>>
>> if(Y)
>> {
>> return retVal2;
>> }
>>
>> if(Z)
>> {
>> return retVal3;
>> }
>>

>
>> which has only one exit point. But it has more If's
>>
>> How do i Optimize this? Please give me some suggestions.

>
> Nothing says the first case generate more than one exit point of your
> function.

There are three exit points show: each return is an exit point.
(It doesn't matter how the compiler compiles it [1]; I suspect
the OP is afflicted by Code Style Rules that values Conformance
over Clarity.)

[1] EG the compiler [2] might translate `return 0;`, `return 1;`
and `return -1;` to jumps into the implementation library
code to load the constant and then return. One might then
say there were /no/ exit points in a function with those
return values ...

[2] OK, it was an RTL/2 compiler, not a C compiler, optimising
for space.

--
Chris "electric hedgehog" Dollin
There' no hortage of vowel on Uenet.

 Richard Bos 02-01-2007 04:16 PM

Re: Optimization of if

"Rajen" <rajenpn@gmail.com> wrote:

> if(X)
> {
> return retVal1;
> }
>
> if(Y)
> {
> return retVal2;
> }
>
> if(Z)
> {
> return retVal3;
> }
>
> The above if can be written like this
> int retVal = 0;
> if(X)
> {
> retVal=retVal1;
> }
>
> if( retVal == 0)
> {
> if( Y)
> retVal=retVal2;
> }
>
> if( retVal == 0 )
> {
> if(Z)
> retVal=retVal3;
> }
>
> return retVal;
> which has only one exit point. But it has more If's
>
> How do i Optimize this? Please give me some suggestions.

As others have noted, you're missing a default value.

Try this:

retval=default_value;
if (Z) retval=retval3;
if (Y) retval=retval2;
if (X) retval=retval1;
return retval;

out a bit more legibly:

if(X) return retVal1;
if(Y) return retVal2;
if(Z) return retVal3;

or if you like braces:

if(X) { return retVal1; }
if(Y) { return retVal2; }
if(Z) { return retVal3; }

Richard

 David T. Ashley 02-01-2007 04:41 PM

Re: Optimization of if

"Rajen" <rajenpn@gmail.com> wrote in message
> Hi all,
> I have a code like this.
> if(X)
> {
> return retVal1;
> }
>
> if(Y)
> {
> return retVal2;
> }
>
> if(Z)
> {
> return retVal3;
> }
>
>
> The above if can be written like this
> int retVal = 0;
> if(X)
> {
> retVal=retVal1;
> }
>
> if( retVal == 0)
> {
> if( Y)
> retVal=retVal2;
> }
>
> if( retVal == 0 )
> {
> if(Z)
> retVal=retVal3;
> }
>
> return retVal;
> which has only one exit point. But it has more If's

You have three options for optimization.

a)First, note in your second example that this is a control flow problem.
Your problem is keeping the value of retVal from being multiply assigned.
It is more economical to do this with an else-if statement, i.e.

if (X)
retVal = retVal1;
else if (Y)
retVal = retVal2;
else
retVal = retVal3;

This suppresses the extra "0" tests and does what you want. Also, if your
possibilities are mutually exclusive and/or exhaustive, you can suppress the
final Z test.

b)Else-if has the limit that in order to get to clause N, all of the
preceding N tests must have been evaluated. If your problem is amenable to
it, try using the switch() statement.

c)Finally, in special cases where switch() can't be used, there are
sometimes relationships that let one optimize. For example, assume that I
want a fast implementation of floor(log_10(x)) up through 10,000. I could
do it like this:

if (x < 100)
{
if (x < 10)
{
}
else
{
}
}
else
{
if (x < 1000)
{
}
else
{
}
}

When the domain is "paneled", you can often build an if() construct where
the time to reach the innermost clause is related to log(N) where N is the
number of cases.

Notice that the construct above gets there in 2 tests (rather than up to
4).
--
David T. Ashley (dta@e3ft.com)
http://gpl.e3ft.com (GPL Publications and Projects)

 Default User 02-01-2007 06:31 PM

Re: Optimization of if

Rajen wrote:

> Hi all,
> I have a code like this.
> if(X)
> {
> return retVal1;
> }
>
> if(Y)
> {
> return retVal2;
> }
>
> if(Z)
> {
> return retVal3;
> }

[snip]

> How do i Optimize this? Please give me some suggestions.

The more typical way to write this if you want to have only one return
statement is with an if-else if ladder.

int retVal = 0; /* or other default value */

if(X)
{
retVal = retVal1;
}
else if(Y)
{
retVal = retVal2;
}
else if(Z)
{
retVal = retVal3;
}

return retVal;

This method probably is about as efficient as the one with returns in
the if() statements, understanding that such things are up to the
implementation.

You could also skip the initialization of retVal and put a terminating
else that sets it to the "no hit" value, but I'd prefer the method
above. If the return value must be one of the three, then set retVal to
one of the values and use only two if()'s.

Brian

 Keith Thompson 02-01-2007 09:36 PM

Re: Optimization of if

rlb@hoekstra-uitgeverij.nl (Richard Bos) writes:
> "Rajen" <rajenpn@gmail.com> wrote:
> > if(X)
> > {
> > return retVal1;
> > }
> >
> > if(Y)
> > {
> > return retVal2;
> > }
> >
> > if(Z)
> > {
> > return retVal3;
> > }

[...]
> As others have noted, you're missing a default value.
>
> Try this:
>
> retval=default_value;
> if (Z) retval=retval3;
> if (Y) retval=retval2;
> if (X) retval=retval1;
> return retval;

That's likely to be (slightly) *less* efficient, since it can assign
to retval multiple times. It can also behave differently if X, Y, and
Z are expressions that depend on each other's evaluation; for example,
evaluating Y might not work if X hasn't already been evaluated.

> Then immediately return to the first, maintainable version, but lay it
> out a bit more legibly:
>
> if(X) return retVal1;
> if(Y) return retVal2;
> if(Z) return retVal3;
>
> or if you like braces:
>
> if(X) { return retVal1; }
> if(Y) { return retVal2; }
> if(Z) { return retVal3; }

I'd probably lay it out that way if the conditions and result
expressions really were that terse, except that I always put a blank
after an "if" (it's not a function call, so it shouldn't look like
one):

if (X) return retVal1;
if (Y) return retVal2;
if (Z) return retVal3;

But in real life, everything is likely to be longer, perhaps too long
to fit on a single line. And if the conditions really were "X", "Y",
and "Z", I'd seriously consider using names that make some actual
sense.

--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

All times are GMT. The time now is 07:34 AM.