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

Have you profiled both? This will answer your question.

Have you also looked at the assembly output of your compiler in both cases? I would take a a look if I was you.

Quote:

Original post by darookie Have you profiled both? This will answer your question.

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

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.

Both versions are dangerous because they dont use RAII.

std::vector< std::vector<int> > my2darray(xsize, std::vector<int>(ysize));

does

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.

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

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.

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

In this case, the [x+w*y] version would be faster as there is no extra dereferencing happening, and the data will all be in one place, not scattered all over the place causing lots of cache misses. It'll even use less memory. What a deal.

Does anybody remember the bit shift trick from the old days of vga mode 13?

pixel[(x << 8) + (x << 6) + y] = colour;

Quote:

by Fractoid Faster yet is: bob[x+(y<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.

and

Quote:

by smr Does anybody remember the bit shift trick from the old days of vga mode 13? pixel[(x << 8) + (x << 6) + y] = colour;

how do these work? i tried these and they seem to skip some numbers...

Quote:

Original post by Alpha_ProgDes Quote: by Fractoid Faster yet is: bob[x+(y<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. and Quote: by smr Does anybody remember the bit shift trick from the old days of vga mode 13? pixel[(x << 8) + (x << 6) + y] = colour; how do these work? i tried these and they seem to skip some numbers...

Bit shifts only work well when working with specific resolutions. The first one only works with 2D arrays that have a width that is a power of 2. For example, if an image is 256 by whatever, then you would use [x + (y << 8)] as the index, since (y << 8) == (y * 2⁸) == (y * 256). The second one uses multiple bitshifts to achieve doing the same for numbers that are combinations of powers of 2. (y << 8) + (y << 6) == (y * 256) + (y * 64) == (y * 320). Mode 13 was 320 by 240, and thus you got the width of 320 multiplication going on.

y is the height right?

so 320 x 640 would map out to X x Y which would be width x height.

right?

Quote:

Original post by Alpha_ProgDes y is the height right? so 320 x 640 would map out to X x Y which would be width x height. right?

320x240, other than that; yes, you're correct.

Sorry My mistake... I didn't read the creation method for the first case, so i thought it was just another case of 'does it compile to the same thing'.

An array of pointers, pointing to a linear array, the only time i would go with that is when i plan on swapping the linear arrays around... a simple pointer swap instead of a copy, otherwise i'd pretty much stick with method two since there's less indirection as others have already said.

The faster one is the one that is less flexable, as is often the case. I would use either, depending on whether I needed speed, or flexability.
Most often that would be case two.

go with smart_idiot's suggestion, he's smarter than you think.

Quote:

Original post by DEVLiN Quote: Original post by Alpha_ProgDes y is the height right? so 320 x 640 would map out to X x Y which would be width x height. right? 320x240, other than that; yes, you're correct.

320x200

Ahh, the good old days... mode13h was so fun.

< sorry for the double post. above was me! >

/edit:

I noticed the following when the width/height values are set to a power of 2 (1024 in this case):

x86 Family 15 Model 2 Stepping 9 at 2394 MHzTesting linear... ... result: 3176Testing linearmatrix... ... result: 135Testing matrix... ... result: 627Done!

Speed with non-power of 2:
1. [y*w+x]
2. [x,y]
3. [x][y]

Speed with powers of 2:
1. [y*w+x]
3. [x][y]
2. [x,y]

Note that when using powers of two, the performance is quite higher. Also, the differences between position 1, 2, and 3 are huge.

By the way, when looking at the processor usage when running the [,] test, I noticed that the processor usage jumps up/down, while staying steady high with the linear method.

/edit2:

I also ran a test with the resolution mentioned above:

x86 Family 15 Model 2 Stepping 9 at 2394 MHzTesting linear... ... result: 13793Testing linearmatrix... ... result: 4701Testing matrix... ... result: 3698Done!

That's clear:
1. []
2. [,] far behind
3. [][] close

[Edited by - Sijmen on October 8, 2004 4:44:34 AM]