Влияет ли объектная ориентация на производительность алгоритма?

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

ОО действительно помогает быстро и легко кодировать алгоритмы. Но может ли этот ООП быть недостатком для программного обеспечения, основанного на производительности, то есть как быстро выполняется программа?

Например, сохранение узлов графа в структуре данных кажется «простым» в первую очередь, но если объекты Node содержат много атрибутов и методов, может ли это привести к медленному алгоритму?

Другими словами, может ли множество ссылок между многими различными объектами или использование многих методов из многих классов привести к «тяжелой» реализации?

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

Посмотрите на числовые библиотеки. Многие из них (не только написанные в 60-х или 70-х годах) не являются ООП. Для этого есть причина - численные алгоритмы работают лучше как набор разобщенных элементов, modulesчем как иерархии ОО с интерфейсами и инкапсуляцией.

Что определяет производительность?

Основы: структуры данных, алгоритмы, компьютерная архитектура, аппаратное обеспечение. Плюс накладные расходы.

Программа ООП может быть разработана так, чтобы точно соответствовать выбору структур данных и алгоритмов, которые считаются оптимальными в теории КС. Он будет иметь такую ​​же характеристику производительности, что и оптимальная программа, плюс некоторые накладные расходы. Накладные расходы обычно могут быть минимизированы.

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

Предостережение: имеет ли значение производительность в программном обеспечении для бизнеса?

Да, но время выхода на рынок (TTM) более важно, на порядки. Деловое программное обеспечение делает акцент на адаптируемость кода к сложным бизнес-правилам. Измерения производительности должны проводиться на протяжении всего жизненного цикла разработки. (См. Раздел: что означает оптимальная производительность? ) Должны быть сделаны только рыночные улучшения, которые должны постепенно вводиться в более поздних версиях.

Что означает оптимальная производительность?

В общем, проблема с производительностью программного обеспечения заключается в следующем: чтобы доказать, что «существует более быстрая версия», сначала должна появиться эта более быстрая версия (т. Е. Никаких других доказательств, кроме себя).

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

Почему мы делаем ООП, если это может помешать нашему поиску оптимальной производительности?

ООП вводит накладные расходы (в пространстве и исполнении) в обмен на улучшение «работоспособности» и, следовательно, коммерческой ценности кода. Это снижает стоимость дальнейшей разработки и оптимизации. Смотрите @MikeNakis .

Какие части ООП могут стимулировать изначально неоптимальный дизайн?

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

• ПОЦЕЛУЙ
• YAGNI
• DRY
• Проектирование объектов (например, с помощью карт CRC) без учета основополагающих принципов)

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

Каковы общие меры по снижению издержек ООП?

Как уже говорилось ранее, используются структуры данных, которые являются оптимальными для проектирования.

Некоторые языки поддерживают встраивание кода, что может восстановить производительность во время выполнения.

Как мы можем принять ООП, не жертвуя производительностью?

Изучите и применяйте как ООП, так и основы.

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

Существуют ли типы кода, которые не выиграют от ООП?

(Расширена из обсуждения между [@quant_dev], [@ SK-logic] и [@MikeNakis])

1. Численные рецепты, которые берут свое начало в математике.
   • Сами математические уравнения и преобразования можно понимать как объекты.
   • Для создания эффективного исполняемого кода необходимы очень сложные методы преобразования кода. Наивная ("белая доска") реализация будет иметь ужасную производительность.
   • Однако сегодняшние основные компиляторы не могут этого сделать.
   • Специализированное программное обеспечение (MATLAB и Mathematica и т. Д.) Имеет как JIT, так и символьные решатели, способные генерировать эффективный код для некоторых подзадач. Эти специализированные решатели можно рассматривать как специальные компиляторы (посредники между читаемым человеком кодом и машиноисполняемым кодом), которые сами выиграют от разработки ООП.
   • Каждая подзадача требует своего собственного «компилятора» и «преобразования кода». Поэтому это очень активная открытая область исследований, и каждый год появляются новые результаты.
   • Поскольку исследования занимают много времени, разработчики программного обеспечения должны провести оптимизацию на бумаге и преобразовать оптимизированный код в программное обеспечение. Переписанный код действительно может быть непонятным.
2. Код очень низкого уровня.
   *

Дело не в ориентации объекта, а в контейнерах. Если вы использовали двойной связанный список для хранения пикселей в вашем видеопроигрывателе, он пострадает.

Однако, если вы используете правильный контейнер, нет никакой причины, по которой std :: vector медленнее, чем массив, и, поскольку у вас уже есть все общие алгоритмы, написанные для него - экспертами, - он, вероятно, быстрее, чем ваш собственный свернутый код массива.

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

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

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

Одним из способов, которым это проявляется, является количество выполнений нового выполнения в секунду , которое, как предполагается, имеет производительность O (1), но может выполнять от сотен до тысяч инструкций (включая соответствующее удаление или время GC). Этого можно избежать, сохранив использованные объекты, но это сделает код менее «чистым».

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

Может быть, производительность данного приложения так же хорошо, как написано.

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

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

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

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

Но может ли этот ООП быть недостатком для программного обеспечения, основанного на производительности, то есть как быстро выполняется программа?

Часто да !!! НО...

Другими словами, может ли множество ссылок между многими различными объектами или использование многих методов из многих классов привести к «тяжелой» реализации?

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

В других языках, таких как Java, есть некоторые накладные расходы на объект (часто довольно маленькие во многих случаях, но астрономические в некоторых редких случаях с действительно маленькими объектами). Например, Integerэто значительно менее эффективно, чем int(занимает 16 байтов, а не 4 на 64-битной). Но это не просто вопиющая трата или что-то в этом роде. В обмен на это Java предлагает такие вещи, как отражение каждого отдельного пользовательского типа, а также возможность переопределить любую функцию, не отмеченную как final.

Но давайте возьмем сценарий с лучшим вариантом: оптимизирующий компилятор C ++, который может оптимизировать интерфейс объектов до нуля . Даже в этом случае ООП часто ухудшает производительность и не дает ей достичь пика. Это может звучать как полный парадокс: как это может быть? Проблема заключается в:

Дизайн интерфейса и инкапсуляция

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

Возьмите этот пример:

class Particle
{
public:
    ...

private:
    double birth;                // 8 bytes
    float x;                     // 4 bytes
    float y;                     // 4 bytes
    float z;                     // 4 bytes
    /*padding*/                  // 4 bytes of padding
};
Particle particles[1000000];     // 1mil particles (~24 megs)

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

Уже сейчас мы видим явные накладные расходы на 4 байта, необходимые для birthправильного выравнивания элемента при непрерывной агрегации частиц. Уже ~ 16,7% памяти теряется из-за мертвого пространства, используемого для выравнивания.

Это может показаться спорным, потому что в наши дни у нас есть гигабайты DRAM. Тем не менее, даже самые ужасные машины, которые мы имеем сегодня, часто имеют всего 8 мегабайт, когда речь идет о самой медленной и самой большой области кэша ЦП (L3). Чем меньше мы вписываемся туда, тем больше мы платим за это с точки зрения повторного доступа к DRAM и тем медленнее получается. Внезапно потеря 16,7% памяти больше не кажется тривиальной сделкой.

Мы можем легко устранить эти издержки без какого-либо влияния на выравнивание поля:

class Particle
{
public:
    ...

private:
    float x;                     // 4 bytes
    float y;                     // 4 bytes
    float z;                     // 4 bytes
};
Particle particles[1000000];     // 1mil particles (~12 megs)
double particle_birth[1000000];  // 1mil particle births (~8 bytes)

Теперь мы сократили объем памяти с 24 до 20 мегабайт. С последовательным шаблоном доступа, машина теперь будет потреблять эти данные немного быстрее.

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

В результате фактические данные, критичные к производительности, составляют не 20 мегабайт, а фактически непрерывный блок размером 12 мегабайт. Реальная горячая память, к которой мы часто обращаемся, сократилась вдвое ! Ожидайте значительного ускорения по сравнению с нашим оригинальным 24-мегабайтным решением (не нужно измерять - уже проделали подобные вещи тысячу раз, но не стесняйтесь, если сомневаетесь).

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

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

Для продолжения скажем, что поскольку мы просто перемещаем частицы, мы можем получить доступ к их полям x / y / z в трех отдельных циклах. В этом случае мы можем извлечь выгоду из встроенных функций SIMD в стиле SoA с регистрами AVX, которые могут векторизовать 8 операций SPFP параллельно. Но чтобы сделать это, мы должны теперь использовать это представление:

float particle_x[1000000];       // 1mil particle X positions (~4 megs)
float particle_y[1000000];       // 1mil particle Y positions (~4 megs)
float particle_z[1000000];       // 1mil particle Z positions (~4 megs)
double particle_birth[1000000];  // 1mil particle births (~8 bytes)

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

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

Решение

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

Тем не менее мы можем принять окончательное представление, на котором остановились, и по-прежнему моделировать объектно-ориентированный интерфейс:

// Represents a collection of particles.
class ParticleSystem
{
public:
    ...

private:
    double particle_birth[1000000];  // 1mil particle births (~8 bytes)
    float particle_x[1000000];       // 1mil particle X positions (~4 megs)
    float particle_y[1000000];       // 1mil particle Y positions (~4 megs)
    float particle_z[1000000];       // 1mil particle Z positions (~4 megs)
};

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

ParticleSystemпотенциально может даже быть абстрактным и использовать виртуальные функции. Это спорный вопрос сейчас, мы платим за накладные расходы на сборе частиц уровень , а не на каждую частицу уровня. Затраты составляют 1/1 000 000 от того, что было бы иначе, если бы мы моделировали объекты на уровне отдельных частиц.

Так что это решение для действительно критичных для производительности областей, которые обрабатывают большую нагрузку, и для всех видов языков программирования (этот метод выгоден C, C ++, Python, Java, JavaScript, Lua, Swift и т. Д.). И это не может быть легко маркировано как «преждевременная оптимизация», так как это относится к дизайну интерфейса и архитектуре . Мы не можем написать кодовую базу, моделирующую одну частицу как объект с множеством клиентских зависимостей вParticle'sпубличный интерфейс, а потом передумать. Я много делал это, когда меня вызывали для оптимизации унаследованных кодовых баз, и это может в конечном итоге занять месяцы тщательного переписывания десятков тысяч строк кода, чтобы использовать более объемный дизайн. Это идеально влияет на то, как мы проектируем вещи заранее, при условии, что мы можем предвидеть большую нагрузку.

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

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

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

На алгоритмическом уровне он часто думает о более широкой картине и об ограничениях или отношениях между значениями, которые приводят к выигрышу Big O. Примером может быть то, что в мышлении ООП нет ничего, что могло бы заставить вас преобразовать «сумму непрерывного диапазона целых чисел» из цикла в(max + min) * n/2

На уровне реализации, хотя компьютеры «достаточно быстры» для большинства алгоритмов уровня приложений, в низкоуровневом критичном к производительности коде очень беспокоит локальность. Опять же, акцент ООП на размышлениях об отдельном экземпляре и значениях одного прохода через цикл может быть отрицательным. В высокопроизводительном коде вместо того, чтобы писать простой цикл, вы можете захотеть частично развернуть цикл, сгруппировать несколько инструкций загрузки вверху, затем преобразовать их в группу, а затем записать их в группу. Все это время вы будете обращать внимание на промежуточные вычисления и, в огромной степени, на доступ к кешу и памяти; проблемы, когда абстракции ООП больше не действительны. И, если следовать, это может ввести в заблуждение: на этом уровне вы должны знать и думать о представлениях машинного уровня.

Когда вы смотрите на что-то вроде примитивов производительности Intel, у вас есть буквально тысячи реализаций быстрого преобразования Фурье, каждая из которых настроена на лучшую работу для конкретного размера данных и архитектуры машины. (Удивительно, но получается, что большая часть этих реализаций генерируется машинным способом : Markus Püschel Automatic Performance Programming )

Конечно, как говорилось в большинстве ответов, для большинства разработок, для большинства алгоритмов ООП не имеет отношения к производительности. Пока вы не «преждевременно пессимизируете» и не добавляете много нелокальных вызовов, thisуказатель не находится ни здесь, ни там.

Это связано и часто упускается из виду.

Это не простой ответ, это зависит от того, что вы хотите сделать.

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

До объектной ориентации многие школы преподают (редактируют) дизайн алгоритмов со структурированным программированием. Сегодня многие школы преподают объектно-ориентированное программирование, игнорируя алгоритмы проектирования и выполнения.

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

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

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

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

Хороший объектно-ориентированный дизайн помог мне значительно ускорить приложение. А должен был генерировать сложную графику алгоритмическим способом. Я сделал это с помощью автоматизации Microsoft Visio. Я работал, но был невероятно медленным. К счастью, я вставил дополнительный уровень абстракции между логикой (алгоритмом) и материалом Visio. Мой компонент Visio раскрыл свою функциональность через интерфейс. Это позволило мне легко заменить медленный компонент другим созданием SVG-файлов, который был как минимум в 50 раз быстрее! Без чистого объектно-ориентированного подхода коды для алгоритма и управления Vision были бы запутаны таким образом, что превратило бы изменения в кошмар.