To Optimize, or to Scrap...

[JamesD]

If you find some code isn't running fast enough you can also do something like this in the first loop.
Basically, I unrolled the inner loop. Yup, you can unroll loops in BASIC and it can speed up the code quite a bit.
Notice the line length is only 1 character longer, though it may take a few more bytes when tokenized..

     FOR X=1 TO 4 :: READ HP(X,1),MP(X,1),NDIS(X,1),HP(X,2),MP(X,2),NDIS(X,2) :: NEXT X

FWIW, someone was writing an MC-10 program and I think the init routine was taking around 30 seconds (?).
I think he was asking about using assembly to speed it up.
We asked him to post the code and after some reorganizing and loop unrolling I think it took around 5 seconds.
Just something to consider.

Edited April 23, 2015 by JamesD

[Opry99er]

Thank you James.

 

Speed really is not much of a factor here, I don't think. This will only happen upon loading the first world (READing from DATA) and then upon entering a new world and LOADing a saved game (both from disk)... It is an "old" game... Players just gotta wait sometimes. LOL!!

 

Seriously though, thank you for the input... Any agonizing load time I can spare the users, the better. When I start building the SAVE and LOAD routines, this will come in VERY handy indeed...

[Opry99er]

In your above example, I am confused about one point...

 

The 1s and 2s in the second dimension.

 

The first dimension will contain the integers "1-4" while the second dimension contains the "meat".

 

It "appears" to my untrained eye that you are reading the DATA into the first dimension... Is that correct?

[Opry99er]

Wouldnt you unroll the X and read the Y?

[JamesD]

Sorry for the slow reply, my network just barfed for some reason.

In your above example, I am confused about one point...

The 1s and 2s in the second dimension.

The first dimension will contain the integers "1-4" while the second dimension contains the "meat".

It "appears" to my untrained eye that you are reading the DATA into the first dimension... Is that correct?

 

Wouldnt you unroll the X and read the Y?

Think of a 2D array as rows of boxes.
In this case you have two rows of four boxes.
You aren't reading into the dimension, you are reading into the boxes and the x,y just address an individual box.
I am just hard coding the values for one of the dimensions.

You can actually unroll either loop or even both loops.
I just chose the inner loop because it gets executed 4 times and the data stays in the same order this way.
If you unroll x you would need to make y the outer loop and then you have this.
Just make sure you reorder the data to match the order you are reading it.

    FOR y=1 TO 2 :: READ HP(1,y),MP(1,y),NDIS(1,y),HP(2,y),MP(2,y),NDIS(2,y),HP(3,y),MP(3,y),NDIS(3,y),HP(4,y),MP(4,y),NDIS(4,y) :: NEXT y

To completely unroll the loops you could do this. Not sure if it would all fit on one line or not as I'm not real experienced with TI BASIC and I don't know the line length restrictions or limits on number of variables you can READ at one time.

READ HP(1,1),MP(1,1),NDIS(1,1),HP(1,2),MP(1,2),NDIS(1,2),HP(2,1),MP(2,1),NDIS(2,1),HP(2,2),MP(2,2),NDIS(2,2)
READ HP(3,1),MP(3,1),NDIS(3,1),HP(3,2),MP(3,2),NDIS(3,2),HP(4,1),MP(4,1),NDIS(4,1),HP(4,2),MP(4,2),NDIS(4,2)

Edited April 23, 2015 by JamesD

[JamesD]

I think I misunderstood what you meant by "reading the DATA into the first dimension...".
I was just manually stepping through the Y values with hard coded values in the order the loop did. Maybe that will make more sense.

Edited April 23, 2015 by JamesD

[JamesD]

Just remember, the more times the outer loop is executed, the greater the boost from unrolling an inner loop.

[Opry99er]

Sorry... My mind is gone today.

 

Thanks for the explanations.

[JamesD]

No big. Loop unrolling is probably the least used technique I see taken advantage of in BASIC.

 

Loop unrolling can also be done like this:

 

for i = 1 to 9 step 2 :: A(i) = 0 :: A(i+1) = 0 :: next i

The thing to remember here, is that the computer spends half as much time testing to see if the loop is done and jumping back to the start of the loop as if you did this:

 

for i = 1 to 9 :: A(i) = 0 :: next i

When you have to decide if a loop can be unrolled you usually ask, Is the loop divisible by 2? 3?

You usually don't want to bloat the code too much by unrolling everything, but cutting the number of loops in half or by 1/3 can usually offer a noticeable speedup.

In the case of nested loops like your code not only loops half as many times, but no time is spent parsing, testing, etc... the for next statements for the inner loop.

 

If your head doesn't hurt enough already, you can initialize all of those data items with a single loop.

All I did was combine the unrolled inner loop and the items from the 2nd loop in one loop and organize the data to match it.

I spaced out the data and used more DATA statements than I normally would to make it easier to follow.

Each DATA statement holds the data for one pass through the loop. If the TI allows long enough lines you could scrunch the data onto a single line.

Arraybuild:
     DIM HP(4,2),MP(4,2),XP(4),LEV(4),CL$(4),NDIS(4,2)
     FOR X=1 TO 4 :: READ HP(X,1),MP(X,1),NDIS(X,1), HP(X,2),MP(X,2),NDIS(X,2), XP(X),LEV(X),CL$(X) :: NEXT X

ArrayData:

DATA 20,20,12,    15,5,5,    10,1,HERO
DATA 16,40,9,     5,20,11,   15,1,MAGE
DATA 25,0,12,    18,0,6,     15,1,FIGHTER
DATA 12,20,12,   5,12,6,     0,1,THIEF

Not only is that faster, it *might* even save a few bytes. Edited April 23, 2015 by JamesD

[+adamantyr]

Loop unrolling is even popular in assembly language... I haven't had to do it myself in any of my code yet... But yeah, it only becomes a performance issue if you're reading data in constantly, one time at the program start should be okay to avoid such extremes.

 

I did find, when writing Aperture, that performance became a consideration. When checking what character was at the next position, I ordered my IF/THEN statements so that the most common block encountered was the very first check. I initially tried to have complex IF statements like IF (G=128)*(G=129)*(G=131) but I found that these ran WAY slower and it was better to just iteratively have a single check per IF statement for speed. I also had two completely separate scan checks for when you were moving normally OR falling, because of different behaviors while you fell.

[JamesD]

If unrolling loops is too extreme then here is the version without unrolling the Y loop:

     FOR X=1 TO 4 :: FOR Y=1 TO 2 :: READ HP(X,Y),MP(X,Y),NDIS(X,Y) :: NEXT Y :: XP(X),LEV(X),CL$(X) :: NEXT X

Notice that the unrolled version is about the same length so frankly, I don't see loop unrolling as extreme in this case.
Unrolling the X loop or completely unrolling both loops... probably.
Just remember that loop unrolling isn't only about reading data.

*edit*

BTW, in the case of your example IF statement, I would try IF (G<127)*(G>131) to skip the desired condition with a 2nd IF (G<>120) following it. It might be slightly quicker than the multiple equal comparisons. No promises though.

Edited April 23, 2015 by JamesD

[+adamantyr]

My apologies, when I said "extreme" I meant that for what his code is attempting to accomplish (reading in starting data), that performance is less of a concern than memory.

[Opry99er]

Performance isn't an issue, truly. My "READ B :: HP(X,Y)=B" code is plenty fast, it is just too bulky and looks dumb as hell.

 

When I coded it, I was really just trying to get ANYTHING to work, since previous attempts ended in gnashing of teeth.

 

It worked, I posted it. And yea, it is extremely inefficient and (probably) poor programming practice.

[JamesD]

The code I posted is smaller, faster and pretty simple but now you are arguing the original code is plenty fast.
Somebody shoot me.

[Opry99er]

It is fast enough. My concern isnt speed, it is compactness and legibility. Yours is superior in both regards.

 

Thank you for your help James.

[JamesD]

FWIW, I've never heard someone complain about a game initializing too quickly.

[Opry99er]

Nor have I.

 

My point wasn't that I didn't want speed improvements, my point was that if it is space vs. speed, I'll take space on this particular project.

 

Your examples (and Adam's) happen to address both, so they're doubly delicious.

[JamesD]

To be honest, I really hadn't planned on posting code. What I originally had in mind when I said to interleave the data was the code in post #36 but when I saw Adam's version the unrolled inner loop became obvious.

It would be interesting to see what speed differences between the different versions offer.
TI BASIC may or may not offer as much of a speed improvement as other BASICs but I would think that due to the double interpreted nature small speed improvements would offer even bigger returns though.

[matthew180]

Don't store information in DATA statements only to load it into arrays. That doubles the storage of that data. Use DATA storage for constants, menus, maps, etc. Look at the DATA statement's best friend: RESTORE

[Opry99er]

Thanks Matthew.

 

The DATA will be on disk and read into the arrays. This DATA READ tester has been sort of a test to see how efficient it can be.

 

Youre absolutely right too. If I keep all the DATA statements in the programfile and read into arrays from there, it would be counterproductive.

[Opry99er]

(To be more precise)... This is not only a test of how functional arrays can be in optimizing my code, but also a primer for how to write my "SAVE/LOAD game" routine.

[+InsaneMultitasker]

Don't store information in DATA statements only to load it into arrays. That doubles the storage of that data. Use DATA storage for constants, menus, maps, etc. Look at the DATA statement's best friend: RESTORE

 

This is true when the data is (can be) loaded from an external source. However, if you do not use an external source the explicit initial values consume program space and variable space whether they are in-line assignments or DATA statements. At that point it is mostly programmer's discretion to determine which is more efficient and/or better organized.

[JamesD]

You could also switch to a language that doesn't require you to READ the data.
One that supports some sort of data structures.

[Opry99er]

Just about done with the data restructuring, thanks to some very excellent help on this thread.

 

I have been working concurrently on the SAVE/LOAD game routine... Once I finish the data restructure, that part will fall right into place.

 

Then it is just a matter of stripping unneeded code from the program, mofifying my display routines for the variables, and this puppy will be a streamlined and greased rocketship.

 

Much appreciated, again, fellas.

[JamesD]

Now if the BASIC compiler supported disk access...