Author Topic: Small calc optimizations  (Read 8328 times)

Offline tictac

  • Mc. Print
  • *
  • Posts: 21
    • View Profile
    • newLisp Italian blog!
Small calc optimizations
« 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!)
« Last Edit: 2008-Jul-12 by ale870 »
-Alessandro

Offline Kitty Hello

  • code monkey
  • Administrator
  • Prof. Inline
  • *******
  • Posts: 10697
  • here on my island the sea says 'hello'
    • View Profile
    • http://www.glbasic.com
Re: Small calc optimizations
« Reply #1 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.

Offline PeeJay

  • Mr. Polyvector
  • ***
  • Posts: 244
    • View Profile
    • PeeJays Remakes
Re: Small calc optimizations
« Reply #2 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 .....
www.peejays-remakes.co.uk
For games, remakes, and GL Basic Tutorials
Artificial Intelligence is no match for Natural Stupidity

Offline Moru

  • Administrator
  • Prof. Inline
  • *******
  • Posts: 1774
    • View Profile
    • Homepage
Re: Small calc optimizations
« Reply #3 on: 2008-Jul-12 »
This is one of the things that make realy old games mysteriously crash after a certain time :-)

Offline tictac

  • Mc. Print
  • *
  • Posts: 21
    • View Profile
    • newLisp Italian blog!
Re: Small calc optimizations
« Reply #4 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:

-Alessandro

Offline PeeJay

  • Mr. Polyvector
  • ***
  • Posts: 244
    • View Profile
    • PeeJays Remakes
Re: Small calc optimizations
« Reply #5 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
 
www.peejays-remakes.co.uk
For games, remakes, and GL Basic Tutorials
Artificial Intelligence is no match for Natural Stupidity

Offline Kitty Hello

  • code monkey
  • Administrator
  • Prof. Inline
  • *******
  • Posts: 10697
  • here on my island the sea says 'hello'
    • View Profile
    • http://www.glbasic.com
Re: Small calc optimizations
« Reply #6 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".

Offline tictac

  • Mc. Print
  • *
  • Posts: 21
    • View Profile
    • newLisp Italian blog!
Re: Small calc optimizations
« Reply #7 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  =)

-Alessandro

Offline Kitty Hello

  • code monkey
  • Administrator
  • Prof. Inline
  • *******
  • Posts: 10697
  • here on my island the sea says 'hello'
    • View Profile
    • http://www.glbasic.com
Re: Small calc optimizations
« Reply #8 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
 

Offline tictac

  • Mc. Print
  • *
  • Posts: 21
    • View Profile
    • newLisp Italian blog!
Re: Small calc optimizations
« Reply #9 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!












-Alessandro

Offline tictac

  • Mc. Print
  • *
  • Posts: 21
    • View Profile
    • newLisp Italian blog!
Re: Small calc optimizations
« Reply #10 on: 2008-Jul-14 »
@Ocean, I fully agree with you  :booze:
-Alessandro

Offline Kitty Hello

  • code monkey
  • Administrator
  • Prof. Inline
  • *******
  • Posts: 10697
  • here on my island the sea says 'hello'
    • View Profile
    • http://www.glbasic.com
Re: Small calc optimizations
« Reply #11 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.

Offline tictac

  • Mc. Print
  • *
  • Posts: 21
    • View Profile
    • newLisp Italian blog!
Re: Small calc optimizations
« Reply #12 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 )
-Alessandro

Offline tictac

  • Mc. Print
  • *
  • Posts: 21
    • View Profile
    • newLisp Italian blog!
Re: Small calc optimizations
« Reply #13 on: 2008-Jul-14 »
Good! So I'm not so old!!!  =D :lol:
-Alessandro

Offline PeeJay

  • Mr. Polyvector
  • ***
  • Posts: 244
    • View Profile
    • PeeJays Remakes
Re: Small calc optimizations
« Reply #14 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.
www.peejays-remakes.co.uk
For games, remakes, and GL Basic Tutorials
Artificial Intelligence is no match for Natural Stupidity