Victor Bazarov wrote:
> dragonslayer008@hotmail.com wrote:
>> instead of using 2D arrays:
>>
>> int A[m][n];
>>
>> I heard it was faster/preferred to use a 1D array to simulate:
>>
>> int A[m*n];
>>
>> Can someone explain why? Is it merely the double dereference you need
>> to do with the 2D array?
>
> There is no "double dereference". A simple calculation is performed,
> and if you simulate a 2D array, you will have to perform the offset
> calculation instead of letting the compiler generate the code to do
> that for you.
>
> There is no real advantage _unless_ you can prove that whatever you
> write is truly faster. In most cases it involves rewriting your
> algorithm[s] to be a single loop instead of double, and providing
> a custom addressing scheme for each.
>
> Most often it's not worth the trouble, but sometimes it is. You
> need to show that operations on your 2D arrays are really slow and
> mostly due to [frequent] calculation of the element addresses. Do
> not try to optimize what you don't have working yet.
>
> V

On a related note, spatial locality of successive array accesses can be
important here too. That is, for an array A[m][n], one may see
significantly better performance when performing the iteration over
successive n for each m, rather than vice versa. This amounts to
contiguous memory access in the underlying 1D array rather than making
large jumps.

Mark