Swift Digest
Add isTriviallyIdentical(to:) Methods for Quick Comparisons to Concrete Types
01 何が問題だったのか
Array や Dictionary、String のような Standard Library のコレクション型は、値が等しいかを == で比較できます。しかしこの比較は最悪計算量 O(n) で、要素数が多くなるほど高くつきます。
たとえば、入力が変わらなければ前回の結果を使い回したい、というメモ化のような場面では、この O(n) の等価比較がそのままボトルネックになります。
final class Memoizer {
private var input: [Int]?
private var result: [Int]?
func result(for input: [Int]) -> [Int] {
if let result = self.result,
self.input == input { // O(n) の等価比較
return result
} else {
print("computing new result")
self.input = input
let result = input.filter { $0 % 2 == 0 }
self.result = result
return result
}
}
}
「O(n) の計算を避けるためにキャッシュしたい」のに、キャッシュの判定自体が O(n) であれば、結果を毎回計算し直すのと大差ないことになります。
SwiftUI の body のように、状態が少しでも変わるたびに再計算され、その中で filter などの O(n) 処理が走るような場面でも事情は同じです。「同じ配列が来たら計算をスキップしたい」と思っても、その判定に == を使ってしまうと、結局 O(n) のコストを払い続けることになります。
copy-on-write が持つ「速い経路」
Array や Dictionary、String などはいわゆる copy-on-write 型で、値型として振る舞いつつ内部に共有ストレージへの参照を持ちます。値をコピーしただけでは中身は複製されず、書き込みが起きるタイミングで初めてストレージが複製されます。
つまり、2つの値が同じストレージを参照していれば、その時点では中身が必ず一致しているはずで、これは O(1) で判定できます。実際 String には公開非公式（アンダースコア付き）の _isIdentical(to:) がすでに存在していて、Span / RawSpan では公式に isIdentical(to:) が提供されています。Swift Collections や Swift Markdown など外部ライブラリでも同様の API が広く使われています。
これまで一般のユーザーがこの「速い経路」を踏むには、withUnsafeBufferPointer で内部バッファのアドレスを比較したり、Array を Span に橋渡ししたりといった、回りくどく制約の多い方法しかありませんでした。連続したストレージが存在しなければ追加で O(n) のコピーが発生してしまうこともあり、本来の目的である「定数時間で速く判定する」ことが達成できないケースもありました。
メモ化の判定のように、「等しいかどうか」までは要らないが、「明らかに同じ値である」ことだけ高速に確かめたい という用途のために、Standard Library の主要な型に対して、定数時間で完了する公式の API が必要でした。
02 どのように解決されるのか
Standard Library の主要な具象型に、定数時間 O(1) で2つの値が「自明に同一」かを判定する isTriviallyIdentical(to:) メソッドを追加します。true を返したときは「2つの値は中身まで等しいことが保証される」、false のときは「等しいかもしれないし違うかもしれない（それ以上のことは何も言わない）」というセマンティクスです。
final class Memoizer {
private var input: [Int]?
private var result: [Int]?
func result(for input: [Int]) -> [Int] {
if let result = self.result,
self.input?.isTriviallyIdentical(to: input) == true {
return result // O(1) で判定して即返す
} else {
print("computing new result")
self.input = input
let result = input.filter { $0 % 2 == 0 }
self.result = result
return result
}
}
}
同じ Array を別変数に代入しただけ（コピー直後でストレージを共有している）なら isTriviallyIdentical(to:) は true を返し、メモ化された結果がそのまま使われます。一方、要素はまったく同じだが別途リテラルから作られた Array のように、ストレージが共有されていない場合は false を返すことがあり、その場合は通常通り計算がやり直されます。「等しい値に対して false を返しうる」ことは仕様であり、その代わりに常に O(1) で済むことが保証されます。
セマンティクス
isTriviallyIdentical(to:) は次の性質を満たすように設計されています。
a.isTriviallyIdentical(to: a)は常にtrue（反射律）。a.isTriviallyIdentical(to: b)ならばb.isTriviallyIdentical(to: a)（対称律）。a.isTriviallyIdentical(to: b)かつb.isTriviallyIdentical(to: c)ならばa.isTriviallyIdentical(to: c)（推移律）。- 型が
Equatableの場合、a.isTriviallyIdentical(to: b)ならばa == b（ただしFloat.nanのような例外的な値は除く）。逆は成り立たない（==でもisTriviallyIdentical(to:)はfalseでありうる）。
導入される型では、内部に「ストレージへの参照」のような速い同一性判定の手がかりがあり、isTriviallyIdentical(to:) が == よりも 意味のあるレベルで 速いことが前提になっています。逆に言えば、Int や Bool のような型にはこの API は導入されません（== 自体が十分速いため）。
対象となる型
このメソッドは Standard Library の以下の具象型に追加されます。型ごとに新たなプロトコルを導入するのではなく、各型のインスタンスメソッドとして個別に追加される形です。
String、Substring、およびそれぞれのUnicodeScalarView/UTF16View/UTF8ViewArray、ArraySlice、ContiguousArrayDictionary、SetUnsafeBufferPointer、UnsafeMutableBufferPointer、UnsafeRawBufferPointer、UnsafeMutableRawBufferPointerUTF8Span、Span、RawSpan
UnsafeBufferPointer 系や UTF8Span / Span / RawSpan のように Equatable でない（あるいは値そのものではなくメモリ領域を指す）型の場合は、「2つのインスタンスがメモリ上の同じ領域を指しているか」というより低レベルなセマンティクスになります。
SwiftUI のメモ化での使用例
冒頭で挙げたような、SwiftUI で body のたびに filter が走ってしまうケースも、同じ要領で書けます。
extension Favorites {
private final class Storage {
private var contacts: [Contact]
private var favorites: [Contact]?
func update(_ contacts: [Contact]) {
// == の代わりに isTriviallyIdentical(to:) で O(1) 判定
if self.contacts.isTriviallyIdentical(to: contacts) == false {
self.contacts = contacts
self.favorites = nil
}
}
var wrappedValue: [Contact] {
if let favorites = self.favorites {
return favorites
}
let favorites = self.contacts.filter { $0.isFavorite }
self.favorites = favorites
return favorites
}
}
}
ユーザーが選択を変えた程度では contacts 自体の値は変わらず、@State として渡される配列はストレージを共有したままなので、isTriviallyIdentical(to:) が true を返してメモ化が効き続けます。
想定される使い所
このメソッドは「とりあえず == の代わりに使う」ための API ではありません。あくまで 値の等価比較が高くつく場面で、まず O(1) の高速判定を試し、ヒットしたら処理をスキップする といった、性能最適化のための補助フックです。
- メモ化や不要な再計算の抑制
- 大きなコレクションを引数として渡す API での「変更があったときだけ再処理」
- SwiftUI / Observation など、状態変化のたびに派生値の計算が走るレイヤーでの最適化
isTriviallyIdentical(to:) が false を返した場合に、どうしても正確な判定が必要なら従来通り == にフォールバックする、という二段構えになります。
Future Directions（参考）
提案では、今回の対象は影響の大きい型に絞られており、Character や Dictionary.Keys / Dictionary.Values、KeyValuePairs、StaticString といった他の copy-on-write 的な型にも将来的に同じメソッドを追加していける、と speculative に触れられています。あくまで今後の方向性を示すもので、実現を約束するものではありません。