Структура массивов и массив структур - разница в производительности

У меня есть класс вроде этого:

//Array of Structures
class Unit
{
  public:
    float v;
    float u;
    //And similarly many other variables of float type, upto 10-12 of them.
    void update()
    {
       v+=u;
       v=v*i*t;
       //And many other equations
    }
};

Я создаю массив объектов типа Unit. И назовите обновление для них.

int NUM_UNITS = 10000;
void ProcessUpdate()
{
  Unit *units = new Unit[NUM_UNITS];
  for(int i = 0; i < NUM_UNITS; i++)
  {
    units[i].update();
  }
}

Чтобы ускорить работу и, возможно, автоматизировать цикл, я преобразовал AoS в структуру массивов.

//Structure of Arrays:
class Unit
{
  public:
  Unit(int NUM_UNITS)
  {
    v = new float[NUM_UNITS];
  }
  float *v;
  float *u;
  //Mnay other variables
  void update()
  {
    for(int i = 0; i < NUM_UNITS; i++)
    {
      v[i]+=u[i];
      //Many other equations
    }
  }
};

Когда цикл не работает autovectorize, я получаю очень плохую производительность для структуры массивов. Для 50 единиц обновление SoA немного быстрее, чем AoS. Но затем от 100 единиц вперед, SoA медленнее, чем AoS. В 300 единиц, SoA почти в два раза хуже. При 100K единицах SoA в 4 раза медленнее, чем AoS. Хотя кеш может быть проблемой для SoA, я не ожидал, что разница в производительности будет такой высокой. Профилирование на cachegrind показывает аналогичное количество промахов для обоих подходов. Размер объекта Unit равен 48 байтам. Кэш L1 составляет 256 КБ, L2 - 1 МБ, а L3 - 8 МБ. Что мне здесь не хватает? Это действительно проблема с кешем?

Edit: Я использую gcc 4.5.2. Параметры компилятора: -o3 -msse4 -ftree-vectorize.

Я сделал еще один эксперимент в SoA. Вместо динамического выделения массивов я выделял "v" и "u" во время компиляции. Когда есть 100K единиц, это дает производительность, которая в 10 раз быстрее, чем SoA с динамически распределенными массивами. Что тут происходит? Почему существует такая разница в производительности между статической и динамически распределенной памятью?

Ответ 1

В этом случае структура массивов не является кэширующей.

Вы используете как u, так и v вместе, но в случае двух разных массивов для них они не будут загружаться одновременно в одну строку кеша, а промахи кеша будут стоить огромного штрафа за производительность.

_mm_prefetch можно использовать, чтобы сделать представление AoS еще быстрее.

Ответ 2

Предварительные выборки имеют решающее значение для кода, который проводит большую часть времени выполнения, ожидая появления данных. Современные боковые шины на передней панели имеют достаточную пропускную способность, которые должны быть безопасными для prefetches, при условии, что ваша программа не будет слишком далеко впереди ее текущего набора нагрузок.

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

float v[N];
float u[N];
    //And similarly many other variables of float type, up to 10-12 of them.
//Either using an inlined function or just adding this text in main()
       v[j] += u[j];
       v[j] = v[j] * i[j] * t[j];

Ответ 3

Конечно, если вы не достигнете векторизации, нет стимула для преобразования SoA.

Помимо довольно широкого де-факто принятия __RESTRICT, gcc 4.9 принял #pragma GCC ivdep, чтобы прервать предполагаемые зависимости наложения.

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

Я не думаю, что разумные комментарии могут быть сделаны о том, что вы называете распределением времени компиляции, без каких-либо подробностей, включая специфику вашей ОС. Нет никаких сомнений в том, что традиция распределения на высоком уровне и повторного использования распределения важна.