Small calc optimizations

Previous topic - Next topic

tictac

Hello, I'm new in GLBasic, and this is my first official post!  :booze:

I wish to give my contribute in calculation optimization (tricks!).

1) I noticed that many people, to get a sprite rotating (forever!), they use something like this:

Code (glbasic) Select

counter = 0
while true
  inc counter, 1
  if counter >= 360 then counter = 0
wend


Even if it is correct, using an if is usually a "slow" procedure. Istead, you can use this code:

Code (glbasic) Select

counter = 0

WHILE TRUE
INC counter, 1

PRINT MOD(counter, 360), 100, 100

SHOWSCREEN
WEND


In this way, the "mod" makes the "dirty" job, and it is faster than using "if".

Another trick is about values switching:

1) true -> false -> true ....
2) 1 -> 0 -> 1 -> ......

You can use the following code:

BOOLEAN:
Code (glbasic) Select

boolValue = FALSE

WHILE TRUE
boolValue = bNOT(boolValue)
PRINT boolValue, 100, 100

SHOWSCREEN
WEND


FOR "1" AND "0" ......

Code (glbasic) Select

boolValue = 0

WHILE TRUE
boolValue = 1 - boolValue
PRINT boolValue, 100, 100

SHOWSCREEN
WEND


In order to see the result, you can put, in the first line, an FPS limiter:

Quote
limitfps 3 ; 3 frames per second.

I hope this small tutorial will help some people! (my 0.02$ contribution!)
-Alessandro

Kitty Hello

another trick is to ignore all this and do:

Code (glbasic) Select

ROTOSPRITE 0,x,y, 12312341.5

it's wrapped automatically. No problem for the ROTO... functions as well as SIN/COS. Only, if you want to "display" the angle, it's better to use the fmod command.

PeeJay

while this is marginally faster, the problem comes when counter reaches really high numbers, as there must be an upper limit that GL can count up to .....
www.peejays-remakes.co.uk
For games, remakes, and GL Basic Tutorials
Artificial Intelligence is no match for Natural Stupidity

Moru

This is one of the things that make realy old games mysteriously crash after a certain time :-)

tictac

Yes, I think automatic wrapping (for the functions) is a good feature, but a real programmer must take full control of its application.
Thank you because I discovered even fmod and not only mod  :booze:

-Alessandro

PeeJay

Of course, if you get really bored, you could try this solution - I don't know if it will be faster that the IF solution though ....

Code (glbasic) Select

counter=0

WHILE TRUE

   INC counter, 1
   DEC counter, 360*INTEGER(counter/360)

   PRINT counter, 100, 100

WEND
www.peejays-remakes.co.uk
For games, remakes, and GL Basic Tutorials
Artificial Intelligence is no match for Natural Stupidity

Kitty Hello

an "IF" statement is propably the fastest thing out there.
So,

WHILE a<0; INC a, 306; WEND
WHILE a>360; DEC a,360; WEND

should be pretty fast. Especially when you increase angles, so that you don't have 1000x360 for "a".

tictac

Generally speaking, loops and conditions are "slow", since the CPU must "brake" internal cache to load another piece of machine code. Statements that "jump", generally speaking, must be used only if the generated code can reside inside the CPU internal cache. Furthermore, other kind of "jumps", like function call, should be avoided in fast calculations, since they constrain the computer to store jumping point in the stack (to come back there later, with a "return" statement).
This is the reason it is better use passive calculations like "mod" and avoid to use IF, GOTO, GOSUB, FOR, WHILE, etc...
Statements like FOR are good for the programmer but not for performance.
Example, this block of code....

a = 0
FOR i=1 to 3
  a = a + 1
NEXT

is slower than...

a = 0
a = a + 1
a = a + 1
a = a + 1

Because linear programming allow better caching algorithms inside CPU.

Some heavy duty applications use very small (compact) algorithms (less than 1Mb) in order to put all the code inside CPU cache, or they try to manually split calculations in several threads executed over multiple CPUs  =)

-Alessandro

Kitty Hello

Yes, nice. How do you interprete this then:
Code (glbasic) Select


DIM test[1000000]
FOR i=0 TO LEN(test[])-1
test[i] = RND(3*360) - 360
NEXT



time1 = GETTIMERALL()
a=0
FOR i=0 TO 10000
INC a, FMOD(test[i], 360)
NEXT
time2 = GETTIMERALL()
a=0
FOR i=0 TO 10000
b=test[i]
WHILE b>360; DEC b, 360; WEND
WHILE b<0; INC b, 360; WEND
INC a, b
NEXT
time3 = GETTIMERALL()

PRINT "fmod: "+FORMAT$(0,2,time2-time1)+" while:"+FORMAT$(0,2,time3-time2),0,0
SHOWSCREEN
MOUSEWAIT


tictac

Hello,

First "interpretation": first block is shorter than second one  =)

One hint more... try to substitute this line in your code...

test = RND(3*360) - 360

With this one...

test = RND(100*360)

The problem is you didn't make a real world example, since you made a test calibrated for your algorithm. In fact, generating random numbers as you made, you created many numbers within 0..360, so no while..wend was made.
If you try to change the code with mine (real, pure range between 0 and 360000) the things are different...

MOD time calculation is always the same, instead your code (since it must execute many while..wend) takes a LONGER time.
In my computer these are the results:

1) With your original RND code ( test = RND(3*360) - 360 ):

--My Algorithm = 0.59 secs
--Your algorithm = 0.43 secs

2) With neutral code (  test = RND(100*360)  )

--My Algorithm = 0.59 secs
--Your algorithm = 1.46 secs

2) With neutral code (  test = RND(1000*360)  )
  (I incremented from "100" -> "1000")

--My Algorithm = 0.59 secs
--Your algorithm = 10.58 secs

Ok, now please believe me I don't want to create a "flame" in this topic. I only wanted to create a pure, simple, constructive discussion about code optimization.

Thank you!












-Alessandro

tictac

@Ocean, I fully agree with you  :booze:
-Alessandro

Kitty Hello

Quote from: Ocean on 2008-Jul-14
...after I realized that an 'exponential moving average' (ema) can be constucted by using only the last two measurements and the prior 'ema'. 

Oh! I would be interested in this, because I have a (slight) jitter problem with the GP2X touchscreen polling.

[edit]
@ale870 - no flaming, I just have a very bad day today. Apologies.

tictac

Don't worry @Kitty, a genuine discussion is always welcome!  =)
(I'm 38, and I'm a programmer since when I was 13 (Texas Instruments TI-994A),
so imagine how many "discussions" I made in the time! =D )
-Alessandro

tictac

Good! So I'm not so old!!!  =D :lol:
-Alessandro

PeeJay

Absolutely - there was no flaming, just a discussion on how and why an optimisation does (or doesn't!) work.

Uncontrolled variables are always a problem - but without that being pointed out and discussed, new users could well write code that is fundamentally flawed, while thinking they are doing the right thing.

To be honest, I am more comfortable writing "bulletproof" code (ie code that will run flawlessly) rather than trying to find an odd millisecond here and there - for example in our loop, I would much rather use >359 rather than =360, purely because that way, if for some reason the check is skipped at some point, or the increment skips the value 360, or a decimal creeps in, then the code will still work, rather than ending up as an uncontrolled variable.
www.peejays-remakes.co.uk
For games, remakes, and GL Basic Tutorials
Artificial Intelligence is no match for Natural Stupidity