Axe Parser Programs optimization tricks
» >
»
» View previous topic :: View next topic  
  • Axe Parser Programs optimization tricks
  • 15 Jan 2013 10:48:03 am
  • Last edited by Guest on 16 Jan 2013 10:18:59 am; edited 1 time in total
So I have been working with Axe lately, and I've made a random walk generator.
Here's the code:


Code:
.BROWNIAN
#ExprOff
sub(RS)
Repeat getKey(15)
If getKey(41)
ClrDraw
sub(RS)
End
rand^8->R
If R=0
Y--
ElseIf R=1
Y++
ElseIf R=2
X--
ElseIf R=3
X++
ElseIf R=4
X++:Y++
ElseIf R=5
X++:Y--
ElseIf R=6
X--:Y--
Else
X--:Y++
End
If X=96:0->X
ElseIf X=-1:95->X
End
If Y=64:0->Y
ElseIf Y=-1:63->Y
End
pxl-Test(X,Y)->A
If A
Pxl-Off(X,Y)
Else
Pxl-On(X,Y)
End
DispGraph
End
Lbl RS
48->X:32->Y


This program compiles to 494 bytes (Axe Fusion on DCS7, Axe Parser 1.2.1a)

Originally it compiled to about 653 bytes under the same specs because I used ElseIf commands instead of Else commands at the ends of the loops.

For instance, I used this at first:

Code:
ElseIf R=7
X--:Y++

instead of:

Code:
Else
X--:Y++


and I used this at first:

Code:
If A=1
Pxl-Off(X,Y)
ElseIf A=0
Pxl-On(X,Y)
End


instead of this:

Code:
If A
Pxl-Off(X,Y)
Else
Pxl-On(X,Y)
End



I was wondering, if just changing the last command of a loop from ElseIf to Else can save so much memory, what else can I do to optimize this program (and others) further?
A really good way to optimize programs is to avoid as much use of If / ElseIf / Else as possible, which can be done if you are doing similar things in the various statements. For instance, rand^8->R and the entire If/ElseIf/Else chain after it can be changed to:

Code:

0->R->S
Repeat R??S
rand^3-1->R
rand^3-1->S
End
X+R->X:Y+R->Y

Basically, your old code was giving a unique direction for each of the eight possible movements, which is a straightforward way to think about it. This code, on the other hand, assigns a delta-X and a delta-Y and adds those to X and Y, and the Repeat loop it is contained in ensures that the two directions aren't both zero.

A solution in between these two, one that uses one random variable but still no If / ElseIf / Else branches, is a Look-Up Table, like this:

Code:

Data(0,-1, 0,1, -1,0, 1,0, 1,1, 1,-1, -1,-1, -1,1)->GDB0DIRS
rand^8->R
X+sign{R*2+GDB0DIRS}->X
Y+sign{R*2+1+GDB0DIRS}->Y

This code stores the delta-X's and delta-Y's in a table, then uses pointers to look up an ordered pair of values from the table and add them to X and Y, as appropriate. Note that this solution takes zero conditional checks.

In all of these, you also need to think about speed as well as size, and you will want to think of your algorithms in terms of big-O notation. If you don't already know what big-O is, here's a summary of terms:
- O(1) = Constant time, which means that the algorithm takes the same amount of time every time it is executed.
- O(log n) = Logarithmic time, which means that the algorithm takes an amount of time proportional to the logarithm (typically base 2) of some factor n. (NOTE: For all big-O notation, you ignore coefficients and any lesser terms, so if it's 2n + 1, you write O(n)).
- O(n) = Linear time, which means the algorithm takes an amount of time directly proportional to some factor n.
- O(n^2), O(n^3), O(n log n), O(2^n), ... you get the idea.
To get to the point: Your If / ElseIf / Else solution is O(n) where n is R, because no matter what you do, all of the previous If statements are checked. The dynamic generation solution (roll both R and S) is "amortized" O(1), because it more or less executes in constant time although it might run more than once sometimes. The LUT solution (as all LUT solutions are) is O(1).
Visit Betafreak Games: http://www.betafreak.com
Help Me Pay for College:
- Sign up for Fastweb through my referal link!
Compynerd255 already brought up one excellent approach to optimization: collapsing complex logic into mathematical formulae (or a lookup table, in some cases). But here is my attempt to fully optimize your code for size:


Code:
.BROWNIAN
Goto RS
While 1
If getKey(41)
ClrDraw
Lbl RS
48->X:32->Y
End
Data(1,0,-1,0,1,1,-1,-1,1)->°Dirs
((Select({rand^8+°Dirs}^r,+Y^64->Y)+256/256+X??96)-97?+96)->X
Pxl-Change(X,Y)
DispGraph
EndIf getKey(15)


Now, you may be saying: "WHAT???" Don't worry, I'll try to explain the changes I've made:
    ▪ Programs are optimized for size by default, so the #ExprOff wasn't really necessary. I decided to remove it as a matter of preference (and backwards compatibility).

    ▪ Since you only use the position reset subrotuine in two places, and both empty out into pretty much the same code path, I inlined it at one location and jump to it from the other.

    ▪ Unless you absolutely need the entry iteration check, a While 1 ... EndIf x style of loop is more optimized than a Repeat x ... End style of loop.

    ▪ Movement and clipping/wrapping... this is where it gets a little complicated. I went with a LUT-driven method like the one suggested by Compynerd255, but with some improvements. Firstly, instead of containing eight separate 2-byte direction pairs, I've smushed all eight pairs into 9 bytes by overlapping them. If you look at every pair of neighboring values in my LUT, you'll see that they are equivalent to the pairs in the LUT suggested by Compynerd255. The code then randomly extracts one of the eight byte pairs and saves a copy of it for later with Select(. The value read from the LUT is added to Y for movement; both the high byte and the low byte read from the LUT are added, but only the low byte really matters. Because immediately after, we perform clipping/wrapping by taking this new value modulo 64, which gets rid of extraneous high bits, wraps -1 to 63, and wraps 64 to 0, all in one! This new value of Y is saved, and then we restore the value initially read from the LUT by closing Select(). Handling X is a little more complicated, since 96 is not a power of 2 and we cannot magically handle everything with a modulus operation. So first I add one to the X offset and bring it down to the proper range with +256/256, and add this to X. Because I have added one to the X offset, if the offset was -1 and X was previously 0, the running value will be -1+1+0=0, so I can simply check for the value being 0 to perform left-side wrapping by replacing 0 with 96 (not 95 because our value is still increased by 1). I then subtract 97, as if the offset was 1 and X was previously 95, the running value will be 1+1+95-97, so I can again simply check for the value being 0 to perform right-side wrapping. If this check evaluated to 0, that's already the value I want for the wrapped value, so I simply leave it if it's 0, and otherwise add back 96 to normalize the X value back to the proper range. Finally I save the new value of X! Hopefully this made some sense.

    ▪ As far as I can tell, when it actually comes to plotting the pixel, your 6 lines of code aim to invert the pixel. However you can simply do it in one command: Pxl-Change(X,Y).
  
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
Axe Parser Programs optimization tricks
»
» View previous topic :: View next topic  
Page 1 of 1
» All times are UTC - 5 Hours
 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

 

Advertisement