GoのスライスとRustのスライス

こんにちは、Wantedly のDX Squadでエンジニアをしている原です。 (DXはDeveloper Experienceの略で、開発者が心地よくプロダクトを作れる環境を作ることを目標に頑張る部門です)

本稿は、WANTEDLY TECH BOOK 9 から「GoのスライスとRustのスライス」という章を抜粋し加筆修正を加えたものです。ウォンテッドリーでは WANTEDLY TECH BOOK のうち最新版を除いた電子版を無料で配布しています。ぜひ読んでみてください。

過去の WANTEDLY TECH BOOK を入手する

以下、本文です。

GoのスライスとRustのスライスは大枠では似ていますが、スライスの共有に関する振舞いが微妙に異なり、GoとRustの設計の違いが垣間見られます。本記事ではこの違いを説明します。

配列型とスライス型

Go/Rustにおいて「配列」は固定長でスタック確保されるものを指します。Goの配列は [N]T, Rustの配列は [T; N] と表記され、この2つの扱いは両言語でほぼ同じです。

一方、スライス型には大きな違いが見られます。Goの「スライス」は []T と表記され、可変長なデータの並びを扱うときは常にこの型を用います。これらに対応するRustにおける「スライス」として、標準ライブラリには &[T], &mut [T], Box<[T]>, Vec<T> の4つの型があり(脚注1)、用途によって使い分けられます。

スライスの内部表現

Goのスライス []T のメモリ表現は以下の通りです(脚注2):

 0-7 | 8-15 | 16-23
-----|------|-------
 ptr | len  |  cap

ptrは先頭へのポインタ、lenはスライスの現在の長さ、capはこのスライスを最大どれくらい伸ばせるかです。

Rustのスライス &[T], &mut [T], Box<[T]> のメモリ表現は以下の通りです:

 0-7 | 8-15
-----|------
 ptr | len

Rustのベクター Vec<T> のメモリ表現は以下の通りです:

 0-7 | 8-15 | 16-23
-----|------|-------
 ptr | cap  |  len

Goのスライスとは順番が異なります。これは内部実装上、前半2つでRawVec、つまり「未初期化値を含んだスライス」が構成できるほうが都合がいいからです。

共有モデルの違い

Goのスライスは、言語仕様上はスライス同士は対等なものとして扱われます。

Rustのスライスのうち &[T]/&mut [T] は常に従属的で、他の配列系の値にぶら下がる形でしか存在できません。通常は Vec<T> がひとつ存在し、それにぶら下がる形で &[T] が存在します。

ビューとしてのスライス

Rustの &[T] と &mut [T] はビュー (view) としての機能をもつスライス、つまり何らかの親データ (スライスや配列) の全体または一部分を指す参照です。ほとんどの場合、関数の引数として登場します。

fn find_even(slice: &[i32]) -> Option<i32> { /* ... */ }
fn sort(slice: &mut [i32]) { /* ... */ }

func findEven(slice []int) (int, bool) { /* ... */ }
func sort(slice []int) { /* ... */ }

別の配列やスライスの一部分を渡すことができます。

let mut array = [3, 2, 5, 6, 7, 1]; // [i32; 6]
sort(&mut array[1..5]);
let mut vector = vec![3, 2, 5, 6, 7, 1]; // Vec<i32>
sort(&mut vector[1..5]);

array := [...]int{3, 2, 5, 6, 7, 1}; // [6]int
sort(array[1:5])
slice := []int{3, 2, 5, 6, 7, 1}; // []int
sort(slice[1:5])

Rustはさらに &[T] と &mut [T] を区別しています。これはRustが「shared XOR mutable」というルールを言語全体で強制していて、「共有できるが読み取り専用」と「書き込めるが共有できない」という2つの排他的なモードをコンパイル時に区別する必要があるからです。「shared XOR mutable」はスレッド安全性やenumの型安全性などのRustの基本的な性質を支えている重要なルールであり、またRustプログラムの最適化にも大きく貢献しています。

append可能スライス

Rustの Vec<T> はGoにおける make 直後のスライスに相当します。 make 直後のスライスはその変数以外から参照されていないことがわかっているので、安全にappendできます。

let mut vector = Vec::with_capacity(10);
for i in 0..10 {
    vector.push(i * 2);
}
// vector = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

slice := make([]int, 0, 10);
for i := 0; i < 10; i++ {
    slice = append(slice, i * 2);
}
// slice = [0 2 4 6 8 10 12 14 16 18]

appendの罠

なお、Goをはじめて触る人のうち、特に関数型プログラミングを背景にもつ人は、この append
を見て連結リストのconsのような印象を受ける人もいるかもしれません。実際のところこの append
は、副作用と戻り値に両方気をつける必要があるという、手続き型と宣言型の悪いところを取ったようなインターフェースになってしまっています。(脚注3)

その証拠に、以下のような悪いプログラムを考えます。

slice1 := make([]int, 0, 5)
slice2 := slice1
for i := 0; i < 10; i++ {
    slice1 = append(slice1, i)
    slice2 = append(slice2, i + 100)
}
fmt.Println("slice1 =", slice1) // => [100 101 102 103 104 5 6 7 8 9]
fmt.Println("slice2 =", slice2) // => [100 101 102 103 104 105 106 107 108 109]

append を宣言的な関数として理解していると、 slice1 と slice2 は独立に成長すると考えられます。しかし実際のところはそうではありません。appendは len < cap かどうかで挙動を変えるため、上の例では5番目の要素からは slice1 と slice2 の参照が分岐し、干渉が回避されています。

これを逆手に取ったパターンとして、in-place filterの実装が挙げられます。

slice := []int{2, 2, 5, 3, 6, 9, 2}
filtered := slice[:0]
for _, elem := range slice {
    if elem % 2 == 0 {
        filtered = append(filtered, elem)
    }
}
fmt.Println("filtered =", filtered) // => [2 2 6 2]
// 元のスライスが変更されている!
fmt.Println("original =", slice) // => [2 2 6 2 6 9 2]

筆者はこれをはじめて見たとき、なんて明快な処理なんだろうと考えていました。とんでもない! これは元のスライスの一部分を書き換えながら、まだ残っているスライスのデータを読んで処理を続行するという、とても綱渡りな処理を、さも平然と書いているにすぎないわけです。

ここもGoとRustの性格の違いがよく出てくる場面といえます。Rustでは上のように書くことは許されず、同じことをしたければ専用のメソッドを使うことになります。

let mut vector = vec![2, 2, 5, 3, 6, 9, 2];
vector.retain(|elem| elem % 2 == 0);

Box<[T]>

Rustにはもう1つ Box<[T]> というスライスがあります。これは Vec<T> とよく似ていますが、メモリレイアウトは &[T] と似ています。つまり、 cap フィールドを持たないため、スライスを伸長・収縮することができません。

Box<[T]> は Vec<T> と比べて利点が少なく、使われる機会はあまり多くありませんが、以下の理由から存在しているといえます。

• 言語の一貫性。つまり「&T があるなら Box<T> もある」というルールにより Box<[T]> も自然に存在するので、それをわざわざ禁止していない。
• Vec<T> が3ワード専有するのに対して Box<[T]> は2ワードしか専有しないため、 Box<[T]> 自体を大量に保持しなければいけないようなごく稀なケースで Box<[T]> のほうが優れている可能性がある。

文字列スライス

文字列スライスは8bit整数のスライスを「文字列」として解釈するために型を再定義したもので、以下のようにバイトスライスと1対1の対応関係があります。

      | バイトスライス | 文字列スライス
------|------------|-------------
  Go  | []byte     | string
 Rust | &[u8]      | &str
 Rust | Vec<u8>    | String

スライス自体の扱いの違いを除けば、GoとRustの文字列スライスの扱いの違いは1点だけです。RustはUTF-8として正しくない文字列を拒否するようにAPIが設計されていますが、Goではその検証はユーザーに任されており、UTF-8として正しくない string 型も作ろうと思えば作れます。

nilの扱い

Goにはnilという特別なスライスがあります。

var slice []int // nilで初期化される
slice = append(slice, 1)

JSON出力時の挙動が違うなど若干の罠があるものの、Goのnilスライスは長さ0、容量0のスライスとほぼ同等に扱われます。これはRustも同様で、 Vec<T> には容量0という特別な状態があります。容量0の場合はptrはヒープ上の値ではなく、ダミーのアドレスを指しています。

ただし、Vec<T> や &[T] などの型はnullポインタ最適化といって、 Option<Vec<T>>
や Option<&[T]> の形で使ったときの None 値をnullポインタとして扱うルールがあります。この None 値との衝突を回避するため、ダミーのアドレスとしては0ではなく正の値(脚注4)が使われます。

親スライスが先にいなくなったらどうするか

GoとRustのスライスは、コピーをせずに部分スライスを切り出すことができるという特徴がありました。では、このとき親スライスが先に消滅したらどうなるでしょうか。

Goの場合は、GCで部分スライスがマーク対象になった場合には親スライス全体が保護されるようです(脚注5)。つまり、不用意に部分スライスを寿命の長いデータに入れてしまうと、必要以上にメモリを消費してしまう可能性があります。

Rustの場合は、部分スライス &[T], &mut [T] にはライフタイムが紐付いているため、親スライスより長く生きることはできないようになっています。

func returnSubslice() []int {
    parent := []int{3, 1, 4, 1, 5, 9, 2}
    // parent自体の参照は消えるが、その部分スライスは参照されたままになる
    return parent[1:6]
}

// 借用検査を通らない (親スライスより部分スライスが長生きすることはできない)
fn return_subslice() -> &[i32] {
    let parent = vec![3, 1, 4, 1, 5, 9, 2];
    &parent[1..6]
}

ライフタイムによらないスライスの共有

ではもし、Goのように自由に使える部分スライスがRustでどうしても必要な場合はどうすればよいでしょうか。これを実現しているライブラリとして bytes クレートがあります(脚注6)。

fn return_subslice() -> Bytes {
    let mem = Bytes::from("Hello world");
    // 親スライスとデータを共有した部分スライスを作り、返却する
    mem.slice(3..8)
}

bytesクレートを理解するには、まず参照カウントされたスライスである Arc<[T]> を導入する必要があります。 Arc<[T]> 自体のメモリレイアウトはこれまで紹介したスライスと同じです。

 0-7 | 8-15
-----|------
 ptr | len

しかし、 ptr の参照先のレイアウトは異なります。通常のスライスと異なり、先頭に参照カウンタが存在しています。 (図は要素型が1バイトの場合)

   0-7  | 8-15 | 16 | 17 | 18 | 19 | ...
--------|------|----|----|----|----|-----
 strong | weak |  0 |  1 |  2 |  3 | ...

Arc<[T]> は参照カウンタを持つため、参照カウンタを増減させることで、データ本体をコピーせずにスライスのコピーを作ることができます。しかし、参照カウンタの位置を把握する必要があるため、部分スライスを取ることはできません(脚注7)。

この解決方法は単純です。 Arc<[T]> にstart, endという2つのフィールドを足したものをスライスと言い張れば、部分スライスを取ることができるようになります。

pub struct SharedSlice<T> {
    parent: Arc<[T]>,
    start: usize,
    end: usize,
}

これをより最適化した上で、 T = u8 に限って実装したものが、先ほど紹介したbytesクレートです。

ゼロコピー構文解析

部分スライスの切り出しが安価であるという性質を使った例として「ゼロコピー構文解析」が存在します。JSONやmsgpackの元データの一部を、そのまま構文解析の結果として使うというものです。

Rustのシリアライゼーションライブラリであるserdeはこのゼロコピー構文解析をサポートしています。たとえば以下はゼロコピー構文解析をJSONに対して適用した例です。

use serde_derive::*;
use std::borrow::Cow;

#[derive(Debug, Clone, Serialize, Deserialize)]
struct Package<'a> {
    #[serde(borrow)]
    name: Cow<'a, str>,
    #[serde(borrow)]
    description: Cow<'a, str>,
}

fn main() {
    let json = r#"{"name":"foo", "description": "Awesome\nlibrary"}"#;
    let package: Package = serde_json::from_str(json).unwrap();
    eprintln!("package.name = {:?}", package.name);
    if let Cow::Borrowed(_) = package.name {
        eprintln!("package.name is borrowed");
    } else {
        eprintln!("package.name is owned");
    }
    eprintln!("package.description = {:?}", package.description);
    if let Cow::Borrowed(_) = package.description {
        eprintln!("package.description is borrowed");
    } else {
        eprintln!("package.description is owned");
    }

    // package.name = "foo"
    // package.name is borrowed
    // package.description = "Awesome\nlibrary"
    // package.description is owned
}

上の例にあるように、JSONの場合は "foo" のようにエスケープを含まない文字列の場合はその部分をそのまま構文解析結果として使えますが、 "Awesome\nlibrary" のようにエスケープがある場合には、構文解析の結果としてそのままは使えません。そのため、 &str と String を選択的に保持するための Cow という型を使っています。(検証のためにborrowedかどうかを調べていますが、実際には透過的に扱うことができます)

すでに述べたように、Rustの狭義のスライス (&[T], &mut [T], &str) はライフタイムで管理されており、親データより長生きすることはできません。そのため、これらを含むデータも同様にライフタイムで管理することになります (そうしないとコンパイルが通りません)。これは不便でもありますが、部分スライスを参照している間は誰かが明示的に親データを管理していることが保証されているという利点もあります。つまり、GoのスライスやRustの Bytes のように、余分なデータがGCされずに残ってしまう危険性が軽減されます。

まとめ

• Goのスライスは1種類の型だが、Rustでは使い方に応じて &[T], &mut [T], Vec<T> などと区別される。
• &[T], &mut [T] は、親スライスに対する部分スライスという使い方を型で区別したものといえる。
• Vec<T> はGoでいう「appendしてよいスライス」である。
• Goでは親スライスが先に消滅した場合でも、親スライス分の領域が確保されたままになる。Rustではライフタイムによりそのような状況自体が発生しない。Rustで同じようなことをしたければ参照カウントを使ってライブラリ定義で頑張る必要がある。
• スライスの一部分が低コストで切り出せるという性質はしばしば構文解析などで役立てられる。

脚注:

1. ここではGoの慣習にあわせて Vec<T> をスライスの一種として扱いますが、Rustではスライスとはあまり呼ばず、ベクターと呼びます。
2. Go Slices: usage and internals - The Go Blog
3. このような設計になってしまったのはおそらく以下の理由からでしょう。まず、GoにはRustのライフタイムのようなものはないので、変数の参照を取って関数に渡した場合は、変数をヒープ上に確保せざるを得ない場合があります。そのため、 slice.append(elem) や append(&slice, elem) のような設計はパフォーマンス上よくありません。かといって、 append(slice, elem) で slice 変数自体が書き換えられるとするのは、何が左辺値式になるかという我々の直感に反する結果になってしまいます。ですから、プログラマが陽に slice = と代入する形式にせざるを得なかったのでしょう。
4. アラインメントの要請があるため、1ではなくその型のアラインメントに等しいアドレスが使われます。たとえば Vec<i32> であればダミーポインタは4です。
5. 部分スライスから親スライスをどう発見しているかは謎です。Goのランタイムの実装を追う余裕はなかったので憶測ですが、メモリアドレスの二分探索など、アドレスの大小関係を利用した方法で発見しているのではないかと思います。同じような状況はスライス以外にも構造体フィールドなどで発生しうるはずです。
6. bytes 0.5.0からはカスタムアロケーターのサポートが入って Bytes 構造体の構造が複雑になりました。本節の内容を理解するには0.4系以前のものを読むほうがいいでしょう。
7. 実は、先頭ポインタの移動だけでなく、より短いスライスを作る操作も行うことができません。長さを知らないと、各要素のデストラクタを適切に呼ぶことができないからです。また、RustのアロケーターはCのアロケーターと異なり free 相当の処理に先頭ポインタだけではなく確保したときの長さを渡す規約になっているため、そのためにも元の長さを覚えておく必要があります。