GoのSliceは実際どうなっているのか
この記事はGo Advent Calendarのエントリではありません。
Go言語を勉強する人であれば、誰でもがsliceの扱いに躓くであろう。sliceの扱いがちょっとよくわからなかったので、まだよくわかってないけど、ひとまずメモ。
Goのアセンブラに関するドキュメント
sliceをアセンブリから扱うには
結論から書くと、今のところの理解では、sliceを関数に渡すとき、フレームにはslice構造体のアドレス、len
、cap
、そして戻り値のアドレスが積まれている。つまり、次の様なコードを書けば、sliceのアドレスがSI
、len
が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
len
とcap
が何故とれるのかよくわかってないけど、これでだいたいのことはできる。以下本題。
sliceはどうなっているのか
sliceの実装はsrc/runtime/slice.goにある。ということで、こんなブログを読まなくてもコードを読めば良い。
type slice struct { array unsafe.Pointer len int cap int }
array
には要素の配列のポインタ、len
には使用している長さ、cap
は確保済みの長さが入っている。このあたりはA Tour of Goをやっていれば理解できているだろうしブログにも書いてある。
図にすると次の様なかんじだ。
ということで、先ほど示したアセンブリのように、引数をデリファレンスして、もう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
の計算処理は次の様なロジックだ。
- 現在の
cap
の2倍の値が求められているcap
よりも小さければ、求められているcap
をnewcap
にする len
が1024より短い場合は現在のcap
を2倍にしていき、求められているcap
よりも大きくなったらその値をnewcap
にするlen
が1024よりも長ければ1/4ずつ増やしていく
つまり、1024より短い時は今のcap
の2倍以上、1024よりも長ければ1.25倍以上にするようになっている。これが良く聞くGoのsliceは2倍ずつ増えていく、の実装である。
拡張後のサイズが計算できたら後はその領域を確保し、値をコピーするだけである。
lenmem
とcapmem
はlen
とcap
のメモリ上で実際に必要な長さを求めている。これを求めるには単純に要素型のサイズをかければ良い。
領域の確保は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してそのアドレスを返す、と理解しておけば今のところ問題ない。あとは確保したメモリに値をコピーし、すればおしまいである。memmove
、memclr
の実装はアセンブリで書かれているが、ひとまず次の様に理解しておけば良いはずだ。
// 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で提供されている。