Fast 2D Array access in C (with inline Assembly?)

[wonder]

Hello again!

Let say I want to represent a 32x32 tiled map for a game with destructible tiles (read-write access).

1) Is the best way a one-dimensional char array of size 1024 or should I declare as a 2D matrix?

Code: Select all

// 1D Array:
// + Faster access with i = ((y * len_x) + x)
// - 16bit index
char map[1024] = {...};

// 2D Matrix:
// + 8 bit indexes
// - Slower access (pointer-to-pointer?)
char map[32][32] = {
    {...},
    {...},
       .
       .
       .
};

2) Given the best possible solution, what's the leanest and fastest way to access (read) it?
I'm looking for either C or inline assembly code.

So far, the [32][32] solution seem to be the faster one, with pre-calculated indexes:

Code: Select all

x = ...; y = ...;
v = map[y][x];

How can I improve this?

Many thanks in advance.

[DRW]

I would only use one-dimensional arrays for NES programming. This makes it clearer what's going on below.

The advantage that a two-dimensional array only has single-byte indices is not really an advantage. Because for the compiler, it's all just one long stripe of data. (No, a two-dimensional array is not a pointer to pointer.)
So, the access: array[y][x] still amounts to &(array[0]) + (y * width + x). Which means the compiler does an int-based calculation anyway.

Performance-wise, both should end up identical. (I'm not sure, though. You should test it out.)
But as I said, with a one-dimensional array, you see more directly what's going on.

For example, the index calculation y * width + x is only fast because your width is a potency of 2. That's why the compiler can convert this into a bit shift: (y * 32) == (y << 5)

If your array was 30 x 30, then the compiler really had to start doing multiplication which is slow. And in this case, a one-dimensional array potentially lets you find the slowness faster. Because accessing with array[y][x] might not clue you why the code is so slow. But in array[y * 30 + x] you see: "Oh, right, I'm using a multiplication."


But yeah, for such a big playfield, you have no choice but to use an array with an int-based index.
That's why the granularity of a single screen in my current game is only 16 x 15 items, i.e. the smallest background object, including destroyable objects, can only be 16 x 16 pixels, not 8 x 8 pixels. This way, I have an array of 240 entires for the background status and can easily use a byte index.


By the way, the playfield on the NES for a non-scrolling screen is only 32 x 30, not 32 x 32.

[aquasnake]

Hello again!

Let say I want to represent a 32x32 tiled map for a game with destructible tiles (read-write access).

1) Is the best way a one-dimensional char array of size 1024 or should I declare as a 2D matrix?

Code: Select all

// 1D Array:
// + Faster access with i = ((y * len_x) + x)
// - 16bit index
char map[1024] = {...};

// 2D Matrix:
// + 8 bit indexes
// - Slower access (pointer-to-pointer?)
char map[32][32] = {
    {...},
    {...},
       .
       .
       .
};

2) Given the best possible solution, what's the leanest and fastest way to access (read) it?
I'm looking for either C or inline assembly code.

So far, the [32][32] solution seem to be the faster one, with pre-calculated indexes:

Code: Select all

x = ...; y = ...;
v = map[y][x];

How can I improve this?

Many thanks in advance.

u8 UrArray[MAX_ARRAY_SIZE] = {
#include "ur_dat_file_whatever_its_type"
};

just so simple

[aquasnake]

i'd rather use linear 1-D array, 'cause its more effective, and no need aligned storage in even addr.

nes is too less in-built ram to use, cant be wasted