C ++ дружественный к кешу способ доступа ко всем элементам всех элементов `vector <struct_type>` - PullRequest
Новая
       18

C ++ дружественный к кешу способ доступа ко всем элементам всех элементов `vector <struct_type>`

5 голосов
/ 28 ноября 2011

Я заинтересован в оптимизации моего кода для многопоточных вычислений.Что касается кеша, конвейерной обработки или любых других аспектов доступа к памяти, как можно сравнить следующие показатели при сохранении этих ресурсов:

Случай 1 

struct something{
    float a;
    float b;
    int c;
    bool d;
};

vector <something> vec(n, something());

for(int q=0; q<n; q++)
    {
         vec[q].a = expression1;
         vec[q].b = expression2;
         vec[q].c = expression3;
         vec[q].d = expression4;
    }

Случай 2 

struct something{
    float a;
    float b;
    int c;
    bool d;
};

vector <something> vec(n, something());

for(int q=0; q<n; q++)
    vec[q].a = expression1;
for(int q=0; q<n; q++)
    vec[q].b = expression2;
for(int q=0; q<n; q++)
    vec[q].c = expression3;
for(int q=0; q<n; q++)
    vec[q].d = expression4;

Случай 3 

vector <float> a(n);
vector <float> b(n);
vector <int>   c(n);
vector <bool>  d(n); 

for(int q=0; q<n; q++)
    a[q] = expression1;
for(int q=0; q<n; q++)
    b[q] = expression2;
for(int q=0; q<n; q++)
    c[q] = expression3;
for(int q=0; q<n; q++)
    d[q] = expression4;

Кроме того, есть ли лучшие способы приблизиться к вышесказанному?

Ответы [ 3 ]

3 голосов
/ 28 ноября 2011
  • Случай 1 является наиболее читабельным.
  • Дело 1 и дело 3 одинаково дружественно к кешу. Оба делают только один проход через все данные. *
  • Случай 2 является наихудшим, потому что он делает 4 прохода по данным - каждый проход касается только одного элемента.

Если все поля структуры различны, то case 3 имеет огромное преимущество, заключающееся в возможности векторизации, тогда как case 1 - нет.

Причина этого в том, что case 3 - это структура структуры массивов , которая последовательно объединяет все те же типы данных в памяти, тем самым подвергая векторизации.

РЕДАКТИРОВАТЬ:

* Случай 3 потенциально еще более дружественен к кэшу, чем случай 1 , потому что он не нуждается в заполнении структурой - поэтому размер данных меньше.

1 голос
/ 28 ноября 2011

С точки зрения доступа к кэшу случай 2 явно худший: он перезагрузит память в кэш 4 раза.

случай 3 такой же, как случай 1 при заполнении данных, но может быть хуже для последующего использования(при условии, что a b c d связаны и, вероятно, будут прочитаны вместе).

Этот вариант даже лучше, чем в случае 1: 

for (vector<something>::iterator it = vec.begin(); it != vec.end(); ++it)
{
    it->a = e1;
    it->b = e2;
    it->c = e3;
    it->d = e4;
}

То, что будет быстрее, зависит от многих вещей.Например, вычисление сложных выражений в неправильном порядке может быть намного хуже, чем любые пропуски кэша.Вы никогда не должны делать чисто теоретический выбор без реального профилирования.

0 голосов
/ 28 ноября 2011

Случай 1 - лучший.Случай 3 так же хорош с точки зрения доступа к кэшу, но он имеет незначительное снижение производительности из-за дополнительных циклов.Случай 2 - это то, что вы должны избегать.

Но почему бы вам не выполнить некоторые тесты и сообщить нам результаты?

...