Perfomance enhancement? Is 1 dimensional arrays faster than multi dimensional?

[cybermind]

Hi :-) I have a multi dimensional array (10,6,14) for tiles in my game. This array is checked every loop. I have read that 1 dimensional arrays should be faster so my question is: Would my game require less if I use 1 dimensional arrays where possible? The one I have now is (X,Y,Layer) so I could X*Y*Layer = 840 and have a 1 dimensional array with 840 entries instead. I am trying to measure perfomance in my game. I store timer at beginning of my loop, I read timer at the end of my loop and subtract the stored timer then I add that to the complete time measurement variable, I count loops and divide complete time variable with loop counts but my loops seems to be less than a millisecond so I can't measure performance and performance gains this way :-( I have here provided how I try to measure performance, is there any other and better way?

EDIT: I have unlocked frames per second and I just measure frames per second instead, lowest and highest :-)

EDIT 2: It seems like I get no extra frames per second by changing the main tile array from multi dimensional to single dimensional. Frames per second stays around 1000-1300 per second.

PlayBASIC Code: [Select]

do
   timer_stored = timer()
   inc loop_count
   
        `all sorts of code and stuff
   
   loop_time = timer() - timer_stored
   complete_time_measured = complete_time_measured + loop_time
   text 0,0,"Loop avarage time: " + str$(complete_time_measured / loop_count)
   sync
loop

[kevin]

   The more dimensions you have in an array the more work (clipping / multiplies) that are required to compute where the cell is in memory.   Which is pretty universal language to language.   

I have a multi dimensional array (10,6,14) for tiles in my game. This array is checked every loop. I have read that 1 dimensional arrays should be faster so my question is: Would my game require less if I use 1 dimensional arrays where possible?

   Require less what ??  Memory / Computation ? - Can't answer either without some actual code.
     

[cybermind]

Require less what ??  Memory / Computation ? - Can't answer either without some actual code.

Less computation mostly, less memory would be good if possible but is not as important as less computation. I can show you the code but it is not good code, I have not learned good, clean programing yet :-P Do you wan't the whole thing or just the part I am referring to?

[kevin]

Just the part your concerned about.

[cybermind]

Here is the single dimension array version:

PlayBASIC Code: [Select]

   `draw combined layer 1, 2 and 3
   drawimage 1500,0,0,0
   
   dim work_map(840) `Normally not dim'ed here, this is just for Kevin
   current_work_map_tile = 0
   render_after_character_x = 0
   check_spawn_x = 1
   for update_map_grid_x = 1 to 10
      inc render_after_character_x
      render_after_character_y = 0
      check_spawn_y = 1
       for update_map_grid_y = 1 to 6
         inc render_after_character_y
         inc current_work_map_tile,3 `skip 3 layers, they have been merged into one single image that is used as backdrop
         `map layer 4, anim layer
         inc current_work_map_tile
         if work_map(current_work_map_tile) > 599 then DrawImage work_map(current_work_map_tile)+anim_tile_frame,(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1
         `map layer 5
         inc current_work_map_tile
          if work_map(current_work_map_tile) > 99 then DrawImage work_map(current_work_map_tile),(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1
          `map layer 6
         inc current_work_map_tile
          if work_map(current_work_map_tile) > 99 then DrawImage work_map(current_work_map_tile),(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1
          `map layer 7
         inc current_work_map_tile
          if conversations_completed(change_layer_7_to_8_by_event(update_map_grid_x,update_map_grid_y,1),change_layer_7_to_8_by_event(update_map_grid_x,update_map_grid_y,2)) = 0 and work_map(current_work_map_tile) > 99 then DrawImage work_map(current_work_map_tile),(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1
          `map layer 8
         inc current_work_map_tile
          if conversations_completed(change_layer_7_to_8_by_event(update_map_grid_x,update_map_grid_y,1),change_layer_7_to_8_by_event(update_map_grid_x,update_map_grid_y,2)) = 1 and work_map(current_work_map_tile) > 99 then DrawImage work_map(current_work_map_tile),(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1
         `map layer 9, spawn door
         inc current_work_map_tile
         for t = check_spawn_x to check_spawn_x + 1
            for u = check_spawn_y to check_spawn_y + 1
                if spawn_pre_calculated_path_1(spawn_steps_1,8) = 1 and spawn_x_1 = t - 1 and spawn_y_1 = u + 1 and work_map(current_work_map_tile) > 99 then DrawImage work_map(current_work_map_tile),(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1
            next u
         next
         `paste layer 10, 11, 12 and 13 before player
         if player_y > update_map_grid_y * 128 - 128 - 1
            `map layer 10
            inc current_work_map_tile
             if work_map(current_work_map_tile) > 99 then DrawImage work_map(current_work_map_tile),(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1
             `map layer 11, anim layer
            inc current_work_map_tile
             if work_map(current_work_map_tile) > 599 then DrawImage work_map(current_work_map_tile)+anim_tile_frame,(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1
             `map layer 12
            inc current_work_map_tile
             if work_map(current_work_map_tile) > 99 then DrawImage work_map(current_work_map_tile),(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1
            `map layer 13
            inc current_work_map_tile
             if conversations_completed(change_layer_7_to_8_by_event(update_map_grid_x,update_map_grid_y,1),change_layer_7_to_8_by_event(update_map_grid_x,update_map_grid_y,2)) = 1 and work_map(current_work_map_tile) > 99 then DrawImage work_map(current_work_map_tile),(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1
         endif
         `paste layer 10, 11, 12 and 13 after player)
         if player_y < update_map_grid_y * 128 - 128
            render_after_character(render_after_character_x,render_after_character_y,1,1) = update_map_grid_x
            render_after_character(render_after_character_x,render_after_character_y,1,2) = update_map_grid_y
            render_after_character(render_after_character_x,render_after_character_y,2,1) = update_map_grid_x
            render_after_character(render_after_character_x,render_after_character_y,2,2) = update_map_grid_y
            render_after_character(render_after_character_x,render_after_character_y,3,1) = update_map_grid_x
            render_after_character(render_after_character_x,render_after_character_y,3,2) = update_map_grid_y
            render_after_character(render_after_character_x,render_after_character_y,4,1) = update_map_grid_x
            render_after_character(render_after_character_x,render_after_character_y,4,2) = update_map_grid_y
            render_after_character(render_after_character_x,render_after_character_y,5,1) = update_map_grid_x
            render_after_character(render_after_character_x,render_after_character_y,5,2) = update_map_grid_y
            inc current_work_map_tile
            render_after_character(render_after_character_x,render_after_character_y,1,3) = work_map(current_work_map_tile)
            inc current_work_map_tile
            render_after_character(render_after_character_x,render_after_character_y,2,3) = work_map(current_work_map_tile)
            inc current_work_map_tile
            render_after_character(render_after_character_x,render_after_character_y,3,3) = work_map(current_work_map_tile)
            inc current_work_map_tile
            if conversations_completed(change_layer_7_to_8_by_event(update_map_grid_x,update_map_grid_y,1),change_layer_7_to_8_by_event(update_map_grid_x,update_map_grid_y,2)) = 1 and work_map(current_work_map_tile) > 99 then render_after_character(render_after_character_x,render_after_character_y,4,3) = work_map(current_work_map_tile)
         endif
         `always draw layer 14 after player
         inc current_work_map_tile
         render_after_character(render_after_character_x,render_after_character_y,5,3) = work_map(current_work_map_tile)
         inc check_spawn_y, 2
       next update_map_grid_y
      inc check_spawn_x, 2
   next update_map_grid_x

And here is the original multi dimension array code:

PlayBASIC Code: [Select]

   `draw combined layer 1, 2 and 3
   drawimage 1500,0,0,0
   
   dim work_map(10,6,14) `Normally not dim'ed here, this is just for Kevin
   render_after_character_x = 0
   check_spawn_x = 1
   for update_map_grid_x = 1 to 10
      inc render_after_character_x
      render_after_character_y = 0
      check_spawn_y = 1
       for update_map_grid_y = 1 to 6
         inc render_after_character_y
         `map layer 4, anim layer
         if work_map(update_map_grid_x,update_map_grid_y,4) > 599 then DrawImage work_map(update_map_grid_x,update_map_grid_y,4)+anim_tile_frame,(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1
         `map layer 5
          if work_map(update_map_grid_x,update_map_grid_y,5) > 99 then DrawImage work_map(update_map_grid_x,update_map_grid_y,5),(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1
          `map layer 6
          if work_map(update_map_grid_x,update_map_grid_y,6) > 99 then DrawImage work_map(update_map_grid_x,update_map_grid_y,6),(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1
          `map layer 7
          if conversations_completed(change_layer_7_to_8_by_event(update_map_grid_x,update_map_grid_y,1),change_layer_7_to_8_by_event(update_map_grid_x,update_map_grid_y,2)) = 0 and work_map(update_map_grid_x,update_map_grid_y,7) > 99 then DrawImage work_map(update_map_grid_x,update_map_grid_y,7),(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1
          `map layer 8
          if conversations_completed(change_layer_7_to_8_by_event(update_map_grid_x,update_map_grid_y,1),change_layer_7_to_8_by_event(update_map_grid_x,update_map_grid_y,2)) = 1 and work_map(update_map_grid_x,update_map_grid_y,8) > 99 then DrawImage work_map(update_map_grid_x,update_map_grid_y,8),(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1
         `map layer 9, spawn door
         for t = check_spawn_x to check_spawn_x + 1
            for u = check_spawn_y to check_spawn_y + 1
                if spawn_pre_calculated_path_1(spawn_steps_1,8) = 1 and spawn_x_1 = t - 1 and spawn_y_1 = u + 1 and work_map(update_map_grid_x,update_map_grid_y,9) > 99 then DrawImage work_map(update_map_grid_x,update_map_grid_y,9),(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1
            next u
         next
         `map layer 10
          if work_map(update_map_grid_x,update_map_grid_y,10) > 99 then DrawImage work_map(update_map_grid_x,update_map_grid_y,10),(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1
          `map layer 11, anim layer
          if work_map(update_map_grid_x,update_map_grid_y,11) > 599 then DrawImage work_map(update_map_grid_x,update_map_grid_y,11)+anim_tile_frame,(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1
          `map layer 12
          if work_map(update_map_grid_x,update_map_grid_y,12) > 99 then DrawImage work_map(update_map_grid_x,update_map_grid_y,12),(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1
         `map layer 13
          if conversations_completed(change_layer_7_to_8_by_event(update_map_grid_x,update_map_grid_y,1),change_layer_7_to_8_by_event(update_map_grid_x,update_map_grid_y,2)) = 1 and work_map(update_map_grid_x,update_map_grid_y,13) > 99 then DrawImage work_map(update_map_grid_x,update_map_grid_y,13),(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1
         `paste layer 10, 11, 12 and 13 after player)
         if player_y < update_map_grid_y * 128 - 128
            render_after_character(render_after_character_x,render_after_character_y,1,1) = update_map_grid_x
            render_after_character(render_after_character_x,render_after_character_y,1,2) = update_map_grid_y
            render_after_character(render_after_character_x,render_after_character_y,2,1) = update_map_grid_x
            render_after_character(render_after_character_x,render_after_character_y,2,2) = update_map_grid_y
            render_after_character(render_after_character_x,render_after_character_y,3,1) = update_map_grid_x
            render_after_character(render_after_character_x,render_after_character_y,3,2) = update_map_grid_y
            render_after_character(render_after_character_x,render_after_character_y,4,1) = update_map_grid_x
            render_after_character(render_after_character_x,render_after_character_y,4,2) = update_map_grid_y
            render_after_character(render_after_character_x,render_after_character_y,1,3) = work_map(update_map_grid_x,update_map_grid_y,10)
            render_after_character(render_after_character_x,render_after_character_y,2,3) = work_map(update_map_grid_x,update_map_grid_y,11)
            render_after_character(render_after_character_x,render_after_character_y,3,3) = work_map(update_map_grid_x,update_map_grid_y,12)
            if conversations_completed(change_layer_7_to_8_by_event(update_map_grid_x,update_map_grid_y,1),change_layer_7_to_8_by_event(update_map_grid_x,update_map_grid_y,2)) = 1 and work_map(update_map_grid_x,update_map_grid_y,13) > 99 then render_after_character(render_after_character_x,render_after_character_y,4,3) = work_map(update_map_grid_x,update_map_grid_y,13)
         endif
         `map layer 13 is found in "draw after character" part at bottom of this document. It is always to be drawn on top of player no matter what
         inc check_spawn_y, 2
       next update_map_grid_y
      inc check_spawn_x, 2
   next update_map_grid_x

The tab's seems messed up, sorry!


MODEDIT: changed the CODE tags for PBCODE tags

[kevin]

 The main recommendation about any such code is to remove redundant calculations from the inner loops, so in other words, try an avoid computing things inside the inner most loops that aren't going to change throughout the loop.

See->> Some Tips  -   More Tips  -  Redundancy Examples

PlayBASIC Code: [Select]

         `map layer 9, spawn door
         for t = check_spawn_x to check_spawn_x + 1
            for u = check_spawn_y to check_spawn_y + 1
                if spawn_pre_calculated_path_1(spawn_steps_1,8) = 1 and spawn_x_1 = t - 1 and spawn_y_1 = u + 1 and work_map(update_map_grid_x,update_map_grid_y,9) > 99 then DrawImage work_map(update_map_grid_x,update_map_grid_y,9),(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1
            next u
         next

     
   a quick look at that condition in the above code and all the conditions have to be meet in order to draw anything.  For the THEN part to execute, all parts of the expression need to be true (they're all computed every time!).   But some parts like this   spawn_x_1 = t - 1 can switch the whole inner loop on or off and thus determine if the inner loop is necessary at all.   So when spawn_x_1 <> t - 1 then the inner loop can be skipped completely.

PlayBASIC Code: [Select]

         `map layer 9, spawn door
         for t = check_spawn_x to check_spawn_x + 1
            if spawn_x_1 = t - 1 
               for u = check_spawn_y to check_spawn_y + 1
                   if spawn_pre_calculated_path_1(spawn_steps_1,8) = 1 and spawn_y_1 = u + 1 and work_map(update_map_grid_x,update_map_grid_y,9) > 99 then DrawImage work_map(update_map_grid_x,update_map_grid_y,9),(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1
               next u
            endif
         next
       endif

         next

     Looking at the conditions again, the work_map(update_map_grid_x,update_map_grid_y,9) > 99 will be constant through both U & T loops.  So it shouldn't be inside the loop at all.
     

PlayBASIC Code: [Select]

         for t = check_spawn_x to check_spawn_x + 1
            if spawn_x_1 = t - 1 
               for u = check_spawn_y to check_spawn_y + 1
                   if spawn_pre_calculated_path_1(spawn_steps_1,8) = 1 and spawn_y_1 = u + 1 and work_map(update_map_grid_x,update_map_grid_y,9) > 99 then DrawImage work_map(update_map_grid_x,update_map_grid_y,9),(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1
               next u
            endif
         next

     If we shuffle that out we get something like this.  

PlayBASIC Code: [Select]

       ; we only need to run through this nest when the tile is above 99
       if work_map(update_map_grid_x,update_map_grid_y,9) > 99
         for t = check_spawn_x to check_spawn_x + 1
            if spawn_x_1 = t - 1 
               for u = check_spawn_y to check_spawn_y + 1
                   if spawn_pre_calculated_path_1(spawn_steps_1,8) = 1 and spawn_y_1 = u + 1  then DrawImage work_map(update_map_grid_x,update_map_grid_y,9),(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1
               next u
            endif
         next
      endif

     Since the comparison spawn_pre_calculated_path_1(spawn_steps_1,8) = 1 and spawn_y_1 = u + 1 is AND'ing the two condition together, and the left condition is looking for a literal 1,  and TRUE condition is Literal 1, then this is the same spawn_pre_calculated_path_1(spawn_steps_1,8) = (spawn_y_1 = u + 1)

      Giving us something like this.  

PlayBASIC Code: [Select]

       ; we only need to run through this nest when the tile is above 99
       if work_map(update_map_grid_x,update_map_grid_y,9) > 99
         for t = check_spawn_x to check_spawn_x + 1
            if spawn_x_1 = t - 1 
               for u = check_spawn_y to check_spawn_y + 1
                   if spawn_pre_calculated_path_1(spawn_steps_1,8) = (spawn_y_1 = u + 1)  then DrawImage work_map(update_map_grid_x,update_map_grid_y,9),(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1
               next u
            endif
         next
      endif

  We can pull the array access out by pulling the Image into a variable.  Variables are simplest data type and are much quicker when doing operations on them.   So it's generally faster to pull a value from an array into a variable, then use that.

PlayBASIC Code: [Select]

       ; Grab the image/tile value once,  since it never changes inside the loop
       ThisImage=work_map(update_map_grid_x,update_map_grid_y,9)
       ; we only need to run through this nest when the tile is above 99
       if ThisImage > 99
         for t = check_spawn_x to check_spawn_x + 1
            if spawn_x_1 = t - 1 
               for u = check_spawn_y to check_spawn_y + 1
                   if spawn_pre_calculated_path_1(spawn_steps_1,8) = (spawn_y_1 = u + 1)  then DrawImage ThisIMage,(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1
               next u
            endif
         next
      endif

       Now just from that tiny nest we're gone from a fixed time execution into a variable time execution.  The inner loop is about 15 operations less than it was.  That's saving a 15*840 VM cycles from that one loop, since it's running that section every time.  


       The same type of tops apply to the rest of the routine really.    

       So this type of stuff

PlayBASIC Code: [Select]

         `map layer 4, anim layer
         if work_map(update_map_grid_x,update_map_grid_y,4) > 599 then DrawImage work_map(update_map_grid_x,update_map_grid_y,4)+anim_tile_frame,(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1

         `map layer 5
          if work_map(update_map_grid_x,update_map_grid_y,5) > 99 then DrawImage work_map(update_map_grid_x,update_map_grid_y,5),(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1
          `map layer 6
          if work_map(update_map_grid_x,update_map_grid_y,6) > 99 then DrawImage work_map(update_map_grid_x,update_map_grid_y,6),(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1

     This has exactly the same execution overhead when none of the layers are top be drawn, but is 50% less array accesses when they are./

PlayBASIC Code: [Select]

         `map layer 4, anim layer
         ThisIMage=work_map(update_map_grid_x,update_map_grid_y,4)
         if ThisIMage > 599 then DrawImage ThisIMage+anim_tile_frame,(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1

         `map layer 5
         ThisIMage=work_map(update_map_grid_x,update_map_grid_y,5)
          if ThisImage > 99 then DrawImage ThisIMage,(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1

          `map layer 6
         ThisIMage=work_map(update_map_grid_x,update_map_grid_y,6)
          if ThisIMAGE > 99 then DrawImage ThisIMAGE,(update_map_grid_x*128)-128,(update_map_grid_y*128)-128,1

       Since update_map_grid_x is constant for the update_map_grid_Y loop we can pre compute the value out.  

PlayBASIC Code: [Select]

      SCreenX=(update_map_grid_x*128)-128
      
       for update_map_grid_y = 1 to 6
         inc render_after_character_y

         `map layer 4, anim layer
         ThisIMage=work_map(update_map_grid_x,update_map_grid_y,4)
         if ThisIMage > 599 then DrawImage ThisIMage+anim_tile_frame,ScreenX,(update_map_grid_y*128)-128,1

         `map layer 5
         ThisIMage=work_map(update_map_grid_x,update_map_grid_y,5)
          if ThisImage > 99 then DrawImage ThisIMage,ScreenX,(update_map_grid_y*128)-128,1

          `map layer 6
         ThisIMage=work_map(update_map_grid_x,update_map_grid_y,6)
          if ThisIMAGE > 99 then DrawImage ThisIMAGE,ScreenX,(update_map_grid_y*128)-128,1

     etc etc

     So by getting rid of redundancy in our programs source code, it's easy to make the logic faster & smaller.   We can also apply this type of thinking to our graphics programming.  Now since the tiles are being drawn transparent, it'd more than likely worth clipping out any unused pixels from them where possible.     The optimization tutorial bellow covers that and more..


See Tutorial: A Crash Course In BASIC program Optimization

[cybermind]

I will read all this and try to understand completely and then implement it where possible :-) You are the best!!! Thank you very much!

[cybermind]

I am currently going through the Crash course in BASIC program optimization, afterwards I will continue through your last reply in this post. What a great way to start a monday :-) I am having a great time reading this stuff oozing with good programing pointers!

EDIT: Quick update, I have removed many redundant calculations in the main game, next up is up is sub parts like menus, battle and other stuff. Really great advice :-)

[cybermind]

Hello again :-) I am not done with the optimizations and I have not started on the suggestions you wrote in the reply yet, but I looked at it quickly right now. I have already started pulling data from arrays into variables :-) I am looking forward to using the suggestions when I have studied them some more :-) I have already gone from 1 loop taking about 0.7 to 0.8 down to near 0.6 and with FPS unlocked I have gone from around 1350 FPS at max to 1450 FPS at max :-)

[kevin]

I have gone from around 1350 FPS at max to 1450 FPS at max :-)

   Is that for the entire program or a portion of it ?  If it's the whole thing, then i wouldn't worry too much about opt'ing it.

[cybermind]

Is that for the entire program or a portion of it ?  If it's the whole thing, then i wouldn't worry too much about opt'ing it.

That is for when walking around the maps, and it is the only part that is realtime, the menus and battles are some slower. Battles are around 500 fps, but they are turnbased and there are only one character moving at any one time. I removed some debugging output text and the frame rate went up to over 4000 fps when walking around on the maps, so I will leave optimization alone for a while :-)