Jump to content
  • Advertisement
Sign in to follow this  
Lyve

What is faster? [x][y] or [y*w+x]?

This topic is 5395 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello members, What technique would you use to create arrays with more than one dimension? First method:
// first method: creation
int** my2darray = new int*[xsize];
for( unsigned int x=0; x<xsize; x++ )
	my2darray = new int[ysize];

// first method: access
int val = my2darray[x][y];


// second method: creation
int* my2darray = new int[xsize*ysize];

// second method: access
int val = my2darray[y*xsize+x];

Which one is faster?

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by darookie
Have you profiled both? This will answer your question.

He wouldn't be asking if he had done so.

Share this post


Link to post
Share on other sites
Quote:
Original post by antareus
Quote:
Original post by darookie
Have you profiled both? This will answer your question.

He wouldn't be asking if he had done so.
It's the polite way of telling him what he already should have done.

Share this post


Link to post
Share on other sites
In version 1, you dereference my2darray, then you dereference my2darray[x].

In version two, you dereference just once, my2darray[y*xsize+x].

So the access using method two should be twice as fast.

Share this post


Link to post
Share on other sites
Neither. It depends on your architecture, and micro-optimizing at this level is really a waste of time unless you know that your code *has* to run in 25 microseconds on an i386EX (just for example).

Generally:
bob[x][y] ~= bob[x+y*stride]
(depends on the relative speeds of int multiplication and memory access, ie. mult is faster on high end CPUs and extra memory access probably faster on slower (pentium and below) chips)

Faster yet is:
bob[x+(y<<shift)]
if you're really choking for speed, but as I said before, it's not really worth it. Your code probably has opportunities for much greater gains at the algorithmic level.

Share this post


Link to post
Share on other sites
For static arrays both access methos are as good.
For dynamic arrays the second is better. It takes less memory(x*pointers + x*y*size of type vs 1*pointer + x*y*size of type), the memoty is allocated in continuous block and it's easier to allocate and deallocate. The access time is also faster because the row size is constant. I personally always use the second if the array is width*height. The first is good for varying row size.

Share this post


Link to post
Share on other sites
I'd prefer the single dimension version and using pointer arithmetics to access data (linearly in one way or the other would be with addition instead of multiplication), if you truly have to use arrays like that. (don't know your platform nor your data access patterns, so hard to give proper advice)

That being said, optimize your real bottlenecks instead of this to begin with. Premature optimization is the root to much evil :p

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!