複素数配列形式の私のオフィスでの一般的な操作

Question

もう一人のための効率と私は複素数マトリックスアレイフォーマットは、より効率的であるかについての議論に入った：のように、インターリーブされた実部と虚部を格納

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

または別々行列の実数部と虚数部を格納することによって：一方

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

を、Complex[][]は複素数の配列の直接的表現の複数であり、要素単位で作業しやすいかもしれません。一方で、CArrayがより一般的に効率的になる可能性があります。例えば、Complex[][]フォーマットは、（a + bi）*（c + di）の間にインターリーブされているように見えるが、CArrayフォーマットを使用して、コンポーネントアレイの4つ​​の行列乗算を使用して行列乗算を行うことができる。 =（ad-bc）+（ac + bd）i）となる。どうやら、MATLABは後者の形式を使用します：enter link description here。

この質問を扱う他の情報源はありますか？

Answer 1

これは、複素数に適用された年齢の古い「構造の配列対配列の構造」問題です。パフォーマンスに関するほとんどの質問と同様に、一般的に答えは「それは依存する」ですが、この場合は構造の配列の配列にお金を入れます。

数値計算のための効率的なデータ構造を選択するための鍵は、メモリ内でお互いの近くに同時に必要なデータを保持することです。データを取得するためにメインメモリに出るのが遅い。一度に1つのデータ・チャンクをキャッシュに取り込み、可能な限りそのキャッシュ・ラインのすべてを使用したいとします。ほとんどの意味のある計算では、複素数の実数成分と虚数成分の両方が必要なので、それらを（実数、虚数）ペアの配列として格納するということは、実数成分で作業している場合、虚数成分ほとんど常に計算される準備ができたキャッシュに既に座っています。

ただし、アクセスパターンによって異なります。私が想像している操作が複素数の配列の恩恵を受けようとしているからといって、同じものを想像しているわけではありません。他の人は2アレイアプローチの恩恵を受けることができます。あなたがRe（A）* Im（B）のようなmatricies AとBについてたくさんの操作をしていたなら、それは私には分かりませんが、それでもなお、CArrayアプローチではかなり速いでしょうあなたが必要としないデータ（例えば、Im（A）とRe（B））をロードすることによってメモリ帯域幅を無駄にする必要がないためです。

最終的に、これは実証的な質問です。あなたの組み合わせのアクセスパターンが何であるか考えているなら、2つのアプローチをテストするのは簡単です。しかし、私が最も簡単に想像できるパターンについては、最初のアプローチが勝つだろう。

Matlabが私の意見に同意できないという事実は、私の答えを疑うほどのものです。私は巨大なMatlabのファンではありませんが、Matlabの人々はスマートで、数値計算を高速化することを心配しています。しかしこれは一度作ったものを元に戻すことが信じられないほど難しい決定の1つです.Matlabは今やそのような基本的なデータレイアウトを変更することはできませんでした。数十年前、キャッシュのパフォーマンスがそれほど重要ではなく、特定のライブラリとの互換性はおそらくもっと重要でした。私は、Lapackのようなパッケージは他のフォーマット、構造体の配列に基づいていることに注意します（ただし、Fortranでは、少なくともFORTRAN 66以来、複合体は基本データ型でした）。