• Advertisement

Archived

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

A really nasty 'if' statement...

This topic is 6379 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

I am trying to create a function that takes a RECT structure as a parameter, and checks if the mouse position is in it. This function has to be as fast as possible, as it is being called in real time, (30+fps). Here is the code that I came up with: //RECT test function int RectTest (RECT test) { if(cursor_x >= test.left){ if(cursor_y >= test.top){ if(cursor_x <= test.right){ if(cursor_y <= test.bottom) { return(RECTTEST_OK); } } } } else { return(RECTTEST_BAD); } } As you may have guessed, the x position of the mouse is stored in the cursor_x variable, and the y position of the mouse likewise in the cursor_y variable. I have define the RECTTEST_OK and RECTTEST_BAD at the beginning of the program. Here are the errors I get when I try to link/compile: D:\STYDX7IN24\Source\prototype\prototype.cpp(361) : error C2059: syntax error : ''='' D:\STYDX7IN24\Source\prototype\prototype.cpp(366) : error C2059: syntax error : ''='' D:\STYDX7IN24\Source\prototype\prototype.cpp(366) : error C2143: syntax error : missing '';'' before '')'' I can''t seem to figure it out (stupid me:p). Anyone here have an answer/better solution?

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
int RecTest(RECT test)
{
if(((cx >= test.left) && (cx <= test.right)) && ((cy >= test.top) && (cy <= test.bottom)))
{
return(RECTTEST_OK);
}

return(RECTTEST_BAD);
}



cant see anything wrong with that code, the errors are most likely due to something missing in the code just before, or a problem with your defines.

Share this post


Link to post
Share on other sites
Well is there difference in performance using many ifs or many logical ands?.

Share this post


Link to post
Share on other sites
I beleive that ifs have some problems with speed as I think they are treated as function calls. Logical ands are fast... Don''t quote me on the first bit tho

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
-Chris Bennett of Dwarfsoft
"The Philosophers' Stone of Programming Alchemy"
IOL (The list formerly known as NPCAI) - A GDNet production
Our Doc - The future of RPGs
Thanks to all the goblins over in our little Game Design Corner niche
          

Share this post


Link to post
Share on other sites
Here's a cleaner way to write this function:

    
int RectTest (RECT test)
{
if(cursor_x >= test.left)
if(cursor_y >= test.top)
if(cursor_x <= test.right)
if(cursor_y <= test.bottom)
return(RECTTEST_OK);
else
return(RECTTEST_BAD);
}


I've never used so many nested 'ifs' like this, but it should work.

Edited by - Zipster on August 29, 2000 8:00:07 PM

Share this post


Link to post
Share on other sites
Ok, to do my part here: here's a messed up way, but faster (yippie)

        
#define RectTest(R) (cx >= R.left && cx <= R.right && cy >= R.top && cy <= R.bottom ? RECTTEST_OK : RECTTEST_BAD)




Edited by - baskuenen on August 29, 2000 8:22:20 PM

Share this post


Link to post
Share on other sites
I just want to make sure everyone is hip to something...

Logical AND''s and OR''s in C++ have what''s known as short circuit evaluation. This means logical operations can evaluate faster without to do all the work all the time.

What that means if I have an AND statement like:

if ((x==2) && (y==3))
...

If x==2 is false, there is no need to evaluate y==3. The statement will exit out before it even evaluates y==3, because it knows the entire expression will evaluate to false regardless of the value of y.

For an OR example:

if ((x==2) || (y==3))
...

If x==2 is true, then there is not need to evaluate y==3. No matter what the value of y, the entire expression will return true.

To put it another way, the language takes advantage of 2 rules:
1) False logically AND''d with anything else is ALWAYS False.
2) True logically OR''d with anything else is ALWAYS True.

I know this to be the case on C/C++, and Java (although Java has operators without this feature).

So...
I''d throw them in one if statement.

PS> Short circuit evaluation can also mess you up . If your expression contains function calls for instance, those functions might not get called because the if statement short circuited on you. If those function calls would have changed data for instance, that data might not have been changed. Keep it in mind...

Share this post


Link to post
Share on other sites
I didn''t use logical and''s in the first place because I was unsure of the performace hit it would make. Would logical and''s be faster or as fast as using the super-nested if statement?

Share this post


Link to post
Share on other sites
I think I''ll try compiling something and disassembling it just to see. With short circuit evaluation it seems like you would not even need to do the actual AND''s on the CPU.

I''ll check it out...

Share this post


Link to post
Share on other sites
I tried this out with Visual C++ 6.0 in a debug build (which obviously does not matter once you see the disassembly ).

Turns out they don't do AND's .

Here is a code snippet I tried:

        

void main()
{
int x = 5;
int y = 7;
int z = 9;

if (x==5)
{
if (y==7)
{
z = 10;
}
}
}



I then tried this:



void main()
{
if ((x==5) && (y==7))
{
z = 10;
}
}



They both produced the exact same assembly:



0040103D cmp dword ptr [ebp-4],5
00401041 jne main+40h (00401050)
00401043 cmp dword ptr [ebp-8],7
00401047 jne main+40h (00401050)



So in summation:

Again, this is in Visual C++, but I have a feeling it's not exactly MS patent pending or anything. An if statement composed of expressions logically AND'ed together produces the exact same code.

Wonder if I should add this to my list of interview questions designed to torture people? j/k

Edited by - Kentamanos on August 30, 2000 3:04:29 AM

Share this post


Link to post
Share on other sites
Yes logical ANDS are faster. I learned this from my old turbo pascal teacher. As a midterm he had us make a poker game. I had like 15 "if" statements nested(silly silly me) and he marked a HUGE red circle around them saying something like "using &''s would make better performance". I always hated that guy...>(

Share this post


Link to post
Share on other sites
You are using a method which tests for the cursor being inside the rectangle. Another (and I think, neater) way is to test for the cursor not being inside the rectangle.

if(cursor_x < test.left) return RECTTEST_BAD;
if(cursor_y < test.top) return RECTTEST_BAD;
if(cursor_x > test.right) return RECTTEST_BAD;
if(cursor_y > test.bottom) return RECTTEST_BAD;

return RECTTEST_OK;

Any ideas how fast this version would be?

-DeVore

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
You are using a method which tests for the cursor being inside the rectangle. Another (and I think, neater) way is to test for the cursor not being inside the rectangle.

if(cursor_x < test.left) return RECTTEST_BAD;
if(cursor_y < test.top) return RECTTEST_BAD;
if(cursor_x > test.right) return RECTTEST_BAD;
if(cursor_y > test.bottom) return RECTTEST_BAD;

return RECTTEST_OK;

Any ideas how fast this version would be?

-DeVore

Share this post


Link to post
Share on other sites
As another suggestion, if you are REALLY bothered about execution speed, then the order of the "if statements" makes a difference. In the last example given, suppose the cursor is outside to the left, then the function would exit after only 1 "if statement". However, if it is below the bottom, then all 4 need to be executed. It could be worth it to gather some statistics about the outcome of this function under it''s real usage and then put the most common failed "if statement" first.

As for whether to use nested if''s or not. Do a test!!!!!

Share this post


Link to post
Share on other sites
quote:
Original post by Rederick

Yes logical ANDS are faster. I learned this from my old turbo pascal teacher. As a midterm he had us make a poker game. I had like 15 "if" statements nested(silly silly me) and he marked a HUGE red circle around them saying something like "using &''s would make better performance". I always hated that guy...>(


This old turbo pascal teacher, has some catching up to do (like almost all teachers )
He''s definately wrong.
Did he also mention NAND''s are the fastest and cheapest

I''m sure both methods are just as fast. Every compiler today compiles to the same code.


quote:
Original post by Anonymous
if(cursor_x < test.left) return RECTTEST_BAD;
if(cursor_y < test.top) return RECTTEST_BAD;
if(cursor_x > test.right) return RECTTEST_BAD;
if(cursor_y > test.bottom) return RECTTEST_BAD;

return RECTTEST_OK;



If you got a very good optimizing compiler, this will be just as fast as the others, but could be slower if you''re using a bad optimizer...
If you look at it at assembly level, you still need a JMP before the RET.
Better to use as less return''s as possible - in this case.


Some good optimized code could look like: (some pseudo asm)
    
cmp cursor_x, test.left
jle bad
cmp cursor_y, test.top
jle bad
cmp cursor_x, test.right
jge bad
cmp cursor_y, test.bottom
jge bad
mov eax, RECTTEST_OK
ret
bad:
mov eax, RECTTEST_BAD
ret


Share this post


Link to post
Share on other sites
int RectTest (RECT test)
{
return (cursor_x >= test.left && cursor_y >= test.top && cursor_x <= test.right && cursor_y <= test.bottom);
}

if (RectTest(WaterMelonRect))
{
Render that damn water melon to the screen...
}

btw, there are FASTER ways, you just have to think about those. And the only way they can be accomplished is by using ASM''s "clever" opcodes (instructions) which use the flags. I have an idea in my mind, but since I have to catch a train, I''ll might discuss it later (I have to try it out first) if I find this thread again.

btw, what I have in mind doesn''t use any if''s (CMP/JLE) etc.

-------------------------------
That's just my 200 bucks' worth!

..-=gLaDiAtOr=-..

Share this post


Link to post
Share on other sites
People have already pointed out that using logical and creates a series of compare-and-jumps, just like nested if statements; this isn''t even allowed to be optimized because both C and C++ guarantee the short-circuiting behavior. (I don''t think you can optimize even if it''s a statement of the form (var1 < constant) && (var2 < constant); for example, if var1 and var2 are floating-point, var1 is good and var2 is a NaN, then doing the compare on var2 may set some CPU status bits and so even in this case there''s a potential side-effect.) But what about arithmetic and? My Intel assembly is horrible, so I don''t know if there''s a compare operation that puts the result of the compare into a general register; if there is, then code that looked something like

    
#define RectTest(R) ((cx >= R.left) \
& (cx <= R.right) \
& (cy >= R.top) \
& (cy <= R.bottom))?RECTTEST_OK:RECTTEST_BAD)


might actually be faster because the four compares (and the bitwise and operations) could be pipelineable. There would be a fifth compare and a single jump at the end, but still this code could conceivably be better...

Share this post


Link to post
Share on other sites
Sheesh, who would have thought that such a topic could bring around a discussion about assembly and optimizations...

Anyway, here is the code I am using for a function (all one line):

#define RectTest(R) (cursor_x >= R.left && cursor_x <= R.right && cursor_y >= R.top && cursor_y <= R.bottom ? RECTTEST_OK : RECTTEST_BAD)
return(RECTTEST_BAD);
}

Here is how I am using it:

if (RectTest(test_area_one) != RectTest_OK) //PROBLEM!!
{
//blit screen 1 as usual
}

Now whenever I try to compile, I get errors about missing a = sign and a semicolon. Can anyone figure this out?

Share this post


Link to post
Share on other sites
#define does not need a return statement or {}.


#define RectTest(R) ((cursor_x >= R.left && cursor_x <= R.right && cursor_y >= R.top && cursor_y <= R.bottom) ? RECTTEST_OK : RECTTEST_BAD)


Personally, I think #defines are evil and would use an inline function instead. Type safety is a good thing(tm).

                        
inline bool IsInRect(LONG x, LONG y, RECT R)
{
return (x >= R.left && x <= R.right && y >= R.top && y <= R.bottom);
}



Edited by - vladg on August 31, 2000 4:21:13 AM

Edited by - vladg on August 31, 2000 4:24:59 AM

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Ok, first of all #define-ing the whole if statement or using that funky ? :, if-else shortcut, provides no extra speed as the assembly turns out the same. Now for the if/&& debate. I couldn''t possibly see the nested if''s being faster than the and''s, BECAUSE (this being the big most important thingy here) when you use a jmp in assembly, the CPU has to predict the jump in order to prevent CPU stalls. Now the CPU is pretty good at this (with branch prediction tables and all), but if it gets it wrong (which it will, on something like this it''ll probably get it right about %60 - %80 percent of the time, though it totally depends on the size of the RECT) it has to stall and flush the whole processor, which is very time consuming. On the other hand AND''s don''t need a prediciton and therefore will never stall the processor. Also JMP''s (especialy nested one''s) have a tendancy of thrashing the code cache (which again will degrade performance), while AND''s don''t. As far as dude''s thing on NAND''s vs AND''s, both NAND''s and AND''s take 1 cycle to complete and both can be piped on either the U or V pipe, so there is NO speed increase in using NAND''s on modern machines (that being pentium and up, anything before that I''m not sure). The fastest way I can think of off hand would be to use some MMX code (though you would probably need to test it first). With proper ordering of your variables (and assuming short''s have high enough precision) you should be able to get all 4 compares with 1 mmx compare, and then a simple add and an if and your all set. Depending on your app, it may or may not be faster. I''d code it out for you but I can''t find my MMX instruction reference. I think I need to print it out again. Anyways good-luck.

Ryan
Boghean

BTW: don''t bother with assembly unless this function is called like some 500 times per frame, otherwise it''s a waste of time. If it''s called only once a frame don''t sweat it and use C code. It''s not worth the effort.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Err... forgot 1 thing.. Inline the function like dude above said, that makes a difference! Also for MOE. You can''t compare to structures (unless you overload the C++ operators), and doing so provides no extra speed increase as you will have to compare each item individually (even if it doesn''t look like that). Also the basic idea behind that has problems. Sorry..

Ryan
Boghean

Share this post


Link to post
Share on other sites
This is a interesting topic..
Here''s a function from Cohen-Sutherland 2D clipping..
do you know anyway to optimize it?

inline BYTE camera::CompOutCode(const double x, const double y)
{ //compute outcode function used by clip2D

BYTE code = 0;
if (y > ymax)
code = TOP;
else
if (y < ymin)
code = BOTTOM;

if (x > xmax)
code += RIGHT;
else
if (x < xmin)
code += LEFT;

return code;
}



BTW, TOP, LEFT rights etc are BYTES
LEFT = 1;
RIGHT = 1<<1;
BOTTOM = 1<<2;
TOP = 1<<3;

Share this post


Link to post
Share on other sites
Just a comment, if cursor_x >= teste.left is true and cursor_y >= test.top is false, the execution will jump to the end of the function and not return a value.... i got a feeling that if you correct the error you are receiveing now, you''ll get another for a lack of return statement

quote:
Original post by Moe

I am trying to create a function that takes a RECT structure as a parameter, and checks if the mouse position is in it. This function has to be as fast as possible, as it is being called in real time, (30+fps). Here is the code that I came up with:

//RECT test function
int RectTest (RECT test)
{
if(cursor_x >= test.left){
if(cursor_y >= test.top){
if(cursor_x <= test.right){
if(cursor_y <= test.bottom) {
return(RECTTEST_OK);
}
}
}
} else {
return(RECTTEST_BAD);
}
}

As you may have guessed, the x position of the mouse is stored in the cursor_x variable, and the y position of the mouse likewise in the cursor_y variable. I have define the RECTTEST_OK and RECTTEST_BAD at the beginning of the program. Here are the errors I get when I try to link/compile:

D:\STYDX7IN24\Source\prototype\prototype.cpp(361) : error C2059: syntax error : ''=''
D:\STYDX7IN24\Source\prototype\prototype.cpp(366) : error C2059: syntax error : ''=''
D:\STYDX7IN24\Source\prototype\prototype.cpp(366) : error C2143: syntax error : missing '';'' before '')''

I can''t seem to figure it out (stupid me:p). Anyone here have an answer/better solution?






You know, I never wanted to be a programmer...

Alexandre Moura

Share this post


Link to post
Share on other sites
Sorry, have to come back on previous post
I think it could be done even faster, in some situations:

Pseudo stuff:
    
mov eax,100
sub eax,200
// normally you would jump, but why not save the signed number...!
mov ebx,300
sub ebx,50
and eax,ebx
jz bad
mov eax, RECTTEST_OK
ret
bad:
mov eax, RECTTEST_BAD
ret


But this would require some bitwise operations on boolean values...is there any compiler smart enough for this stuff? ... I think not yet?...

Share this post


Link to post
Share on other sites
Okay, I am still getting some wierd errors. Would it work if I did something like:

#define RECTTEST_OK 1
#define RECTTEST_BAD 0

//later in the program...

//RECT test function
int RecTest(RECT test)
{
if(cursor_x < test.left) return RECTTEST_BAD;
if(cursor_y < test.top) return RECTTEST_BAD;
if(cursor_x > test.right) return RECTTEST_BAD;
if(cursor_y > test.bottom) return RECTTEST_BAD;

return(RECTTEST_BAD);
}

//even further in the program...
if (RectTest(test_area_one) != RectTest_OK)
{
//blit the stuff as desired
}

Share this post


Link to post
Share on other sites

  • Advertisement