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

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems.

Moderator: Moderators

Post Reply
User avatar
wonder
Posts: 23
Joined: Sat Aug 31, 2019 2:12 pm

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

Post by wonder » Tue Sep 10, 2019 1:15 am

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.
Image

User avatar
DRW
Posts: 1913
Joined: Sat Sep 07, 2013 2:59 pm

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

Post by DRW » Tue Sep 10, 2019 1:37 am

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.
Available now: My game "City Trouble".
Sales website: https://megacatstudios.com/products/city-trouble
Gameplay: https://youtu.be/Eee0yurkIW4
Download website: http://www.denny-r-walter.de/city.htm

aquasnake
Posts: 40
Joined: Fri Sep 13, 2019 11:22 pm

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

Post by aquasnake » Fri Sep 13, 2019 11:32 pm

wonder wrote: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
Posts: 40
Joined: Fri Sep 13, 2019 11:22 pm

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

Post by aquasnake » Fri Sep 13, 2019 11:48 pm

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

Post Reply