Data Oriented Design - нецелесообразно с более чем 1-2 структурными «членами»?

23

Обычный пример Data Oriented Design со структурой Ball:

struct Ball
{
  float Radius;
  float XYZ[3];
};

а затем они делают некоторый алгоритм, который повторяет std::vector<Ball>вектор.

Затем они дают вам то же самое, но реализованное в Data Oriented Design:

struct Balls
{
  std::vector<float> Radiuses;
  std::vector<XYZ[3]> XYZs;
};

Это хорошо, и все, если вы собираетесь сначала пройти все радиусы, затем все позиции и так далее. Тем не менее, как вы перемещаете шары в векторе? В оригинальной версии, если у вас есть std::vector<Ball> BallsAll, вы можете просто переместить любой BallsAll[x]в любой BallsAll[y].

Однако, чтобы сделать это для версии, ориентированной на данные, вы должны сделать то же самое для каждого свойства (2 раза в случае Ball - радиус и положение). Но это становится хуже, если у вас есть намного больше свойств. Вы должны будете сохранить индекс для каждого «шара», и когда вы пытаетесь переместить его, вы должны сделать движение в каждом векторе свойств.

Разве это не убивает какой-либо выигрыш в производительности от Data Oriented Design?

улак клинок
источник

Ответы:

23

Другой ответ дал превосходный обзор того, как вы бы хорошо инкапсулировали хранилище, ориентированное на строки, и дали лучший обзор. Но так как вы также спрашиваете о производительности, позвольте мне ответить на это: макет SoA - это не серебряная пуля . Это довольно хорошее значение по умолчанию (для использования кэша; не так много для простоты реализации на большинстве языков), но это еще не все, даже в ориентированном на данные дизайне (что бы это ни значило). Возможно, что авторы некоторых прочитанных вами введений упустили этот момент и представили только макет SoA, потому что они думают, что в этом весь смысл DOD. Они были бы неправы, и, к счастью, не все попадают в эту ловушку .

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

Однако есть и вторая сторона DOD. Вы не получите всех преимуществ кеша и организации, просто повернув компоновку памяти на 90 ° и сделав минимум усилий для исправления ошибок компиляции. Есть и другие распространенные приемы, которые преподаются под этим знаменем Например, «обработка на основе существования»: если вы часто деактивируете шары и повторно активируете их, не добавляйте флаг к объекту шара и заставляйте цикл обновления игнорировать шары с флагом, установленным в false. Переместите шарик из «активной» коллекции в «неактивную» коллекцию и заставьте цикл обновления проверять только «активную» коллекцию.

Что более важно и актуально для вашего примера: если вы тратите так много времени на перетасовку массива шаров, возможно, вы делаете что-то не так. Почему заказ имеет значение? Можете ли вы сделать это не имеет значения? Если это так, вы получите несколько преимуществ:

  • Вам не нужно перетасовывать коллекцию (самый быстрый код - это вовсе не код).
  • Вы можете добавлять и удалять более легко и эффективно (поменять местами, бросить последними).
  • Оставшийся код может стать пригодным для дальнейшей оптимизации (например, изменение макета, на котором вы сосредоточены).

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

Сообщество
источник
18

Ориентированное на данные мышление

Дизайн, ориентированный на данные, не означает применение SoAs везде. Это просто означает проектирование архитектур с преимущественным акцентом на представление данных - в частности, с упором на эффективную компоновку памяти и доступ к памяти.

Это может привести к повторениям SoA, когда это уместно, так:

struct BallSoa
{
   vector<float> x;        // size n
   vector<float> y;        // size n
   vector<float> z;        // size n
   vector<float> r;        // size n
};

... это часто подходит для вертикальной петлевой логики, которая не обрабатывает компоненты вектора центра радиуса и радиус одновременно (четыре поля не являются одновременно горячими), но вместо этого по одному за раз (цикл через радиус, еще 3 цикла через отдельные компоненты сферных центров).

В других случаях было бы более целесообразно использовать AoS, если к полям часто обращаются вместе (если ваша циклическая логика выполняет итерации по всем полям шаров, а не по отдельности) и / или если необходим произвольный доступ к шару:

struct BallAoS
{
    float x;
    float y;
    float z;
    float r;
};
vector<BallAoS> balls;        // size n

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

struct BallAoSoA
{
    float x[8];
    float y[8];
    float z[8];
    float r[8];
};
vector<BallAoSoA> balls;      // size n/8

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

struct BallAoSoA16
{
    Float16 x2[16];
    Float16 y2[16];
    Float16 z2[16];
    Float16 r2[16];
};
vector<BallAoSoA16> balls;    // size n/16

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

struct BallAoSoA16Hot
{
    Float16 x2[16];
    Float16 y2[16];
    Float16 z2[16];
};
vector<BallAoSoA16Hot> balls;     // size n/16: hot fields
vector<Float16> ball_radiuses;    // size n: cold fields

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

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

Преждевременная оптимизация

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

Тем не менее, возможно, сильное послание, которое следует извлечь из дизайна, ориентированного на данные, - это оставить место для такой оптимизации. Вот что может помочь ориентированный на данные образ мыслей:

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

Гранулированный объектно-ориентированный дизайн

Многие дискуссии по проектированию, ориентированному на данные, натолкнутся на классические понятия объектно-ориентированного программирования. Тем не менее, я бы предложил способ взглянуть на это, который не настолько хардкорный, как полное отклонение ООП.

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

В качестве преувеличенного примера представьте объектно-ориентированный дизайн мышления, примененный к одному пикселю изображения.

class Pixel
{
public:
    // Pixel operations to blend, multiply, add, blur, etc.

private:
    Image* image;          // back pointer to access adjacent pixels
    unsigned char rgba[4];
};

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

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

Теперь нет ничего плохого с классом в смысле непосредственных издержек в контексте C ++, кроме этого обратного указателя. Оптимизация компиляторов C ++ прекрасно подходит для того, чтобы взять всю построенную нами структуру и уничтожить ее вдребезги.

Сложность в том, что мы моделируем инкапсулированный интерфейс на слишком гранулярном уровне пикселей. Это оставляет нас в ловушке с таким типом детального проектирования и данных, потенциально огромным количеством клиентских зависимостей, связывающих их с этим Pixelинтерфейсом.

Решение: уничтожить объектно-ориентированную структуру гранулярного пикселя и начать моделирование ваших интерфейсов на более грубом уровне, имея дело с большим количеством пикселей (на уровне изображения).

Благодаря моделированию на уровне объемных изображений у нас значительно больше возможностей для оптимизации. Мы можем, например, представить большие изображения в виде объединенных листов размером 16x16 пикселей, которые идеально вписываются в 64-байтовую строку кэша, но обеспечивают эффективный соседний вертикальный доступ к пикселям с обычно небольшим шагом (если у нас есть ряд алгоритмов обработки изображений, которые необходимо получить доступ к соседним пикселям по вертикали) в качестве жесткого ориентированного на данные примера.

Проектирование на более грубом уровне

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

Ключ к обеспечению ориентированной на данные оптимизации (в предвидении или ретроспективе) часто сводится к разработке интерфейсов на гораздо более грубом уровне, в целом. Идея проектирования интерфейсов для отдельных сущностей заменяется разработкой для коллекций сущностей с большими операциями, которые их массово обрабатывают. Это особенно и сразу нацелено на последовательные петли доступа, которые должны иметь доступ ко всему и не могут не иметь линейной сложности.

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

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

Ключ в том, чтобы проектировать интерфейсы на более грубом уровне, чем мы обычно испытываем. Это также часто имеет побочные преимущества, такие как уменьшение накладных расходов на динамическую диспетчеризацию, связанных с виртуальными функциями, вызовы указателей на функции, вызовы dylib и невозможность их включения. Основная идея, которую можно извлечь из всего этого, состоит в том, чтобы рассматривать массовую обработку (когда это применимо).

Томас Оуэнс
источник
5

То, что вы описали, является проблемой реализации. ОО дизайн явно не касается реализаций.

Вы можете инкапсулировать свой ориентированный на столбцы контейнер Ball за интерфейсом, который предоставляет представление, ориентированное на строки или столбцы. Вы можете реализовать объект Ball с помощью таких методов, как volumeand move, которые просто изменяют соответствующие значения в базовой структуре по столбцам. В то же время ваш контейнер Ball может предоставлять интерфейс для эффективных операций по столбцам. С соответствующими шаблонами / типами и умным встроенным компилятором вы можете использовать эти абстракции с нулевыми затратами времени выполнения.

Как часто вы будете получать доступ к данным по столбцам, а не изменять их по строкам? В типичных случаях использования для хранения столбцов упорядочение строк не оказывает влияния. Вы можете определить произвольную перестановку строк, добавив отдельный индексный столбец. Изменение порядка потребует только замены значений в столбце индекса.

Эффективное добавление / удаление элементов может быть достигнуто с помощью других методов:

  • Поддерживать растровое изображение удаленных строк вместо смещения элементов. Компактная структура, когда она становится слишком разреженной.
  • Группируйте строки в фрагменты соответствующего размера в структуре, подобной B-Tree, чтобы вставка или удаление в произвольных позициях не требовало изменения всей структуры.

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

user2313838
источник
+1 Организация AoS идеально подходит для хорошего API, ориентированного на сущности, хотя, по общему признанию, его использование становится более уродливым (по ball->do_something();сравнению с ball_table.do_something(ball)), если только вы не хотите подделать связную сущность с помощью псевдо-указателя (&ball_table, index).
1
Я сделаю еще один шаг: вывод об использовании SoA можно получить исключительно из принципов разработки ОО. Хитрость в том, что вам нужен сценарий, в котором столбцы являются более фундаментальным объектом, чем строки. Мячи не являются хорошим примером здесь. Вместо этого рассмотрите местность с различными свойствами, такими как высота, тип почвы или количество осадков. Каждое свойство моделируется как объект ScalarField, который имеет свои собственные методы, такие как градиент () или divergence (), которые могут возвращать другие объекты поля. Вы можете инкапсулировать такие вещи, как разрешение карты, и различные свойства на местности могут работать с различными разрешениями.
16807 19.09.16
4

Короткий ответ: вы полностью правы, и статьи, подобные этой , полностью упускают этот пункт.

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

Итак, второе, что нужно учитывать при выборе дизайна, это какие операции вам больше всего нужны в вашей программе, и выиграют ли они от разного расположения памяти. Тем не менее, первое, что нужно учитывать, это то, действительно ли вам нужна эта производительность (я думаю, в программировании игр, где вышеприведенная статья от вас часто есть это требование).

Большинство современных ОО-языков используют макет памяти Array-Of-Struct для объектов и классов. Получение преимуществ ОО (таких как создание абстракций для ваших данных, инкапсуляция и более локальная область действия основных функций), как правило, связано с этим типом структуры памяти. Поэтому, пока вы не выполняете высокопроизводительные вычисления, я бы не рассматривал SoA как основной подход.

Док Браун
источник
3
DOD не всегда означает структуру структуры массива (SoA). Это часто встречается, потому что часто соответствует шаблону доступа, но когда другой макет работает лучше, обязательно используйте это. DOD гораздо более общий (и нечеткий), больше похож на парадигму дизайна, чем на конкретный способ размещения данных. Кроме того, хотя статья, на которую вы ссылаетесь, далека от лучшего ресурса и имеет свои недостатки, она не рекламирует макеты SoA. «A» и «B» могут быть полнофункциональными Balls, равно как и индивидуальными floatили vec3s (которые сами будут подвергаться SoA-преобразованию).
2
... и упомянутый вами дизайн, ориентированный на строки, всегда включается в DOD. Он называется массивом структур (AoS), и отличие от того, что большинство ресурсов называют «ООП» (лучше или хуже), заключается не в расположении строк или столбцов, а в том, как этот макет отображается в память (множество небольших объектов). связаны через указатели против большой непрерывной таблицы всех записей). Таким образом, -1 потому что, хотя вы поднимаете хорошие моменты против неправильных представлений OP, вы неверно представляете весь джаз DOD, а не исправляете понимание OP DOD.
@delnan: спасибо за ваш комментарий, вы, вероятно, правы, что я должен был использовать термин «SoA» вместо «DOD». Я отредактировал свой ответ соответственно.
Док Браун
Намного лучше, пониженный голос удален. Посмотрите ответ пользователя user2313838 о том, как можно объединить SoA с хорошими API-интерфейсами, ориентированными на «объекты» (в смысле абстракций, инкапсуляции и «более локального охвата основных функций»). Это более естественно для макета AoS (поскольку массив может быть тупым универсальным контейнером, а не соединенным с типом элемента), но это выполнимо.
И этот github.com/BSVino/JaiPrimer/blob/master/JaiPrimer.md, который имеет автоматическое преобразование из SoA в / из AoS Пример: reddit.com/r/rust/comments/2t6xqz/… а затем есть это: новости. ycombinator.com/item?id=10235766
Джерри Иеремия,