in reply to How to speed up a nested loop?

The index mappings produced (fixing $bx & $by as 0) are: 

tiles[ 0][ 0][constant][type] = type_data[  0]
tiles[ 1][ 0][constant][type] = type_data[ 16]
tiles[ 2][ 0][constant][type] = type_data[ 32]
tiles[ 3][ 0][constant][type] = type_data[ 48]
tiles[ 4][ 0][constant][type] = type_data[ 64]
tiles[ 5][ 0][constant][type] = type_data[ 80]
tiles[ 6][ 0][constant][type] = type_data[ 96]
tiles[ 7][ 0][constant][type] = type_data[112]
tiles[ 8][ 0][constant][type] = type_data[128]
tiles[ 9][ 0][constant][type] = type_data[144]
tiles[10][ 0][constant][type] = type_data[160]
tiles[11][ 0][constant][type] = type_data[176]
tiles[12][ 0][constant][type] = type_data[192]
tiles[13][ 0][constant][type] = type_data[208]
tiles[14][ 0][constant][type] = type_data[224]
tiles[15][ 0][constant][type] = type_data[240]
...
tiles[ 0][15][constant][type] = type_data[ 15]
tiles[ 1][15][constant][type] = type_data[ 31]
tiles[ 2][15][constant][type] = type_data[ 47]
tiles[ 3][15][constant][type] = type_data[ 63]
tiles[ 4][15][constant][type] = type_data[ 79]
tiles[ 5][15][constant][type] = type_data[ 95]
tiles[ 6][15][constant][type] = type_data[111]
tiles[ 7][15][constant][type] = type_data[127]
tiles[ 8][15][constant][type] = type_data[143]
tiles[ 9][15][constant][type] = type_data[159]
tiles[10][15][constant][type] = type_data[175]
tiles[11][15][constant][type] = type_data[191]
tiles[12][15][constant][type] = type_data[207]
tiles[13][15][constant][type] = type_data[223]
tiles[14][15][constant][type] = type_data[239]
tiles[15][15][constant][type] = type_data[255]

[download]

Which means that you are taking a one dimension array of 256 values, treating it as a 2D 16x16 array, and mapping vertical slices of that, onto horizontal slices of your display: 

    @type_data
    [00,01,02,03]
    [10,11,12,13]
    [20,21,22,23]
    [30,31,32,33]

    @tiles
                bx
                |
    +--+--+--+--+--+--+--+--+--+--+--
    |  |  |  |  |  |  |  |  |  |  |  
    +--+--+--+--+--+--+--+--+--+--+--
    |  |  |  |  |  |  |  |  |  |  |  
    +--+--+--+--+--+--+--+--+--+--+--
    |  |  |  |  |  |  |  |  |  |  |  
    +--+--+--+--+--+--+--+--+--+--+--
    |  |  |  |  |  |  |  |  |  |  |  
 by-+--+--+--+--+--+--+--+--+--+--+--
    |  |  |  |  |00|10|20|30|  |  |  
    +--+--+--+--+--+--+--+--+--+--+--
    |  |  |  |  |01|11|21|31|  |  |  
    +--+--+--+--+--+--+--+--+--+--+--
    |  |  |  |  |02|12|22|32|  |  |  
    +--+--+--+--+--+--+--+--+--+--+--
    |  |  |  |  |03|13|23|33|  |  |  
    +--+--+--+--+--+--+--+--+--+--+--
    |  |  |  |  |  |  |  |  |  |  |

[download]

And it is actually much worse than that, because you have two extra layers of indirection at each of those points: $bz & type(???):

As there is no OpenGL premative that can use this 4-deep array structure directly, then at some point later you must be unpacking chunks of it to pass to OpenGL primitives.

At the very least, you should re-order your tiles structure to: $tiles[$bz][$by][$bx][type] which would allow for a far more direct mapping of the elements with far less indirect for any given value of $bz which appears to be a constant during these loops. If you could move the type constant lower in the structure, then you could do the assignments using array slices 16 values at a time.

Basically, to improve your performance much beyond where you are now, you need to seriously re-consider the way you are structuring your data. First the ordering to allow more direct mapping.

Secondly, the complexity. If type is a constant, why is it there? It seems like you're just overstructuring your data and paying for it in time.

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
"Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."

Replies are listed 'Best First'.
Re^2: How to speed up a nested loop?
by Xenofur (Monk) on Sep 18, 2008 at 14:00 UTC
    Thanks for visualizing that. I never thought of doing that and it helped a good bit to show me that i really need to reverse the tiles array.

    As for OpenGL primitives, they won't be much help to me anyhow. Each tile can be a variety of things, either a full cube, a ramp, stairs, a door, a tree, etc. As such i'll need to construct objects for each tile anyhow, and what makes it worse: The exact visual of each tile is highly dependant on the tiles around it, for example in the case of ramps.

    As for the type constant: Each tile actually has 3 datasets. The type, which consists of two bytes, and binary flags for designation and occupation, which are stored in 4 byte values. Right now i'm ignoring those, but later on i'll need to add them in, and i figured there won't be much of a difference between doing it as pseudo-hash built by using constants or by creating 3 arrays for each of these datasets.

    "then you could do the assignments using array slices 16 values at a time."
    I'm not 100% sure what you mean by this, but it denotes some kind of bulk operation, right? I'm not too sure that that would be very useful, given that i don't only need to transfer the data, but also need to check whether the input data is different than the already existing data.

    This may help a bit in understanding it: http://i34.tinypic.com/20j2pep.jpg

    Update: Argh, changing around got it to $tiles[$bz][type][$rx][$ry] now, but can't figure out a good way how to swap x and y, as that turns the cells by 90° and would need correction ... somewhere else too.

    Update 2: I was being stupid and shouldn't have changed the order of parameters in the function that actually draws the tile. The code looks as follows now:
    Read more... (907 Bytes)
    Next step will be to play around with getting the reference to either $tiles[$bz][type] or $tiles[$bz][type][$by] at the appropiate places and see if that gives some kind of speed-up.

    Update 3: Damn, references actually give me a speed boost of 40% over what we already head. Right now i'm only wondering if there is a visually more pleasing way to dereference that.
    Read more... (894 Bytes)
[reply]
[d/l]
[select]
      I'm not 100% sure what you mean by this, but it denotes some kind of bulk operation, right? I'm not too sure that that would be very useful, given that i don't only need to transfer the data, but also need to check whether the input data is different than the already existing data.

      I assume that you are doing some kind of billboarding for the backdrops of your scenes. And you are attempting to optimise that by onlu updating the cells or slices if they have changed. But, often as not with these things, is frequently quicker to avoid the conditionals and simple update everything. When the screen is redrawn, because the player moved or rotated his viewpoint, everything needs to be scaled/slewed and redrawn anyway.

      So, if you could do @{ $tiles[z][y] } = @tile_data[ $y*16 .. ($y+1) * 16 - 1 ];-- that is, assign a complete X-slice in one go--then you've both avoided 16*2 index calculations, but also 16 condition tests.

      If you could arrange for the input data to be pre-formatted as a 2d array, then you can also avoid the slice operation and just assign pointers to arrays of 16 values, with a significant further saving.

      I appreciate it might require a re-think on some of your logic to make use of this, and that may be further than you wish to go, but it can be effective.

      It's similar to some descriptions of the Fischer-Yates shuffle, that test each pairing and avoid the swap if the values are the same. In most cases, it is cheaper to go ahead and swap them unconditionally, than to test the condition for every pairing.

      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
[d/l]
        Ah, i see where you're coming from. I need to explain however that that the analysis for change is necessary. You see, in order to actually have things be decently fast in OpenGL, i compile the contents of one 16x16 block into one display list, that can be called as one single line in perl and gets drawn directly from gfx card ram. Without those this would be pretty much impossible.

        However the act of actually constructing those is pretty costly timewise. To give a comparison, the following is from one refresh cycle where ALL display lists (98 in this instance) get generated:
        the code took: 0.467388 wallclock secs ( 0.47 usr +  0.06 sys =  0.53 CPU)
        And this one is from when NO display lists are generated:
        the code took: 0.025486 wallclock secs ( 0.03 usr +  0.00 sys =  0.03 CPU)
        As such, making the assignments would shave time off of an "idle refresh", but greatly increase the general costs by increasing the number of "rebuild refreshes".

        The increases i'm looking for right now are necessary to ensure the ability to refresh at a constant rate while no game changes are occuring, without having any skipping in the operation. This goal is pretty much reached, as i can now fix the FPS at 30 and updates should fit inbetween frame generation.
[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom