質問への回答

質問の歴史

この設計決定は、Swiftが標準ライブラリのコレクションに対して値セマンティクスを根本的にコミットしていることに起因しています。Objective-CのNSMutableDictionaryやC++のstd::unordered_mapのように参照セマンティクスを露呈したり、内部ノードへの外部ポインタを許可したりするのに対し、SwiftはDictionaryとSetを純粋な値型として扱います。Swiftがこれらのコレクションに対して参照型のパフォーマンスを維持しつつ値型の安全性を保つためにCopy-on-Write（COW）最適化を採用したとき、エンジニアリングチームはインデックスの安定性に関する重要な決定に直面しました。ミューテーション時にインデックスを無効化するという解決策は、ハッシュテーブルの拡張、衝突解決、またはエントリ削除の際に再割り当てされたストレージへのダングリング参照を防ぐために公式化されました。

問題

核心的な問題は、COWセマンティクスとハッシュテーブルの実装詳細の相互作用から生じます。Dictionaryが挿入や削除を通じてミューテートすると、負荷係数が閾値を超えるとリサイズを引き起こす可能性があり、新しい大きなバッファが割り当てられ、すべてのエントリが再ハッシュされます。それ以前に作成された既存のIndex値は、古いバッファの物理メモリへのオフセットまたはポインタをカプセル化しています。そのインデックスがミューテーション後にアクセスされた場合、解放されたメモリを逆参照する（use-after-free）か、間違ったバケットからのデータを返すことになります。Swiftは、独立したDictionaryのコピー間で各Index値の寿命を追跡することができないため（値セマンティクスは無制限のコピーを許す）、すべての未解決のインデックスを安全に更新することができません。したがって、言語はメモリ安全性の保証を維持するためにそのようなインデックスを無効と宣言する必要があります。

解決策

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上で高頻度取引ダッシュボードを構築しており、Stringティッカーシンボルをキーとして使用してライブ価格データをキャッシュするためにDictionaryを利用していました。迅速な更新時にUIレンダリングパフォーマンスを最適化するため、彼らはテーブルビューセルの構成中に繰り返しハッシュ計算を避けるために、直接のDictionaryインデックスをビューモデル内に保存していました。しかし、バックグラウンドのWebSocketスレッドが辞書に新しい価格ポイントを挿入すると、アプリケーションはEXC_BAD_ACCESSのまばらなクラッシュを示したり、再割り当てされたメモリ領域からの破損したデータを表示したりしました。これはキャッシュされたインデックスがリサイズ操作中に再割り当てされたハッシュテーブルのバケットを参照していたためです。

考えられた最初の解決策は、参照セマンティクスと安定したオブジェクト参照を提供するFoundationからNSMutableDictionaryに移行することでした。このアプローチは、辞書のミューテーションに関わらずエントリへの永続的な参照を維持できるため、アプリケーションライフサイクル全体にわたるインデックスのような安定性を保つことができました。しかし、これは値型の隔離を破り、バックグラウンドキューとメインスレッド間で辞書をコピーする際に意図しないデータ共有や競合状態を引き起こしました。さらに、NSMutableDictionaryはSwiftのジェネリック型安全性を欠き、値型（structインスタンスなど）に対して高価なブリッジオーバーヘッドを必要とし、パフォーマンスを低下させるボクシング操作を強いられました。

考えられた二つ目の解決策は、UnsafeMutablePointerを使用してカスタムオープンアドレッシングハッシュテーブルを実装し、安定したノードメモリアドレスを手動で管理し、Swiftのインデックス無効化メカニズムを完全に回避することでした。これにより、格納されたインデックスに対して決定論的なポインタの安定性を提供し、検索時の再ハッシュオーバーヘッドなしにO(1)アクセスを可能にするはずでした。しかし、このアプローチはmallocとfreeを使用した手動メモリ管理を必要とし、ノードが削除時に適切に解放されない場合にメモリリークの重大なリスクを引き起こしました。また、これはSwiftのCOW最適化を回避し、辞書の各コピーはヒープに割り当てられたバッファの完全なディープコピーを必要とし、1万件を超えるデータセットのパフォーマンスを台無しにしました。

チームは最終的に三つ目の解決策を選び、インデックスキャッシングを完全に排除し、代わりにビューモデル内にキー（Stringティッカー）の配列を保存し、各セル構成サイクル中にキーを基にしたルックアップを行うことにしました。このアプローチは、Swiftの値セマンティクスとメモリ安全性の保証を維持しつつ、依然としてO(1)の平均ケースのルックアップパフォーマンスを提供しました。アクセスするたびにキーの再ハッシュコストがかかりましたが、最新のSwiftの文字列ハッシュはSipHashを通じて高度に最適化されており、安全性の保証が微小なマイクロ秒レベルのパフォーマンス損失を上回りました。また、彼らはオープンソースのSwift CollectionsパッケージからOrderedDictionary型を採用し、不安定なインデックスに頼らずに決定論的な順序を提供しました。

その結果、以降の三ヶ月間のモニタリング期間中にEXC_BAD_ACCESSクラッシュが完全に排除されました。アプリケーションのメモリフットプリントは、50,000の同時価格エントリがあっても安定しており、コードベースはUnsafeMutablePointer操作の複雑さなしで大幅にメンテナブルになりました。チームは、ミューテーションの境界を越えたDictionaryやSetのインデックスの保存を禁止する厳格なアーキテクチャガイドラインを確立し、将来の回帰を防ぐためにこのパターンを内部Wikiに文書化しました。

候補者が見逃すことがよくあること

なぜSwiftのArrayは一部のミューテーション後にインデックスの再利用を許可し、Dictionaryはそうしないのか？両者はCOWセマンティクスを持つ値型にもかかわらず。

Arrayのインデックスは、連続ストレージのベースアドレスからのオフセットを表す軽量なInt値です。容量を超えて追加するなどの再割り当てを引き起こすArrayのミューテーションは、バッファを移動することで技術的にインデックスを無効化しますが、Arrayのインデックスは検証のための世代メタデータを持たないため、キャッシュするのは危険ですが明示的にチェックされてはいません。一方、Dictionaryのインデックスは、スパースハッシュテーブル内のバケットオフセットを含む複雑な内部状態をカプセル化しています。ハッシュテーブルのエントリは再ハッシュ中に予測不可能に移動するため（負荷係数のしきい値や衝突解決によってトリガーされる）、整数オフセットは意味を失います。理論的にはSwiftはDictionaryに論理インデックスの間接参照を実装できますが、これはすべてのアクセスを遅くする追加のポインタ追跡を必要とします。したがって、DictionaryとSetは世代カウントを通じてインデックスを積極的に検証し、無効化しますが、Arrayのインデックスはプログラマーに有効性を保証することを依存しており、連続ストレージとハッシュストレージ間の異なるパフォーマンスと安全性のトレードオフを反映しています。

Copy-on-Writeメカニズムは、Dictionaryのミューテーションが現在のインスタンスでインデックス無効化を要求するか、新しいコピーを生成する必要があるかをどのように決定するのか？

Swiftは、内部バッファ（_NativeDictionary）の参照カウントを利用します。ミューテーションの前に、ランタイムはisUniquelyReferencedNonObjCを呼び出してバッファの参照カウントを確認します。カウントが1（ユニーク所有）に等しければ、その場でミューテーションが行われ、この特定のインスタンスのインデックスのみが無効化され、世代カウントがインクリメントされます。参照カウントが1を超えた場合（共有所有）、Swiftは新しいバッファを割り当て、すべての要素をコピーし、新しいコピー上でミューテーションを行います。元のインスタンスは変更されず、有効なインデックスが維持され、新しいコピーは新しい世代カウント（効果的にインデックスゼロ）で開始します。この違いは価値セマンティクスにとって重要であり、値代入後、両方の変数はストレージを共有し、一方がミューテートすると遅延コピーがトリガーされます。ミューテーションポイントは論理的な分割が発生する場所であり、ミューテーションインスタンスが修正前にユニークな所有権を持つことを保証します。

UnsafeMutablePointerやUnmanagedを使用して原始ストレージにアクセスすることで、SwiftのDictionaryのインデックス無効化を回避できるか、そしてそれが引き起こす壊滅的なリスクは何か？

技術的には、UnsafeMutablePointerやUnmanagedは、withUnsafeMutablePointerを使用してDictionaryの内部ストレージへの直接アクセスを提供できますが、これは未定義の動作を構成します。Dictionaryの内部レイアウトは不透明であり、Swiftのバージョン間で変化する可能性があります（レジリエンス）。直接ポインタ操作は世代カウントのチェックをバイパスし、リサイズ中に再割り当てが行われた場合、解放されたメモリにアクセス可能にします。さらに、ハッシュテーブルは占有ビットマップや削除されたエントリのトゥームストーンマーカーに関する複雑な不変条件を維持します。手動ポインタ操作はこれらの不変条件を壊し、プローブシーケンス中に無限ループを引き起こしたり、静かにデータが破損したり、次のDictionary操作中にクラッシュを引き起こす可能性があります。Swiftの安全モデルはこれを明示的に禁止しており、安定した参照を維持する唯一の安全なメカニズムは、キーを使用することです（アクセスのたびに再ハッシュされる）またはコレクションから値を別の配列にコピーすることです。