SwiftのArrayがヤバイ #Swift

(2015.11.18に追記) 「Swift List」で検索するとこの投稿にたどり着いてしまいますが、関数型言語でいうところのリストをお求めの方は "Swiftでhead、tailにパターンマッチできる遅延リスト" を御覧下さい。

(2014.7.24に追記) SwiftのArrayの新仕様（beta 3以降）がヤバイどころかすばらしいのでまとめました 。

(2014.7.10に追記) SwiftのArrayがヤバくなくなりました。 本投稿に書かれているのはbeta 2までの古いSwiftについての情報ですのでご注意下さい 。beta 3以降では次のような挙動となり、値型としてごく自然な挙動になりました。

var a = [11, 22, 33]

var b = a
a[0] = 777 // b[0]は777にならない

a.append(44)
a[0] = 888 // b[0]は888にならない

Arrayは相変わらず内部にバッファへの参照を持っているはずですが、mutatingなメソッドにおいて必要に応じてコピー処理を行うことで純粋な値型のように振る舞わせているものと考えられます。ただ、その結果subscript(Int) setの内部でバッファへの参照の一意性チェックが必要になったはずなので、subscript(Int) setのパフォーマンスはコピーが発生しない場合でも若干低下しただろうと予測されます。

（以下本文です）

The Swift Programming Languageを読んでいておどろいたのが、SwiftのArrayでは次のようなことが起こるということです。

var a = [11, 22, 33]

var b = a
a[0] = 777 // b[0]も777になる

a.append(44)
a[0] = 888 // b[0]は888にならない

なぜappendするとArrayの実体が共有されなくなるのか

一見すると奇妙な挙動ですが、SwiftのArrayが構造体（struct）であることから考えればその理由がわかります。おそらく、C言語で考えると次のような実装になっているのではないでしょうか¹²。

// Array b = a;をすると、Arrayはstructなので
// aのelementsに格納されたアドレスとcountの値がbコピーされる。
// elementsはポインタなのでaとbで同じメモリ領域が参照される。
typedef struct {
    int *elements;
    int count;
} Array;

// appendが呼ばれるとelementsを作りなおして要素をコピーする。
// そのため、b = aした後でaをappendすると
// aとbで異なるメモリ領域を参照することになる。
void append(Array *array, int element) {
    int *newElements = malloc(sizeof(int) * (array->count + 1));
    memcpy(newElements, array->elements,
        sizeof(int) * array->count);
    array->elements = newElements;
    array->elements[array->count] = element;
    array->count++;
}

// Arrayのinitializer相当
Array init() {
    Array array = {
        NULL, 0
    };

    return array;
}

// Arrayのsubscript(get)相当
int get(Array array, int index) {
    return array.elements[index];
}

// Arrayのsubscript(set)相当
void set(Array array, int index, int element) {
    array.elements[index] = element;
}

試しに↑のArrayについて次のコードを実行するとSwiftと同じ結果が得られます。

int main(int argc, char *argv[]) {
    Array a = init();
    append(&a, 11);
    append(&a, 22);
    append(&a, 33);

    Array b = a;
    set(a, 0, 777); // get(b, 0)も777になる

    append(&a, 44);
    set(a, 0, 888); // get(b, 0)は888にならない

    return 0;
}

SwiftのArrayをどのように使うか

SwiftがArrayをクラスではなく構造体として実装したのはパフォーマンスのためだと思われます。↑のような実装であれば、Cの配列と同等のパフォーマンスを実現できます。

しかし、そのような実装は直観に反し、プログラマが注意していないと思わぬバグを引き起こしかねません。また、可変長配列の実装がイメージできなかったり、値と参照の理解が浅い未熟なプログラマの場合、注意していても理解不足によるバグを生み出してしまうと思います。たとえば、次のコードはgroupからusersを取り出してUserオブジェクトを追加しているつもりですが、groupのusersにはUserオブジェクトを追加できていません。

var users : User[] = group.users
users.append(User(name: "Einstein"))
users.append(User(name: "Newton"))

for user in group.users {
    println(user.name) // EinsteinとNewtonは表示されない
}

Swiftのプログラムを安全に書くには、Arrayを直接さわるときはletで宣言して固定長配列として使うのが良いかと思います。可変長配列が必要なケースでは、varで宣言して直接Arrayをさわるのではなく、クラスでラップして参照型（Reference Type）として扱うのが良いのではないでしょうか。

Array相当のクラス

せっかくなので、Swiftの練習もかねてArrayをラップしたListクラスを実装してみました。と言っても、ラップされているArrayインスタンスにデリゲートしているだけですが・・・。

Listクラスは、次のようにほぼArrayと同じように扱えます。

var list = List(2, 3, 5, 7, 11, 13)

list.append(17)
list += 19

for element in list {
    println(element)
}

ちなみに、冒頭のArrayの変な挙動も、Listクラスを使えば起こりません。

var a = List(11, 22, 33)

var b = a
a[0] = 777

a.append(44)
a[0] = 888 // b[0]も888になる

SwiftのArrayはどうなっていれば良かったか

最後に、SwiftのArrayがどうなっていれば良かったのか考えてみます。

Swiftで書かれるだろう一般的なプログラム（iOSアプリやMacアプリ）を考えると、ほとんどの箇所では配列がCと同等のパフォーマンスである必要はありません。たとえば、Table Viewのセルが高速な配列に格納されていたからといって、GUIの描画処理を考えるとそこが大きな影響を与えることはないからです。配列のパフォーマンスが重要になるのは、画像処理のように配列の要素に繰り返しアクセスが必要で、かつその処理がボトルネックになるような場合だけです。

そうであれば、若干パフォーマンスには劣るものの標準の配列は参照型（クラス）として提供し、一部のパフォーマンスが重要な処理のために値型（構造体）の配列型を提供すればよかったのではないでしょうか。個人的には、パフォーマンス重視の箇所で可変長配列が必要になることはめずらしいように思うので、構造体の方は固定長で十分ではないかと思います。たとえば、ArrayクラスとBuffer構造体とかだと良かったと思います。

まとめ

SwiftのArrayはクラスではなく構造体なので、直観に反する挙動をすることがある
Arrayが構造体なのはパフォーマンスのためと思われる
Arrayの実装をイメージできないとArrayに挙動を理解するのは難しい
直観通りの挙動を期待するならArrayはletで固定長としてのみ使うのが良さそう
可変長であってほしいときはクラスにラップして参照型として使うと良いのでは
Arrayをラップしたクラスを実装してみた
Arrayはクラスで、パフォーマンス重視用の構造体を別途提供という設計の方が良かったのでは

補足（2014.6.23に追加）

ここで書いたような実装だとappendがO(N)になり遅すぎるのではないかというコメントをいただいたのですが、注釈に書いたように実際のArrayにはcapcityがあり、Swiftで定数（let）のArrayの要素は変更できるけどDictionaryでは変更できない理由に書いたようなcapcityを指数関数的に増やす実装になっていると思われます。その場合、appendの平均的な計算量はO(1)になります。

ただし、Swiftで定数（let）のArrayの要素は変更できるけどDictionaryでは変更できない理由に書いたArrayの実装だと、appendで配列の実体が変わる現象はcapacityが拡張されるときにのみ発生することになります。そのため、capacityが拡張されるかに関わらずappendでCopy-on-writeが起こり、かつ平均的にO(1)を実現するために、配列の実体（本文のCのコードで言うelements）への参照カウントが2以上の場合についてのみ実体の再構築と要素のコピーが実行されるよう実装されているのではないかと想像しています。

また、本エントリーがSwiftやAppleをdisる材料みたいになってしまいましたが、僕個人としてはSwiftの登場を好意的に受け止めていますし期待もしています。SwiftのArrayがヤバい→だからSwiftは（Appleは）ダメだ、という図式になるのは本意ではありません。Appleはクローズドではありますがその仕事自体は素晴らしいと思いますし、SwiftもArrayやDictionaryの挙動が微妙とはいえトータルでは良い言語だと思います。これから先、Swiftのようなモダンな言語を趣味だけでなく仕事で書けるのはとても楽しみです。

この実装はArrayの概念を表したものです。このままではmallocされたメモリ領域がfreeされずメモリリークします。本物のArrayではelementsの参照カウントが別途管理されているのでしょうが、C上でARCは再現できないですしretain/releaseを書いても話の本筋が見えづらくなるだけなので、ここではメモリ管理の話は省略しています。同様に、capacityの話もコードを複雑にするだけなので省略しています。 ↩
appendだけArray *を引数のとるのは、appendがmutatingなメソッドであることに対応します。 ↩