Sign in to follow this  
darren_mfuk

Best way to declare (C++) array ?

Recommended Posts

What is the better way to declare an array ??? myArray[100][100] or myArray[100 * 100] ????? If it matters, it's to declare a tiles grid (cols by rows) and to populate an array with the data before rendering. Cheers

Share this post


Link to post
Share on other sites
Quote:
Original post by darren_mfuk
What is the better way to declare an array ???

myArray[100][100]

or

myArray[100 * 100]

?????

If it matters, it's to declare a tiles grid (cols by rows)
and to populate an array with the data before rendering.

Cheers


If you use myArray[100][100] I believe c++ will internally use myArray[100*100] and will do the correct index math.

Share this post


Link to post
Share on other sites
The two declare different things. Ultimately, you must decide what object you need, and then use the corresponding declaration.

So, do you need a one-dimensional array, or a two-dimensional array? Judging by your mention of a grid, you seem to want the two-dimensional array. The only way of declaring a two-dimensional array is through:

myArray[100][100]

Share this post


Link to post
Share on other sites
I'd probably do the first one, it's largely a matter of taste.

Whichever you do, wrap up the array into an object so that you can guarantee there's no accidental reading/writing past the bounds. Ensuring safety is always A Good Thing.

Share this post


Link to post
Share on other sites
The second method is what I prefer to use, though I'm not exactly sure if there is any major performance benefit to it.

In actuality, I would skip using the pointer method altogether and use a vector container.

ie:


#include <iostream>
using std::cout;

#include <vector>
using std::vector;

void func(int *x)
{
cout << *x;
}

int main(void)
{
size_t x_size = 100;
size_t y_size = 100;

vector<int> vint;

vint.reserve(x_size*y_size); // must reserve the memory first
vint.resize(x_size*y_size); // now resize

// indexing example
for(size_t i = 0; i < x_size; i++)
for(size_t j = 0; j < y_size; j++)
vint[j*y_size + i] = 3;

// at and array notation
vint.at(0) = 1; // using a method which guards against out of bounds
vint[1] = 2; // does not guard against out of bounds, so be careful

// using address-of operator to pass in address of element as pointer
func(&vint[0]);
func(&vint[1]);
func(&vint[2]);

// vector is deallocated for you automatically when it goes out of scope
// (no delete[] / free() required like with a pointer)
return 0;
}



Share this post


Link to post
Share on other sites
Quote:
The second method is what I prefer to use, though I'm not exactly sure if there is any major performance benefit to it.

Of course there isn't any performance benefit at all. If it would give better performance then the compiler would transform it itself. Of course the reverse may be true, that if it knows it's dealing with a multidimensional array then it may utilize optimizations specific to those. I don't really know of any however, so I doubt it will be noticeable at all.

Ultimately, what it comes down to is what message you want to convey to both other programmers and the compiler. If I saw an uncommented declaration of an array of 10000 elements I would assume it was one-dimensional, not a hack for a two-dimensional array and therefore it would hurt my understanding of your code.

Of course the one-dimensional alternative have some benefits (they aren't performance though), for instance how would you pass a multidimensional-array to a standard algorithm?

If you want the best of both alternatives (and some extra features in addition), I suggest you check out Boost.MultiArray. Better than any of the original alternatives.

[Edited by - CTar on March 1, 2007 10:09:36 AM]

Share this post


Link to post
Share on other sites
First of all to taby:
You don't have to use reserve before resize. Look it up in Stroustrup's book.

For the original question, any decent compiler will make as efficient code for one as for the other. It's not unlikely that it will even generate identical code.

Just use the one you are more comfortable with. If you want to sweep through the whole array many times probably type array[100*100] is better, but if you wish to make a lot of random access to you array the other one is more convenient.

shinjin

Share this post


Link to post
Share on other sites
ok,

well 2 dimensional seems the obvious choice here for a grid.

So lets widen the topic a little, although it is an openGL problem

I am creating a (hexagonal) grid using

for 0 to cols
for 0 to rows
drawHexTile();
}
}

where we would call drawHexTile() 100 times, for a 10x10 grid ok ?

drawHexTile() actually draws a TRIANGLE_FAN to form a hexagon.
of cause this is doing it all EVERY single frame.

So it was suggested that I populate an array, just once with all the hexagon co-ords, before render.

Heres the thread:
Original Post

Share this post


Link to post
Share on other sites
Quote:
Original post by crshinjin
If you want to sweep through the whole array many times probably type array[100*100] is better, but if you wish to make a lot of random access to you array the other one is more convenient.
shinjin


How do you figure?

Share this post


Link to post
Share on other sites
There really shouldn't be any debate here. Both are the "best" way to declare an array, because there is only one way to declare a one-dimensional array and only one way to declare a two-dimensional one. Both methods will allocate the exact same amount of memory in the same way.

You stated that you want a 2-D grid where you can access both dimensions easily. Hence, use the two-dimensional array. The only real arguments here for the 1-D array are for speed. The speed difference will be negligible, and it will result in harder-to-read code. When programming, code it so that it WORKS first, then once it works identify the slow areas if needed. How you declare the array will have a negligible effect on speed (unless you are perhaps either very clever or very inefficient).

Share this post


Link to post
Share on other sites
The performance difference is non existant. If you know the dimensions of your 2d array beforehand, use a 2d array.

Tile myArray[100][100];

If you are dynamically allocating your 2d array, because the dimensions may change , the 1d array allocation is the only way you are going to dynamically allocate what amounts to a 2d array(and keep a contiguous memory profile for your tile map).

Tile myArray[100 * 100];
or
Tile *myArray = new Tile[100 * 100];

With this method however the way you index it will be different than indexing a 2d array. I recommend hiding these details in a TileMap class or something similar.

That's really all there is to it. No performance difference. They both allocate the same amount of memory. How you index each will be different. If you have the foresight to expect to need dynamically sized tile maps I'd go with the 1d array method, otherwise just use the static sized 2d array.

Share this post


Link to post
Share on other sites
Quote:
Original post by DrEvil
Quote:
Original post by crshinjin
If you want to sweep through the whole array many times probably type array[100*100] is better, but if you wish to make a lot of random access to you array the other one is more convenient.
shinjin


How do you figure?


i think he assumes

for (int i=0;i<10000;i++) {
doSomething(myArray[i]);
}


would be slightly faster than
[code]
for (int i=0;i<100;i++) {
for(int j=0;j<100;j++) {
doSomething(myArray[i][j]);
}
[code]

and that:

doSomething(myArray[x][y]);

is slightly faster than

myArray[y*100 + x];

Share this post


Link to post
Share on other sites
You've gotten some good advice on your original question, but I've not yet seen this important aside said:

When you are using arrays, either multi-dimensional or 1-dimensional using math to access the desired elements, you want to access it in the most efficient way possible --

For something like a Tile-based map of say 256 wide by 192 tall, and assuming that you process/draw the map in a top-to-bottom, left-to-right manner (eg - how english is read) you want to define your array like this:

myArray[192][256]

rather than:

myArray[256][192]

Notice that the width of the array should come last. The reason is because the right-most dimension is the one which lies linearly in memory, accessing the next tile to the right will be the very next position in memory. This optimizes your memory access patterns by making perfect use of the CPU cache. In the "wrong" example, the next tile to the right is located 192 memory positions away! This is the exact *wrong* way to use the cache efficiently, and will result in your code having to hit main memory on nearly every access, which is probably 100 times slower than having your data good and ready in level 1 cache.


You can extend this for more dimensions if you want:
myArray[width]
myArray[height][width]
myArray[depth][height][width]
myArray[etc.][depth][height][width]

It helps to think of multi-dimensional arrays not as a grid, cube, etc. but rather as an array of arrays, or an array of arrays of arrays.


When I was a young programmer, and cache's were very small, I remember having this epiphany and literally multiplying the frame-rate of my tile-based engine by 10 times - I was probably 14 years old at the time. This is one of those things that *everyone* does wrong at first, but never does again once they learn better.

Share this post


Link to post
Share on other sites
Hi ravyne2001,

Good point to mention that !!

For those that did not read all this thread, or the thread about my original project, where the question stemed from

Here's the thread:
Original Post

Basically I am using a char map :

const int tilesPerRow = 10; //no of hexaons per row (Y)
const int tilesPerCol = 10; //no of hexaons per col (X)

char map[tilesPerRow ][tilesPerCol ] = {
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{1, 0, 2, 0, 0, 0, 0, 0, 0, 1},
{1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{1, 0, 0, 0, 3, 3, 0, 0, 0, 1},
{1, 0, 0, 0, 3, 3, 0, 0, 0, 1},
{1, 0, 0, 0, 3, 0, 0, 0, 0, 1},
{1, 0, 0, 0, 3, 0, 4, 4, 0, 1},
{1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
};

Note: WILL (at some point) be using the char map, the numbers will denote the releavent texture for the tile later.

So I will loop through the number of rows then cols

Obviously going Row by row, hence the Y loop on the outside,
then for every tile in the grid Thats (X)....
draw a tile.... simple....


for Y 0 to tilesPerRow blah blah
{
for X 0 to tilesPerCol blah blah
{
drawHexTile(size, X, Y);
}
}

Note: dont be confused by X,Y - these are 2D coords, as if you were reading a map.
This will translate to world X,Z (there is no Y elevation) - producing a flat grid on the X,Z planes.


basically drawHexTile() is drawing a hexagon from a triangle_fan.
If you read the original thread, it works great, I have an awsome hexagonal grid, pixel perfect.
But I have a few suggestions on how to declare arrays,
either
[size*size]
OR
[size][size]

I neede to know the best way to improve things.

Really the flaw in the tiling is, that A) I'm going through the whole loop and drawing hexagon, every single frame.
B) that with this method, where each tile touches the next (in fact every 3 hexagons touch each other)
Is that I am drawing each vertex 3 times, which is kind of redundant.

I need to create a Vertex Array (which is where I lack knowledge)
So I can generate ALL the vertexes before render.

The map/grid is static, and wont change. all be it, you may only see part of the map as you scroll/move etc..
The grid in theory only ever need calculating once, and hopefully avoid drawing every vertex 3 times also.

So really back to the post, I need the best or most efficient way to declare a 2D 'static' array for a grid, prior to rendering.

If you have other ideas, on my actual Vertex Array or hexagon issue, please read that thread and post in there.

As thats where it gets complex for me really.
If you are folowing this (fingers crossed)
There is a 2D grid array (10 x 10) tiles. thats (100 * x, y, z coords)
(obviously world position to place the tile)
This will vary per 'game level'.. next level 15x15, 20x20.. or what ever is desired.

So I need to store a basic tile array info (for each of the above)
then the Tile data (the triangle fan actually 8 * x,y,z points) for every hexagon
(obviously world coords for each point of the hexagon tile)

So thats 100 * tile position coords
and 8 * hexagon vertex coords

Confused yet ?? Just read the original thread, and check out the screen shots, if I still have your interest.

Here's the thread:
Original Post

Thanks Guys

[Edited by - darren_mfuk on March 1, 2007 3:42:39 PM]

Share this post


Link to post
Share on other sites
Please check out the original post for those with some ideas, if you could help.

Otherwise I'll just end up jumping between 2 threads on this one.

Cheers, I just wanted an answer on the best way to declare arrays, which I think you guys have helped with.

But if you want to learn more on my vertex array issue, please check the link above

Share this post


Link to post
Share on other sites
Quote:
Of course there isn't any performance benefit at all. If it would give better performance then the compiler would transform it itself. Of course the reverse may be true, that if it knows it's dealing with a multidimensional array then it may utilize optimizations specific to those. I don't really know of any however, so I doubt it will be noticeable at all.


Im just being picky here, however, there is actually a difference to how they are alocated and hence if your not careful performance.
int array[100][100];
Will allocate a column major 2d array so....
for (int i = 0; i < 100; ++i)
{
for (int j = 0; j < 100; ++j)
{
array[i][j] = i + j;
}
}

will traverse the memory storing the array inorder (good for the cache), however
int array[100 * 100];
will (treated as a 2d array using the most common indexing method) alocate a row major 2d array so....
for (int i = 0; i < 100; ++i)
{
for (int j = 0; j < 100; ++j)
{
// of course using i * 100 + j here will treat the array as column major
// avoiding this problem (or just swap the order of the loop)
array[j * 100 + i] = i + j;
}
}

will trash the cache by acessing the 1st then 101st then 201'st... location in memory.

Of course row major or column major doesnt really mater as long as you traverse the array in the right order (however, in my experience most ppl for some reason or another tend to traverse the flat array in the wrong order)

Edit: mismatched [code] tags and just thought i should mention the standard garuentess that the 2d array is column major so the compiler cant swap it around if you use it in a way where row major would be more performant.

Share this post


Link to post
Share on other sites
Hi Julian90,

Thanks for your input, it seems to be the common answer really.

2D arrays seem the way to go, and much more logical, and eaier to access the correct data.

So do all these principles still apply for 3D arrays (multi-dimensional) ??


Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this