先日SwiftのArrayがヤバイという投稿をしましたが、その後仕様が変更されたこともあり、考えれば考えるほど SwiftのArrayがすばらしいように思えてきました。
SwiftのArrayがすばらしいと思うのは、 Arrayが参照型ではなく値型であることで無駄なコピーが回避できる からです。単純に考えると、代入の度にコピーが発生する値型の方が無駄なコピーが発生しそうなものです。
なお、本投稿ではArrayのみを扱いますが、Dictionaryについてもまったく同じことが言えます。
可変長配列は普通は参照型なんじゃないの？
多くの言語では可変長配列は参照型として実装されています。しかし、SwiftのArrayは値型でした。最初にそれを知ったとき、気持ち悪い言語だなぁと思いました。
値型はその性質上、メモリ上でのサイズが固定されている必要があります[*1]。そのため、可変長配列のようにサイズが変化するものをそのまま値型で表現することはできません。あくまで実体となるバッファへの参照を値型でラップして、値であるかのように振る舞わせているだけです。
そのようなまどろっこしいことをしてまでArrayを値型にする理由は何なのでしょうか。実体は参照型なんだから可変長配列自体が参照型であった方が自然です。JavaもObjective-CもC#もPythonもRubyもJavaScriptも可変長配列は参照型です。Swiftと同じように可変長配列を純粋な値型として振る舞わせているのは、メジャー言語では僕の知る限りPHPくらいです[*2]。
むしろ、逆にすべてを参照型のように見せるのが最近の潮流ではないでしょうか。IntやDoubleみたいに値型でないとパフォーマンス上問題があるものは、プログラマにはイミュータブルなオブジェクトに見せておいて処理系では値型としてあつかうという手法をよく見かけます。RubyとかScalaとかCeylonとか。
では、なぜSwiftはあえてArrayを値型にしたのでしょう？
Arrayが値型だと何がうれしいのか
通常は参照型であるArrayを値型とするからには何かしらの理由があるはずです。僕がまず思いついたのは次の三つでした。
- パフォーマンス
- ミュータブルとイミュータブルを簡単に実現できる
- 初心者にとってわかりやすい
パフォーマンス
参照型はアドレスを元に値を参照しなければならないので、直接アクセスできる値型とくらべてデリファレンスの分だけ余計なオーバーヘッドが発生します。
通常その程度のオーバーヘッドは問題になりません。しかし、Arrayはその役割上、極めて多くの回数くり返しアクセスされることがあります。たとえば、1000万画素の写真に対して画像処理を施す際には、1ピクセルあたりRGBAの4チャネルがあり、それぞれに読み書きすることを考えると、画素値が格納されたArrayに最低でも8000万回（=1000万×4チャネル×2回）アクセスしなければなりません。そのようなケースではArrayへのアクセスがボトルネックになる可能性があり、デリファレンスによるわずかなオーバーヘッドがパフォーマンスに大きく影響を与えかねません。
Swiftは速さを売りの一つにしているので、パフォーマンスを重視するのは自然な設計です。
ミュータブルとイミュータブルを簡単に実現できる
Arrayを参照型、つまりクラスで実装する場合、一つのクラスでミュータブルとイミュータブルの両方を実現することはできません（もちろんフラグを使って切り替えるようなことはできますが、それはオブジェクト指向的に望ましい設計ではありません）。Arrayが値型であればvarとletによって簡単にミュータブルとイミュータブルの両方を実現できます[*3]。
クラスでミュータブルとイミュータブルを実現するにはどのような設計が必要になるでしょうか。Objective-CではNSArrayというイミュータブルな配列クラスと、NSMutableArrayというミュータブルな配列クラスがあります。Objective-CではNSMutableArrayがNSArrayを継承しており、まとめてNSArrayとしてあつかうことができます。しかしそれには問題があり、NSArray型変数の参照しているインスタンスがイミュータブルであることを保証できません。
// Objective-C
NSMutableArray *mutableArray = [[NSMutableArray alloc] init];
NSArray *array = mutableArray; // 継承しているのでis-aで代入可
[mutableArray addObject:@"ABC"]; // イミュータブルに見えるarrayにも@"ABC"が追加される
これはObjective-Cのクラス設計のミスで、本来はミュータブルな配列とイミュータブルな配列の間に継承関係があってはいけないのです。しかし、ミュータブルな配列とイミュータブルな配列の間に継承関係がなければ、ミュータブルでもイミュータブルでもいいから配列をまとめて扱いたいときに困ります。そのような操作を可能にするためには、ベースとなるArrayクラスと、Arrayを継承したMutableArray、ImmutableArrayの三つのクラスが必要ということになってしまいます[*4]。これはやや複雑です。
値型だと一つの型でミュータブルもイミュータブルも実現でき、とてもシンプルです。
初心者にとってわかりやすい
経験の浅いプログラマにとって参照は理解しづらい概念です。次のコードは、参照という概念を持たない初心者と、参照の概念を理解している熟練の考え方の違いを表したものです。
// Swift
var a = [1, 2, 3]
var b = a // 初心者はbにaの値をコピーしてるつもり、熟練者は参照をコピーしているつもり
a[0] = 999
println(b[0]) // 初心者は1が表示されるつもり、熟練者は999が表示されるつもり
Swiftは↑の初心者の考え通りに動きます。配列が参照型であることに慣れてしまうとb[0]も999になるのが自然に感じますが、それが自然に感じられるようになるにはある程度の経験を積まなければなりません。
Swiftは初心者にも優しい言語を目指しているようなので、Arrayが値型であるという設計も理解できます。
SwiftのArrayがすばらしい理由
これまでに挙げた理由だけだと、僕はArrayが参照型である方がシンプルでよかったんじゃないかと考えていました。デリファレンスのパフォーマンスへの影響は多くの場合無視できるほどだし、やや複雑だけどクラスを三つ用意すればミュータブルとイミュータブルは実現できます。また、Arrayが値型であっても、結局クラスがある以上参照という概念を避けて通ることはできません。どこかで参照型について学ぶ必要があるなら、Arrayは良い機会のように思います。
しかし、値型のArrayについてよく考えてみると、参照型のときに困っていた問題がきれいに解決できることがわかってきました。
例1: メソッドがArrayを返す場合
Userクラスと、ユーザーが所属するGroupクラスがあるとします。GroupクラスにはaddUserメソッドと、所属ユーザーのArrayを返すusersメソッドがあります。ただし、addUserメソッドでGroupの状態が更新されたときには、最新状態をファイル（なりデータベースなり）に保存したいという場合を考えてみましょう。
まずは可変長配列が参照型である言語（ここではSwiftユーザーに馴染み深いだろうObjective-C）で考えてみましょう。
// Objective-C
@implementation Group {
NSMutableArray *_users;
}
...
- (void)addUser:(User *)user {
[_users addObject:user]; // userを追加
[self writeToFile:_path]; // 自身の状態をファイルに保存
}
- (NSArray *)users {
return _users;
}
@end
上記のコードには問題があります。何がまずいのでしょう？次のような使い方をされると問題です。
// Objective-C
NSMutableArray *users = (NSMutableArray *)group.users;
[users addObject:aUser]; // Groupの外部でユーザーを追加
このように、オブジェクトの外でユーザーを追加されてしまうと、addUser:メソッドで行っていたファイルへの保存が実行されません。これを避けるためにはusersメソッドを次のように実装しなければなりません。
// Objective-C
- (NSArray *)users {
return [NSArray arrayWithArray:_users]; // Arrayをコピーしてreturn
}
しかし、本当にこれが良い実装でしょうか？usersメソッドを呼ぶコードは↓のようにユーザー一覧を出力したいだけかもしれません。
// Objective-C
for (User *user in group.users) {
printUser(user); // userを出力
}
このような場合、_usersをコピーするのは完全に無駄な処理です。とはいえ、usersメソッドを実装するときに戻り値がどのように利用されるかを知ることはできません。変更を加えられるかもしれない以上、無駄かもしれないけれどコピーは必須となります。
それでは、Arrayが値型であるSwiftの場合はどうなるでしょうか。
// Swift
class Group {
var _users: [User]
...
func addUser(user: User) {
_users.append(user) // userを追加
self.writeToFile(user) // 自身の状態をファイルに保存
}
var users: [User] {
get {
return _users
}
}
}
一見、最初のObjective-Cのダメな例と同じに見えます。しかし、SwiftのArrayは値型なので次のようなことをされてもグループの_usersが変更されることはありません。
// Swift
var users = group.users
users.append(aUser) // 値型なのでgroup.usersには追加されない
また、次のようにArrayに変更を加えない場合は最適化によってreturn時にバッファのコピーは実行されません。そのため、Arrayが参照型だと避けられなかった無駄なコピーが値型では避けられます。
// Swift
for user in group.users {
printUser(user) // userを出力
}
最適化って何をやってるの？
具体的に「最適化」とは何をするのでしょうか。ここで言う最適化はコンパイラの最適化の話ではなく、プログラミング上の最適化テクニックのことです。このテクニックはCopy-on-writeと呼ばれ、これによって参照をラップした値型を純粋な値であるかのように振る舞わせることができます。
次の単純なルールを導入することで、ArrayにCopy-on-writeを適用できます。
- Arrayを代入するときには、バッファはコピーせず共有する（バッファ自体ではなくバッファへの参照だけをコピーする）
- Arrayに変更を加えるときにバッファの参照カウントが2以上であれば、バッファをコピーしてから変更を加える
Arrayに変更を加えるときにバッファが共有されていると、一方を変更すると他方も変更されてしまいます。これは、値型の振る舞いとしてはおかしなことなので避けなければなりません。とはいえ、代入時にバッファをコピーするとそのコピーが無駄になってしまうかもしれません。Copy-on-writeを適用すれば、上記の二つのルールによって無駄なコピーを避けながらも、一方が変更された際に他方も変更されてしまうことを防ぐことができます。
具体例で見てみましょう。Copy-on-writeを適用すると、次のようなタイミングでバッファのコピーが発生します。
// Swift
let a = [1, 2, 3]
var b = a // バッファはコピーせずaとbでバッファを共有
b[0] = 888 // bのバッファはaと共有されているのでバッファをコピーしてから変更
b[0] = 999 // bのバッファは共有されてないのでコピーせずに変更
b.reserveCapacity(6) // 新しいバッファをサイズ6で確保して古いバッファからコピー
b.append(4) // bのバッファは共有されてないのでコピーせずに変更
let c = b // バッファはコピーせずbとcでバッファを共有
println(b[0]) // bのバッファはcと共有されているけど変更を加えないのでコピーしない
b.append(5) // bのバッファはcと共有されているのでバッファをコピーしてから変更
b.append(6) // bのバッファは共有されてないのでコピーせずに変更
b.append(7) // bのバッファは共有されてないけど空きがないので新しいバッファを確保して古いバッファからコピー
SwiftがGCではなく参照カウント方式を採用していることで、前述のCopy-on-writeのテクニックと相性が良いのもおもしろいところです。
例2: クラスにArrayを渡す場合
次に、Groupクラスのインスタンス初期化時にArrayで所属ユーザーを渡すことを考えます。
Arrayが参照型の言語では次のようになります。
// Objective-C
@implementation Group {
NSMutableArray *_users;
}
- (id)initWithUsers:(NSArray *)users {
self = [super init];
if (self) {
_users = [NSArray arrayWithArray:users]; // Arrayをコピーして保持
}
return self;
}
...
@end
ここでも、Arrayのコピーが必要なことに注意して下さい。コピーをせずusersを直接_usersに代入して保持していると、usersとしてミュータブルなArrayが渡された場合、オブジェクトの外部から_usersを直接変更されてしまう危険性があります。_usersを直接変更されると、例1のときのように変更をファイルに反映することができません。
しかし、このイニシャライザが次のようなコードで呼ばれた場合、コピーは無駄です。
// Objective-C
Group *group = [[Group alloc] initWithUsers:@[userA, userB, userC]];
Swiftの場合はどうなるでしょうか。
// Swift
class Group {
init(users: [User]) {
_users = users
}
...
}
group = Group(users: [userA, userB, userC])
group.addUser(userD)
この場合、次のように参照カウントが変化し無駄なバッファのコピーが発生しません。
- [userA, userB, userC]のリテラルでArrayが生成されメモリスタックに乗る（バッファの参照カウントは 1 ）
- イニシャライザの引数usersにバッファへの参照がコピーされる（バッファの参照カウントは 2 ）
- _usersにバッファへの参照がコピーされる（バッファの参照カウントは 3 ）
- イニシャライザのスコープを抜けてusersが消える（バッファの参照カウントは 2 ）
- イニシャライザをコールした行を抜けてメモリスタックからArrayが消える（バッファの参照カウントは 1 ）
- addUserするときにはバッファの参照カウントが 1 なのでバッファのコピーは不要
また、次のようにイニシャライザに渡したArrayに変更を加えようとしても、ArrayはコピーされるのでGourp内部のArrayを変更することはできません。
// Swift
initialUsers = [userA, userB, userC]
group = Group(users: initialUsers)
initialUsers.append(userD)
- [userA, userB, userC]のリテラルでArrayが生成されメモリスタックに乗る（バッファの参照カウントは 1 ）
- initialUsersにバッファへの参照がコピーされる（バッファの参照カウントは 2 ）
- 最初の行を抜けてメモリスタックからArrayが消える（バッファの参照カウントは 1 ）
- イニシャライザの引数usersにバッファへの参照がコピーされる（バッファの参照カウントは 2 ）
- _usersにバッファへの参照がコピーされる（バッファの参照カウントは 3 ）
- イニシャライザのスコープを抜けてusersが消える（バッファの参照カウントは 2 ）
- addUserするときにはバッファの参照カウントが 2 なのでバッファをコピーをしてから変更を加える
実例: JavaのEnum#values()
JavaのEnumクラス（のサブクラス）には、そのenumに属しているすべての値を返すvaluesメソッドがあります。valuesメソッドの戻り値に次のような操作をするとどうなるでしょう？
// Java
enum Type { A, B, C }
...
Type[] types = Type.values();
types[0] = null;
もしTypeが内部に保持している配列をそのまま返していたとすると、Typeの保持しているvaluesが書き換えられてしまいます。enumのメンバーが変更されるなんてことは許されません。Javaでは、valuesの戻り値に変更を加えられてもenum内部のvaluesが書き換えられてしまわないように、配列をコピーしてからreturnします。
// Java
Type[] types1 = Type.values();
Type[] types2 = Type.values(); // types1 != types2
しかし、valuesメソッドの戻り値に変更が加えられるなんてことは実際にはほぼありません。そのような極めてレアなケースであっても、可能性が0でないならenumのイミュータブル性を保つためにコピーしてreturnするしかないのです[*5]。
より一般的な話
例1、2のUserとGroupの話では利点がわかりやすいように、変更が加えられる度にファイルに保存するというケースを取り上げました。しかし、イニシャライザとgetterで可変長配列をコピーをした方が良いのはそのようなケースに限りません。
一般的に、カプセル化されたオブジェクトの内部状態をメソッドを介さずに変更できるのは望ましくありません。そのようなクラス設計は状態管理や依存関係を複雑化し、メンテナンスやデバッグの負荷を増大させます。それを避けるには、たとえ変更をファイルに反映する必要がなくても、例1、2のようにイニシャライザやgetterで可変長配列をコピーする必要があります。また、イミュータブルなクラスのイニシャライザに可変長配列を渡すときにも、オブジェクトがイミュータブルであることを保証するにはコピーが必須です。
このように、オブジェクトの内外で可変長配列をやりとりするときにはコピーをするのが望ましく、それを実際にはコピーのコストを支払わずに実現できるSwiftのArrayは素晴らしいと思います。
結論
Arrayが値型かつCopy-on-writeであれば、参照型では避けられなかった無駄なコピーを回避することができます。
参照を色々な箇所で共有すると依存関係が複雑になり、メンテナンスやデバッグが大変になります。一方で、参照型のオブジェクトを共有しないようにすると無駄になるかもしれないコピーが必要になります。値型とCopy-on-writeを組み合わせることで、共有をできるだけ避けながらもパフォーマンス上のデメリットも回避することができます。
以上のような理由から、SwiftのArrayの設計はすばらしいと思います。僕が思い付いていないデメリットがあれば指摘していただけるとうれしいです。
もう一つ
SwiftのArrayはミュータブルでもCovariantです。これも、Arrayが値型だから実現できることです。
まとめ
- 可変長配列は素直に実装すると参照型になり、多くの言語では実際に参照型である
- SwiftのArrayは値型である
- Arrayを値型にするには、値型に見せかけるための工夫が必要
- Arrayが値型だと参照型の可変長配列では避けづらい無駄なコピーを回避できて素晴らしい
- Arrayが値型だとミュータブルでもCovariantで素晴らしい
補足
(2014.8.2に追記) Copy-on-Writeにはパフォーマンス上の問題がありC++では使われなくなってきているという指摘を受けたので、Swiftにおいては影響は限定底だと思う理由をまとめました。
[*1] 値型とは、メモリ上に直接その値が格納されている型のことです。変数を確保すると、そのサイズにあわせたバイト数だけ領域が確保されます。値型を代入するときには、そのバイト列がそのままコピーされます。もし、同じ型なのにサイズが異なる値型が存在すると代入することすらできません。そのため、値型のサイズは固定されている必要があります。
[*2] PHPの場合、配列は可変長配列ではなく連想配列ですが。GoのSliceは値型ですがCopy-on-writeはありません。その他のパターンでは、HaskellやErlangなどの関数型言語ではリストがイミュータブルな連結リストになっています。先頭にノードを足していくことでイミュータブルだけど要素を追加できるというおもしろい設計です。
[*3] Beta 3より前のSwiftではsubscript(Int) setがnonmutatingだったため、letでもArrayをsubscript(Int) setをコールして要素を変更することができました。また、nonmutatingなのでバッファをコピーすることもできず、バッファが共有された状態のまま要素が書き換えられるので、値型にラップしてかくされたバッファへの参照を意識して利用する必要がありました。それが、SwiftのArrayがヤバかった理由です。Appleが当初そのような設計としていたのは、subscript(Int) setでバッファのコピーが必要かどうかの分岐（参照カウントの確認）をしたくなかったからだと思います。分岐は比較的重い処理であり、くり返しコールされるsubscript(Int) setにそのような分岐を作るのは、パフォーマンスの項で挙げたのと同じ理由で避けたかったのでしょう。
[*4] Scalaはそんな感じだったと思います。
[*5] このケースについては、valuesメソッドは配列ではなくイミュータブルなListを返すべきだったと思いますが。