2D arrays

[dragonslayer008]

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?

 

[Victor Bazarov]

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

 

[Mark P]

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

 

[Victor Bazarov]

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

If the entire array fits in the processor cache, the order of element
access may not matter. Only measurement could show exactly what is
happening and when. That's why trying to optimize what's not working
is pointless.

V

 

[James Kanze]

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];

Which is bullshit. The compiler will normally generate exactly
the same code for the first as that which you write for the
second.

The second may be faster if you iterator over the entire array,
because it would only require a single loop, rather than nested
loops. I imagine that most compilers would convert the nested
loops into a single loop, however, if optimization is turned on.

In any event, you have to measure for your compiler.