optimize if (where first two if-branches have some statements in common)

[jononanon]

Hi there,

how would you optimize this:


if (a) {
x = v + size;
} else if (b) {
v = buf;
x = v + size;
} else {
fun();
}

Note the common line
x = v + size;
in the first two if-branches.



How do you like this, using comma-operator:

if (a || b && (v=buf, 1)) {
x = v + size;
} else {
fun();
}


Thanks for your comments.

 

[jononanon]

Hi there,



how would you optimize this:





if (a) {

x = v + size;

} else if (b) {

v = buf;

x = v + size;

} else {

fun();

}



Note the common line

x = v + size;

in the first two if-branches.







How do you like this, using comma-operator:



if (a || b && (v=buf, 1)) {

x = v + size;

} else {

fun();

}





Thanks for your comments.

Or in a similar way ... how do you like this:

if (a || (b ? (v=buf, 1) : 0)) {
x = v + size;
} else {
fun();
}



A goto would also do the trick, right?

if (a) {
goto label_here;
} else if (b) {
v = buf;
label_here:
x = v + size;
} else {
fun();
}

 

[Siri Cruz]

Hi there,

how would you optimize this:


if (a) {
x = v + size;
} else if (b) {
v = buf;
x = v + size;
} else {
fun();
}

I would use cc -O3.

There might be predicates p and q that would more clearly express their relation
to the statements so

if (p) v = buf;
if (q) x = v+size; else func();

is the most easily understood presentation, but it really should be about what
makes the most sense in six months when you have to fix some bug in your now
forgotten code.

 

[Fuseblower]

if (a || (b ? (v=buf, 1) : 0)) {
x = v + size;
} else {
fun();
}

if (a) {
goto label_here;
} else if (b) {
v = buf;
label_here:
x = v + size;
} else {
fun();
}

These aren't optimizations. These are obfuscations!

Anyway, I would use a LUT and do the whole thing in Assembly (portable
Assembly, of course

 

[Eric Sosman]

Hi there,

how would you optimize this:


if (a) {
x = v + size;
} else if (b) {
v = buf;
x = v + size;
} else {
fun();
}

Note the common line
x = v + size;
in the first two if-branches.

I'd concentrate on correctness and readability, and let
the compiler attend to the optimizing. Compilers are pretty
good at recognizing and rearranging shared code stretches.

If the "common line" were a larger bunch of code I might
think about rearranging things, not to optimize but to make
more readable (less material for the reader to digest) and
more maintainable (fixes and changes need be applied only once
and not twice; a single stretch of code can't get out of sync
with itself). One likely rearrangement might be:

if (b) {
v = buf;
}
if (a || b) {
// the "common line" section of code
} else
fun();
}

This supposes that the expressions `a' and `b' are not themselves
expensive to evaluate, and don't have side-effects that must occur
exactly as in the original. If they're expensive but the side-
effects don't matter I might cache the result of `b':

_Bool bresult = b; // only one expensive evaluation
if (bresult) {
v = buf;
}
if (bresult || a) { // avoid expensive `a' if unneeded
// the "common line" section of code
} else {
fun();
}

Finally, if `a' and/or `b' have side-effects whose occurrence and
ordering are important, I might well write

if (a) {
commonCode();
} else if (b) {
v = buf;
commonCode();
} else {
fun();
}

.... so the "common line" is easily readable and there's still only
one version of its innards floating around.

How do you like this, using comma-operator:

if (a || b && (v=buf, 1)) {
x = v + size;
} else {
fun();
}

Not very much: It's too clever by half, and cleverness is not
usually a good thing in computer programs. Also, it requires that
the "special line" after `b' be an expression, and won't work if
it's a statement instead.

(Aside: When you mix || and && in the same expression, it's
a *very* good idea to be generous with parentheses. Even if you
know what the parse tree looks like, the next person to work on
the code might not know you knew, and might wonder whether you
really meant what you actually wrote. Use the extra parens to
allay his doubts.)

 

[James Kuyper]

Hi there,

how would you optimize this:


if (a) {
x = v + size;
} else if (b) {
v = buf;
x = v + size;
} else {
fun();
}

Note the common line
x = v + size;
in the first two if-branches.

I wouldn't ordinarily bother with rearranging it unless "x = v + size;"
was replaced with a much more complicated block of code. But the
re-write I'd go for would be:

if(!a && b)
v = buf;

if(a || b)
x = v + size;
else
fun();

How do you like this, using comma-operator:

if (a || b && (v=buf, 1)) {
x = v + size;
} else {
fun();
}

Not very much at all. It's "cleverness" is achieved at the expense of
clarity.

 

[James Kuyper]

I'd concentrate on correctness and readability, and let
the compiler attend to the optimizing. Compilers are pretty
good at recognizing and rearranging shared code stretches.

If the "common line" were a larger bunch of code I might
think about rearranging things, not to optimize but to make
more readable (less material for the reader to digest) and
more maintainable (fixes and changes need be applied only once
and not twice; a single stretch of code can't get out of sync
with itself). One likely rearrangement might be:

if (b) {

This block gets executed even if a!=0, which differs from the original code.

 

[Keith Thompson]

how would you optimize this:

if (a) {
x = v + size;
} else if (b) {
v = buf;
x = v + size;
} else {
fun();
}

Note the common line
x = v + size;
in the first two if-branches.

How do you like this, using comma-operator:

if (a || b && (v=buf, 1)) {
x = v + size;
} else {
fun();
}

Sometimes a little bit of duplicated code is better than the gyrations
you'd have to go through to eliminate it. On the other hand, even one
duplicated line opens the risk that you'll eventually modify one and
forget to modify the other.

I presume your conditions aren't really "a" and "b". If you can come up
with meaningful names for them, you might consider something like this:

const bool cond0 = a;
const bool cond1 = !a && b;
const bool cond2 = !a && !b;

if (cond0) {
v = buf;
}
if (cond0 || cond1) {
x = v + size;
}
if (cond2) {
fun();
}

This avoids the repetition by refactoring the conditions rather than the
code controlled by them. I don't think I'm entirely happy with this
approach, but I offer it as an alternative.

Or you could do:

if (a) {
if (b) {
v = buf;
}
x = v + size;
}
if (!a && !b) {
fun();
}

Which if these (including the original) is clearer is going to depend on
how meaningful the conditions are going to be to future readers of the
code.

 

[Barry Schwarz]

Hi there,

how would you optimize this:


if (a) {
x = v + size;
} else if (b) {
v = buf;
x = v + size;
} else {
fun();
}

Note the common line
x = v + size;
in the first two if-branches.



How do you like this, using comma-operator:

if (a || b && (v=buf, 1)) {
x = v + size;
} else {
fun();
}

Do you think the comma helps? If buf is not NULL, then the comma and
subsequent expression serve no purpose since v = buf is equivalent to
true. If buf is NULL, then the expression v + size is probably not
going to do you very much good when you evaluate x. On those systems
where NULL is actually represented as 0, the resulting address is
probably somewhere in the kernel of the operating system.

 

[Andrew Smallshaw]

Hi there,

how would you optimize this:


if (a) {
x = v + size;
} else if (b) {
v = buf;
x = v + size;
} else {
fun();
}

How do you like this, using comma-operator:

if (a || b && (v=buf, 1)) {
x = v + size;
} else {
fun();
}

As others have noted, I'd leave it in the original form unless the
two statements x = v + size and v = buf are replaced by something
a lot larger in terms of code put down - i.e. they could call some
vastly complex function and I'd still leave it as is. All of your
optimisations take two conditional branches (the two ifs) and
replace them with three (an if, and shortcut logical operators).
That increases the chances of a branch prediction miss and those
are becoming ever more costly as pipelines get longer and longer.

 

[Fuseblower]

Hi there,

how would you optimize this:


if (a) {
x = v + size;
} else if (b) {
v = buf;
x = v + size;
} else {
fun();
}

Okay then, I'll bite (because everybody else takes it so seriously)

c = a | b;
v = v - v * b + buf * b;
x = x + c * (v + size);
if (!c)
fun();

There you are! Of course, I made some gross assumptions about the
types of the variables and their values (like a and b being either 0
or 1).

The whole objective was, of course, to eliminate as many if's as
possible (a false branch prediction is costly with nowadays long
pipelines).

Hmmm.... perhaps I should have done something with the shift
operators. Shifting is faster than multiplication but I bet the
mythical C optimizer will recognize the idiom and optimize it for me

 

[Stephen Sprunk]

how would you optimize this:
...

gcc -O3

Note the common line
x = v + size;
in the first two if-branches.

If a common subexpression happens to useful to the compiler's
optimization routines, that's not my concern.

How do you like this, using comma-operator:
...

If it's equal in meaning, then it will probably result in identical
output, which means you have wasted time and made your code more
difficult to read for no benefit. However, many such "optimizations"
also introduce subtle bugs, which means you might have broken the code
as well. However, since it's now so difficult to read, you'll probably
never notice, nor will the poor soul who's forced to maintain your code
years in the future. Is that really "optimal"?

Summary: Focus on making your code clear and correct; let the compiler
worry about making it fast.

S

 

[Fuseblower]

x = x + c * (v + size);

Oh darn! This should have been

x = x - x * c + c * (v + size);

And that's why you shouldn't optimize like that! XD

 

[Rosario1903]

if (a) {
goto label_here;
} else if (b) {
v = buf;
label_here:
x = v + size;
} else {
fun();
}

as you with one else and a couple of {} less...

if(a) goto there;
if(b){ v=buf;
there: x=v+size;
}
else fun();

 

[ais523]

how would you optimize this:

if (a) {
x = v + size;
} else if (b) {
v = buf;
x = v + size;
} else {
fun();
}

I asked a C compiler, because it's probably better at this sort of thing
than I am, asking for the fastest possible code, then translated its
output back into C:

if (a) goto l7;
if (!b) goto l4;
v = buf;
x = v + size;
l3:
/* rest of the function goes here, including the code for the "return"
at the end of it*/
l4:
fun();
goto l3;
l7:
x = v + size;
goto l3;

Why did it leave the "x = v + size" lines separate? Because it used a
different register to store v in the two codepaths. In the "if (b)"
codepath, the value of v was already in a register because it had just
assigned it from buf, so the assignment could be done in a faster way.
With small assignments like that, leaving the codepaths separate is
actually the fastest thing you can do.


Then I asked it for the shortest possible code, not the fastest, and got
this:

/* a is not in a register, so on x86 it needs to be compared against
a literal zero rather than just taking its boolean value */
if (a == 0) goto l2;
x = v + size;
goto l3;
l2:
if (!b) goto l4;
x = buf + size;
v = buf;
goto l3;
l4:
fun();
l3:

You might note that the "x = v + size" line /still/ hasn't been merged
in the two codepaths; in fact, it's actually different code in them,
now! Interestingly, it'd be possible to save bytes compared to the
compiler (x86 gcc 4.8.1 with -Os) via generating the assembler
corresponding to the following:

if (a != 0) goto l5;
if (!b) goto l4;
v = buf;
l5:
x = v + size;
goto l3;
l4:
fun();
l3:

which would be three bytes shorter, and AFAICT would work fine.

Just to make sure, I asked a different compiler (clang 3.2 with -Os),
asking for minimum size, and it produced this code:

if (a == 0) goto lbb0_2;
x = v + size;
goto lbb0_5;
lbb0_2:
if (!b) goto lbb0_4;
x = buf + size;
v = buf;
goto lbb0_5;
lbb0_4:
fun();
lbb0_5:

which is identical to the code produced by gcc, except with different
label names.

I'm not sure why compilers are doing it this way. If two compilers agree
on not merging the "x = v + size", then either neither optimizes merging
the start of an if block, or there's something I'm missing. (In case
anyone's wondering, "x = v + size" and "x = buf + size" both compile
into 3 bytes of machine code on my platform, with the registers the
compilers chose for the variables in question.)

Here's a comparison of the resulting machine code sizes for my test
program:

gcc's -O3: 21+28 = 49 bytes
gcc's -Os: 33 bytes
clang's -Os: 28 bytes
my optimization shown above, compiled via gcc -Os: 26 bytes
my optimization shown above, compiled via clang -Os: 30 bytes

The difference between clang's output and gcc's for the non-optimized
case was a little spurious; clang chose registers that were shorter for
the code in question but which required some extra bytes to use the
values of some of the variables afterwards, whereas gcc placed those
extra bytes inside the code in question.

What's most interesting, though, is what's happening with the code that
I optimized by hand; it gives the shortest output yet in gcc, but
actually makes it worse in clang! The worsening in clang is entirely
because it put a variable in the wrong register, costing four bytes of
moving variables around between registers. gcc's output also placed six
extra bytes inside the code in question that could have been outside (it
decided to store "size" in %eax rather than in memory, meaning that it
had to copy it to a temporary when it called fun(). In general, the
issues of trying to do register allocation well meant that the savings
from the shortened code came mostly from the fact that it saves one
"goto", rather than from the removal of the repeated assignment to x
(which is just three bytes on x86; it has a three-byte instruction that
does "a = b + c" on many combinations of registers).

For what it's worth, I think I can get it down to 23 bytes of assembler
by hand via massaging the compiler output, although I haven't verified
that this assembler version is correct, and I might have made a mistake
somewhere.

(For anyone wondering how I was counting bytes: I initialized all the
variables from stdin, and then wrote them all out to stdout, to prevent
any of them being optimized out, rather than using "volatile" or the
like in order to prevent optimizations, which would have defeated the
point of the exercise. Then I counted only the bit between the
initializations and the final writeout. gcc's -O3 output had the final
writeout in the middle, so I had to count both the code before and the
code after it.)

So, the upshot from this:

* Trying to optimize the code by hand is likely to have unexpected
effects on modern compilers. In general, writing it in the most
straightforward way increases the chance that it will be optimized
well.

* Trying to optimize for speed by hand is basically impossible nowadays;
the compiler has a better idea than you of what will run quickly.

* It's still possible to optimize for size by hand and beat the compiler,
if you know of an optimization that it doesn't know, or are just
better at allocating registers. (This last advantage only really
matters on x86; other systems tend to have less insane register
allocation requirements.)

* Trying to generate specific assembler from specific C code is very
difficult, or near impossible, to do in such a way that the original
C code is platform-agnostic. (I have done this before, but it basically
involves trying lots of different C as compiler input until it
generates the output that you want.)

And the answer to the original question is "I wouldn't". I think the
cleanest solution involves goto, and when the cleanest solution uses
goto, it's probably not the sort of problem you want to solve.

 

[Eric Sosman]

[...]
if (b) {

This block gets executed even if a!=0, which differs from the original code.

Oh, drat. Or, as Hook put it, "By carbonate of soda!"

It wasn't my intent to offer an object lesson in the benefits
of clarity over micro-optimization, but I guess I've done so ...

 

[Tim Rentsch]

Hi there,

how would you optimize this:


if (a) {
x = v + size;
} else if (b) {
v = buf;
x = v + size;
} else {
fun();
}

How do you like this, using comma-operator:

if (a || b && (v=buf, 1)) {
x = v + size;
} else {
fun();
}

[snip] All of your optimisations take two conditional branches
(the two ifs) and replace them with three (an if, and shortcut
logical operators). [snip]

This statement is, umm, let me say inaccurate, for two reasons.

One is that one of the re-writes used 'goto', and had only two
if() conditions and no shortcut operators.

The other is that if() conditions and shortcut operators are
not the same as conditional branches. The compiled code
might have one conditional branch for each if()/SCLO, or
more, or fewer, or conceivably none at all (eg, using an
indirect jump). No compiler worth its salt would translate
an expression like

b && (v=buf, 1)

into code with two conditional branches, even though it
might appear that two tests are being done.

 

[Tim Rentsch]

Do you think the comma helps? If buf is not NULL, then the comma
and subsequent expression serve no purpose since v = buf is
equivalent to true. If buf is NULL, then the expression v + size
is probably not going to do you very much good when you evaluate
x. On those systems where NULL is actually represented as 0, the
resulting address is probably somewhere in the kernel of the
operating system.

Neither v nor buf have declarations in evidence. For all we know
buf might be 0.0, with v and buf both being of type double.

In fact, even if buf is known to be of type Foo * for some Foo, I
would recommend against re-writing (v=buf, 1) to just (v=buf) in
that context. The semantics are different; also there's a good
chance the form without the ',1' would prevent the compiler from
optimizing away the branch. Not to mention that the shorter form
obscures the original meaning.

btw, if this is meant as satire, I will just add: A, good one!
and B, unless it's more obviously satirical there is a real
danger that novices will take the suggestions seriously (and
I hope no one thinks that's a good thing).

 

[Tim Rentsch]

Hi there,

how would you optimize this:


if (a) {
x = v + size;
} else if (b) {
v = buf;
x = v + size;
} else {
fun();
}

Note the common line
x = v + size;
in the first two if-branches.



How do you like this, using comma-operator:

if (a || b && (v=buf, 1)) {
x = v + size;
} else {
fun();
}

I don't.

More importantly though, you haven't said what it is you are
hoping to achieve or why. Are you trying to

A. Maximize program speed?
B. Minimize program space?
C. Some combination of A and B?
D. Factor out the common statement so it appears in only one
place?
E. Something else?

It would help to know which of these is the case, as well as why
you want to do so.

Without knowing answers to these questions I can't really make
any recommendation. However, perhaps it is worth pointing out
another way of writing this that AFAIK hasn't yet been mentioned:

switch( a ? 2 : b ? 1 : 0 ){
case 0: fun(); break;
case 1: v = buf;
case 2: x = v + size;
}

If it were important for some reason to factor out the common
statement, this might be a good way to write it - it's hard to
say without more specifics.

 

[glen herrmannsfeldt]

(snip, someone wrote)

[snip] All of your optimisations take two conditional branches
(the two ifs) and replace them with three (an if, and shortcut
logical operators). [snip]

This statement is, umm, let me say inaccurate, for two reasons.

One is that one of the re-writes used 'goto', and had only two
if() conditions and no shortcut operators.

The other is that if() conditions and shortcut operators are
not the same as conditional branches. The compiled code
might have one conditional branch for each if()/SCLO, or
more, or fewer, or conceivably none at all (eg, using an
indirect jump).

Or conditional load. Many systems now have a conditional load
instruction such that:

x=1;
if(condition) x=2;

can be implmented without any branch, and the complications
of branch prediction. I don't know how many compilers actually
generate them, though.

No compiler worth its salt would translate an expression like

b && (v=buf, 1)

into code with two conditional branches, even though it
might appear that two tests are being done.

-- glen