Вступление

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

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

Может показаться, что за подобную функциональность обязательно придётся заплатить либо производительностью, либо памятью. На самом деле, чтобы максимально избежать подобных издержек, под капотом в языке имеется шесть разных реализаций перечислений. Решение о том какую из них использовать, принимается автоматически во время компиляции на этапе формирования промежуточного представления кода для llvm, ну и иногда в рантайме. Таким образом, вы можете быть уверены в том, что при использовании классических С-подобных перечислений, компилятор не потащит вместе с ними весь скрытый багаж функциональности для работы с ассоциативными значениями, и наоборот, если вы работаете с перечислениями с ассоциативными значениями, то там уж всё будет оптимизировано как надо. 

В данной статье мы рассмотрим как осуществляется работа с памятью в основных реализациях перечислений и к каким приёмам прибегает компилятор для её оптимизации. Как принято, начнём с простого.

1. Singleton enums

Самый примитивный случай - перечисление с нулевым или одним, единственным вариантом:

enum Empty { }
enum Singleton {
    case A
}
enum RawSingleton: String {
    case A = "Degenerate case"
}

Такое перечисление является вырожденным типом и не требует выделения памяти. Если у единственного варианта есть raw-значение, то при обращении к нему в коде, оно будет браться из метаданных типа. По сути, это будет аналогом глобальной константы. Однако, при наличии ассоциативного значения расклад меняется:

enum Singleton {
    case number(Int)
}

Очевидно, что одинаковые варианты в общем случае не эквивалентны между собой (так-как в каждом случае хранимое ассоциативное значение будет уникально), следовательно под каждое созданное значение данного перечисления, будет выделяться объём памяти соответствующий типу ассоциативной нагрузки. Столько же, сколько необходимо "обычной" переменной данного типа, если бы она не была завёрнута в перечисление.

let a = RawSingleton.A // zero size
let b = Singleton.number(5) // size: 8 bytes

2. No-payload strategy

Переходим к классике: перечисления с двумя или более вариантами без ассоциативной нагрузки.

Говоря о классическом перечислении, на ум сразу приходит C-подобные конструкции, где каждый вариант представлен просто порядковым числом. Также это работает и в Swift. Дополнительно, как и во многих других языках, каждому варианту можно назначить определённое raw-значение:

enum ImplStrategy: String {                // size: 4 bits
    case singleton = "Singleton"           // 0b0000
    case noPayload = "No-payload"          // 0b0001
    case singlePayload = "Single-payload"  // 0b0010
    case manyPayload = "Many-payload"      // 0b0011
    case resilent = "Resilent"             // 0b0100
}

ImplStrategy.resilent == ImplStrategy(rawValue: "Resilent") // true

Процесс выделения памяти прост и прямолинеен:

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

2. Далее определяется минимальная необходимая память из ряда 2^n в в которой могут поместиться все дискриминаторы.

3. Каждому дискриминатору назначается соответствующее raw-значение, которое затем размещается в метаданных этого типа и всегда доступно по запросу. Например, при создании значения перечисления через .init(rawValue: String).

Extra inhabitants

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

Не трудно заметить что для представления всех дискриминаторов достаточно трёх бит. Из всего множества значений 0b000-0b111 которые в этот объём памяти можно записать, только подмножество 0b000-0b100 будет представлять собой корректные значения (valid values) для данного перечисления. Подмножество же незадействованных битовых последовательностей, 0b101-0b111, является набором некорректных значений и носит название extra inhabitants (за неимением какого-то устойчивого перевода для этого термина, далее мы так и будем к нему обращаться).

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

Итак, с extra inhabitants разобрались, теперь немного о запасных битах (spare bits). Как мы отметили, явно видно что для хранения любого варианта перечисления достаточно трёх бит памяти, однако при генерации промежуточного кода, выделено будет не три бита, а четыре. Связано это с тем, что при работе с размерностями отличными от "нормальных", LLVM начинает работать медленней и не так стабильно. Поэтому, после определения минимально необходимиго числа бит, это значение округляется вверх до ближайшей величины в ряде 2^n с которыми LLVM работать удобней. Выделенные, но не используемые, биты именуются "запасными" и также присуще любому типу в Swift, не только перечислениям.
В довесок ко всему, минимальная выделяемая память для размещения какого-либо объекта в Swift - один байт, таким образом в нашем примере мы получим не один, а целых пять запасных битов для типа ImplStrategy.

В зависимости от ситуации, запасные биты могут использоваться в разных целях, например для формирования дополнительных extra inhabitants, если в этом есть нужда, в итоге наш тип ImplStrategy потенциально имеет следующий набор extra inhibitance:  0x04-0xFF.

Суммируя:

1. Запасные биты - по определённым причинам выделяемая, но никогда не участвующая в формировании корректных значений определённого типа, память.

2. Extra inhabitants - все комбинации битовых последовательностей, не являющиеся корректными значениями определённого типа, но потенциально размещаемые в выделяемую под значение этого типа память.

3. Множества корректных значений и extra inhabitants в рамках одного типа никогда не пересекаются.

4. Каждый тип в языке имеет свой набор extra inhabitants и запасных бит на момент компиляции (если это не шаблонный, a.k.a. generic, тип).

3. Single-payload strategy

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

enum FontSize {
    case small
    case medium
    case large
    case custom(UInt)
}

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

Обратите внимание, что теперь одна ячейка на изображении это уже полноценный байт из 8 бит. Как мы видим, для тегового бита выделяется один дополнительный байт. Общий размер выделяемой памяти с учётом нагрузки равен 9 байтам, что в общем то не страшно, но приводит к ряду неприятных последствий.  Так как значение не помещается в одно машинное слово, то считывание и запись осуществляются уже за две операции. Так же, исходя из величин stride = 16 и alignment = 8, мы понимаем что на каждое хранимое в памяти значение типа FontSize будет приходиться 7 байт не используемой памяти. Если мы планируем хранить большой массив таких данных, то ~46% памяти выделенной под массив останется незадействованной (на хабре есть отличная статья на эту тему).

Не приятно что один теговый бит так радикально портит нам общую картину, однако это не такая уж необычная ситуация. Вспомним, что опционал в Swift это перечисление, и оно как раз такого типа, так-что любой условный Int? автоматически будет страдать от тех же болячек. К счастью, в ряде случаев компилятор постарается оптимизировать используемую память и отказаться от использования тегового бита. Если тип данных в ассоциативном значении имеет достаточное количество extra inhabitants, они будут задействованы как дискриминаторы для пустых вариантов.

Рассмотрим такой случай на конкретном примере. В Swift предполагается что в начале адресного пространства программы всегда есть неразмеченная область памяти размером минимум 4КБ. Иными словами, и на стадии компиляции и в рантайме, заранее известно что любая ссылка на эту область будет некорректной, а значит все эти значения (адреса 0x0-0x4095) для любых объектов типа ссылки являются её extra inhabitans.

class Director { ... }

enum CardBuilder {
    case profile                  // 0x0
    case document                 // 0x1
    case nomenclature             // 0x2
    case custom(Director)         // 0x1000 - 0xFFFFFFFF_FFFFFFFF
}

Таким образом, используя extra enhabitans типа ассоциативного значения и заранее зная что это перечисление с одним ассоциативным вариантом, всегда можно однозначно идентифицировать какой вариант записан в выделеный участок памяти даже без тегового бита:

Все оставшиеся не задействованными extra enhabitans (0x003 - 0xFFF) наследуются объявленым перечислением CardBuilder и становятся его собственными extra inhabitants, которые в будущем могут быть использованы аналогичным образом. Например, если CardBuilder будет ассоциативным значением в другом перечислении.

4. Many-payloads strategy

Вот мы и подошли к самому продвинутому случаю. Для оптимизации перечислений с несколькими ассоциативными значениями используются немного другой подход. Однако начнём опять с самого общего случая:

enum State {
    case ready, finished, canceled
    case working(progress: Double)
    case failed(errorCode: UInt8)
}

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

Опять же, нам интересно как Swift это всё оптимизирует и оптимизирует ли вообще. Так как мы должны суметь различить между собой разные варианты с ассоциативными значениями, трюк с использованием extra inhabitants в качестве дискриминаторов для пустых вариантов уже не сработает. В этот момент в дело вступают запасные биты.  Как мы уже знаем, каждый тип в языке может обладать своим набором запасных бит. И если у всех типов ассоциативных значений есть общие пересекающиеся запасные биты, то они могут быть задействованы для хранения дискриминатора. Опять хорошим объектом для примера будут объекты типа ссылки в качестве нагрузки:

class Storage { ... }
class Service { ... }
class Item { ... }

enum ItemProvider {
    case storage(Storage)
    case service(Service)
    case placeholder(Item)
}

Ранее мы уже рассматривали случай с экземпляром класса в качестве ассоциативного значения. Опытные товарищи заметили определённую некорректность этого примера. Известно что в 64 битных системах под указатель выделяется 8 байт памяти, однако для хранения адреса реально используется лишь 48 из 64 бит (иногда 52). Может показаться что оставшиеся 16 бит мы можем рассматривать как запасные, однако разные платформы накладывают различные ограничения на их применение. В зависимости от платформы и языка, они могут быть использованы для хранения различной дополнительной информации (Top byte ignore, Memory Tagging, Pointer Authentication), либо вообще быть запрещены.

К сожалению мне не удалось найти официальных данных как это устроено на процессорах Apple. Судя по комментариям в исходном коде, а так-же некоторым in-situ экспериментам, указатели на native-Swift классы (в данном контексте в первую очередь подразумевается классы не насладующиеся от NSObject) имеют как минимум 3 запасных бита.  В целом вопрос об устройстве указателей довольно комплексный и уходит далеко за рамки данной статьи, ниже приведено изображение как это примерно выглядит на Apple Silicon:

И опять, тот факт что удалось избежать выделения девятого байта для тега (как и в примере для Single-payload) привело к тому, что теперь мы вписываемся в одно машинное слово. А это значит, что чтение и запись значений данного перечисления, будет осуществляться уже в одну операцию, а не две, что довольно хороший и значимый результат, а массив с такими значениями будет более "плотно" упакован в памяти.

5. Resilient strategy

Последняя реализация - ResilientEnumImplStrategy. Большая часть её методов переопределяет методы базового класса EnumImplStrategy заглушками, которые, как предполагается, никогда не будут вызваны. По сути сама эта реализация лишь временная заглушка назначаемая перечислениям на время компиляции программы, если вычислить их метаданные на этом этапе невозможно. Например, если это перечисление использует шаблонные типы Enum<T> { ... }, либо если в качестве ассоциативных значений стоят типы из внешних библиотек с включенной, по неведомой причине, опцией resilience. Тем не менее, во время рантайма метаданные этих типов в любом случае будут вычислены и перечислению в итоге будет назначена одна из вышеописанных реализаций.

Заключение

Перечисления очень мощный и выразительный инструмент в Swift. Как мы увидели, внутри языка имеется целый набор различных реализаций, оптимизированных под каждую конкретную конструкцию перечисления. В данной статье мы рассмотрели основные принципы выделения памяти в этих реализациях, хотя и не задели множество нюансов. Например, не были затронуты случаи когда в качестве нагрузки выступает кортеж из нескольких значений, хотя там всё работает по схожим принципам.
На самом деле, чтобы писать хороший код,  разработчику не обязательно всё это знать. Всё спроектировано так, чтобы не обременять нас подобным знанием. Понимание нюансов в реализации разных видов перечислений может сыграть роль разве что в редких случаях в server-side разработке, если вы работаете с большими объёмами данных. В остальном же это, по большей части, интересно с академической точки зрения, для желающих повысить общее понимание внутреннего устройства языка.