Структуры против Классов

С самого начала, когда я начинал заниматься программированием, вставал вопрос, что использовать для улучшения быстродействия: структуру или класс; какие массивы лучше использовать и как. По поводу структур, Apple приветствует их использование, объясняя это тем, что они лучше поддаются оптимизации, и вся суть языка Swift — это структуры. Но есть и те, кто с этим не согласен, ведь можно красиво упростить код, отнаследовав один класс от другого и работая с таким классом. Для ускорения работы с классами создавали разные модификаторы и объекты, которые оптимизировались специально под классы, и тут уже сложно сказать, что и в каком случае будет быстрее.

Для расстановки всех точек на «е» я написал несколько тестов, которые используют обычные подходы к обработке данных: передача в метод, копирование, работа с массивами и так далее. Громких выводов я решил не делать, каждый решит для себя сам, стоит ли верить тестам, сможет скачать проект и посмотреть, как он будет работать у вас, и попробовать оптимизировать работу того или иного теста. Возможно даже выйдут новые фишки, которые я не упомянул, или они настолько редко используются, что я просто не слышал о них.
P.S. Я начинал работу над статьёй на Xcode 10.3 и было думал попробовать сравнить его скорость с Xcode 11, но всё же статья не про сравнение двух приложений, а о скорости работы наших приложений. Я не сомневаюсь, что время работы функций уменьшится, и то, что было плохо оптимизировано, станет быстрее. В итоге я дождался новый Swift 5.1 и решил проверить гипотезы на практике. Приятного чтения.

Тест 1: Сравним массивы на структурах и классах


Предположим, у нас есть некий класс, и мы хотим положить объекты этого класса в массив, обычное действие над массивом — это пройтись по нему циклом.

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

Если мы пройдемся по структуре, то в момент вызова объекта по индексу создастся копия объекта, смотрящая на ту же область памяти, но помеченная immutable. Сложно сказать, что быстрее: увеличение числа ссылок на объект или создание ссылки на область в памяти с отсутствием возможности её изменить. Проверим это на практике:

mei52ghwjxv_pg3c1toaoqachty.png
Рис. 1: Сравнение получения переменной из массивов на основе структур и классов

Тест 2. Сравненим ContiguousArray vs Array


Что более интересно — сравнить производительность массива (Array) с ссылочным массивом (ContiguousArray), который нужен специально для работы c классами, хранимыми в массиве.

Проверим производительность для следующих случаев:

ContiguousArray, хранящий struct с value типом
ContiguousArray, хранящий struct с String
ContiguousArray, хранящий class с value типом
ContiguousArray, хранящий class с String
Array, хранящий struct с value типом
Array, хранящий struct с String
Array, хранящий class с value типом
Array, хранящий class с String

Так как результаты тестов (тесты: передача в функцию с отключенной оптимизацией inline, передача в функцию c включенной оптимизацией inline, удаление элементов, добавление элементов, последовательный доступ к элементу в цикле) будут включать большое количество проведенных тестов (для 8 массивов по 5 тестов), я приведу наиболее значимые результаты:

  1. Если вы вызываете функцию и передаете в неё массив, отключая inline, то такой вызов будет очень дорого стоить (для классов на основе ссылочного String в 20 000 раз медленнее, для классов на основе Value тип в 60 000 раз, хуже с выключенным inline оптимизатором).
  2. Если оптимизация (inline) у вас сработает, то деградацию стоит ожидать всего в 2 раза, в зависимости от того, какой тип данных в какой массив добавлен. Исключением стал только value тип, обёрнутый в структуру, лежащей в ContiguousArray — без деградации по времени.
  3. Удаление — разброс между ссылочным массивом и обычным составил около 20% (в пользу обычного Array).
  4. Добавление (append) — при использовании объектов, обёрнутых в классы, у ContiguousArray скорость была примерно на 20% быстрее, чем у Array с такими же объектами, а у Array при работе со структурами скорость была быстрее, чем у ContiguousArray со структурами.
  5. Доступ к элементам массива при использовании обёрток из структур оказывался быстрее, чем любые обёртки над классами, в том числе ContiguousArray (порядка 500 раз быстрее).


В большинстве случаев использовать обычные массивы для работы с объектами более эффективно. Использовали раньше, используем и дальше.

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

В использовании структур в качестве инструмента оптимизации присутствуют свои подводные камни, такие как использование типов, которые внутри имеют ссылочную природу: строки, словари, ссылочный массивы. Тогда, когда переменная, хранящая в себе ссылочный тип, поступает на вход у какой-либо функции, происходит создание дополнительной ссылки на каждый элемент, который является классом. У этого есть и другая сторона, о ней чуть дальше. Можно попробовать использовать класс-оболочку над переменной. Тогда количество ссылок при передаче в функции увеличится только у неё, а количество ссылок на значения внутри структуры останутся прежними. В целом хочется посмотреть, какое количество переменных ссылочного типа должно быть в структуре, чтобы её производительность снизилась ниже, чем производительность классов с теми же параметрами. В сети есть статья «Stop Using Structs!», которая задает тот же вопрос и отвечает на него. Я скачал проект и решил разобраться, что где происходит, и в каких случаях мы получаем медленные структуры. Автор показывает низкую производительность структур по сравнению с классами, спорить с тем, что создание нового объекта намного медленное занятие, чем увеличение ссылки на объект, абсурдно (поэтому я убрал строку, где в цикле каждый раз создается новый объект). Но если мы не будем создавать ссылку на объект, а будем просто передавать его в функцию для работы с ним, то разницы в производительности будет очень несущественная. Каждый раз, когда мы ставим inline (never) у функции, наше приложение обязано выполнять её и не создавать кода в строку. Судя по тестам, Apple сделала таким образом, что объект, передаваемый в функцию немного модифицируется, для структур компилятор меняет мутабельность и делает доступ к не мутабельным свойствам объекта ленивыми. В классе происходит нечто подобное, но заодно увеличивает число ссылок на объект. И теперь у нас есть объект lazy, все его поля также lazy, и каждый раз, когда мы вызываем переменную объекта, он его инициализирует. В этом у структур нет равных: при вызове в функции двух переменных, у объекта структура лишь немного уступает классу в скорости; при вызове трёх и более, структура всегда будет быстрее.

Тест 3: Сравниваем производительность Структур и Классов хранящих большие классы


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

zvq_ens-bwgnuetcl53shkecjd0.png
Рис. 2: Производительность структур и классов из статьи «Stop Using Structs»

Разнице в результатах теста незначительны.

Тест 4: Функция, принимающая Generic, Protocol и функция без Generic


Если взять дженерик функцию и передать туда два значения, объединенных только возможностью сравнения этих значений (func min), тогда код из трёх строк превратится в код из восьми (так говорит Apple). Но так бывает не всегда, у Xcode есть способы оптимизации, в которых, если он при вызове функции видит, что в него передается две структурных значения, он автоматически генерирует функцию, принимающую две структуры, и уже не копирует значений.

zofd2v5qz7q3dkhzdcp_srpspyg.png
Рис. 3: Типичная Generic функция

Я решил протестировать две функции: в первой обьявлен тип данных Generic, второй принимает просто Protocol. В новой версии Swift 5.1 Protocol даже немного быстрее, чем Generic (до Swift 5.1 протоколы были в 2 раза медленнее), хотя по версии Apple всё должно быть наоборот, а вот когда дело касается прохода по массиву, нам уже надо приводить тип, что замедляет Generic (но они всё равно молодцы, ведь побыстрее протоколов):

k-oxvrhsx5mbw_osj7azkzu9x7y.png
Рис. 4: Сравнение Generic и Protocol принимающей функции.

Тест 5: Сравним вызов родительского метода и родного, а заодно проверим final класс на такой вызов


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

trwzi-l8v51yv4oftdl33a-30z4.png
Рис. 5: Вызовы методов классов, для тестирования диспетчеризация

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

Тест 6: Вызов переменной с модификатором final против обычной переменной класса


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

eft7d7u2wpc4htxcas5tiffnari.png
Рис. 6: Вызов final переменной

Очевидно, что на пользу переменной модификатор не пошел, и она всегда медленнее своего конкурента.

Тест 7: Проблема полиморфизма и протоколов для структур. Или производительность Existential container


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

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

Для решения проблемы хранения данных используется Existential container. Он хранит в себе 5 ячеек информации, каждая по 8 байт. В первых трёх выделяется место под хранимые данные в структуре (если они не влезают, то он создает ссылку на кучу, в которой хранятся данные), в четвертой хранится информация о типах данных, которые используются в структуре, и говорит нам о способе управления этими данными, на пятой хранятся ссылки на методы объекта.

jhtu6cgi7hcnllrybgfphk9gx-i.png
Рис 7. Сравнение производительности массива, который создает ссылку на объект и который его содержит

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

Немного теории для оптимизации ваших проектов


На производительность структур могут влиять следующие факторы:

  • где хранятся её переменные (куча/стэк);
  • необходимость подсчета ссылок для свойств;
  • методы диспетчеризация (статические/динамические);
  • Copy-On-Write используется только теми структурами данных, которые под капотом являются ссылочными типами, притворяющиеся структурами (String, Array, Set, Dictionary).


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

Чем плохи и опасны классы по сравнению со структурами

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

Они не такие быстрые как структуры.

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

Если мы пытаемся избежать Race Condition, мы тратим много ресурсов на Lock«и наших данных, что начинает подъедать ресурсы и тратить время вместо быстрой обработки и мы получаем еще более медленные объекты, чем те же самые, построенные на структурах.

Если мы проделываем все упомянутые выше действия над нашими объектами (ссылками), то велика вероятность возникновения непредвиденных deadlock«s.

Сложность кода из-за этого возрастает.

Больше кода = больше багов, всегда!

Выводы


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

  1. В массив лучше всего класть структуры.
  2. Если хочется создать массив из классов, то лучше выбрать обычный Array, так как ContiguousArray предоставляет преимущества редко, и они не сильно высоки.
  3. Inline оптимизация ускоряет работу, не отключайте её.
  4. Доступ к элементам Array всегда быстрее, чем доступ к элементам ContiguousArray.
  5. Структуры всегда быстрее классов (если конечно включить Whole module optimization или подобную оптимизацию).
  6. При передаче объекта в функцию и вызове его свойства, начиная с третьего, структуры быстрее классов.
  7. При передаче значения в функцию, написаную для Generic и Protocol, Generic будет быстрее.
  8. При множественном наследовании классов скорость вызова функции деградирует.
  9. Переменные с пометкой final работают медленнее обычных перечных.
  10. Если функция принимает объект, объединяющий протоколом несколько объектов, то он будет быстро работать, если в нём хранится всего одно свойство, и сильно деградировать при добавлении большего количества свойств.


Ссылки:
medium.com/@vhart/protocols-generics-and-existential-containers-wait-what-e2e698262ab1
developer.apple.com/videos/play/wwdc2016/416
developer.apple.com/videos/play/wwdc2015/409
developer.apple.com/videos/play/wwdc2016/419
medium.com/commencis/stop-using-structs-e1be9a86376f
Исходный код тестов

© Habrahabr.ru