Golangにおける配列とスライスの違い
自己紹介
はじめまして。
homie株式会社でエンジニアとして働いている根橋と申します。
弊社ではHOTLEADという不動産営業における支援ツールを開発しています。
このHOTLEADというプロダクトでは、反響と呼ばれる問い合わせメールからお客様と会うまでのアポイントメント数を最大化するための一次対応を行っています。
私は普段、サーバーサイドエンジニアとして機能設計から運用までを行い、コールセンター業務の改善に従事しています。
今回はHOTLEADの開発言語のひとつであるGolangに関して、配列とスライスの違いをまとめてみました。
P.S. 最近のマイブームはスイカをたべることです。夏を感じますね。
配列
配列とは
配列は指定した型の要素をメモリ上に連続して保持するデータ構造です。
固定長のため初期化時は要素数を指定する必要があり、指定した要素数以上のデータを保持する事はできません。
func main() {
var arr [4]int
fmt.Println(arr) // => [0 0 0 0]
arr[0] = 1
fmt.Println(arr) // => [1 0 0 0]
arr[5] = 5 // => invalid argument: index 5 out of bounds [0:4]
}上記がコード例です。同じ型の要素をまとめて保持できるのは便利ですが、固定長であるため柔軟性に欠ける一面もあります。
スライス
スライスとは
指定した型の要素を複数保持できるデータ構造です。
配列と比較すると、保持できる要素数に上限がないため柔軟に要素を追加することができます。
func main() {
s := make([]int, 0, 4)
fmt.Println(s) // => []
fmt.Println(len(s)) // => 0
for i := 0; i < 4; i++ {
s = append(s, i)
}
fmt.Println(s) // => [0 1 2 3]
fmt.Println(len(s)) // => 4
}上記がコード例です。前述した通り、配列と違い要素数の上限がないため柔軟に要素を追加することが可能です。
スライスの実態
golangにおいて、スライスは上述した配列の先頭のアドレスを保持している構造体として定義されています。
https://github.com/golang/go/blob/1f8f2ab9661c78876d8a8cb0ccc4625728842b26/src/runtime/slice.go#L15-L19
type slice struct {
array unsafe.Pointer
len int
cap int
}
$${ ptr }$$ が配列の先頭を指し示しています。
そして$${ len }$$ は現在の要素数、$${ cap }$$ は最大要素数です。
そのため必ず $${ len <= cap }$$ が成り立ちます。
$${ cap }$$ 以上の要素を保持できないのであれば、配列と変わらないのではないか？？と最初は思いましたが、上限に達したタイミングで最大要素数が増えるようになっているみたいです。
実験
初期化時に長さが0のスライスに要素を追加していき、最大要素数がどのように増加するか調べます。
func main() {
s := make([]int, 0)
printSliceInfo(s) // => slice: [], len: 0, cap: 0
s = append(s, 1)
printSliceInfo(s) // => slice: [1], len: 1, cap: 1
s = append(s, 2)
printSliceInfo(s) // => slice: [1 2], len: 2, cap: 2
s = append(s, 3)
printSliceInfo(s) // => slice: [1 2 3], len: 3, cap: 4
s = append(s, 4)
printSliceInfo(s) // => slice: [1 2 3 4], len: 4, cap: 4
s = append(s, 5)
printSliceInfo(s) // => slice: [1 2 3 4 5], len: 5, cap: 8
}
func printSliceInfo(s []int) {
fmt.Printf("slice: %v, len: %d, cap: %d\n", s, len(s), cap(s))
}要素を上限いっぱいまで保持している状態から、新しく要素を追加しようとすると最大要素数が2倍に増えていることが分かりました。
https://github.com/golang/go/blob/master/src/runtime/slice.go#L157-L284
func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice {
oldLen := newLen - num
if raceenabled {
callerpc := getcallerpc()
racereadrangepc(oldPtr, uintptr(oldLen*int(et.Size_)), callerpc, abi.FuncPCABIInternal(growslice))
}
if msanenabled {
msanread(oldPtr, uintptr(oldLen*int(et.Size_)))
}
if asanenabled {
asanread(oldPtr, uintptr(oldLen*int(et.Size_)))
}
if newLen < 0 {
panic(errorString("growslice: len out of range"))
}
if et.Size_ == 0 {
// append should not create a slice with nil pointer but non-zero len.
// We assume that append doesn't need to preserve oldPtr in this case.
return slice{unsafe.Pointer(&zerobase), newLen, newLen}
}
newcap := oldCap
doublecap := newcap + newcap
if newLen > doublecap {
newcap = newLen
} else {
const threshold = 256
if oldCap < threshold {
newcap = doublecap
} else {
// Check 0 < newcap to detect overflow
// and prevent an infinite loop.
for 0 < newcap && newcap < newLen {
// Transition from growing 2x for small slices
// to growing 1.25x for large slices. This formula
// gives a smooth-ish transition between the two.
newcap += (newcap + 3*threshold) / 4
}
// Set newcap to the requested cap when
// the newcap calculation overflowed.
if newcap <= 0 {
newcap = newLen
}
}
}
var overflow bool
var lenmem, newlenmem, capmem uintptr
// Specialize for common values of et.Size.
// For 1 we don't need any division/multiplication.
// For goarch.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
// For powers of 2, use a variable shift.
switch {
case et.Size_ == 1:
lenmem = uintptr(oldLen)
newlenmem = uintptr(newLen)
capmem = roundupsize(uintptr(newcap))
overflow = uintptr(newcap) > maxAlloc
newcap = int(capmem)
case et.Size_ == goarch.PtrSize:
lenmem = uintptr(oldLen) * goarch.PtrSize
newlenmem = uintptr(newLen) * goarch.PtrSize
capmem = roundupsize(uintptr(newcap) * goarch.PtrSize)
overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
newcap = int(capmem / goarch.PtrSize)
case isPowerOfTwo(et.Size_):
var shift uintptr
if goarch.PtrSize == 8 {
// Mask shift for better code generation.
shift = uintptr(sys.TrailingZeros64(uint64(et.Size_))) & 63
} else {
shift = uintptr(sys.TrailingZeros32(uint32(et.Size_))) & 31
}
lenmem = uintptr(oldLen) << shift
newlenmem = uintptr(newLen) << shift
capmem = roundupsize(uintptr(newcap) << shift)
overflow = uintptr(newcap) > (maxAlloc >> shift)
newcap = int(capmem >> shift)
capmem = uintptr(newcap) << shift
default:
lenmem = uintptr(oldLen) * et.Size_
newlenmem = uintptr(newLen) * et.Size_
capmem, overflow = math.MulUintptr(et.Size_, uintptr(newcap))
capmem = roundupsize(capmem)
newcap = int(capmem / et.Size_)
capmem = uintptr(newcap) * et.Size_
}
// The check of overflow in addition to capmem > maxAlloc is needed
// to prevent an overflow which can be used to trigger a segfault
// on 32bit architectures with this example program:
//
// type T [1<<27 + 1]int64
//
// var d T
// var s []T
//
// func main() {
// s = append(s, d, d, d, d)
// print(len(s), "\n")
// }
if overflow || capmem > maxAlloc {
panic(errorString("growslice: len out of range"))
}
var p unsafe.Pointer
if et.PtrBytes == 0 {
p = mallocgc(capmem, nil, false)
// The append() that calls growslice is going to overwrite from oldLen to newLen.
// Only clear the part that will not be overwritten.
// The reflect_growslice() that calls growslice will manually clear
// the region not cleared here.
memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
} else {
// Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.
p = mallocgc(capmem, et, true)
if lenmem > 0 && writeBarrier.enabled {
// Only shade the pointers in oldPtr since we know the destination slice p
// only contains nil pointers because it has been cleared during alloc.
bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(oldPtr), lenmem-et.Size_+et.PtrBytes)
}
}
memmove(p, oldPtr, lenmem)
return slice{p, newLen, newcap}
}またコードレベルでも確認してみました。元々の上限が256未満の場合はやはり2倍に増加するように書かれています。
また $${ memmove }$$ 関数を使って、新しく確保したメモリ領域に元々の配列の内容を書き込み、配列を作り直しているみたいです。
役に立つかもしれないtips
配列とスライスの構造については理解できたので、配列・スライスを扱っていく上で役に立ちそうなtipsを書き連ねてみました。
配列において要素数も型の一部
下記のように同じint型でも要素数が異なる配列は別の型とみなされるため注意が必要かもしれません。
func main() {
arr := [5]int{}
arr = [10]int{} // => cannot use [10]int{} (value of type [10]int) as [5]int value in assignment
}スライスはnilでも操作可能
下記のようにスライスを初期化せず宣言しているだけの場合、$${ append }$$や $${ len }$$などの組み込み関数を使ってもPanicにならないようです。
func main() {
var s []int
fmt.Println(s == nil) // => true
s = append(s, 1)
fmt.Println(s) // => [1]
}なので$${ append }$$する前のnilチェックは不要みたいです。
スライスをコピーするときはコピー先の長さを指定しておく
以下のようにコピー先のスライスの長さを予め指定していない場合、コピーはうまくいきません。
func main() {
src := []int{1, 2, 3, 4, 5}
var dst []int
copy(dst, src)
fmt.Println(dst) // => [] 空っぽ
}これは $${ copy }$$ 関数が、コピー元・コピー先のうち、要素数の小さいスライスの長さ分しかコピーを実行しないためです。
https://github.com/golang/go/blob/1f8f2ab9661c78876d8a8cb0ccc4625728842b26/src/builtin/builtin.go#L151-L155
// The copy built-in function copies elements from a source slice into a
// destination slice. (As a special case, it also will copy bytes from a
// string to a slice of bytes.) The source and destination may overlap. Copy
// returns the number of elements copied, which will be the minimum of
// len(src) and len(dst).なので解決策としては、コピー先を指定する際に長さを指定してあげれば良いと思います。
func main() {
src := []int{1, 2, 3, 4, 5}
dst := make([]int, len(src)) // srcの全要素コピーしたいので長さも合わせる
copy(dst, src)
fmt.Println(dst)
}参考書籍
最後に
homieでは新しい仲間を募集しています。
「エンジニア組織が気になる！」という方は是非カジュアルにお話できれば嬉しいです。
