Are If Thens faster then multiplication and assignment?

Question

I have a quick question, suppose I have the following code and it's repeated in a simliar way 10 times for example.

if blah then
    number = number + 2^n
end if

Would it be faster to evaluate:

number = number + blah*2^n?

Which also brings the question, can you multiply a boolean value times a integer (Although I am not sure the type that is returned from 2^n, is it an integer or unsigned..etc)? (i'm working in Ada, but let's try to generalize this maybe?)

EDIT: Sorry I should clarify I am looking at 2 to the power of n, and I put c in there cause I was interested for my own learning in the future if I ever run into this problem in c and I think there are more c programmers out there on these boards then Ada (I'm assuming and you know what that means), however my current problem is in the Ada language, but the question should be fairly language independent (I hope).

Answer 1

If your language allows multiplication between a boolean and a number, then yes, that is faster than a conditional. Conditionals require branching, which can invalidate the CPU's pipeline. Also if the branch is big enough, it can even cause a cache miss in the instructions, though that's unlikely in your small example.

Answer 2

There is no general answer to such a question, this depends a lot on your compiler and CPU. Modern CPU have conditional move instructions, so everything is possible.

The only ways to know here are to inspect the assembler that is produced (usually -S as compiler option) and to measure.

Answer 3

I would keep it with the conditional. You shouldn't worry about low-level optimisation details at this point. Write the code that describes your algorithm best and trust your compiler. On some CPUs the multiplication is slower (e.g. ARM processors that have conditionals on each instruction). You could also use the ?: expression which optimises better under some compilers. For example:

number += (blah ? 2^n : 0);

If for some reason this little calculation is the bottleneck of your application after profiling then worry about low-level optimisation.

Answer 4

In C, regarding blah*2^n: Do you have any reason to believe that blah takes the values 0 and 1? The language only promises that 0 <-> FALSE and (everything else) <-> TRUE. C allows you to multiply a "boolean" temporary with another number, but the result is not defined except insofar as result=0 <=> the bool was false or the number was zero.

In Ada, regarding blah*2^n: The language does not define a multiplication operator on type Boolean. Thus blah cannot be a bool and be multiplied.

Answer 5

In either case, you can't avoid a branch (internally), so don't try!

In

number = number + blah*2^n

the full expression will always have to be evaluated, unless the compiler is smart enough to stop when blah is 0. If it is, you'll get a branch if blah is 0. If it's not, you always get an expensive multiply. In case blah is false, you'll also get the unnecessary add and assignment.

In the "if then" statement, the statement will only do the add and assignment when blah is true.

In short, the answer to your question in this case is "yes".

Answer 6

In Ada...

The original formulation:

if Blah then
  Number := Number + (2 ** N);
end if;

The alternative general formulation, assuming Blah is of type Boolean and Number and N are of suitable types:

Number := Number + (Boolean'pos(Blah) * (2 ** N));

(For N and Number of user-defined integer or floating point types, suitable definitions and type conversions may be required, the key point here is the Boolean'pos() construct, which Ada guarantees will give you a 0 or 1 for the predefined Boolean type.)

As for whether this is faster or not, I concur with @Cthutu:

I would keep it with the conditional. You shouldn't worry about low-level optimisation details at this point. Write the code that describes your algorithm best and trust your compiler.

Answer 7

Generaly, and particularly when working with Ada, you should not worry about micro-optimization issues like this. Write your code so that it is clear to a reader, and only worry about performance when you have a problem with performance, and have it tracked down to that portion of the code.

Different CPUs have different needs, and they can be insanely complex. For example, in this case which is faster depends a lot on your CPU's pipeline setup, what's in cache at the time, and how its branch prediction unit works. Part of your compiler's job is to be an expert in those things, and it will do a better job than all but the very best assembly programmers. Certianly better than you (or me).

So you just worry about writing good code, and let the compiler worry about making efficient machine code out of it.