Это проектное решение происходит от Swift'а, который принципиально придерживается семантики значений для коллекций стандартной библиотеки. В отличие от NSMutableDictionary в Objective-C или std::unordered_map в C++, которые используют семантику ссылок или позволяют внешние указатели на внутренние узлы, Swift рассматривает Dictionary и Set как чистые типы значений. Когда Swift принял оптимизации Copy-on-Write (COW) для этих коллекций, чтобы достичь производительности ссылочных типов, сохраняя безопасность типов значений, инженерная команда столкнулась с критическим решением по поводу стабильности индексов. Решение об аннулировании индексов при мутации было зафиксировано, чтобы предотвратить зависшие ссылки на перераспределённую память во время роста хэш-таблицы, разрешения коллизий или удаления записей.
Основная проблема возникает из взаимодействия между семантикой COW и деталями реализации хэш-таблицы. Когда Dictionary мутирует через вставку или удаление, это может вызвать изменение размера, если коэффициент загрузки превышает пороги, выделяя новый, более крупный буфер и перехешируя все записи. Любое существующее значение Index, созданное до мутации, инкапсулирует смещение или указатель на физическую память старого буфера. Если этот индекс будет доступен после мутации, он разыменует освобождённую память (use-after-free) или вернёт данные из неправильных ящиков. Поскольку Swift не может отслеживать время жизни каждого значения Index через независимые копии Dictionary (семантика значений допускает неограниченное копирование), он не может безопасно обновить все действительные индексы. Поэтому язык должен объявить такие индексы недействительными, чтобы поддерживать гарантии безопасности памяти.
Swift решает эту проблему, встраивая счетчик поколения или номер версии в заголовок внутреннего хранилища Dictionary. Каждый Index захватывает этот идентификатор поколения в момент создания. Когда Dictionary мутирует, среда выполнения увеличивает этот счетчик поколения и потенциально перераспределяет основной буфер. Любое последующее использование устаревшего Index сравнивает его сохранённое поколение с текущим; несовпадение приводит к детерминистической ошибке времени выполнения (нарушение предусловия). Этот подход жертвует стабильностью индексов при мутациях в пользу безопасности памяти и целостности семантики значений. Для оптимизации COW среда выполнения проверяет счётчики ссылок перед мутацией: если ссылка уникальна, она мутирует на месте (аннулируя индексы); если общая, сначала копирует буфер, оставляя индексы оригинального экземпляра действительными, в то время как новая копия получает свежий счётчик поколения.
var marketData: [String: Double] = ["AAPL": 150.0, "GOOGL": 2800.0] let indexBeforeUpdate = marketData.index(forKey: "AAPL")! // Поколение 0 marketData["TSLA"] = 700.0 // Мутация увеличивает поколение, может перераспределить // Ошибка времени выполнения: попытка доступа с использованием недействительного индекса из поколения 0 // let price = marketData[indexBeforeUpdate]
Команда разработчиков строила панель высокочастотной торговли, используя Swift на iPad, используя Dictionary для кэширования живых цен с String тикерами в качестве ключей. Чтобы оптимизировать производительность рендеринга пользовательского интерфейса во время быстрых обновлений, они хранили прямые индексы Dictionary внутри своих моделей представлений, чтобы избежать повторных вычислений хешей во время конфигурации ячеек представления таблицы. Однако, когда фоновый поток WebSocket вставлял новые ценовые значения в словарь, приложение проявляло спорадические сбои с EXC_BAD_ACCESS или отображало повреждённые данные из освобождённых областей памяти, поскольку кэшированные индексы ссылались на ящики хэш-таблицы, которые были перераспределены во время операций изменения размера.
Первое рассмотренное решение заключалось в переходе на NSMutableDictionary из Foundation, который предоставляет семантику ссылок и стабильные ссылки на объекты, а не семантику значений. Этот подход позволил бы команде поддерживать постоянные ссылки на записи независимо от мутаций словаря, сохраняя стабильность индексов в течение всего жизненного цикла приложения. Однако это ввело семантику ссылок, которая нарушала изоляцию типов значений между моделями представлений, ведя к непреднамеренному совместному использованию данных и гонкам при копировании словарей между фоновыми очередями и основным потоком. Кроме того, NSMutableDictionary не обладает типобезопасностью Swift и требует дорогостоящих операций промежуточного представления для типов значений, таких как экземпляры struct, что приводит к операциям упаковки, ухудшающим производительность.
Второе исследованное решение заключалось в реализации собственной хэш-таблицы с открытой адресацией с использованием UnsafeMutablePointer, чтобы вручную управлять стабильными адресами памяти узлов, тем самым полностью обойдя механизм аннулирования индексов Swift. Это обеспечило бы детерминистическую стабильность указателей для хранящихся индексов, позволяя доступ O(1) без накладных расходов на перехеширование во время поиска. Однако этот подход требовал ручного управления памятью с помощью malloc и free, что вводило значительные риски утечек памяти, если узлы не были правильно освобождены после удаления. Он также обходил оптимизации COW в Swift, что означает, что каждое копирование словаря потребовало бы полного глубокого копирования буфера, выделенного в куче, разрушая производительность для наборов данных, превышающих десять тысяч записей.
Команда в конечном итоге выбрала третье решение: полностью исключить кэширование индексов, а вместо этого хранить массивы ключей (String тикеры) в своих моделях представлений, выполняя поиск на основе ключей во время каждого цикла конфигурации ячейки. Этот подход был выбран, поскольку он сохранял семантику значений Swift и гарантии безопасности памяти, обеспечивая при этом производительность поиска O(1) в среднем. Хотя это влекло за собой необходимость перехеширования ключа при каждом доступе, современное хеширование строк Swift высоко оптимизировано с помощью SipHash, и гарантии безопасности перевешивали незначительные микросекундные штрафы по производительности. Они также приняли тип OrderedDictionary из открытого пакета Swift Collections, чтобы обеспечить детерминистический порядок без зависимости от нестабильных индексов.
Результатом стало полное устранение сбоев EXC_BAD_ACCESS в течение последующего трехмесячного периода мониторинга. Объём памяти приложения оставался стабильным, даже при 50 000 одновременных записей цен, и кодовая база стала значительно легче в обслуживании без сложности операций UnsafeMutablePointer. Команда установила строгие архитектурные рекомендации, запрещающие хранение индексов Dictionary или Set через любые границы мутации, документируя этот шаблон в своей внутренней вики, чтобы предотвратить будущие регрессии.
Почему Array в Swift допускает повторное использование индексов после некоторых мутаций, а Dictionary нет, хотя оба являются типами значений с семантикой COW?
Индексы Array представляют собой легковесные значения Int, представляющие смещения от базового адреса в непрерывном хранилище. В то время как мутации Array, которые вызывают перераспределение (такие как добавление за пределами ёмкости), технически аннулируют индексы перемещением буфера, индексы Array не несут метаданных о поколении для проверки, что делает их опасными для кэширования, но явно не проверяемыми. Однако индексы Dictionary инкапсулируют сложное внутреннее состояние, включая смещения корзин в разреженной хэш-таблице. Поскольку записи хэш-таблицы перемещаются непредсказуемо во время перехеширования (инициируемого пороговыми значениями коэффициента загрузки или разрешением коллизий), целочисленные смещения теряют семантическое значение. Swift теоретически мог бы реализовать логическую индексацию для Dictionary, но это потребовало бы дополнительной адресной обработки, замедляющей каждый доступ. Таким образом, Dictionary и Set активно проверяют и аннулируют индексы через счета поколений, тогда как индексы Array полагаются на программиста для обеспечения действительности, что отражает различные компромиссы производительности и безопасности между непрерывным и хэшированным хранилищем.
Как механизм Copy-on-Write определяет, требует ли мутация Dictionary аннулирования индексов в текущем экземпляре или создания новой копии с новыми индексами?
Swift использует подсчет ссылок на внутренний буфер (_NativeDictionary). Перед любой мутацией среда выполнения вызывает isUniquelyReferencedNonObjC, чтобы проверить счётчик ссылок буфера. Если счётчик равен одному (уникальное владение), мутация происходит на месте, аннулируя только индексы в этом конкретном экземпляре, увеличивая счётчик поколения. Если счётчик ссылок превышает один (общая собственность), Swift выделяет новый буфер, копирует все элементы и выполняет мутацию в новой копии. Оригинальный экземпляр остаётся неизменным с действительными индексами, в то время как новая копия начинается с нового счётчика поколения (фактически индекс 0). Это различие критично для семантики значений: после присвоения значения обе переменные разделяют хранилище, пока одна из них не мутирует, инициируя ленивое копирование. Точка мутации это место, где происходит логический разрыв, обеспечивая уникальное владение мутирующего экземпляра перед изменением.
Можно ли обойти аннулирование индексов Dictionary в Swift, используя withUnsafeMutablePointer или Unmanaged для доступа к сырому хранилищу, и какие катастрофические риски это вводит?
Технически UnsafeMutablePointer и Unmanaged могут предоставить прямой доступ к внутреннему хранилищу Dictionary через withUnsafeMutablePointer к внутреннему хранилищу или путём приведения Dictionary к сырым байтам. Однако это является неопределённым поведением. Внутренняя структура Dictionary является непрозрачной и подвержена изменениям между версиями Swift (устойчивость). Прямое манипулирование указателями обходит проверки счётчиков поколения, позволяя доступ к освобождённой памяти, если произошла перераспределение во время изменения размера. Более того, хэш-таблицы поддерживают сложные инварианты, касающиеся битмапирования заполняемости и маркеров могил для удалённых записей. Ручное манипулирование указателем может испортить эти инварианты, что приведет к бесконечным циклам во время последовательностей проб, молчаливой порче данных или сбоям в последующих операциях Dictionary. Модель безопасности Swift явно запрещает это; единственный безопасный механизм для обеспечения стабильных ссылок — это использование ключей (которые перехешируются при каждом доступе) или копирование значений из коллекции в отдельный массив.