Протокольно ориентированное программирование, часть 2

В продолжение темы разберемся в протокольных типах и обобщенном (generic) коде.

По ходу будут рассмотрены следующие вопросы:

• реализация полиморфизма без наследования и ссылочных типов
• как объекты протокольных типов хранятся и используются
• как с ними работает отправка метода

Протокольные Типы

Реализация полиморфизма без наследования и ссылочных типов:

protocol Drawable { 
    func draw()
}

struct Point: Drawable {
    var x, y: Int
    func draw() {
        ...
    }
}

struct Line: Drawable {
    var x1, x2, y1, y2: Int
    func draw() {
        ...
    }
}

var drawbles = [Drawable]()

for d in drawbles {
    d.draw()
}

1. Обозначим протокол Drawable, который имеет метод draw
2. Реализуем этот протокол для Point и Line — теперь можно обращаться с ними, как с Drawable (вызывать метод draw)

Мы по прежнему имеем полиморфный код. Элемент d массива drawables имеет один интерфейс, который обозначен в протоколе Drawable, но имеет разные реализации своих методов, которые обозначены в Line и Point.

Главный принцип (ad-hoc) полиморфизма: "Общий интерфейс — много реализаций"

Dynamic dispatch без virtual-table

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

В случае структур наследование, также как и переопределение методов, невозможно. Тогда, на первый взгляд, в virtual-table нет надобности, но как тогда будет работать Динамическая отправка? Как программе понять, какой метод будет вызван на d.draw()?

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

Protocol Witness Table

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

в дальнейшем Protocol Witness Table будет называться "протокольно-методная таблица"

Отлично, теперь мы знаем где искать реализации методов. Остается лишь два вопроса:

1. Как найти соответствующую протокольно-методную таблицу для того или иного объекта, который реализовал этот протокол? Как в нашем случае найти эту таблицу для элемента d массива drawables?
2. Элементы массива должны быть одного размера (в этом и есть суть массива). Тогда как массив drawable может соответствовать этому требованию, если он может хранить в себе и Line и Point, а они имеют разные размеры?

MemoryLayout.size(ofValue: Line(...))  // 32 bits
MemoryLayout.size(ofValue: Point(...)) // 16 bits

Экзистенциальный контейнер

Для решения этих двух вопросов, в Swift используется специальная схема хранения для экземпляров протокольных типов, которая называется экзистенциальный контейнер. Выглядит она вот так:

Занимает 5 машинных слов (в x64 битной системе 5 * 64 = 320 бит). Разделен на три части:

value buffer — пространство для самого экземпляра
vwt — указатель на Value Witness Table
pwt — указатель на Protocol Witness Table

Рассмотрим все три части подробнее:

Буфер Содержимого

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

let point: Drawable = Point(...)

Point() занимает 2 машинных слова и прекрасно поместится в value buffer — программа сложит его туда:

let line: Drawable = Line(...)

Line() занимает 4 машинных слова и не может поместиться в value buffer — программа выделит для нее память на хипе, а в value buffer сложит поинтер на эту память:

ptr указывает на экземпляр Line(), размещенный на куче:

Таблица жизненного цикла

Также как и протокольно-методная таблица, эта таблица есть у каждого типа, который соответствует протоколу. Содержит в себе реализацию четырех методов: allocate, copy, destruct, deallocate. Этими методами управляется весь жизненный цикл объекта. Рассмотрим на примере:

1. При создании объекта ( Point(...) as Drawable) вызывается метод allocate из Т.Ж.Ц. этого объекта. Метод allocate решит, где должно быть размещено содержимое объекта (в буфере значений или на куче), и если он должен быть размещен на куче, то выделит необходимое количество памяти
2. Метод copy поместит содержимое объекта в соответствующее место
3. После окончания работы с объектом вызовется метод destruct, который убавит все счетчики ссылок, если таковые имеются
4. После destruct будет вызван метод deallocate, который освободит выделенную на хипе память, если таковая имеется

Протокольно-методная таблица

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

Экзистенциальный контейнер — Ответы

Таким образом мы ответили на поставленные два вопроса:

1. Протокольно-методная таблица хранится в Экзистенциальном контейнере этого объекта и может быть без труда из него получена
2. Если тип элемента массива является протоколом, то любой элемент этого массива занимает фиксированное значение в 5 машинных слов — именно столько необходимо для Экзистенциального контейнера. Если содержимое элемента не может быть помещено в буфер значений, то он будет размещен на куче. Если может, то все содержимое будет размещено в буфере значений. В любом случае мы получим, что размер объекта с типом протокола равен 5 машинным словам (40 бит), а из этого следует, что все элементы массива будут иметь одинаковый размер.

let line: Drawable = Line(...)
MemoryLayout.size(ofValue: line) // 40 bits
let drawables: [Drawable] = [Line(...), Point(...), Line(...)]
MemoryLayout.size(ofValue: drawables._content) // 120 bits

Экзистенциальный контейнер — Пример

Рассмотрим поведение экзистенциального контейнера в этом коде:

func drawACopy(local: Drawable) {
    local.draw()
}
let val: Drawable = Line(...)
drawACopy(val)

Экзистенциальный контейнер можно представить вот так:

struct ExistContDrawable {
    var valueBuffer: (Int, Int, Int)
    var vwt: ValueWitnessTable
    var pwt: ProtocolWitnessTable
}

Псевдокод

За кулисами функция drawACopy принимает в себя ExistContDrawable:

func drawACopy(val: ExistContDrawable) {
    ...
}

Параметр функции создается вручную: создаем контейнер, заполняем его поля из полученного аргумента:

func drawACopy(val: ExistContDrawable) {
    var local = ExistContDrawable()
    let vwt = val.vwt
    let pwt = val.pwt
    local.type = type
    local.pwt = pwt
    ...
}

Решаем, где будет хранится содержимое (в буфере или хипе). Вызываем vwt.allocate и vwt.copy, чтобы заполнить local содержимым val:

func drawACopy(val: ExistContDrawable) {
    ...
    vwt.allocateBufferAndCopy(&local, val)
}

Вызываем метод draw и передаем ему указатель на self ( projectBuffer метод решит, где расположен self — в буфере или на куче — и вернет верный указатель):

func drawACopy(val: ExistContDrawable) {
    ...
    pwt.draw(vwt.projectBuffer(&local))
}

Завершаем работу с local. Чистим все ссылки на хип от local. Функция возвращает значение — чистим всю память, выделенную для работы drawACopy (стэковый кадр):

func drawACopy(val: ExistContDrawable) {
    ...
    vwt.destructAndDeallocateBuffer(&local)
}

Экзистенциальный контейнер — Цель

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

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

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

Экзистенциальный контейнер — Хранимые свойства

Мы рассмотрели как переменная протокольного типа передается и используется функцией. Рассмотрим как такие переменные хранятся:

struct Pair {
    init(_ f: Drawable, _ s: Drawable) {
        first = f 
        second = s
    }
    var first: Drawable
    var second: Drawable
}

var pair = Pair(Line(), Point())

Каким образом хранятся эти две структуры типа Drawable внутри структуры Pair? Что представляет из себя содержимое pair? Оно представляет из себя два экзистенциальных контейнера — один для first, другой для second. Line не может поместится в буфере и размещена на куче. Point поместился в буфере. Также это позволяет структуре Pair хранить объекты разного размера:

pair.second = Line()

Теперь и содержимое second размещено на куче, так как не поместилось в буфер. Рассмотрим к чему это может привести:

let aLine = Line(...)
let pair = Pair(aLine, aLine)
let copy = pair

После выполнения этого кода программа получит следующее состояние памяти:

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

1. Создадим класс-аналог Line

class LineStorage: Drawable {
    var x1, y1, x2, y2: Double 
    func draw() {}
}

1. Используем его в Pair

let lineStorage = LineStorage(...)
let pair = Pair(lineStorage, lineStorage)
let copy = pair

Получаем одно размещение на куче и 4 указателя на него:

Но мы имеем дело с ссылочным поведением. Изменение copy.first отразится на pair.first (то же самое для .second), а это не всегда то, что мы хотим.

Косвенное хранение и копирование при изменении (copy-on-write)

До этого было упомянуто, что String это copy-on-write структура (хранит свое содержимое на куче и копирует его при изменении). Рассмотрим как можно реализовать свою структуру, которая копируется при изменении:

struct BetterLine: Drawable {
    private var storage: LineStorage
    init() {
        storage = LineStorage((0, 0), (10, 10))
    }
    func draw() -> Double { ... }
    mutating func move() {
        if !isKnownUniquelyReferenced(&storage) {
            storage = LineStorage(self.storage)
        }
        // storage editing
    }
}

1. Все свойства BetterLine хранит в storage, а storage является классом и хранится на куче
2. Изменять storage можно только методом move. В нем мы проверяем, что на storage указывает только один указатель. Если указателей больше, то этот BetterLine делит с кем-то storage, а для того, чтобы BetterLine полностью вел себя как структура, storage должен быть индивидуальным — делаем копию и в дальнейшем работаем с ней.

Посмотрим как это работает в памяти:

let aLine = BetterLine()
let pair = Pair(aLine, aLine)
let copy = pair

copy.second.x1 = 3.0

В результате выполнения этого кода, получим:

Иными словами мы имеем два экземпляра Pair которые делят между собой один storage: LineStorage. При изменении storage в одном из его пользователей (first/second) будет создана отдельная копия storage для этого пользователя, чтобы его изменение не сказались на других. Это решает проблему нарушение семантики типов значений из прошлого примера.

Протокольные Типы — Итог

1. Маленькие значения. Если мы работаем с объектами, которые занимают мало памяти и могут быть помещены в буфер экзистенциального контейнера, то:

• не будет размещения на куче
• нет подсчета ссылок
• полиморфизм (динамическая отправка) при помощи протокольной таблицы

1. Большие значения. Если мы работаем с объектами, которые не помещаются в буфер, то:

• размещение на куче
• подсчет ссылок, если объекты содержат ссылки.

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

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