Speed of Looping through an Array

K

Kululu17

Guest
Hi All,

I was hoping someone could explain what is causing the difference in processor load for a draw event, for a demo project I am working on.

I have a 2D map that I am drawing sprite by sprite in squares - the map is set up as a array, and the draw event loops through the map array, and draws each sprite in its proper place. Long term, I will probably switch to tiles, but for now I am using sprites, because what needs to get drawn is not fixed, but depends on a lot of different parameters (which character is viewing the map, which map mode you are in, etc). So for now I am just using sprites. Anyway, if I use a really big map, predictably the performance slows down a lot. I was able to get around this by changing the draw even to only draw the squares that are visible in the current view. So far, so good, and performance jumps back up to acceptable level.

Now here's the weird thing - the performance (fps) varies A LOT depending on where on the map you are looking at. For example if you are viewing the upper left corner of the map, fps is about 70, but if you scroll down to the lower right corner, the fps jumps to over 200. The total number of squares being drawn in each case should be the same, since I am referencing the upper right and lower left corner of the view (which doesn't change), and then drawing the sprites only for the map coordinates that fall within that frame.

Can someone explain why referencing different parts of the array (but the same total number of of values) seems to require different processor loads?

The code is below for reference... it goes longer and draws all kinds of things depending on various map parameters, view modes, etc, but the important part is shown here:

Code:
var Quad_X;
var Quad_Y;

//Determine visible view, so that you only need to draw visible
var Visible_St_X = floor(view_xview[0]/g.Grid_Size);
var Visible_St_Y = floor(view_yview[0]/g.Grid_Size);
var Visible_End_X = ceil((view_xview[0]+view_wview[0])/g.Grid_Size);
var Visible_End_Y = ceil((view_yview[0]+view_hview[0])/g.Grid_Size);
//Make sure you do not exceed the array's range
Visible_St_X = max(Visible_St_X,1);
Visible_St_Y = max(Visible_St_Y,1);
Visible_End_X = min(Visible_End_X,g.Map_Width);
Visible_End_Y = min(Visible_End_Y,g.Map_Height);

//Could eventually be done as tiles, not sprites to save processor power
for (Quad_X = Visible_St_X; Quad_X <= Visible_End_X; Quad_X ++) {
    for (Quad_Y = Visible_St_Y; Quad_Y <= Visible_End_Y; Quad_Y ++) {   
        var Quad_Number = script_execute(SCR_Get_Map_Key,Quad_X,Quad_Y);
        draw_sprite(SPR_Map_Tile,-1,Quad_X*g.Grid_Size,Quad_Y*g.Grid_Size);//eliminating this has no noticeable effect
        if g.Debugging_Info != "Off" && g.Exploration_Map[(Quad_Number),3] != 0 {//Here is the exploration overlay
            draw_sprite(SPR_Show_Explore,-1,Quad_X*g.Grid_Size,Quad_Y*g.Grid_Size);
            draw_text(Quad_X*g.Grid_Size,Quad_Y*g.Grid_Size,string(g.Exploration_Map[(Quad_Number),4])+" ("+string(g.Exploration_Map[(Quad_Number),3])+")")
            }
        var Hillsize = 0;
        var Map_Hillsize = g.Global_Map[(Quad_Number),3];
        if g.Debugging_Info != "Off" or g.Player_Map[(Quad_Number),3] >=1 {
            switch Map_Hillsize {
                case 10:
                case 9:
                draw_sprite(SPR_Hills,0,Quad_X*g.Grid_Size,Quad_Y*g.Grid_Size);
                break;
                case 8:
                case 7:
                case 6:
                draw_sprite(SPR_Hills,1,Quad_X*g.Grid_Size,Quad_Y*g.Grid_Size);
                break;
                case 5:
                case 4:
                case 3:
                draw_sprite(SPR_Hills,2,Quad_X*g.Grid_Size,Quad_Y*g.Grid_Size);
                break;           
                }
            }
 

Tthecreator

Your Creator!
I can't see it directly by looking at your code.
What you could do is disable different part of your code to see if it has any effect. (I see you already did that to a few lines)
What you could also do is make a counter that counts up how many sprites are being draw, and then move the camera to see if that number changes.
What I do see are some if statements inside your for loops, which might be part of the cause. Maybe inspect those further?
 

NightFrost

Member
Are you sure the loop remains within the array? Look into the compile window while running and check for a stream of notifications that array read is not within bounds. I've noticed this significantly slows down a game.
 
K

Kululu17

Guest
Hi,

Thanks for the response. It's not a problem per se, I just want to know if referencing different parts of an array should make a difference in speed - for example referencing g.Map[1,2] ->g.Map[10,2], should it be the same load as referencing g.Map[101,2] ->g.Map[110,2]?
 

PNelly

Member
I'd suggest double checking this area:

Code:
//Determine visible view, so that you only need to draw visible
var Visible_St_X = floor(view_xview[0]/g.Grid_Size);
var Visible_St_Y = floor(view_yview[0]/g.Grid_Size);
var Visible_End_X = ceil((view_xview[0]+view_wview[0])/g.Grid_Size);
var Visible_End_Y = ceil((view_yview[0]+view_hview[0])/g.Grid_Size);
//Make sure you do not exceed the array's range
Visible_St_X = max(Visible_St_X,1);
Visible_St_Y = max(Visible_St_Y,1);
Visible_End_X = min(Visible_End_X,g.Map_Width);
Visible_End_Y = min(Visible_End_Y,g.Map_Height);
put some show_debug_messages (or draw_text or use the debugger or whatever you like) for the values of those variables to ensure that they're coming out the way you mean them to. If it's not what you expect it could be that you're traversing a much larger portion of the array than you think you are.
 
K

Kululu17

Guest
Hey guys, thanks for all the suggestions! I did make the "Visible X, Y" numbers draw on the screen, and they showed the numbers that they were supposed to. One thing occurs to me - the simulation runs faster at the bottom right, which corresponds to the highest numbers of the array (towards the end). I remember reading something about arrays initializing in reverse order - could it be that the number at the end are faster to read, because there (internally) initialized first?
 

NightFrost

Member
Arrays don't automatically initialize in reverse order - they grab memory in the order you put content into them. The reverse order thing is a speedup tip as it forces the array to reserve all the memory it needs on the very first push.

To put arrays simply, it is a pointer to a memory address and the array position(s) just get added to its initial memory address to reach the desired position. So reading Array[10] would be "read memory position from first spot plus ten." There's no speedup or slowdown depending on the accessed position.
 

icuurd12b42

TMC Founder
GMC Elder
slowdowns can occur with grids, for example, if trying to access data outside the grid bounds. SInce you are not using grids, I cant say for sure...

Verify you start and end for the loop...

all these:
(view_xview[0]/g.Grid_Size);
should be floor(pos/(grid_size-1))

Because the grid size is say 10, addresses 0 through 9. Not 0 through 10

also these
//Make sure you do not exceed the array's range
Visible_St_X = max(Visible_St_X,1);
Visible_St_Y = max(Visible_St_Y,1);
Visible_End_X = min(Visible_End_X,g.Map_Width);
Visible_End_Y = min(Visible_End_Y,g.Map_Height);

arrays are 0 based, not 1 based and end at size-1, not size...

Also, why are you calling script_execute if you are calling the script... That is a script and not a variable holding a script is it?
Also, your debug being a string "OFF", it's a waste of CPU

If you are modifying the content of that array, each step, that may the thing that is lagging as opposed to the drawing of it...
 
Top