Sign in to follow this  
AshleysBrain

How smart is the compiler?

Recommended Posts

I'm using Visual Studio 2005 and I was writing a while loop like this (C++):
const bool x = GetSomeBool();

while (running) {
	if (x) FuncA();
	FuncB();
}

Since 'x' is const and it can know the result of the if every time, will the compiler perform the following optimisation?:
if (x) while(running) { FuncA(); FuncB(); }
else while(running) { FuncB(); }

Is it smart enough to do that? The performance of this while is important, and I actually have 4 or 5 ifs. Writing out every combination is lengthy in the source code, but would the compiler do this for me?

Share this post


Link to post
Share on other sites
I don't think it's allowed to. What if, say, FuncA() modified x?
In practice, these things shouldn't happen an the compiler is smart enough to find out such things through simple static analysis AND act on it. It's just that a sadistic program could break this kind of behaviour.

Share this post


Link to post
Share on other sites
If x is a const bool, then possibly. Or if x is a #define.

However, what's wrong with hand coding it yourself the way you want?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
the answer to this certainly varies with the compilers you are using:so, why don't you simply write a small testcase and check your compiler's output for the testcase?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
To really be sure of what the optimized is doing for you you should instruct the compiler to generate an assembly output using the /Fa command-line switch. Make sure, however, to do that in release mode.

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
I don't think it's allowed to. What if, say, FuncA() modified x?
In practice, these things shouldn't happen an the compiler is smart enough to find out such things through simple static analysis AND act on it. It's just that a sadistic program could break this kind of behaviour.


But if x is a const bool, then any program that modifies it is malformed. The only question should be whether or not the compiler knows that x is const.

Pointer to const would be a problem, though... :/

Quote:
Origianl post by daerid
If x is a const bool, then possibly. Or if x is a #define.


Actually, in this case, a #define would not allow this optimization since it's a function call which, so far as we can tell, might not always return the same value.

Share this post


Link to post
Share on other sites
Quote:
Original post by Way Walker
But if x is a const bool, then any program that modifies it is malformed.


Oops, I overlooked the const. The compiler can make this optimization safely.

Share this post


Link to post
Share on other sites
You may just want to know out of curiousity, but if you are wondering this out of serious concern for your program's speed, I wouldn't worry about it. Write the code how you think is best (which can incorporate some friendliness with the compiler, but nothing too particular). Even if it doesn't perform this optimization, the cost of a couple thousand compares is nothing to what you could probably save elsewhere.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by ToohrVyk
Quote:
Original post by Way Walker
But if x is a const bool, then any program that modifies it is malformed.


Oops, I overlooked the const. The compiler can make this optimization safely.


OMFG!!!! Everyone look! He made a mistake! He is human!!!

Hehe, I joke. You know we love you.... :P

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
Quote:
Original post by Way Walker
But if x is a const bool, then any program that modifies it is malformed.


Oops, I overlooked the const. The compiler can make this optimization safely.
bool* ptr = (bool*) &x; *ptr = <value>;
This is C(++), after all -- we can do whatever the hell we want.

If the compiler doesn't correctly perform the optimization, you could try copying the value of the flag to a local variable, which will demonstrate to the compiler that no non-local modifications can be made. I'd only do that after reading the assembly listing and seeing that the compiler wasn't doing the optimization, though.

On the other hand, if you assume a desktop processor, you've got a branch predictor to save your ass here. Even if the compiler doesn't optimize, that compare will be free every single time after the first run through the loop.

Share this post


Link to post
Share on other sites
If you always know the value of x before the while loop starts, and it's never modified during the loop, why don't you do the optimisation yourself? In fact, I don't understand why your code is doing such a thing as a test on a const bool.

Share this post


Link to post
Share on other sites
Quote:
Original post by Way Walker
Quote:
Origianl post by daerid
If x is a const bool, then possibly. Or if x is a #define.


Actually, in this case, a #define would not allow this optimization since it's a function call which, so far as we can tell, might not always return the same value.

Stop whatever you're doing right now, and go look up the word "pre-processor".

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by daerid
Quote:
Original post by Way Walker
Quote:
Origianl post by daerid
If x is a const bool, then possibly. Or if x is a #define.


Actually, in this case, a #define would not allow this optimization since it's a function call which, so far as we can tell, might not always return the same value.

Stop whatever you're doing right now, and go look up the word "pre-processor".


Thats what he's saying - a define cannot be assigned to a function call.

Share this post


Link to post
Share on other sites
Quote:
Original post by King of Men
If you always know the value of x before the while loop starts, and it's never modified during the loop, why don't you do the optimisation yourself?


OP: I have a professor and several computer hardware engineering friends who would repeat this sentiment. Usually loudly, at the top of their lungs. They seem to be a bit touchy about keeping such if comparisons out of loops.

As far as the compiler, I'm not sure if VS 2005 knows to optimize it out. But if you're aware that such a thing should be optimized (which you obviously are), why wouldn't you just do it yourself?

Share this post


Link to post
Share on other sites
Considering you can use the values of such const bool variables as template arguments, I'd say it's safe to say that any modern compiler will optimize the loop away.


#include <iostream>

namespace
{
bool const x = false;

template<bool T>
void p()
{
std::cout << "true\n";
}

template<>
void p<false>()
{
std::cout << "false\n";
}
}

int main()
{
p<x>();
}

Share this post


Link to post
Share on other sites
Quote:
Original post by Promit
bool* ptr = (bool*) &x; *ptr = <value>;
This is C(++), after all -- we can do whatever the hell we want.


To the best of my knowledge, in C++, 4.4 [conv.qual] disagrees with this pointer conversion because it removes cv-qualifiers. A const_cast might have been possible, but it is only guaranteed to work if the referenced rvalue is defined as non-const (which is not the case here).

Share this post


Link to post
Share on other sites
It looks like the compiler isn't as smart as you'd like it to be. At least mine isn't:

I compiled the following code under MSVC++ 2003 with full optimisations on:

void ConstCall() {
OutputDebugStringA("ConstCall\n");
const bool x = GetSomeBool();
while (running) {
if (x) FuncA();
FuncB();
}
}

void NotConstCall() {
OutputDebugStringA("NotConstCall\n");
bool x = GetSomeBool();
while (running) {
if (x) FuncA();
FuncB();
}
}

The debug strings are just there to aid my disassembler. The compiler was hell-bent on inlining everything in sight, so some bullying was necessary (__declspec(noinline)), but I don't see how that would affect the test. The two functions came out identical.

Here's the assembly (edited for readability), for anyone who cares:

00401080 push    ebx

00401081 push ("ConstCall")
00401086 call (OutputDebugStringA)

0040108C call (GetSomeBool)
00401091 mov bl, al
00401093 mov al, (running)
00401098 test al, al
0040109A jz short 4010B7
0040109C lea esp, [esp+0]

004010A0 test bl, bl
004010A2 jz short 4010A9
004010A4 call (FuncA)

004010A9 call (FuncB)
004010AE mov al, (running)
004010B3 test al, al
004010B5 jnz short 4010A0

004010B7 pop ebx
004010B8 retn


Regards
Admiral

Share this post


Link to post
Share on other sites
The reason I asked the question is my actual case is that the while is a little more complex with 4 or 5 ifs and longer code segments. Coding out every of the 16 or so combinations would take up a lot of code, and being a programmer, I don't like the feel of copy-paste programming nor the verbosity of it; I appreciate the conciseness and logical layout of a while loop written like so. The question is, with speed favoured over size, would the compiler perform this expansion for me?

I don't really know Assembly, I'm not sure I could tell if the optimisation was done from assembly listings. Also this is specific to VS2005.

edit: post timing conflict, thanks for investigating theAdmiral - I'll save the expansion for the end of my project.

Share this post


Link to post
Share on other sites
I certainly appreciate your point about long code. Perhaps, though, you could do it with some function pointers? Say you have three bits of code in your while loop, each of which depends on some logic; move each of those snippets to a function, then do the logic outside your while loop and assign the results to function pointers which get called inside your loop.

Share this post


Link to post
Share on other sites
Quote:

It looks like the compiler isn't as smart as you'd like it to be. At least mine isn't:


Not surprising.

The presumed optimization cannot be made if the code AshleysBrain supplied is taken literally, as you have done; the value of x is not neccessarily known at compile-time. If "GetSomeBool()" is replaced with something that is actually known at compile-time, then I would imagine the compiler would make the optimization.

Share this post


Link to post
Share on other sites
Again, the compiler is compiling for a processor that has branch prediction. It knows perfectly well that the comparison will be free, so there is no need to make the "optimization".

Share this post


Link to post
Share on other sites
Quote:
Original post by jpetrie
Quote:

It looks like the compiler isn't as smart as you'd like it to be. At least mine isn't:


Not surprising.

The presumed optimization cannot be made if the code AshleysBrain supplied is taken literally, as you have done; the value of x is not neccessarily known at compile-time. If "GetSomeBool()" is replaced with something that is actually known at compile-time, then I would imagine the compiler would make the optimization.


Compiling it out is not possible, but hoisting the comparison out of the loop and splitting it is (i.e. do the comparison first, and then choose between two versions of the loop using the result).

However, like Promit said, this is a step backwards on modern processors with good branch prediction: the comparison is essentially free in the "normal" version, and therefore the only thing the "optimized" version can accomplish is to bloat the working set, possibly spilling out of the instruction cache and making performance *worse*.

Share this post


Link to post
Share on other sites
This function is actually a member function of an object that is instanced many times, most of them having differing member data, with GetSomeBool() returning different values between the objects. This member function is then called on all instances of the object.

Assume for example that for each instance GetSomeBool() returns randomly either 0 or 1, and assume there is only one instance of the function assembly. Won't the processor mispredict the branches? Isn't it therefore in this case more efficient to do the original proposed optimisation?

Of course this is a matter for the compiler - I will be moving the ifs outside the while at the end of my project, and I'll profile it to check up the results.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this