常见运算的复数数组格式效率

Question

我办公室的另一个人和我讨论了哪种复数矩阵数组格式更有效:交错存储实部和虚部，如下所示

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

或者通过分别存储矩阵的实部和虚部：

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

一方面，Complex[][]更多地是一种简单的复数组表示，并且可能更容易处理元素；另一方面，CArray似乎在一般情况下可能更高效。例如，矩阵乘法可以使用使用CArray格式的分量阵列的4个矩阵乘法来完成，而Complex[][]格式似乎由于元素之间的交织而受到影响(因为(a+bi)*(c+di) = (ad - bc) + (ac + bd)i)。显然，MATLAB使用后一种格式：enter link description here。

有没有其他关于这个问题的资料？

Answer 1

这是一个古老的“结构数组与数组结构”的问题，适用于复数。像大多数性能问题一样，通常答案是“视情况而定”，但在这种情况下，我会把我的钱押在结构数组版本上。

为数值计算选择有效数据结构的关键是将通常同时需要的数据保存在内存中。到主存获取数据的速度很慢；您希望一次将一个数据块放入缓存中，并尽可能多地使用所有缓存线。因为对于大多数有意义的计算，你几乎总是需要复数的实部和虚部，所以将它们存储为(实部，虚部)对的数组意味着，如果你正在处理实部，虚部几乎总是已经在缓存中，准备进行计算。

但这取决于访问模式。仅仅因为我想象的操作将从复数组中受益，并不意味着您正在想象相同的操作；其他操作可以从双数组方法中受益。如果你在矩阵A和B上有很多像Re(A)*Im(B)这样的操作-这意味着什么，我不知道，但仍然-那么我认为在CArray方法中可能会快得多，因为你不必通过加载不需要的数据来浪费内存带宽(例如，Im(A)和Re(B))。

归根结底，这是一个经验性的问题；如果您知道您的访问模式的组合是什么，那么测试这两种方法就足够容易了。但对于我最容易想象的模式，第一种方法将获胜。

根据你的链接，Matlab不同意我的观点，这一事实让我大吃一惊，几乎让我怀疑我的答案。我不是Matlab的狂热粉丝，但Matlab的人很聪明，他们关心的是如何快速地进行数值计算。但这是其中一个决定，一旦做出，就很难撤销- Matlab现在无法改变如此基本的数据布局，而不会破坏自己和第三方的无数其他东西-这个决定可能是几十年前做出的，当时缓存性能不那么重要，与某些库的兼容性可能更重要。我注意到像Lapack这样的包基于另一种格式，结构数组(尽管只是隐式地--在Fortran中，complex至少从FORTRAN 66开始就是一种原始数据类型)。