Эффективность формата массива комплексных чисел для обычных операций - PullRequest
Новая
       45

Эффективность формата массива комплексных чисел для обычных операций

4 голосов
/ 14 февраля 2012

Другой человек в моем офисе и я вступили в дискуссию о том, какой формат массива матрицы комплексных чисел более эффективен: хранение действительных и мнимых частей с чередованием, как в 

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

или сохраняя действительные и мнимые части матрицы отдельно: 

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

С одной стороны, Complex[][] является более простым представлением массива комплексных чисел, и с ним может быть проще работать поэлементно; с другой стороны, кажется, что CArray может быть более эффективным в целом. Например, умножение матриц может быть выполнено с использованием 4 умножений матриц массивов компонентов с использованием формата CArray, в то время как формат Complex[][] выглядит так, как будто он может пострадать из-за чередования между элементами (так как (a + bi) * ( c + di) = (ad - bc) + (ac + bd) i). Очевидно, MATLAB использует последний формат: введите описание ссылки здесь .

Есть ли другие источники, которые относятся к этому вопросу?

1 Ответ

3 голосов
/ 22 февраля 2012

Это старый вопрос "массив структур против структуры массивов", применяемый к комплексным числам.Как и большинство вопросов производительности, в общем случае ответ «это зависит», но в этом случае я бы положил деньги на версию массива структур.

Ключом к выбору эффективных структур данных для численных вычислений является сохранениеДанные, которые вам, как правило, понадобятся одновременно в памяти друг друга.Выход в основную память для получения данных идет медленно;Вы хотите вводить один кэш данных за раз в кеш и максимально использовать всю эту строку кеша.Поскольку вам почти всегда понадобится как действительный, так и мнимый компоненты комплексного числа для наиболее значимых вычислений, хранение их в виде массивов (реальных, мнимых) пар означает, что если вы работаете с реальным компонентом, мнимый компонентпочти всегда будет сидеть там уже в кеше, готовом к вычислению.

Но это зависит от шаблонов доступа.Просто потому, что операции, которые я представляю, получат выгоду от массива комплексных чисел, не означает, что вы представляете себе те же самые;другие могут извлечь выгоду из подхода с двумя массивами.Если бы у вас было много операций над матрицами A и B, таких как Re (A) * Im (B) - что бы это значило, я не знаю, но все же - тогда я думаю, что в подходе CArray, скорее всего, будет значительно быстреепоскольку вам не придется тратить пропускную способность памяти, загружая данные, которые вам не нужны (например, Im (A) и Re (B).)

В конечном счете, это эмпирический вопрос;Если у вас есть представление о том, каков ваш набор шаблонов доступа, то достаточно просто проверить оба подхода.Но для шаблонов, которые я могу легко представить, победит первый подход.

Тот факт, что Matlab не согласен со мной, согласно вашей ссылке, удивляет меня настолько, что почти заставляет меня сомневаться в моем ответе.Я не большой поклонник Matlab, но люди Matlab умны и озабочены тем, как быстро выполнять численные вычисления.Но это одно из тех решений, которые после принятия невероятно сложно отменить - Matlab не может изменить такой фундаментальный макет данных сейчас, не нарушив миллиарды других вещей, своих и сторонних, - и решение, вероятно, было принятодесятилетия назад, когда производительность кэша была менее важной, а совместимость с некоторыми библиотеками, вероятно, имела большее значение.Я отмечаю, что такие пакеты, как Lapack, основаны на другом формате, массиве структур (хотя и неявно - в Fortran комплекс является типом данных примитивов, по крайней мере, с FORTRAN 66).

...