Ориентация объекта, ориентация данных, загрязнение кэша и очевидность кэша

Question

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

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

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

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

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

Что же касается того, что вместо объектов, хранящих свои собственные элементы данных, они хранят только ссылку на коллекции, где их элементы данных хранятся последовательно в своих собственных контейнерах, а их методы-члены возвращают данные из этих контейнеров, таким образом, шансы окончания ненужных данных на пути к ЦП следует сократить и увеличить шансы данных, необходимых в ближайшем "будущем". Логическим предположением является то, что этот подход улучшит эффективность предварительной выборки, попадания в кэш и эффективность использования, а также сократит задержки, связанные с автоматическим и ручным распараллеливанием.

Как вы думаете?

Позднее редактирование: применение "шаблона ориентации данных" может быть еще более полезным, если принять во внимание заполнение структуры и класса, если "модель" имеет char и int элементы данных, в ООП-режиме он будет дополнен, что будет только больше загрязнять кеш, но ориентированный на данные режим хранения может хранить все char и все int s последовательно, без места и кэша.

Answer 1

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

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

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

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

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

Неоднородные критические петли

Возьмите пример Orc наследуется Creature а также Human наследуется Creature, Elf наследуется ElvesНо люди, орки и эльфы имеют разные размеры / поля, разные требования к выравниванию и разные таблицы. В том случае, когда клиентский код хочет обработать их неоднородный список, хранящий полиморфные базовые указатели на существа, например:

for each creature in creatures:
     creature.do_something();

... в отличие от этого, который пожертвовал бы полиморфизмом:

for each orc in orcs:
     orc.do_something();
for each human in humans:
     humans.do_something();
for each elf in elves:
     elves.do_something();

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

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

Поэтому решение для меня в этом случае, если вы хотите наследования и полиморфизма, состоит в том, чтобы абстрагироваться на уровне контейнера: Orcs наследуется Creatures, Humans унаследовать Creatures, Elves наследуется Creatures, Это передает некоторую дополнительную сложность клиентскому коду, когда он хочет выразить операции, выполняемые для конкретного существа, но теперь приведенный выше последовательный цикл можно записать так:

for each creatures in creature_types:
     creatures.do_something();

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

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

Однородные циклы и представления

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

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

Вот так я вижу подход к этой проблеме, если хочу использовать ООП. Я думаю, что ваш тип идеи проекта может быть полезен для упрощения случаев, когда клиентский код должен выражать операцию, которая применяется только к одному конкретному существу, и в этот момент они могут работать через некоторый прокси-объект, который указывает на контейнер и может хранить индекс или указатель на конкретную запись, чтобы сделать это удобным, как CreatureHandle который ссылается на конкретную запись в одном из абстрактных Creatures контейнеры.

Answer 2

Прежде всего, хорошая слайд-презентация. Ну, как я понял, ваш вопрос сильно отличается от подхода к презентации. Переменные хранятся случайным образом в основной памяти, даже атрибуты объектов. Если вы попытаетесь выделить память для постоянной структуры данных, размер вашей структуры данных будет ограничен самым большим "воздушным пузырем" в вашей основной памяти, иначе он не будет чисто случайным. Может быть, вы думали что-то вроде этого:

class MyClass
{
public:
    MyClass()
    {
        m_dataMembers = new GenericObject[DATA_MEMBERS_AMOUNT];

        //initialize array values...
    }

    int getMyVar()
    {
        return (int)m_dataMembers[MY_VAR_INDEX];
    }

    //others functions...

private:
    GenericObject* m_dataMembers;
}

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