GLBasic forum

Codesnippets => Math => Topic started by: tictac on 2008-Jul-12

Title: Small calc optimizations
Post by: tictac on 2008-Jul-12
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!)
Title: Re: Small calc optimizations
Post by: Kitty Hello on 2008-Jul-12
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.
Title: Re: Small calc optimizations
Post by: PeeJay on 2008-Jul-12
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 .....
Title: Re: Small calc optimizations
Post by: Moru on 2008-Jul-12
This is one of the things that make realy old games mysteriously crash after a certain time :-)
Title: Re: Small calc optimizations
Post by: tictac on 2008-Jul-13
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:

Title: Re: Small calc optimizations
Post by: PeeJay on 2008-Jul-13
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
Title: Re: Small calc optimizations
Post by: Kitty Hello on 2008-Jul-14
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".
Title: Re: Small calc optimizations
Post by: tictac on 2008-Jul-14
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  =)

Title: Re: Small calc optimizations
Post by: Kitty Hello on 2008-Jul-14
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

Title: Re: Small calc optimizations
Post by: tictac on 2008-Jul-14
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!












Title: Re: Small calc optimizations
Post by: tictac on 2008-Jul-14
@Ocean, I fully agree with you  :booze:
Title: Re: Small calc optimizations
Post by: Kitty Hello on 2008-Jul-14
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.
Title: Re: Small calc optimizations
Post by: tictac on 2008-Jul-14
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 )
Title: Re: Small calc optimizations
Post by: tictac on 2008-Jul-14
Good! So I'm not so old!!!  =D :lol:
Title: Re: Small calc optimizations
Post by: PeeJay on 2008-Jul-15
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.
Title: Re: Small calc optimizations
Post by: Quentin on 2008-Aug-16
@ale870
could you please explain how you did the tests to say MOD is faster than using IF. Because if couldn't believe it ;)
I did a simple test with the following coding and IF is always much faster. (10,000,000 iterations so it takes some millisecs)

Code (glbasic) Select

LOCAL count = 10000000
LOCAL counter, i
LOCAL diff1, diff2, time1, time2

time1 = GETTIMERALL()
FOR i = 1 TO count
INC counter, 1
IF counter >= 360 THEN counter = 0
NEXT
diff1 = GETTIMERALL() - time1

time2 = GETTIMERALL()
FOR i = 1 TO count
INC counter, 1
counter = MOD(counter, 360)
NEXT
diff2 = GETTIMERALL() - time2

PRINT "IF-Statement: " + diff1, 0, 0
PRINT "MOD-Statement:" + diff2, 0, 40
SHOWSCREEN
MOUSEWAIT