読者です 読者をやめる 読者になる 読者になる

BLOG::はるかさん

はるかさん のブログです。近況情報や技術的な話題など。

GoのSliceは実際どうなっているのか

この記事はGo Advent Calendarのエントリではありません。

Go言語を勉強する人であれば、誰でもがsliceの扱いに躓くであろう。sliceの扱いがちょっとよくわからなかったので、まだよくわかってないけど、ひとまずメモ。

Goのアセンブラに関するドキュメント

sliceをアセンブリから扱うには

結論から書くと、今のところの理解では、sliceを関数に渡すとき、フレームにはslice構造体のアドレス、lencap、そして戻り値のアドレスが積まれている。つまり、次の様なコードを書けば、sliceのアドレスがSIlenがAX、capがBXに入り、要素の最初の値を返す関数になる。

// func FirstElem(x []uint64) uint64
TEXT ·FirstElem(SB),NOSPLIT,$0
MOVQ $x_base+0(FP), SI
MOVQ $x_len+8(FP), AX
MOVQ $x_cap+16(FP), BX
MOVQ 0(SI), SI
MOVQ 0(SI), CX
MOVQ CX, ret+24(FP)
RET

lencapが何故とれるのかよくわかってないけど、これでだいたいのことはできる。以下本題。

sliceはどうなっているのか

sliceの実装はsrc/runtime/slice.goにある。ということで、こんなブログを読まなくてもコードを読めば良い。

type slice struct {
    array unsafe.Pointer
    len   int
    cap   int
}

arrayには要素の配列のポインタ、lenには使用している長さ、capは確保済みの長さが入っている。このあたりはA Tour of Goをやっていれば理解できているだろうしブログにも書いてある。

図にすると次の様なかんじだ。

f:id:harukasan:20151204122947p:plain

ということで、先ほど示したアセンブリのように、引数をデリファレンスして、もう1回デリファレンスすれば要素の最初の値がとれた。これだけ理解しておけば、アセンブリからsliceを扱うことは比較的容易だ。

growするときにどうしているのか

ここまででだいたい実装はわかったけれど、良く理解できていなかったのでsliceの長さを拡張するときの実装を見てみる。実装はruntime.growsliceにある。エラー処理を省略してコメントを追加しておいた。

// growslice handles slice growth during append.
// It is passed the slice type, the old slice, and the desired new minimum capacity,
// and it returns a new slice with at least that capacity, with the old data
// copied into it.
func growslice(t *slicetype, old slice, cap int) slice {
    et := t.elem

    // 新しいcap(newcap)を計算する
    newcap := old.cap
    if newcap+newcap < cap {
        newcap = cap
    } else {
        for {
            if old.len < 1024 {
                newcap += newcap
            } else {
                newcap += newcap / 4
            }
            if newcap >= cap {
                break
            }
        }
    }

    lenmem := uintptr(old.len) * uintptr(et.size)
    capmem := roundupsize(uintptr(newcap) * uintptr(et.size))  
    newcap = int(capmem / uintptr(et.size))

    // メモリを確保して内容をコピーする
    var p unsafe.Pointer
    p = rawmem(capmem)
    memmove(p, old.array, lenmem)
    memclr(add(p, lenmem), capmem-lenmem)

    return slice{p, old.len, newcap}
}

まずはnewcapの計算から見てみよう。newcapは拡張後の新しいcapの値になる。newcapの計算処理は次の様なロジックだ。

  1. 現在のcapの2倍の値が求められているcapよりも小さければ、求められているcapnewcapにする
  2. lenが1024より短い場合は現在のcapを2倍にしていき、求められているcapよりも大きくなったらその値をnewcapにする
  3. lenが1024よりも長ければ1/4ずつ増やしていく

つまり、1024より短い時は今のcapの2倍以上、1024よりも長ければ1.25倍以上にするようになっている。これが良く聞くGoのsliceは2倍ずつ増えていく、の実装である。

拡張後のサイズが計算できたら後はその領域を確保し、値をコピーするだけである。

lenmemcapmemlencapのメモリ上で実際に必要な長さを求めている。これを求めるには単純に要素型のサイズをかければ良い。

領域の確保はruntime.rawmemが使われている。この関数の実装はつぎのようになっている。

// rawmem returns a chunk of pointerless memory.  It is
// not zeroed.
func rawmem(size uintptr) unsafe.Pointer {
    return mallocgc(size, nil, flagNoScan|flagNoZero)
}

mallocgcを呼ぶだけであるが、ひとまずはsize分mallocしてそのアドレスを返す、と理解しておけば今のところ問題ない。あとは確保したメモリに値をコピーし、すればおしまいである。memmovememclrの実装はアセンブリで書かれているが、ひとまず次の様に理解しておけば良いはずだ。

// frmからtoにlength分移動させる
func memmove(to *any, frm *any, length uintptr)

// ptrからlength分クリアする
func memclr(ptr *byte, length uintptr)

これでcapmemのサイズだけメモリをコピーし、lenmemの長さだけ値をコピーして、残りの領域をmemclrでクリアする、という流れがわかった。おしまい。

まとめ

最近のGoはGoで記述されているので非常に読みやすく、内部構造を理解しやすい。ということでGoで躓いたときはまずGoのコードを読めばよい。ところで、関数呼び出しの際にフレームにbase, len, capで積まれているように見えるんだけど、なぜこうなるのか未だに理解できていない。関数の引数がどういう風にフレームに積まれるのか、どこ読んだらわかるんだろ。

License

// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

本記事はgolang/goで公開されているGoのソースコードを含んでおり、LICENSEファイルは以下のURLで提供されている。