Back to General and Gameplay Programming

Arrays - One vs Multi-Dimensional

General and Gameplay Programming Programming

Started by QuaXiFalen June 18, 2000 10:51 PM

11 comments, last by QuaXiFalen 23 years, 10 months ago

QuaXiFalen

122

Author

June 18, 2000 10:51 PM

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

BigBlueMonkey

122

June 18, 2000 11:32 PM

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

Poltras

122

June 18, 2000 11:38 PM

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

Now I know what I'm made of, and I'm afraid of it...

QuaXiFalen

122

Author

June 19, 2000 11:28 AM

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

LowRad

234

June 19, 2000 11:58 AM

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

Poltras

122

June 19, 2000 01:37 PM

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

Now I know what I'm made of, and I'm afraid of it...

DeltaVee

138

June 19, 2000 01:47 PM

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.

D.V.Carpe Diem

Eric

138

June 19, 2000 02:47 PM

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.

Domini

126

June 19, 2000 03:02 PM

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

Domini Miracle Man Studios

Poltras

122

June 19, 2000 04:32 PM

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

Now I know what I'm made of, and I'm afraid of it...

Arrays - One vs Multi-Dimensional

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Arrays - One vs Multi-Dimensional

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines