SwiftのArraySliceのおもしろい話

ArraySlice は Array の部分列を表す型です。たとえば、↓の s は a の 2 〜 4 番目の要素を表す ArraySlice です。

let a: [String] = ["A", "B", "C", "D", "E", "F"]
//                            ^    ^    ^
let s: ArraySlice<String> = array[2 ..< 5] // ["C", "D", "E"]

Swift の ArraySlice はおもしろい特徴を持っています。 他の言語と比較しながらそのおもしろさを見てみましょう。

本記事は Swift Zoomin' #1 で話した内容をテキスト化したものです。

部分列の生成とコピー

他の言語でも配列やリストの部分列を取得することができます。↓は Python と Java の例です。

# Python
a = ['A', 'B', 'C', 'D', 'E', 'F']
#               ^    ^    ^
s = a[2:5]

// Java
List<String> a = asList("A", "B", "C", "D", "E", "F");
//                                 ^    ^    ^
List<String> s = a.subList(2, 5);

これだけだと Swift との違いがないように見えます。次に、得られた部分列に変更を加えてみましょう。

// Swift
var a = ["A", "B", "C", "D", "E", "F"]
//        ^    ^    ^
var s = a[..<3]

s[0] = "*"

a[..<3] で ["A", "B", "C"] を取得し、その後 s[0] = "*" で 0 番目の要素を "*" に変更しています。そのため、 s は ["*", "B", "C"] になります。

問題は、このとき a がどうなるかです。 Swift の Array と ArraySlice は値型なので^[1]、 a と s への変更が互いに影響を与えることはありません。そのため、 s を変更しても a の 0 番目の要素は変更されず、 a は ["A", "B", "C", "D", "E", "F"] のままです。

しかし、 Java では事情が異なります。 Java の List は参照型で、 List とその部分列はバッファを共有しています。そのため、片方に変更を加えるともう片方に影響を与えます。

// Java
List<String> a = asList("A", "B", "C", "D", "E", "F");
//                       ^    ^    ^
List<String> s = a.subList(0, 3);

s.set(0, "*");

このとき、 a の 0 番目の要素も "*" に変更されます。多くの場合、これは望ましい挙動ではありません。片方への変更が、意図せずもう一方に影響を与えてしまう可能性があり、わかりづらいバグの原因になり得るからです。

Python ではどうでしょうか。 Python のリストも Java 同様に参照型ですが、バッファの共有は起こりません。

# Python
a = ['A', 'B', 'C', 'D', 'E', 'F']
#               ^    ^    ^
s = a[:3]

s[0] = '*'

↑を実行しても a[0] は 'A' のままです。どうしてでしょうか。 Python では a[:3] で部分列を生成するときに、バッファの該当部分をコピーして新しいリストが作られます。リストとその部分列がバッファを共有するわけではありません。部分列生成時にバッファをコピーすることで、バッファ共有に起因する意図しない変更を防止することができます。

しかし、部分列をコピーするのに要する計算量は、部分列の長さを n として $O(n)$ です。一方で、 Java では部分列を作るのに $O(1)$ しかかかりません。バッファを共有するのでコピーの必要がないからです。元の List の何番目の要素から何番目の要素までを切り出すのか、始めと終わりを記録するだけです。

Swift ではどうでしょうか。 Array から ArraySlice を生成する処理は、 Java 同様に $O(1)$ で実行できます。 ArraySlice 生成時には、元の Array と生成された ArraySlice の間でバッファが共有されます。これも Java と同じです。では、バッファが共有されるにも関わらずどうして変更に対して独立な（片方に変更を加えてももう片方に影響を与えない）のでしょうか。

これは Copy-on-Write によって実現されています。 Array や ArraySlice は自身に変更を加える前に、自分が保持するバッファが他のインスタンスと共有されていないかをチェックします。そして、共有されていた場合はバッファのコピーを生成し、自分はそのコピーされたバッファを保持するようにします。そうすると、今自分が保持しているのは新しく生成されたバッファなので、誰とも共有されていません。他に影響を与える心配をすることなく、変更を加えることができます。

このようにして、 $O(1)$ での ArraySlice の生成と、変更に対する独立性を両立しています。 ArraySlice 生成後に初めて変更を加える場合には、コピーのコスト $O(n)$ を支払う必要があります。しかし、これは Java であっても同じ話です。バッファ共有による意図しない変更を防ぐためにはコピーは避けられません。

// Java
List<String> a = asList("A", "B", "C", "D", "E", "F");
//                       ^    ^    ^
List<String> s = new ArrayList<>(a.subList(0, 3)); // 明示的なコピー

s.set(0, "*");

Java ではプログラマーが明示的にコピーのコードを書く必要がありますが、この明示的なコピーを忘れてしまうとバッファ共有による意図しない変更を引き起こしてしまう可能性があります。 Copy-on-Write はそのようなコピー忘れを防止する仕組みと考えることもできます。

整理すると、次のようになります。

言語	部分列生成時のコスト	部分列に初回変更を加える際のコスト	明示的なコピー
Python	$O(n)$	$O(1)$	不要
Java	$O(1)$	$O(n)$	必要
Swift	$O(1)$	$O(n)$	不要

生成された部分列に後から変更が加えられるかは、部分列生成時にはわかりません。 Python は変更に備えて、部分列生成時に予め $O(n)$ のコストを支払います。 Java は変更が加えられる段階になって初めて $O(n)$ のコストを支払うため、 $O(n)$ が無駄になることはありません。しかし、コピーを明示的に書かなければいけないので、コードのミスによってバッファ共有による意図しない変更と、それに起因するバグを引き起こす可能性があります。 Swift は Java 同様に必要になって初めて $O(n)$ を支払うので無駄がなく、またコピーは Copy-on-Write で自動的に行われるので、コピー忘れが発生することもありません。

このように見比べてみると、 Swift の ArraySlice が Python と Java の方式のいいとこどりになっていることがわかります。

部分文字列とリーク

今度は視点を変えて String とその部分列について見てみましょう。

Java では、 String クラスの substring メソッドで部分文字列を生成することができます。

昔の Java の実装では、 List と同じように部分文字列はオリジナルとバッファ共有をしていました。そのため、 substring メソッドを用いて $O(1)$ で部分文字列を生成することができました。

// 昔の Java
String a = "...";
String s = a.substring(i, j); // バッファを共有 O(1)

しかし、今の Java では Python のリストと同じように、部分文字列を生成する際にコピーを実行します。そのため、 substring メソッドの計算量は $O(n)$ です。

// 今の Java
String a = "...";
String s = a.substring(i, j); // バッファをコピー O(n)

Java の String はイミュータブルクラスです。 subList のように変更を加えられる心配はありません。バッファ共有による意図しない変更は起こりません。 substring こそバッファ共有して $O(1)$ にすれば良さそうです。どうして、わざわざバッファをコピーする実装に変更されたのでしょうか。

Java の substring に変更が加えられたのは、生成された部分文字列によるリークが問題になったからです。例として、 "Hello, world!" という String を考えてみましょう。この文字列の 7 文字目から 5 文字を抜き出して "world" という部分文字列を生成します。

Hello, world!
       ^^^^^

このとき、生成された部分文字列 "world" は、内部でオリジナルの文字列 "Hello, world!" とバッファを共有しています。つまり、 "Hello, world!" というバッファを参照しているわけです。

すると、オリジナルの文字列が利用されなくなって解放されても、部分文字列 "world" が生き残っている限り "Hello, world!" 全体のバッファが解放されません。

"Hello, world!" のようなわずか 13 文字の文字列であればあまり問題にはなりませんが、これが　10 万文字の文字列のうちの 5 文字だとどうでしょうか。わずか 5 文字のために 10 万文字分のバッファを確保し続けることになってしまいます。ベンチマークの結果、コピーを避ける効果よりもリークの弊害の方が大きく、 Java は部分文字列生成時にコピーを行うように実装の修正がされました。

しかし、この変更は常に適切とは限りません。パーサーのような、大量の部分文字列を生成する用途ではパフォーマンスに悪影響を与える可能性があります。

Swift では、 String と Substring を分けることでこの問題を回避しています。

ArraySlice が Array の部分列を表すように、 Swift には String の部分列を表す型 Substring があります。 Substring の生成は、昔の Java と同じく $O(1)$ です。

// Swift　
let a: String = "..."
let s: Substring = a[i..<j]   // バッファを共有 O(1)

では、リークの問題にはどうやって対処しているのでしょうか。

String と Substring は異なる型です。そのため、 Substring を String 型の変数やプロパティに代入することはできません。

たとえば、 UILabel の text プロパティは String? 型です。もし、 10 万文字の String から 5 文字の Substring を作っても、それをそのまま UILabel に渡すことはできません。そのため、 5 文字のために 10 万文字分のバッファがリークすることもありません。 text に Substring を渡すには、必ず String への変換が必要となります。

// Swift
let string: String = ... // 10 万文字
let substring: Substring = string.prefix(5) // 先頭 5 文字
lable.text = substring // ⛔ コンパイルエラー
label.test = String(substring) // ✅ 5 文字だけコピーするのでリークしない

このようにして、 Swift の String と Substring では、 $O(1)$ での部分文字列生成とリーク防止を両立しています。

ArraySlice と抽象型

まったく同じ話は Array と ArraySlice にも言えます。巨大な Array から短い ArraySlice を切り出した場合、 ArraySlice を長期的に保持すると巨大なバッファ全体が生き続けてしまう可能性があります。長期的に保持する場合（プロパティなどで）は ArraySlice ではなく Array として保持することで、このようなリークを防止できます。

これのおもしろいところは、短所を長所に変えていることです。

Swift は値型中心の言語で、標準ライブラリの提供するほとんどの型が値型です。 Array や ArraySlice も例外ではありません。

しかし、（参照型と異なり）値型は抽象的な型で扱いづらいという問題があります。たとえば、 [Int] と ArraySlice<Int> を抽象的な Collection 型の変数で扱うことはできません。

let array: [Int] = [0, 1, 1, 2, 3, 5, 8]
let slice: ArraySlice<Int> = array.dropFirst() // [1, 1, 2, 3, 5, 8]

var collection: Collection<Int> = array // ⛔ コンパイルエラー
collection = slice // ⛔ コンパイルエラー

Java では ArrayList もそのサブリストもすべて List 型の変数で抽象的に扱えます。 Swift はそれができないという短所を、 $O(1)$ の部分列生成とリーク防止を両立する手段として利用することで長所に変えているわけです。

なお、 Swift でも Array と ArraySlice の抽象化ができないわけではありません。 Java などの参照型中心のオブジェクト指向言語ではサブタイピング（サブタイプポリモーフィズム）で抽象化を実現することが多いですが、 Swift ではパラメトリックポリモーフィズムを用います。

たとえば、次のようにして [Int] でも ArraySlice<Int> でも（もっと言えば Set<Int> や Range<Int> などでも）要素の和を求める関数を作ることができます。

func sum<S: Sequence>(of sequence: S) -> Int where S.Element == Int {
    sequence.reduce(0, +)
}

Swift の値型と抽象化については、詳細は↓を御覧ください。

• Protocol-oriented Programming とは

まとめ

• Swift の ArraySlice は元の Array から $O(1)$ で生成できる
• にも関わらず、 ArraySlice と元の Array は変更に対して独立
• Array と ArraySlice 、 String と Substring のように、オリジナルと部分列で型が分かれていることでリークを防止している
• 抽象的なコレクション型の変数（やプロパティ）を作ることはできないが、その短所をリーク防止の長所に変えている
• Swift のコレクションを抽象的に扱うには、サブタイピングではなくパラメトリックポリモーフィズムを用いる

脚注

1. より正確には「値型として自然な振る舞いをするように実装されているので」です。この「値型として自然な振る舞い」をすることを Value Semantics を持つと言います。