Go のスライスの内部実装 - Block Rockin’ Codes

History

14/05/09: Merge2 を修正しました。http://twitter.com/jbking/status/464659353945911297

Intro

Go のスライスは、いわゆる LL 系の言語が持つ可変長配列の実装と似ています。よって LL のような手軽な扱いをすることもできますが、その内部実装を知ることでより効率の良いメモリハンドリングができ、パフォーマンスを改善や、メモリーリークの防止などに繋がる可能性があります。

この辺は SWrap というライブラリを作りながら勉強したので、今回は、この Go のスライスの内部実装を解説します。

Go の配列

スライスを知るためには、まず配列について知っておく必要があります。

Go の配列は固定長のため、以下のように長さを指定して宣言します。

var arr [4]int

func main() {
    arr = [4]int{1, 2, 3, 4}
    log.Println(arr)
}

配列は長さを含めて型です。つまり、以下の関数は [4]int のみを引数として許し、 [5]int は型が合わずコンパイルでエラーになります。

func fn(arr [4]int) {
    log.Println(arr)
}

func main() {
    arr4 := [4]int{1, 2, 3, 4}
    arr5 := [5]int{1, 2, 3, 4, 5}
    fn(arr4) // ok
    fn(arr5) // cannot use arr5 (type [5]int) as type [4]int in function argument
}

関数に渡した場合は、値渡しになります。つまり渡した先では配列がまるっとコピーされます。参照渡しにしたい場合は、ポインタを渡します。

func fnV(arr [4]int) {
    for i, _ := range arr {
        arr[i] = 0
    }
    log.Println(arr) // [0, 0, 0, 0]
}

func fnP(arr *[4]int) {
    for i, _ := range arr {
        arr[i] = 0
    }
    log.Println(arr) // [0, 0, 0, 0]
}

func main() {
    arr := [4]int{1, 2, 3, 4}
    fnV(arr)
    log.Println(arr) // [1, 2, 3, 4]
    fnP(&arr)
    log.Println(arr) // [0, 0, 0, 0]
}

また、配列の長さは変更できないため、長さを増やしたいなどの場合は、長い配列を宣言し自分で移し替える必要があります。(後述する append() や copy() は、配列には使用できません)

Slice

スライスは、可変長配列のようなものです。その実体は、固定長配列への View として実装されています。

まず、使いかたを見てみます。

配列の宣言から長さの情報を消すと、スライスとして宣言されます。長さの情報が無いため、関数に渡す際に実際いくつの要素が入っていても、要素の型が同じなら渡すことができます。

関数に渡す場合は、ただスライスを渡せば、渡した先で中身を書き換えることができます。 fnP() のようにスライス自体のポインタを渡すことも可能です。

func fnV(arr []int) {
    for i, _ := range arr {
        arr[i] = 10
    }
    log.Println(arr) // [10, 10, 10, 10]
}

func fnP(a *[]int) {
    arr := *a // 一旦中身をとりだす
    for i, _ := range arr {
        arr[i] = 20
    }
    log.Println(arr) // [20, 20, 20, 20]
}

func main() {
    arr := []int{1, 2, 3, 4}
    fnV(arr)
    log.Println(arr) // [10, 10, 10, 10]
    arr = []int{1, 2, 3, 4}
    fnP(&arr)
    log.Println(arr) // [20, 20, 20, 20]
}

内部実装

内部では、スライスは固定長配列への View として実装されています。具体的な構造は、以下のようなイメージです。

宣言

まず、以下のようにスライスの宣言と初期化同時に実行してみます。この時、内部的には固定長配列である [4]int のメモリが確保され、値が入り初期化されます。スライスはその固定長配列への参照(コメント内の * )を持ちます。 len() を使って、値の数も見てみましょう。

// []int    *
//          |
// [4]int  [1, 2, 3, 4]
arr := []int{1, 2, 3, 4}
log.Println(arr, len(arr)) // [1 2 3 4] 4

make()

次にスライスのもう一つの宣言方法、 make() を使って書きなおしてみます。 make() は第一引数に型を、第二引数に長さ(len)を指定します。以下の場合は、配列 [4]int のメモリを確保し、型に応じたゼロ値で初期化します。 (int の場合は 0 です)

変数 arr は、その配列への参照が格納されます。

// []int    *
//          |
// [4]int  [0, 0, 0, 0]
arr := make([]int, 4)
log.Println(arr, len(arr)) // [0 0 0 0] 4

したがって、値は index 0~3 までは代入可能です。 index 4 は、 index out of range になります。

// []int    *
//          |
// [4]int  [1, 2, 3, 4]
arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 4
arr[4] = 5 // index out of range

append

len よりも外側の領域まで値を追加していくためには append() を使います。 apeend() は、スライスの末尾に値を追加し、その結果を返します。以下は先ほど初期化したサイズの外、 arr[4], arr[5] まで値を格納しています。

arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 4
arr = append(arr, 5)
arr = append(arr, 6)
log.Println(arr, len(arr)) // [1, 2, 3, 4, 5, 6] 6

では、この時内部の固定長配列はどうなっているのでしょうか？それを知るためには、 cap() について知る必要があります。

cap

cap() で内部配列のサイズを知ることができます。まず、以下の例で見てみましょう。

先ほどの make([]int, 4) で生成したスライスの cap() は 4 です。これは、内部配列の長さが 4 だからです。

よってこのスライスに対し 4 つまでは、値を格納できますが、 append() によって配列のサイズ以上に値を追加する場合は、内部の配列を拡張する必要があります。

Go は append() で内部の配列を拡張する時、必ず現在の配列の 倍の長さ の配列を確保し、そこにコピーするという実装になっています。実際に確認してみると、最後のスライスは、 len() が 5 で、 cap() は 8 を返しています。

// []int    *
//          |
// [4]int  [0, 0, 0, 0]
arr := make([]int, 4)
log.Println(arr, len(arr), cap(arr)) // [0 0 0 0] 4 4

arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 4
log.Println(arr, len(arr), cap(arr)) // [1 2 3 4] 4 4
arr = append(arr, 5) // 内部で [8]int が確保され、そこに 5 つの値がコピーされる
log.Println(arr, len(arr), cap(arr)) // [1 2 3 4 5] 5 8
// []int    *
//          |
// [8]int  [1, 2, 3, 4, 5, , , ,]

最後の状態は、内部的には [8]int があり、そのうちの index 0~4 までが使われている状態です。 len() は値の入っている数、 cap() は内部配列のサイズ、 append() は末尾への追加と、足らない場合の配列の拡張を行っています。

make() で cap の指定

スライスに最初から沢山の値を入れることがわかっている場合、 append() で何度も配列を拡張するより、最初から大きな配列を内部に確保すれば、メモリ確保の回数を減らすことができます。

この、最初に確保する配列のサイズは、 make() の第三引数で指定できます。

例えば、 cap = 0 でスライスを確保し 5 個の値を append() していくと、合計で 5 回の配列確保(allocate) が行われます。

func Append1() {
    arr := make([]int, 0, 0) // 0, 0 (alloc)
    arr = append(arr, 0)    // 1, 1 (alloc)
    arr = append(arr, 1)    // 2, 2 (alloc)
    arr = append(arr, 2)    // 3, 4
    arr = append(arr, 3)    // 4, 4 (alloc)
    arr = append(arr, 4)    // 5, 8 (alloc)
}

cap を最初から 5 にしておけば alloc は最初だけで済みます。

func Append2() {
    arr := make([]int, 0, 5) // 0, 5 (alloc)
    arr = append(arr, 0)    // 1, 5
    arr = append(arr, 1)    // 2, 5
    arr = append(arr, 2)    // 3, 5
    arr = append(arr, 3)    // 4, 5
    arr = append(arr, 4)    // 5, 5
}

make() の第一引数 len を 0 にしているのは、値を初期化しないためです。初期化してしまうと、その範囲は添字アクセス、それ移行は append() と使い分ける必要もあるため、こうした指定をしています。

// []int    *
//          |
// [10]int  [ , , , , , , , , , ]
arr := make([]int, 0, 10)
log.Println(arr, len(arr), cap(arr)) // [] 0 10

ちなみに以下のような宣言では、暗黙的に len=0, cap=0 になります。

var arr []int // 0, 0

このように、スライスの下にある実配列を意識することで、効率の良いメモリ確保が可能になる場合があります。具体的には、一度確保(Allocate)したメモリを使い回し、確保の回数を減らすことで処理を高速化するといった場合です。

メモリの使い回し

上記を踏まえて次の「スライスの連結」を考えてみましょう。

以下のような実装の、メモリ確保面での効率を考えてみます。

func Merge1(a, b []int) []int {
    for i := range b {
        a = append(a, b[i])
    }
    return b
}

筋は悪そうですが、もし a の cap に b の len 分の余裕が必ずあるなら、配列の再確保は行われないため、これでも問題ないでしょう。しかし、 b の len が大きく、 a の cap が小さい場合は、再確保が何度も起こる可能性があります。

毎回、必ず一回確保することを選ぶのであれば、こうなります。 copy() は、第二引数のスライスの内容を、第一引数のスライスに移します。最初から、必要な長さを確保しているので、 alloc は一回で済みます。

func Merge2(a, b []int) []int {
    c := make([]int, len(a)+len(b))
    copy(c, a)
    copy(c[len(a):], b)
    return c
}

といいつつ実は append() はこんな書き方ができます。

func Merge3(a, b []int) []int {
    return append(a, b...)
}

配列確保も 1 回で最適化されるので、基本的にこの方法を使うのが良いでしょう。

GC

スライスから見える値が消えていても、内部配列に残っていることで GC されず値が残る場合があります。例えば、スライスから指��したインデックスの値を削除し、その分前に詰めて返す del() 関数を考えてみます。既にある内部配列内の移動だけで済ませれば、再確保はいらないので、以下のようにしてみます。

func del(a []int, i int) []int {
    copy(a[i:], a[i+1:])
    a = a[:len(a)-1]
    return a
}

func main() {
    a := []int{1, 2, 3, 4, 5}
    a = del(a, 2)
    log.Println(a, len(a), cap(a)) // [1 2 4 5] 4 5
}

メモリの Allocate も無く、スライス側から見ると値は消えています。

しかし、内部配列はどうでしょうか。 del() の後は、以下のようになっています。 (実際に a[:cap(a)] で確認できます。)

// []int    *
//          |
// [5]int  [1, 2, 4, 5, 5]
log.Println(a[:cap(a)])

このように、スライスからは見えない値が、内部の配列に残っている場合があります。例えば大きなサイズの構造体の参照を持つスライスなどの場合は、内部配列に参照が残っていることにより、 GC されない可能性もあります。

万全を期すためには、 del() を以下のようにし、末尾の値に、型に応じたゼロ値(宣言して初期化しないことで生成可能)を代入しておく方法があります。 int の場合は 0 ですが、参照型のスライスの場合は、ここが nil になります。

var zero int // ゼロ値
func del(a []int, i int) []int {
    copy(a[i:], a[i+1:])
    a[len(a)-1] = zero // ゼロ値, nil の代入
    a = a[:len(a)-1]
    return a
}

削除する範囲が大きい場合は、一旦別のスライスに対比することで GC を促す方法もあるでしょう。この辺の話は、 Slice Tricks や Arrays, slices (and strings): The mechanics of 'append' - The Go Blog、 Go Slices: usage and internals - The Go Blog などで紹介されています。

まとめ

Go のスライスの内部実装について、色々と細かい解説をしましたが、そういったことを抽象化して全て len=0, cap=0 で宣言したスライスを append() だけで拡張していくこともできるのが Go の手軽な部分です。カジュアルな用途では、それで十分でしょう。

しかし、スライスを多用したり、そこにサイズの大きい構造体を格納したり、詰替えや拡張をよく行うようになると、こうしたことを知っておくだけで効率が数倍変わることもあります。

処理の速度やメモリ確保については testing パッケージを用いたベンチマークを記述し、 go test コマンドにある、 -benchmem オプションを用いてベンチマークを実行すると、以下の様な感じで実行時間とともに alloc 回数を知ることができます。

PASS
BenchmarkAppend1   5000000         741 ns/op       120 B/op        4 allocs/op
BenchmarkAppend2  50000000        48.8 ns/op         0 B/op        0 allocs/op
ok    jxck  6.825s

あらかじめ、おおよそのサイズを見積もり、テストやベンチで測定と検証を繰り返しながらチューニングすることで、より効率の良いプログラムの作成に繋がると思います。

何か間違いなどありましたら、遠慮なく指摘頂けると幸いです。