В продолжение темы разберемся в протокольных типах и обобщенном (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. Большие значения. Если мы работаем с объектами, которые не помещаются в буфер, то:

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

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

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