Войти
ПрограммированиеСтатьиОбщее

Data Oriented Design. Виртуальные функции.

Внимание! Этот документ ещё не опубликован.

Автор:

Data Oriented Design. Виртуальные функции.

Источник: http://petecubano.wordpress.com/2010/12/20/data-oriented-design-the-numbers/

Прим.: В некоторых местах изложение статьи идет от лица автора.

В недавнем времени была довольно интересная дискуссия по поводу DOD (Data Oriented Design). Я последовал некоторым аргументам из дискуссии, и мне захотелось опробовать эту технику самостоятельно. Что немаловажно, я – программист, помешанный на оптимизации. Мне захотелось убедиться в том, что DOD дает очень большой рост производительности. Действительно, могут ли виртуальные функции или несколько дополнительных байт в структуре, спустя 30 лет после выхода процессоров x86, быть настолько важными в отношении производительности?

Чтобы это выяснить, определим пару объектов – Car и Truck. Следуя правилам традиционного ООП, и учитывая то, что оба эти объекта могут передвигаться, сделаем их наследуемыми от класса Movable. Затем будем обновлять эти объекты каждый кадр, как это было бы в игре.

typedef vec_type ...;

class Movable
{
  vec_type pos;
  vec_type speed;
  virtual void update(float timestep)
  {
    pos += speed * timestep;
  }
};

class Car : public Movable
{
  void* model;
  void* wheels[4];
  void* damage;
  void* driver;
  int type;
  virtual void update(float timestep)
  {
    Movable::update(timestep);
  }
};

class Truck : public Movable
{
  void* model;
  void* wheels[6];
  void* damage;
  void* driver;
  int type;
  virtual void update(float timestep)
  {
    Movable::update(timestep);
  }
};

Это выглядит не сложно. Я добавил несколько полей данных для классов Car и Truck, чтобы их можно было добавлять в кэш при обновлении каждого объекта.

Теперь об update-менеджерах. Я написал несколько разных update-менеджеров, чтобы протестировать разные способы обновления объектов типа Movable. Как мне кажется, наихудший из них – вектор std::vector указателей на объекты Cars & Trucks. Все объекты «обновлены», так что они не могут быть расположены в памяти последовательно, отсюда получаем большие потери в кэше.

#define NUM_OBJECTS 1000000

class VectorUpdateManager
{
  vector<Movable<vec_type>*> objects;
  /* constructors, etc */
  void update(float timestep)
  {
    for (auto it = objects.cbegin(); it != objects.cend(); ++it)
    {
      auto object = *it;
      object->update(timestep);
    }
  }
};

Следующая реализация update-менеджера – массив фиксированного размера вместо вектора, что позволит нам избавиться от потери производительности обновления итератора вектора. По-прежнему используются указатели, так что данные не расположены последовательно.

class VectorUpdateManager
{
  Movable<vec_type>* objects[NUM_OBJECTS];
  /* constructors, etc */
  void update(float timestep)
  {
    for (int i = 0; i < NUM_OBJECTS; i++)
    {
      objects[i]->update(timestep);
    }
  }
};

Следующий способ – массив фиксированного размера для кажого типа объекта Car & Truck. В этом случае, отказавшись от указателей, гарантируется последовательное размещение данных в памяти. Этот метод должен помочь избежать больших потерь в кэше.

class VectorUpdateManager
{
  Car<vec_type> cars[NUM_OBJECTS / 2];
  Truck<vec_type> trucks[NUM_OBJECTS / 2];
  /* constructors, etc */
  void update(float timestep)
  {
    for (int i = 0; i < NUM_OBJECTS / 2; i++)
    {
      cars[i].update(timestep);
    }
    for (int i = 0; i < NUM_OBJECTS / 2; i++)
    {
      trucks[i].update(timestep);
    }
  }
};

И последний способ реализации – Data Oriented Design – массив фиксированного размера, типа Movable. Отсутствуют виртуальные вызовы и данных столько, сколько необходимо для их обновления.

class VectorUpdateManager
{
  Movable<vec_type> objects[NUM_OBJECTS];
  /* constructors, etc */
  void update(float timestep)
  {
    for (int i = 0; i < NUM_OBJECTS; i++)
    {
      objects[i].update(timestep);
    }
  }
};

Результаты

4 способа: вектор указателей, массив указателей, два массива объектов, и DOD.


Цифры такие (время выполнения в мкс):

Вектор указателей: 86961
Массив указателей: 77188
Два массива объектов: 71645
Data Oriented Design: 37521

Переход от вектора к массиву указателей, от массива указателей к массиву объектов дает по 10% увеличения производительности. Однако, Data Oriented Design дает 100% увеличение производительности! Update-менеджер в реальных играх намного сложнее, однако, эти примеры показывают, что устранение виртуальных функций в значительной степени влияет на производительность.

Из комментариев

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

Что ж, усложнив функцию и добавив в нее простейшее определение коллизий, получились следующие показатели (врем выполнения в мкс):

Вектор указателей: 118566
Массив указателей: 100268
Два массива объектов: 87025
Data Oriented Design: 70832

Теперь DOD дает порядка 60% производительности относительно способа с вектором.

#C++

18 февраля 2011

Комментарии [80]