Complex array format efficiency for general operations

Question

Another person in my office, and I discussed which complex array matrix format is more efficient: storing the real and imaginary parts alternates, as in

struct { double real; double imag; } Complex foo[m][n]; 

or by storing the real and imaginary parts of the matrix separately:

 struct { double rarray[m][n]; double iarray[m][n]; } CArray foo; 

On the one hand, Complex[][] is a simpler representation of an array of complex numbers and it may be easier to work on an element; on the other hand, it seems that CArray may be more efficient overall. For example, matrix multiplication can be performed using 4 matrix multiplications of component arrays using the CArray format, while the Complex[][] format looks as if it might suffer due to the alternation of elements (since (a + bi) * (c + di) = (ad-bc) + (ac + bd) i). MATLAB seems to use the latter format: enter the link here .

Are there any other sources that are considering this issue?

Answer 1

This is an age array called “array of structures versus array structure” that applies to complex numbers. Like most performance issues, in general the answer is "it depends", but in this case I would put my money in an array of versions of structures.

The key to choosing effective data structures for numerical calculations is to save data, which, as a rule, you will need at the same time next to each other in memory. The transition to the main memory for receiving data is slow; you want to add one piece of data to the cache at the same time and make the most of this entire cache line. Since for most meaningful calculations you almost always need both a real and an imaginary component of a complex number, storing them as arrays of (real, imaginary) pairs means that if you are working on a real component, the imaginary component will almost always sit there in the cache ready for calculation.

But it depends on access patterns. Just because the operations that I assume will be useful from an array of complex numbers does not mean that you imagine the same ones; others may benefit from a two-array approach. If you had a lot of operations on matrices A and B, like Re (A) * Im (B) - what would it mean, I don’t know, but still - then I think that, most likely, it will be much faster in CArray's approach, since you won’t need to waste memory space by loading data that you don’t need (for example, Im (A) and Re (B).)

Ultimately, this is an empirical question; if you have an idea of ​​what your combination of access patterns is, just check two approaches. But for models that I can easily imagine, the first approach will win.

The fact that Matlab disagrees with me, through your link, surprises me so much that I almost doubt my answer. I'm not a big fan of Matlab, but Matlab people are smart and concerned about fast computing. But this is one of those decisions that were once made, it is incredibly difficult to cancel - Matlab could not change such a fundamental data layout without violating any other things, both its own and third-party ones, and the decision was probably made several decades ago. when cache performance was less important, and compatibility with some libraries was probably more important. I note that packages such as Lapack are based on a different format, an array of structures (albeit implicitly - in Fortran, complex was a primitive data type since at least FORTRAN 66).