Swift позволяет осуществлять неограниченную рекурсию в перечислениях значений с помощью ключевого слова indirect, которое заставляет конкретные случаи хранить свои связанные значения в контейнерах, выделенных в куче и управляемых по подсчету ссылок. Когда случай помечен как indirect, компилятор преобразует инлайн-хранение полезной нагрузки в указатель на контейнер, выделенный в куче и управляемый ARC. Эта индирекция позволяет перечислению рекурсивно ссылаться на себя без бесконечного увеличения размера, поскольку компилятору нужно хранить лишь указатель, а не все значение инлайн.
Тем не менее, эта трансформация значительно влияет на производительность сопоставления шаблонов. Каждый доступ к indirect-случаю требует поиска указателя для достижения полезной нагрузки, что ухудшает локальность кэша ЦПУ по сравнению с перечислениями, полностью хранящимися в стеке. Кроме того, выделение памяти в куче вызывает атомарные операции удержания и освобождения, что увеличивает накладные расходы на синхронизацию в конкурентных контекстах, хотя само перечисление сохраняет семантику значений на уровне языка.
indirect enum Expression { case literal(Int) case add(Expression, Expression) case multiply(Expression, Expression) } // Сопоставление шаблонов требует разыменования func evaluate(_ expr: Expression) -> Int { switch expr { case .literal(let value): return value case .add(let left, let right): return evaluate(left) + evaluate(right) case .multiply(let left, let right): return evaluate(left) * evaluate(right) } }
Мы разрабатывали парсер языка специальной конфигурации для механизма конфигурации, который должен был обрабатывать глубоко вложенные логические выражения. Исходная реализация использовала рекурсивное перечисление для представления AST выражения без аннотаций indirect, что немедленно приводило к сбоям переполнения стека при обработке файлов конфигурации с глубиной вложенности, превышающей несколько тысяч уровней.
Первое решение, которое было рассмотрено, заключалось в том, чтобы полностью отказаться от перечислений в пользу структуры дерева на основе классов с ссылками на родительские и дочерние элементы. Этот подход обеспечил бы естественное выделение памяти в куче для рекурсивных отношений. Однако мы отвергли это, поскольку это жертвовало семантикой значений, делая невозможным безопасное совместное использование разобранных поддеревьев между потоками конкурентной компиляции без реализации сложных механизмов защиты копирования или блокировок.
Мы выбрали второе решение: применять indirect конкретно к рекурсивным случаям в перечислении, таким как те, которые содержат дочерние выражения. Это сохранило семантику значений, одновременно заставляя выделять память в куче только там, где это необходимо для неограниченной рекурсии. Компромисс был приемлемым, поскольку мы сохраняли гарантии неизменности и безопасность типов, хотя нам пришлось реализовать собственные оптимизации копирования при записи для часто изменяемых деревьев выражений.
В результате получился стабильный парсер, способный обрабатывать произвольно глубокую вложенность. Поздние профилирования показали, что сопоставление шаблонов по indirect-случаям потребляло примерно на двадцать процентов больше циклов ЦПУ из-за индирекции указателя и трафика ARC, что мы смягчили, уплотняя небольшие структуры фиксированной глубины в неиндиректные вспомогательные перечисления для общих случаев.
Как indirect взаимодействует с оптимизацией копирования при записи в Swift?
Многие кандидаты предполагают, что indirect-случаи всегда вызывают глубокое копирование всей рекурсивной структуры. На самом деле Swift применяет семантику копирования при записи к куче, содержащей индиректную полезную нагрузку. Когда перечисление с indirect-случаем присваивается новой переменной, компилятор сохраняет ссылку на кучу, а не копирует содержимое. Полезная нагрузка копируется только тогда, когда происходит мутирующая операция, и количество ссылок превышает одну. Эта оптимизация имеет решающее значение для производительности с большими рекурсивными структурами, но требует внимательного рассмотрения при работе с безопасностью потоков, поскольку подсчет ссылок является атомарным, но логика копирования при записи требует синхронизации через потоки.
Можно ли применять indirect к отдельным случаям, а не к всему перечислению, и каковы последствия для размещения в памяти?
Кандидаты часто полагают, что indirect должен применяться ко всему объявлению перечисления. Тем не менее, Swift позволяет маркировать отдельные случаи как indirect, что значительно влияет на размещение в памяти. Когда конкретные случаи помечены как indirect, перечисление использует представление с помеченным указателем, где индиректные случаи занимают указатель размером слова на кучу, тогда как неиндиректные случаи хранят свои полезные нагрузки инлайн в объеме памяти перечисления. Это смешанное представление оптимизирует использование памяти для перечислений, в которых только определенные случаи требуют рекурсии. Однако это приводит к усложнению сопоставления шаблонов, поскольку компилятор должен генерировать разные пути доступа к инлайн и индиректным полезным нагрузкам, а общий размер перечисления определяется крупнейшей инлайн-полезной нагрузкой плюс битами тегов, а не размерами индиректных случаев.
Почему рекурсивные перечисления с indirect могут создавать циклы удержания, когда мы имеем дело с замыканиями, и чем это отличается от стандартного поведения типов значения?
Это тонкий момент, который показывает глубокое понимание ARC. Обычно типы значения, такие как перечисления, не могут создавать циклы удержания, потому что они лишены идентичности и подсчета ссылок на уровне значения. Однако, когда случай помечен как indirect, полезная нагрузка выделяется в куче и управляется по подсчету ссылок. Если значения, связанные с индиректным случаем, включают замыкание, которое захватывает само перечисление, и это замыкание хранится обратно в связанные значения перечисления, возникает цикл удержания между кучей и замыканием. Это отличается от циклов, основанных на классах, поскольку цикл существует в контейнере, выделенном в куче, а не в самом значении перечисления. Чтобы разорвать цикл, необходимо использовать списки захвата, такие как [weak self] или [unowned self], но поскольку перечисления обычно являются типами значения, разработчики часто забывают, что indirect вводит семантику ссылок для полезной нагрузки, требуя такой же бдительности, как и классы при работе с замыканиями.