Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

jollyjeffers

(C++) Early Rejection in boolean-expressions

This topic is 5650 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

hi, just wondering to what extent C++ compilers (or the ISO spec) optimizes boolean expressions. Best with examples:
if ( b0 && b1 && b2 && b3 && b4 )
   //do something

if ( b0 || b1 || b2 || b3 || b4 )
   //do something
 
in the first (&&) example, will the compiler set it up so that as soon as any of them is false (Left->right or right->left??) it stops evaluating any remaining? likewise, the 2nd (||) example, will it stop when one is found to be true. my reason for asking is thus: assuming b0...b4 were expressions rather than just variables, if I ordered them in terms of time complexity would it be a valid optimization?
if ( bSomeSimpleFunc() && bSomeHarderFunc() && bSomeSuperLongTask() )
 //do something
 
would the compiler order that above code so that (possibly) bSomeSuperLongTask() need not be processed at all if bSomeHarderFunc() evaluated as false? any ideas/thoughts? cheers, Jack DirectX 4 VB: All you need for multimedia programming in Visual Basic Formula 1 Championship Manager, My Game Project.

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
So far as I know, most compiler DO in fact stop as soon as the expression is proven.

Try it for yourself!

if (function1() && function2()) {
return(-1);
}

int function1() {
wrlog("called function1()";
return(0);
}

int function2() {
wrlog("called function2()";
return(0);
}

It''s the only way to know for sure, right?

Share this post


Link to post
Share on other sites
quote:
Original post by jollyjeffers
in the first (&&) example, will the compiler set it up so that as soon as any of them is false (Left->right or right->left??) it stops evaluating any remaining?

likewise, the 2nd (||) example, will it stop when one is found to be true.

Yes, and they're evaluated left->right. It's called short circuit somethingsomething-. And it's in the standard (since some things depend on it) so you can count on it.

E.g. You could safely do

  
if (foo && foo->member == 5) {

}

And if foo was 0, it wouldn't evaluate the second expression (which would cause problems)

[edited by - civguy on April 1, 2003 11:13:20 AM]

Share this post


Link to post
Share on other sites
Visual C++ processes them from left to right, as expected the way we read text. (anyone, please let me know if I am wrong).

It it definately appropriate to organize your functions from quickest to most comples in such a scenario.

HOWEVER, some compilers may indeed process the conditions right to left, or in fact process ALL of the conditionals when it''s already proven true or false after the first test..

Personally I would aviod the confusion by implementing:

if(simple()) {
if(moreMomplex()) {
if(complex()) {
//do something...
};
};
};

...just to be safe... A smart compiler will ANYWAYS ultimately organize them properly during optimization, so you have nothing to lose.

Do you see what I mean? Its better to play safe, because you will ANYWAYS succeed with a better compiler, as it will optimise it at the machine code level...


www.cppnow.com

Share this post


Link to post
Share on other sites
quote:
Original post by jollyjeffers
assuming b0...b4 were expressions rather than just variables, if I ordered them in terms of time complexity would it be a valid optimization?
Yes.
quote:
would the compiler order that above code so that (possibly) bSomeSuperLongTask() need not be processed at all if bSomeHarderFunc() evaluated as false?
Well in your example bSomeSuperLongTask is last so it won't be evaluated if bSomeHarderFunc if false. But if the order was different, compiler couldn't reorder the expressions as it could have nasty side effects. (well, I think it can reorder them if it can somehow check that there are no side effects in doing so)

[edited by - civguy on April 1, 2003 11:16:51 AM]

Share this post


Link to post
Share on other sites
thanks for the responses everyone... much appreciated.

I''ve been doing a fair bit of work (at uni) with Haskell/Functional Programming, which has a very sophisticated "lazy evaluation" system, and was wondering if/where these sorts of ideas would apply to a procedural/OO language like C/C++ (and Java/C# to a lesser extent).

are there any other similar short circuit / lazy evaluation type things to know about?

cheers,
Jack

DirectX 4 VB: All you need for multimedia programming in Visual Basic
Formula 1 Championship Manager, My Game Project.

Share this post


Link to post
Share on other sites
quote:
Original post by superdeveloper
HOWEVER, some compilers may indeed process the conditions right to left, or in fact process ALL of the conditionals when it''s already proven true or false after the first test..

I wouldn''t use such a compiler. Do you know of any such compilers or are you just guessing? Because short-circuit evaluation is part of the standard, and I would shudder to think that some people would be using non-standard compilers and generating non-standard code...

quote:

Personally I would aviod the confusion by implementing:
<snip!>

Personally, I would prefer it if you would write standard code and avoid non-standard compilers, as much as possible. Short-circuit evaluation is not complicated to implement, so any compiler that doesn''t isn''t worth my time. Besides, your implementation will cause problems with civguy''s example.

Share this post


Link to post
Share on other sites
I guess I have to:
http://www.zib.de/benger/C%2B%2B/clause5.html#s5.14
quote:
Original post by jollyjeffers
are there any other similar short circuit / lazy evaluation type things to know about?
Lazy evaluation can be done in C++ when things are completely encapsulated in classes. I believe there are some matrix libraries for C++ that use lazy evaluation for the calculations (perhaps uBLAS?). I.e. when you multiply two matrices, nothing is calculated. But when you try to access cell (1,6) from the result matrix, it''ll evaluate the value on that cell.

Share this post


Link to post
Share on other sites
hey Oluseyi,

I totally agree with you in all your comments, and I use a standard compiler so I don't actually run into these situations.

Its just that I ran into people writing code for things like remote controls, and other devices where the compiler is limited in quality or standardization.

Furthermore, right-to left, or "all conditional tests" are usually project options, and are necessary because sometimes you WANT to execute all of the tests instead of short-circuiting..

i.e. a messed up example where each function needs to be executed, even though they all return a boolean result stating if a character is a carriage-return...

if(GetChar() == 13 && NextCharIsBufferEOF() && IncrementLineNumber(GetChar() == 13)) {
cprintf("New line was reached\n");
};

...or better yet.

if(MovementSuccessful() || UpdateCollisionsSuccess(MyCollisions)) {
DrawShipAndPossibleCollisions(MyCollisions);
};

Does this make sence?

www.cppnow.com

[edited by - superdeveloper on April 1, 2003 12:25:56 PM]

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!