Archived

This topic is now archived and is closed to further replies.

QuaXiFalen

Arrays - One vs Multi-Dimensional

Recommended Posts

Is there any performance difference between dynamically allocating a one-dimensional array versus a two (or more) dimensional one? For example, here are two possibilities:
                            
Tile *tiles;
tiles=new Tile[width*height];


//or



Tile **tiles;
tiles=new Tile*[height];

for(int j=0;j<height;j++)
{
tiles[j]=new Tile[width];
}

                        
Is one or the other more efficient and/or faster? Also, since one allocates one width*height "chunk" of memory, while the other allocates a height number of "chunks" each of width of memory, which one is less likely to fail with large values of width and height ? Or is it about the same? I'm just wondering if this makes any difference, especially with large arrays. Thanks -IK Edited by - QuaXiFalen on 6/18/00 11:24:34 PM

Share this post


Link to post
Share on other sites
I would think that doing it in one line (tiles=new Tile[width*height]; ) would be more efficient than making the first array, then having to iterate through a for loop to create the heighth section of the array. If you were going to create a 512x512 array, you would end virtually adding 500+ "new" calls when you could have done it all in one line. Additionally, it's a lot easier to read one line.

As for which one would fail, I don't think it makes any difference. When it's all said and done, no matter which way you do it, it's basically going to occupy the same ammount of memory.

Then again, maybe it's just me. If I'm wrong, someone please point it out.



Edited by - BigBlueMonkey on June 18, 2000 12:58:53 AM

Share this post


Link to post
Share on other sites
Yes. If you use an array of pointers, both the access, the creation and the destruction will take more time.
I''m sorry, it''s like that. If I knew God personnally, I would change this out, but I always get stuck with His secretary. She''s kind of annoying sometimes.

If you use this, though:
int TITI[10][10];

The compiler (Borland did, don''t know for MSVC but it should) will take it as one array and will implement it with the fastest access possible. No dynamical creation/destruction though

(( Anyone here knows God personnally? I got two or three things to tell Him... ))

Programming is:
A.The art of debugging a blank sheet of paper (or an empty file).
B.A pastime similar to banging one's head against a wall, but with fewer opportunities for reward.
C.The most fun you can have with your clothes on (although clothes are not mandatory).

Share this post


Link to post
Share on other sites
Well, the array has to be allocated dynamically because the size can change, although the increase in creation time is not too big of a deal, since the array will only be created once (at the beginning of a game). I''m not sure about the cost of the second dereference, though.

But I wonder which one (if any) is less likely to fail. I thought that may be the two-dimensional method is less likely, because it doesn''t have to find one big "chunk" of memory all at once but creates numerous small "chunks".

But then again all of that memory can not overlap so may be it is easier for the system to find the memory with for a one-dimensional array?

Any ideas?

-IK

Share this post


Link to post
Share on other sites
The only thing i can add is this.

It''s will be easier to implent a ''asm'' function with one dimension then multi-dimension array.

That''s all...


Lowrad

Share this post


Link to post
Share on other sites
The double dereference will take twice as much time as a single. You really better to use the one array. Moreover, it will take a 32-bits pointer for every elements of the first array.

Programming is:
A.The art of debugging a blank sheet of paper (or an empty file).
B.A pastime similar to banging one's head against a wall, but with fewer opportunities for reward.
C.The most fun you can have with your clothes on (although clothes are not mandatory).

Share this post


Link to post
Share on other sites
Poltras, if you create a 1d array to emulate a 2d array you will still need to dereference a second time to access the desired element.

i.e.

int a[10][10]
a[6][5] = 6

of int a[100]
a[6*10 + 5] = 6

wether you do it or the compilere does it makes no difference.

One thing I will say is that if you dimmension one of you dimensions sizes to a power of 2 ie. 4,8,16,32...... the maths becomes an order of magnitude quicker.

i.e.

// declare a 16 by 16 array
int a[16 * 16]

// set element 6,5
a[6 << 4 + 5] = whatever.

arithmentic shift left and arithmetic shift right using integers is lightning quick, faster than floating point and much faster than integer multiplication and division.

If you have a large amount of array processing, you might want to take this into account.

Share this post


Link to post
Share on other sites
DeltaVee, I disagree, I think a 1d array that emulates a 2d array can be faster than a genuine 2d array. Here''s an example where you don''t have to multiply (or shift) every time to get the y offset:

DWORD* a = new DWORD[ width * height ];

for(y=0, yOffset=0; y < height; y++, yOffset+=width){
for(x=0; x < width; x++){
a[ yOffset + x ] = x + y; // or whatever
}
}

You''re right, though; when you''re accessing a single arbitrary element, there''s not much difference.

QuaXiFalen, I think it''s better under Windows to have one big chunk. It''s kinda like how they''re promoting the use of VirtualAlloc() on their SDK, which is where you "reserve" a big chunk and then allocate within the chunk.

Share this post


Link to post
Share on other sites
QuaXiFalen, from the 2 examples that you gave I would go with the first and allocate just one array. It will save you a lot of trouble in the long run. It is easier to delete and allocate a single array. This may not be a problem to you, but based on you second example, the multidimensional array may not be contiguous.
I prefer one large chunk at all times. You also run a greater risk of memory leaks and other bad memory things.

Domini

Share this post


Link to post
Share on other sites
Ok guys...

Prog Course 101
Today: The Multi dimentional Array

If you are using MSVC (which I'm assuming you are), the following structures are both the same:


int Toto[100];
int Popo[10][10];


Why is that? Because the compiler understand what you are trying to do, and convert this:

Popo[2][3]=1;

into this:

Popo[2*10+3]=1;


Now that's logical... Totally logical. No more logic than that.

Thanks.

Now we will change a bit our course and go over DYNAMIC ARRAYS.



Prog Course 101
Today: The Multi dimentional dynamic Array

Say we declare those variables:

int *Titi = new int[100];
int **Pipi = new int*[10];


We have Titi who is the exact same as Toto (there are differences because the compiler will faster Toto, but that's out of the point). But what is Pipi?
By definition, Pipi is a pointer to a pointer of integer. It means that when you allocate a
new int*[10] 
you allocate an array of pointer. Logical, isn't it?

Ok now what you have to do with Pipi is allocate each pointers to arrays... with this:

for(int j=0; j < 10; j++)
Pipi[j] = new int[10];

And from now on we can access to Pipi the same way as Popo.

But if you think Pipi is the same as Popo, you are totally wrong. The compiler, super-intelligent form of pure knowledge, will act differently with Pipi and Popo... In fact, Popo will be a single pointer and Pipi will be an array of pointers, which means that
Pipi[2][3]=1 
will be transformed into:

*(*(Pipi+2)+3)=1;

instead of:

*(Titi+2*10+3)=1;


Which means WHAT? In assembly language, Popo will be much faster than Pipi... and Toto and Titi will be more or less equals (that depends of the situations in which it is used... The compiler may want to tranform Titi into an array of pointers of arrays...)

(( Man I love those variables name... ))


Am I right?


Edited by - Poltras on June 19, 2000 5:34:26 PM

Share this post


Link to post
Share on other sites
Thanks to everyone for posting!

Since I''m making dynamic arrays, I''ll use the one dimensional method. I used that initially, than i switched to two-dimensional, ''cause I thought it seemed more "correct" somehow. But I think I''ll go back to one-dimensional.

Actually, my reasoning for using two-dimensional arrays was that may be it would be easier for the system to find the memory since it doesn''t have to be all linear (a "height" number of seperate linear "width" chunks) but I don''t think this makes much of a difference, and the one-dimensional dereference is faster.

(By the way, Domini, I''m from MD too! Where are you at? I''m in Baltimore )

Share this post


Link to post
Share on other sites
This isnt about multi-D arrays, but you guys are sooo good at array stuff I figured you might be able to help... I have an array of type TSetEntry TileCache*[256]. TSetEntry is a struct with a BITMAP struct and a few other variables. What I want to do is when a unique tile is read in from the tileset file, TileCache = new TSetEntry; where i = TSetEntry.iIndex. I posted about this a couple of days ago, but got nothing useful.

Here is the code:

//World is a 1-D array of type GridStruct (map points)...
//TileCache is TSetEntry TileCache*[256]

while(i < MHeader_t.iNumGrids) //MHeader_t.iNumGrids =
MapSizeX + MapSizeY
{
while(j < World[i].iNumTiles) //up to 3 tiles per grid
{
//if this tile# not already loaded
if(bTileLoaded[World[i].iTileIndex[j]] == false)
{
//*****FIX THIS*****
//allocate TSetEntry pointer
TileCache[World[i].iTileIndex[j]] = new TSetEntry;
//seek to entry point in the file
hInTSet.seekg(THeader_t.lByteOffsets[World[i].iTileIndex[j]],
ios::beg);

//read in bitmap
hInTSet.read(reinterpret_cast
(TileCache[World[i].iTileIndex[j]]),
THeader_t.lEntrySizes[World[i].iTileIndex[j]]);

//tile# loaded successfully (eventually!!)
bTileLoaded[World[i].iTileIndex[j]] = true;
}

j++;
}

j = 0; //reset TileIndex counter
i++;
}

This code gives an Access Violation on the hInTSet.read() statement. I cant figure out why.... Im telling the damn thing how big the TSetEntry is... Im probably not allocating the array of pointers right. Well there it goes, please tell me how wrong I am so I can move on to the next step. =)

Share this post


Link to post
Share on other sites