Fast Comparisons = big speed increase

[nzo]

I was doing something which was pushing the boundaries the other day and had to do some serious optimisation.
I found that the following drastically improved large loop repetition (e.g. screen buffer updates.

A typical bounds check of:

Code: [Select]

if (x>0) and (x<XRES) and (y>0) and (y<YRES) then ..
is commonly used. In some languages, the if statement will terminate when the first false condition is hit (providing the statement is fully parsed and the condition is determined to fail).
We normally don't have to worry about wasting CPU on pointless checking of the other conditions.
In FB however, it appears that all tests are evaluated - regardless of a single condition failure means the result will always be false, therefore:

Code: [Select]

if x>0 then
if x<XRES then
if y>0 then
if y<YRES then .....
endif
endif
endif
endif

Will offer a significant reward in processing time. Obviously, sort the checks into the "most likely order of occurance" to abort the test at the earliest opportunity.

I found that this made some huge speed improvements!

[Shockwave]

Thats a nice tip, I am surprised that FB doesn't fall over at the first failed test. Even though the language is very good it does need a gentle touch sometimes.

[Jim]

Seems that FB doesn't do short-circuit evaluation by default (nasty and unexpected) but there is an ANDALSO operator
http://www.freebasic.net/wiki/wikka.php?wakka=KeyPgOpAndAlso
So looks like

Code: [Select]

if (x>0) andalso (x<XRES) andalso (y>0) andalso (y<YRES) then
will work for a one-liner.

Jim

[rdc]

Yes, AndAlso was added to to allow short-circuit evaluation since that was a common complaint with the compiler.

[nzo]

AndAlso.. nice one guys. Found it in the chm also (wish all the operators were together in one place!)

I am suprised though - I've never come across a language where an alternative method was implemented. Usually see parenthesis control order/sequence of logical comparisons (or automatic "false" computed for the condition).

Still, it was very satisfying to find this, as I had run out of precalc, bitshifting and other optimising tricks on this problem

 

[Shockwave]

It's great that there is an alternative, I am surprised that it was not just fixed though instead of adding another method.

I can't think why you'd want to evaluate all the remaining conditions had it already failed.

[rdc]

I think that was the behavior of QB, if I remember right, so it was implemented in FB. Since there aren't any active developers for the compiler, I don't think they wanted to monkey around with the existing code. Just my guess.

[Jim]

->Shockwave
Imaging the following code:

Code: [Select]

dim a as integer
function test1() as integer
  a = a + 3
  return 0
end function
function test2() as integer
  a = a + 5
  return 0
end function
...
a=0
if test1() and test2() then
end if
print a

a=0
if test1() andalso test2() then
end if
print a
So, QB would have a=8, but a more C-like implementation with early-out would have a=3.  You have to have the first behaviour if you're trying to be backwards compatible, because evaluating the conditions can have side effects (like changing 'a').

Incidentally, this code is a great way to find out which behaviour your language uses.  Parabellum used it on yabasic and blitz (can't remember the results though).

<edit>code sample didn't do what I said it should.

Jim

[Shockwave]

That makes sence now that you've explained it Jim, thanks.

[bj]

Code: [Select]

if x>0 then
if x<XRES then
if y>0 then
if y<YRES then .....
endif
endif
endif
endif


I only know ZX Spectrum Basic - using line numbers instead of labels and (the dreaded and verboten) GOTO statement I'd have done something like

Code: [Select]

1010 GOTO 1100 - (80*(x>0))
1020 GOTO 1100 - (70*(x<XRES))
1030 GOTO 1100 - (60*(y>0))
1040 GOTO 1100 - (50*(y<YRES))
1050 . . . do something if boundary check succeeds
1100 continue if boundary check fails


[Jim]

Love it!!

Jim

[rain_storm]

I had noticed this fact some time ago and mentioned it in an older thread. Can't seem to find that post atm. From just looking at the disassembly of various compilers FB seems to be excellent for optimising arithmetic (to a point) but falls short in most other places. I have neven seen a compiler do a better job of optimisation than VS Express, so that was the compiler I had used to gauge the performance against.
One major thing I noticed is the following...

Code: [Select]

if (x = 0) then
'do something
end if
if (x = 0) then
'do something else
end if
in FB the above gets compiled to two separate if statement blocks whilst in VS Cpp its compiled into a single if statement block. I was very surprised by this as this is exactly the type of optimisation that a compiler should excell at. After having seen this I decided that it was time to move on to cpp/asm. Now Im using VS Cpp to teach me how to write better asm.

[JL235]

It might be slower (without short circuiting), but:

Code: [Select]

if (x>0) and (x<XRES) and (y>0) and (y<YRES) then ..is far easier to read then

Code: [Select]

if x>0 then
if x<XRES then
if y>0 then
if y<YRES then .....
endif
endif
endif
endif
Infact I'd go one further and add the cost of a function call too:

Code: [Select]

if isInBounds(x, y, XRES, YRES) then ..Then you can tell what the comparisons are for. IMHO code readability is more important then optimization.

[nzo]

IMHO code readability is more important then optimization.

I partially agree. However, you can't *not* optimise something when it's too slow, just for the sake of readability.

[Shockwave]

I am in agreement with Nzo here.

In applications where you are relying on the hardware to draw stuff or even if the code is a professional piece of work then you can afford to be ultra neat and readable.

In certain situations (that happen often) in pixel pushing, it's imperitive to optimise these checks as much as possible, especially when you consider that an 800*600 screen has about half a million pixels, many of which may need checking several times each depending on what you have got going on.

Sometimes there's no alternative than to go for all out speed. The code may be ugly but it will do the job.

This is particularly true for remakes, nearly everyone who does them uses some kind of framebuffer, whether it's using gdi to draw the pixels or opengl to draw the little quads.. Pixel pushing is the most effective way, it affords total control and allows for a much more authentic looking result.... You probably wouldn't consider me for a programming job though if you could see some of the hacks I've used in the past!

[nzo]

So, JL235? What do you think.. extra evaluation?

[Stonemonkey]

In demo-coding I say screw readability. And avoid bounds checking inside your loops as much as possible.