ПОП vs ООП в Swift ч.1

Данный материал является комментированным переводом
презентации WWDC 2016. Вопреки частому мнению о том, что вещи "под капотом" должны там и оставаться, иногда крайне полезно разобраться, что же там происходит. Это поможет использовать предмет правильно и по назначению.

Цель:

дать поверхностное представление о слабых местах объектно ориентированного программирования (ООП), объяснить, как работает протокольно ориентированное программирование (ПОП) в Swift, и как заместить им ООП.

В данном материале будут затронуты ключевые проблемы Объектно-ориентированного программирования и то как ПОП их решает. Всё будет рассматриваться в реалиях языка Swift, в подробностях будет рассмотрена "подкапотная" работы протоколов.

Проблемы ООП и зачем нам нужно ПОП

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

1. Allocation: Stack или Heap?
2. Reference counting: больше или меньше?
3. Method dispatch: статическая или динамическая?

1.1 Allocation - Stack

Stack - это довольно простая и примитивная структура данных. Мы можем положить на вершину stack-а (push), можем взять с вершины stack-а (pop). Простота заключается в том, что это все, что мы можем делать с ним.

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

Push - кладем на вершину стэка, увеличиваем stack pointer;

pop - уменьшаем stack pointer.

Типы значений

Рассмотрим принципы работы стэка в Swift, используя структуры (struct).

В Swift типами значений являются структуры (struct) и перечисления (enum), а ссылочными типами являются классы (class) и функции/замыкания (func). Типы значений хранятся на Stack, ссылочные типы хранятся на Heap.

Размещаем первую структуру на Stack-е
Копируем содержимое первой структуры
Изменяем память второй структуры (первая остается нетронутой)
Конец использования. Освобождение памяти

1.2 Allocation - Heap

Heap - это древовидная структура данных. Тема реализации heap здесь затронута не будет, но мы попытаемся сравнить её со стэком.

Почему, если это возможно, стоит использовать Stack вместо Heap? Вот почему:

Подсчет ссылок
Администрация свободной памяти и ее поиск для аллокации
Перезапись памяти для деалокации

Всё это - лишь малая часть того, что обеспечивает работу Heap и явно отягощает его в сравнении со Stack.

Например, когда нам нужна свободная память на Stack, мы просто берем значение stack-pointer и увеличиваем его (ведь всё, что выше stack-pointer в Stack, является свободной памятью) - O(1) - операция, которая постоянна по времени.

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

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

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

Ссылочные типы

Рассмотрим принцип работы Heap в Swift, используя классы.

Размещаем тело класса на Heap. Размещаем указатель на это тело на Stack
Копируем указатель, который ссылается на тело класса
Изменяем тело класса
Конец использования. Освобождение памяти

1.3 Allocation - Небольшой и "Реальный" пример

В некоторых ситуациях выбор в пользу Stack не только упрощает работу с памятью, но и улучшает качество кода. Рассмотрим на примере:

Если в словаре cache есть значение с ключом key, то функция просто вернет закэшированный UIImage.

Проблемы этого кода:

Не лучшей практикой является использование String как ключа в cached, ведь String в конце концов "может оказаться чем-угодно".
String - это copy-on-write структура, для реализации ее динамичности все свои Character-ы она хранит на Heap. Таким образом String - это структура, и хранится в Stack, но все свое содержимое она хранит на Heap.

Это необходимо для того, чтобы обеспечить возможность изменения строки (убрать часть строки, добавить новую строку к этой строке). Если бы все символы строки хранились на Stack, то такие манипуляции были бы невозможными. Например, в C строки - статические, а это значит, что размер строки невозможно увеличить в runtime т. к. всё содержимое хранится на Stack. Про copy-on-write и более детальный разбор строк в Swift можно обратиться сюда.

Решение:

1. Использовать вместо строки вполне очевидную здесь структуру:

2. Изменить словарь на:

3. Избавиться от String

В структуре Attributes все свойства хранятся на Stack, так как перечисление (enum) хранится на Stack. Значит, что никакого неявного использования Heap здесь нет, и теперь ключи для словаря cache предельно точно определены, что увеличило безопасность и ясность этого кода. Также мы избавились от неявного использования Heap.

Вердикт: Stack гораздо легче и быстрее Heap - выбор для большинства ситуаций очевиден.

2. Подсчет ссылок

Для чего?

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

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

Stack: поиск свободной памяти и освобождение используемой - операция с stack-pointer

Heap: поиск свободной памяти и освобождение используемой - алгоритм поиска в дереве и reference counting.

Псевдокод

Рассмотрим небольшой фрагмент псевдокода для демонстрации работы подсчета ссылок:

Struct

При работе со структурами, такой механизм как reference counting просто не нужен:

struct не хранится на Heap
struct - копируется при присваивании, следовательно, нет ссылок

Копирование ссылок

Снова, struct и любые другие типы значений в Swift копируются при присваивании. В случае, если структура хранит в себе ссылки, они также скопируются:

label и label2 делят между собой общие инстансы, размещенные на Heap:

содержимое text
и font

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

И снова "реальный" пример:

Проблемы этой структуры в том, что она имеет:

3 Heap аллокации
Из-за того, что String может быть какой угодно строкой, страдают безопасность и ясность кода.

В то же время uuid и mimeType - строго определенный вещи:

uuid - это строка формата xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx
mimeType - это строка формата type/extension.

Решение

let uuid: UUID // UUID это тип, который дает нам Foundation

В случае mimeType отлично подойдет enum:

Или лучше и проще:

И не забыть изменить:

let mimeType: MimeType

3.1 Method Dispatch

- это алгоритм, который ищет код метода, который был вызван

Прежде чем говорить о реализации этого механизма, стоит определить, что такое "сообщение" и "метод" в этом контексте:

- сообщение - это имя, которое мы отсылаем объекту. Вместе с именем ещё могут быть отправлены аргументы.

Сообщение это draw - имя метода. Объект-получатель - это circle. Origin - это вдобавок переданный аргумент.

- метод - это код, который будет отдан в ответ на сообщение.

Тогда Method Dispatch - это алгоритм, который решает, какой метод должен быть отдан на то или иное сообщение.

Более конкретно о Method Dispatch в Swift

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

Создадим пару инстансов и вызовем метод me:

Довольно очевидный и простой пример. А что, если:

Это уже не столь очевидно и требует ресурсов и определенного механизма для определения корректной реализации метода me. Ресурсы - это процессор и оперативная память. Механизм - это Method Dispatch.

Иными словами, Method Dispatch - это то, как программа определяет какую реализацию метода вызвать.

Когда в коде вызывается метод - его реализация должна быть известна. Если она известна к моменту компиляции, то это Static Dispatch. Если реализация определяется непосредственно перед вызовом (в runtime, в момент выполнения кода), то это Dynamic Dispatch.

3.2 Method Dispatch - Static Dispatch

Наиболее оптимальный, так как:

1. Компилятор знает, какой блок кода (реализация метода) будет вызван. Благодаря этому он может максимально оптимизировать этот код и прибегнуть к такому механизму как inlining.
2. Также в момент выполнения кода программа просто выполнит этот известный компилятору блок кода. Не будет затрачено никаких ресурсов и времени на определение корректной реализации метода, что ускорит выполнение программы.

3.3 Method Dispatch - Dynamic Dispatch

Не самый оптимальный, так как:

1. Корректная реализация метода будет определяться в момент выполнения программы, что требует ресурсов и времени
2. Ни о каких оптимизациях компилятора не может быть и речи

3.4 Method Dispatch - Inlining

Был упомянут такой механизм, как inlining, но что это? Рассмотрим на примере:

point.draw() метод и drawAPoint функция будут обработаны через Static Dispatch, так как здесь нет никакой сложности в определении корректной реализации для компилятора (т. к. нет наследования и переопределение невозможно)
так как компилятор знает, что будет выполнено, он может оптимизировать это. Сначала оптимизирует drawAPoint, просто заменив вызов функции на её код:

затем оптимизирует point.draw, так как реализация этого метода так же известна:

Создали point, выполнили код метода draw - компилятор просто подставил нужный код этих функций вместо их вызова. В Dynamic Dispatch это будет несколько сложнее.

3.5 Method Dispatch - Inheritance-Based Polymorphism

Зачем вообще нужен Dynamic Dispatch? Без него невозможно определить переопределенные дочерними классами методы. Не был бы возможен полиморфизм. Рассмотрим на примере:

массив drawables может содержать Point и Line
интуитивно понятно, что Static Dispatch невозможен здесь. d в цикле for может быть Line, а может быть Point. Компилятору не под силу определить это, а ведь у каждого типа своя реализация draw

Тогда как работает Dynamic Dispatch? У каждого объекта есть поле type. Так Point(...).type будет равен Point, а Line(...).type будет равен Line. Также где-то в (статической) памяти программы расположена таблица (virtual-table), где для каждого type есть список с его реализациями методов.

В Objective-C поле type известно как поле isa. Оно присутствует у каждого Objective-C объекта (NSObject).

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

Таким образом, компилятор изменит этот код на:

В момент выполнения кода необходимо заглянуть в virtual-table, найти там класс d, взять из полученного списка метод draw и передать ему объект типа d в качестве self. Это приличная работа для простого вызова метода, но она необходима для обеспечения работы полиморфизма. Схожие механизмы используются в любом ООП языке.

Method Dispatch - Итог

методы классов по умолчанию обрабатываются через Dynamic Dispatch. Но не все методы классов должны быть обработаны через Dynamic Dispatch. Если метод не будет переопределяться, то можно озаглавить его ключевым словом final, и тогда компилятору будет известно, что этот метод невозможно переопределить и он обработает его через Static Dispatch
не классовые методы не могут быть переопределены (так как struct и enum не поддерживают наследование) и обрабатываются через Static Dispatch

Проблемы ООП - Итог

Необходимо обращать внимание на такие мелочи как:

1. При создании инстанса: где он будет размещен?
2. При работе с этим инстансом: как будет работать подсчет ссылок?
3. При вызове метода: чем он будет обработан?

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

Полиморфизм - очень важная и полезная вещь. На данный момент известно лишь то, что полиморфизм в Swift напрямую связан с классами и ссылочными типами. Мы же, в свою очередь, говорим, что классы - это медленно и тяжело, а структура - просто и легко. Возможен ли полиморфизм, реализованный через структуры? Ответ на этот вопрос может дать протокольно ориентированное программирование.

Спасибо за внимание!