Generic code enables you to write flexible, reusable functions and types that can work with any type, subject to requirements that you define. You can write code that avoids duplication and expresses its intent in a clear, abstracted manner. — Swift docs

Каждый, кто писал на Swift использовал дженерики. Array, Dictionary, Set — самые базовые варианты использования дженериков из стандартной библиотеке. Как они представлены внутри? Расмотрим, как данная основополагающая возможность языка реализована инженерами Apple.

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

Для реализации дженериков Swift использует два подхода:

Runtime-way — generic код является обёрткой (Boxing).
Compiletime-way — generic код преобразуется в код конкретного типа для оптимизации (Specialization).

Boxing

Рассмотрим простой метод с неограниченным протоколом дженериковым параметром:

func test<T>(value: T) -> T {
    let copy = value
    print(copy)
    return copy
}

Компилятор swift создаёт один единственный блок кода, который будет вызываться для работы с любым <T>. То есть, независимо от того, напишем мы test(value: 1) или test(value: "Hello"), будет вызван один и тот же код и дополнительно в метод будет передана информация о типе <T>, содержащая в себе всё необходимое.

Мало что можно сделать с такими неограниченными протоколами параметрами, но, уже для реализации этого метода, необходимо знать, как копировать параметр, необходимо знать его размер, чтобы выделить под него память в рантайме, необходимо знать, как его уничтожать, когда параметр уходит из области видимости. Для хранения этой информации используется Value Witness Table (VWT). VWT создаётся на этапе компиляции для всех типов и компилятор гарантирует, что в рантайме будет именно такой лэйаут объекта. Напомню, что структуры в Swift передаются по значению, а классы по ссылке, поэтому для let copy = value при T == MyClass и T == MyStruct будут сделаны разные вещи.

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

// Приблизительный псевдокод, параметр metadata добавляется компилятором
let myStruct = MyStruct()
test(value: myStruct, metadata: MyStruct.metadata)

Вещи становятся чуть сложнее, когда MyStruct сама является дженериковой структурой и принимает вид MyStruct<T>. В зависимости от <T> внутри MyStruct, метаданные и VWT будут разными для типов MyStruct<Int> и MyStruct<Bool>. Это два разных типа в рантайме. Но создавать метаданные для каждой возможной комбинации MyStruct и T крайне неэффективно, поэтому Swift идёт другим путём и для таких случаев конструирует метаданные в рантайме на ходу. Компилятором создаётся один metadata pattern для дженериковой структуры, который можно комбинировать с конкретным типом и, в итоге, получать полную информацию по типу в рантайме с корректной VWT.

// Опять же псевдокод, параметр metadata добавляется компилятором
func test<T>(value: MyStruct<T>, tMetadata: T.Type) {
    // Комбинируем информацию и получаем итоговые метаданные
    let myStructMetadata = get_generic_metadata(MyStruct.metadataPattern, tMetadata)
    ...
}

let myStruct = MyStruct<Int>()
test(value: myStruct) // Исходный код
test(value: myStruct, tMetadata: Int.metadata) // Примерно вот в это компилируется

Когда мы комбинируем информацию, мы получаем метаданные, с которыми можно работать (копировать, перемещать, уничтожать).

Всё ещё немного сложнее, когда на дженерики добавляются ограничения в виде протоколов. К примеру, ограничим <T> протоколом Equatable. Пусть это будет очень простой метод, который сравнивает два переданных аргумента. Получится просто обёртка над методом сравнения.

func isEquals<T: Equatable>(first: T, second: T) -> Bool {
    return first == second
}

Для правильной работы программы необходимо иметь указатель на метод сравнения static func ==(lhs:T, rhs:T). Как его получить? Очевидно, что передачи VWT не хватит, она не содержит этой информации. Для решения этой проблемы существует Protocol Witness Table или PWT. Эта табличка похожа на VWT и создаётся на этапе компиляции для протоколов и описывает эти протоколы.

isEquals(first: 1, second: 2) // Исходный код

// Примерно во что превращается
isEquals(first: 1, // 1
         second: 2,
         metadata: Int.metadata, // 2
         intIsEquatable: Equatable.witnessTable) // 3

Передаются два аргумента
Передаём метаданные для Int, чтобы можно было копировать/перемещать/уничтожать объекты
Передаём информацию и том, что Int реализует Equatable.

Если бы ограничение требовало реализации ещё одного протокола, к примеру, T: Equatable & MyProtocol, то информация о MyProtocol добавилась бы следующим параметром:

isEquals(...,
        intIsEquatable: Equatable.witnessTable,
        intIsMyProtocol: MyProtocol.witnessTable)

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

Специализация дженериков

Чтобы устранить излишнюю необходимость получения информации во время выполнения программы, был использован так называемый подход специализации дженериков. Он позволяет заменить дженериковую обёртку конкретным типом с конкретной реализацией. К примеру, для двух вызовов isEquals(first: 1, second: 2) и isEquals(first: "Hello", second: "world"), помимо основной "обёрточной" реализации, будут скомпилированы две дополнительные абсолютно разные версии метода для Int и для String.

Исходный код

Для начала создадим generic.swift файл и напишем небольшую generic функцию, которую будем рассматривать.

func isEquals<T: Equatable>(first: T, second: T) -> Bool {
    return first == second
}
isEquals(first: 10, second: 11)

Теперь необходимо понять, во что это в итоге превращается компилятором.
Это можно наглядно посмотреть, скомпилировав наш .swift файл в Swift Intermediate Language или SIL.

Немного о SIL и процессе компиляции

SIL является результатом одним из нескольких этапов компиляции swift.

Исходный код .swift передаеётся Lexer, который создаёт абстрактное синтаксическое дерево (AST) языка, на основе которого проводится проверка типов и семантический анализ кода. SilGen преобразует AST в SIL, называемый raw SIL, на основе которого происходит оптимизация кода и получается оптимизированный canonical SIL, который передаётся в IRGen для преобразования в IR — специальный формат, понятный LLVM, который будет преобразован в `.oфайлы, собранные под конкретную архитектуру процессора. Во что превращается наш дженериковый код можно посмотреть как раз на этапе созданияSIL`.

И снова к дженерикам

Создадим SIL файл из нашего исходного кода.

swiftc generic.swift -O -emit-sil -o generic-sil.s

Получим новый файл с расширением *.s. Заглянув вовнутрь, мы увидим гораздо менее читаемый код, чем исходный, но, всё равно, относительно понятный.

Найдём строку с комментарием // isEquals<A>(first:second:). Это и есть начало описания нашего метода. Заканчивается он комментарием // end sil function '$s4main8isEquals5first6secondSbx_xtSQRzlF'. У вас название может немного отличаться. Немного разберём описание метода.

%0 и %1 на 21 строке являются first и second параметрами соответственно
На 24 строке получаем информацию о типе и передаём в %4
На 25 строке получаем указатель на метод сравнения из информации о типе
на 26 строке Вызываем метод по указателю, передавая ему оба параметра и информацию о типе
На 27 строке отдаём результат.

В итоге мы видим: чтобы выполнить необходимые действия в реализации дженерикового метода, нам нужно во время выполнения программы получать информацию из описания типа <T>.

Перейдём непосредственно к специализации.

В скомпилированном SIL файле сразу после объявления общего метода isEquals следует объявление специализированного для типа Int.

На 39 строке вместо получения метода в рантайме из информации о типе сразу вызывается метод сравнения целых чисел "cmp_eq_Int64".

Чтобы метод "специализировался", необходимо включить оптимизацию. Также, необходимо знать, что

The optimizer can only perform specialization if the definition of the generic declaration is visible in the current Module (Источник)

То есть, метод не может быть специализирован между разными модулями Swift (например, дженериковый метод из Cocoapods библиотеки). Исключением является стандартная библиотека Swift, в которой такие базовые типы, как Array, Set и Dictionary. Все дженерики базовой библиотеки специализируются в конкретные типы.

Note: В Swift 4.2 были реализованы аттрибуты @inlinable и @usableFromInline, которые позволяют оптимизатору видеть тела методов из других модулей и вроде как есть возможность их специализировать, но данное поведение мной не тестировалось (Источник)

Ссылки

Описание дженериков
Оптимизация в Swift
Более подробная и глубокая презентация по теме
Статья на английском

Swift under the hood: Generic implementation