知りませんでした。
これは、Go6 Advent Calendar 2019 25日目の記事です。
はじめに
Goにはsliceという内部で配列の参照を持つ可変長のリストが存在します。
このsliceに要素を追加する場合、よくappendという関数が用いられます。
a = append(a, b...)
上記のコードを用いると、aのsliceにbの要素が追加されます。
この際、もしaのsliceのcap（容量）が追加されるbの要素を加えても足りるのであれば、bはaのsliceが参照を持っている配列に追加されます。
逆にcapが足りない場合は、新たに配列を割り当ててそちらに追加するようになっています。
（詳しくは、Go7 Advent Calendar 2019 9日目の @ueokande さんによる 図解 Go Slice Tricks がわかりやすいため、そちらを参照してください）
では、この新たに配列を割り当てる仕組みは一体どうなっているのでしょうか？
package main
import "fmt"
func main() {
var a []int32
a = append(a, 0, 1)
fmt.Printf("len=%d cap=%d\n", len(a), cap(a))
a = append(a, 0, 1)
fmt.Printf("len=%d cap=%d\n", len(a), cap(a))
a = append(a, 0, 1)
fmt.Printf("len=%d cap=%d\n", len(a), cap(a))
}
---結果---
len=2 cap=2
len=4 cap=4
len=6 cap=8
一見すると、もとの配列におけるcapの2倍のcapで作成しているように見受けられます。
次に下記のコードを見てみましょう。
package main
import "fmt"
func main() {
// int32の場合...
var a []int32
a = append(a, 0)
fmt.Printf("len=%d cap=%d\n", len(a), cap(a))
a = append(a, 0, 1, 2, 3)
fmt.Printf("len=%d cap=%d\n", len(a), cap(a))
// byteの場合...
var b []byte
b = append(b, 0)
fmt.Printf("len=%d cap=%d\n", len(b), cap(b))
}
---結果---
// 1つ追加しただけなのに、なぜcap=2になる？
len=1 cap=2
// cap=5あれば十分なはずなのに、cap=8まで拡張されている
len=5 cap=8
// byteに至っては、1つ追加しただけでcap=8になっている？？
len=1 cap=8
もとのcapの2倍分のcapを確保しているものかと思いきや、そうではない挙動をしています。
一体Goは、どういった基準でcapを確保しているのでしょうか？
この記事ではそこにフォーカスを当てていきたいと思います。
appendの実装を追う
appendの実装を知るには、appendの内部コードを見るのが一番です。
ただ、appendは組み込み関数で実装がコンパイラ部分にあるため、少し追いづらくなっています。
Golang/goには、それらの処理がコンパイラによってどう置き換えられるか、その実装の擬似コードがコメントとして記述されているため、そちらを見てみましょう。
// expand append(l1, l2...) to
// init {
// s := l1
// n := len(s) + len(l2)
// // Compare as uint so growslice can panic on overflow.
// if uint(n) > uint(cap(s)) {
// s = growslice(s, n)
// }
// s = s[:n]
// memmove(&s[len(l1)], &l2[0], len(l2)*sizeof(T))
// }
// s
//
// l2 is allowed to be a string.
func appendslice(n *Node, init *Nodes) *Node {
...
github: https://github.com/golang/go/blob/go1.13.5/src/cmd/compile/internal/gc/walk.go#L2571-L2584
このように、appendの際にcapが足りず配列を新規確保する場合はgrowsliceが用いられていることがわかります。
次からは、このgrowsliceの実装にフォーカスを当ててみます。
growsliceの実装を追う
このgrowsliceの実装は、Goで記述されているため追いやすいです。
コードは下記の場所に記述されています。
github: https://github.com/golang/go/blob/go1.13.5/src/runtime/slice.go#L76
このうち、新たに確保するcapの定義する部分を追っていきます。
ただ、コード量が多いため、前後半に分割して見ていくことにします。
growsliceの前半部分
まずは前半部分です。
// ここでの変数「cap」は、新たに割り当てられる配列のlenと同等（詳しくは上の擬似コードを参照）
newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
newcap = cap
} else {
if old.len < 1024 {
newcap = doublecap
} else {
// Check 0 < newcap to detect overflow
// and prevent an infinite loop.
for 0 < newcap && newcap < cap {
newcap += newcap / 4
}
// Set newcap to the requested cap when
// the newcap calculation overflowed.
if newcap <= 0 {
newcap = cap
}
}
}
github: https://github.com/golang/go/blob/go1.13.5/src/runtime/slice.go#L95-L114
（ここでの変数「cap」は、新たに割り当てられる配列のlenと同等になります）
この処理を箇条書きで書き出すと、
- 新たに割り当てられる配列のlenと、もとの配列におけるcapの2倍を比較する
- 新規配列のlenの方が大きいなら、そちらの値を新規capとして定義する
- それ以外なら、下記の条件に分岐する
- もとの配列におけるlenが1024未満なら、もとのcapの2倍を新規capとして定義する
- 1024以上なら、もとのcapに自身の1/4の値を追加する処理を、新規配列のlenの値を超えるまで繰り返す
- 例外があれば、新規配列のlenを新規capとして定義する
となっています。
（言語化してみましたが、コードの方を見ていただく方がわかりやすいかもしれません...）
実際、試してみると確かに上記のような処理になっていることがわかります。
package main
import "fmt"
func main() {
// byteの場合...
a := make([]byte, 1024)
a = append(a, 0)
fmt.Printf("len=%d cap=%d\n", len(a), cap(a))
// int32の場合...
b := make([]int32, 1024)
b = append(b, 0)
fmt.Printf("len=%d cap=%d\n", len(b), cap(b))
}
---結果---
// 1024以上なので、
// 1024の1/4である256が足され、1024+256=1280で正しい
len=1025 cap=1280
// ①ここも本来cap=1280にならないとおかしい？
len=1025 cap=1344
ただ、やはりコメントの①の箇所などcapが想定と異なっている部分もあります。
この、今回の記事を書く要因にもなったcap確保の不明瞭な部分を読み解く鍵が、growsliceの後半に隠されています。
実際に見ていきましょう。
growsliceの後半部分
それでは後半部分です。
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 sys.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(old.len)
newlenmem = uintptr(cap)
capmem = roundupsize(uintptr(newcap))
overflow = uintptr(newcap) > maxAlloc
newcap = int(capmem)
case et.size == sys.PtrSize:
lenmem = uintptr(old.len) * sys.PtrSize
newlenmem = uintptr(cap) * sys.PtrSize
capmem = roundupsize(uintptr(newcap) * sys.PtrSize)
overflow = uintptr(newcap) > maxAlloc/sys.PtrSize
newcap = int(capmem / sys.PtrSize)
case isPowerOfTwo(et.size):
var shift uintptr
if sys.PtrSize == 8 {
// Mask shift for better code generation.
shift = uintptr(sys.Ctz64(uint64(et.size))) & 63
} else {
shift = uintptr(sys.Ctz32(uint32(et.size))) & 31
}
lenmem = uintptr(old.len) << shift
newlenmem = uintptr(cap) << shift
capmem = roundupsize(uintptr(newcap) << shift)
overflow = uintptr(newcap) > (maxAlloc >> shift)
newcap = int(capmem >> shift)
default:
lenmem = uintptr(old.len) * et.size
newlenmem = uintptr(cap) * et.size
capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
capmem = roundupsize(capmem)
newcap = int(capmem / et.size)
}
github: https://github.com/golang/go/blob/go1.13.5/src/runtime/slice.go#L116-L154
いくつかの条件で分けられています。
例えば、et.size == 1の場合を見てみましょう。
case et.size == 1:
lenmem = uintptr(old.len)
newlenmem = uintptr(cap)
capmem = roundupsize(uintptr(newcap))
overflow = uintptr(newcap) > maxAlloc
newcap = int(capmem)
このet.sizeは、バイト数と同等なため、例えば配列の型がbyteの場合は、この条件にヒットすることになります。
このうち、最終的に確保されるcapはnewcapであるため、このnewcapに至るまでの処理を追えばいいことがわかります。
上記のコードを見ると、newcapに対してroundupsizeが実行されています。
つまり、このroundupsizeで行っている処理こそ、本命のcap確保の仕組みになります。
補足
他の条件でも、基本的な処理は同じです。
例えば、et.size == sys.PtrSizeの場合だと、
case et.size == sys.PtrSize:
lenmem = uintptr(old.len) * sys.PtrSize
newlenmem = uintptr(cap) * sys.PtrSize
capmem = roundupsize(uintptr(newcap) * sys.PtrSize)
overflow = uintptr(newcap) > maxAlloc/sys.PtrSize
newcap = int(capmem / sys.PtrSize)
となり、sys.PtrSizeを乗算している部分で違っているように見えますが、実際はet.size==1の場合も型のバイト数が1のため乗算する必要がなかっただけで、roundupsizeに対して配列の合計バイト数を渡そうとしていること自体は同じになります。
roundupsizeを追う
このroundupsizeの処理は、下記のようになっています。
func roundupsize(size uintptr) uintptr {
if size < _MaxSmallSize {
if size <= smallSizeMax-8 {
return uintptr(class_to_size[size_to_class8[(size+smallSizeDiv-1)/smallSizeDiv]])
} else {
return uintptr(class_to_size[size_to_class128[(size-smallSizeMax+largeSizeDiv-1)/largeSizeDiv]])
}
}
if size+_PageSize < size {
return size
}
return round(size, _PageSize)
}
github: https://github.com/golang/go/blob/go1.13.5/src/runtime/msize.go#L13
上記のコードを見ると、引数で渡されたsizeに対して、何らかの変換を行っていることがわかります。
変換の内容自体は、コードを見ればわかるかと思います。
ただ、_MaxSmallSizeなどの変数の値がわからないため、このままではどういった結果になるかわかりません。
ここで使われる変数は、下記の場所に存在しました。
// Code generated by mksizeclasses.go; DO NOT EDIT.
//go:generate go run mksizeclasses.go
package runtime
// class bytes/obj bytes/span objects tail waste max waste
// 1 8 8192 1024 0 87.50%
// 2 16 8192 512 0 43.75%
// 3 32 8192 256 0 46.88%
// 4 48 8192 170 32 31.52%
// 5 64 8192 128 0 23.44%
// 6 80 8192 102 32 19.07%
// 7 96 8192 85 32 15.95%
// 8 112 8192 73 16 13.56%
// 9 128 8192 64 0 11.72%
// 10 144 8192 56 128 11.82%
// 11 160 8192 51 32 9.73%
// 12 176 8192 46 96 9.59%
// 13 192 8192 42 128 9.25%
// 14 208 8192 39 80 8.12%
// 15 224 8192 36 128 8.15%
// 16 240 8192 34 32 6.62%
// 17 256 8192 32 0 5.86%
// 18 288 8192 28 128 12.16%
// 19 320 8192 25 192 11.80%
// 20 352 8192 23 96 9.88%
// 21 384 8192 21 128 9.51%
// 22 416 8192 19 288 10.71%
// 23 448 8192 18 128 8.37%
// 24 480 8192 17 32 6.82%
// 25 512 8192 16 0 6.05%
// 26 576 8192 14 128 12.33%
// 27 640 8192 12 512 15.48%
// 28 704 8192 11 448 13.93%
// 29 768 8192 10 512 13.94%
// 30 896 8192 9 128 15.52%
// 31 1024 8192 8 0 12.40%
// 32 1152 8192 7 128 12.41%
// 33 1280 8192 6 512 15.55%
// 34 1408 16384 11 896 14.00%
// 35 1536 8192 5 512 14.00%
// 36 1792 16384 9 256 15.57%
// 37 2048 8192 4 0 12.45%
// 38 2304 16384 7 256 12.46%
// 39 2688 8192 3 128 15.59%
// 40 3072 24576 8 0 12.47%
// 41 3200 16384 5 384 6.22%
// 42 3456 24576 7 384 8.83%
// 43 4096 8192 2 0 15.60%
// 44 4864 24576 5 256 16.65%
// 45 5376 16384 3 256 10.92%
// 46 6144 24576 4 0 12.48%
// 47 6528 32768 5 128 6.23%
// 48 6784 40960 6 256 4.36%
// 49 6912 49152 7 768 3.37%
// 50 8192 8192 1 0 15.61%
// 51 9472 57344 6 512 14.28%
// 52 9728 49152 5 512 3.64%
// 53 10240 40960 4 0 4.99%
// 54 10880 32768 3 128 6.24%
// 55 12288 24576 2 0 11.45%
// 56 13568 40960 3 256 9.99%
// 57 14336 57344 4 0 5.35%
// 58 16384 16384 1 0 12.49%
// 59 18432 73728 4 0 11.11%
// 60 19072 57344 3 128 3.57%
// 61 20480 40960 2 0 6.87%
// 62 21760 65536 3 256 6.25%
// 63 24576 24576 1 0 11.45%
// 64 27264 81920 3 128 10.00%
// 65 28672 57344 2 0 4.91%
// 66 32768 32768 1 0 12.50%
const (
_MaxSmallSize = 32768
smallSizeDiv = 8
smallSizeMax = 1024
largeSizeDiv = 128
_NumSizeClasses = 67
_PageShift = 13
)
var class_to_size = [_NumSizeClasses]uint16{0, 8, 16, 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224, 240, 256, 288, 320, 352, 384, 416, 448, 480, 512, 576, 640, 704, 768, 896, 1024, 1152, 1280, 1408, 1536, 1792, 2048, 2304, 2688, 3072, 3200, 3456, 4096, 4864, 5376, 6144, 6528, 6784, 6912, 8192, 9472, 9728, 10240, 10880, 12288, 13568, 14336, 16384, 18432, 19072, 20480, 21760, 24576, 27264, 28672, 32768}
var class_to_allocnpages = [_NumSizeClasses]uint8{0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 3, 2, 3, 1, 3, 2, 3, 4, 5, 6, 1, 7, 6, 5, 4, 3, 5, 7, 2, 9, 7, 5, 8, 3, 10, 7, 4}
type divMagic struct {
shift uint8
shift2 uint8
mul uint16
baseMask uint16
}
var class_to_divmagic = [_NumSizeClasses]divMagic{{0, 0, 0, 0}, {3, 0, 1, 65528}, {4, 0, 1, 65520}, {5, 0, 1, 65504}, {4, 11, 683, 0}, {6, 0, 1, 65472}, {4, 10, 205, 0}, {5, 9, 171, 0}, {4, 11, 293, 0}, {7, 0, 1, 65408}, {4, 13, 911, 0}, {5, 10, 205, 0}, {4, 12, 373, 0}, {6, 9, 171, 0}, {4, 13, 631, 0}, {5, 11, 293, 0}, {4, 13, 547, 0}, {8, 0, 1, 65280}, {5, 9, 57, 0}, {6, 9, 103, 0}, {5, 12, 373, 0}, {7, 7, 43, 0}, {5, 10, 79, 0}, {6, 10, 147, 0}, {5, 11, 137, 0}, {9, 0, 1, 65024}, {6, 9, 57, 0}, {7, 9, 103, 0}, {6, 11, 187, 0}, {8, 7, 43, 0}, {7, 8, 37, 0}, {10, 0, 1, 64512}, {7, 9, 57, 0}, {8, 6, 13, 0}, {7, 11, 187, 0}, {9, 5, 11, 0}, {8, 8, 37, 0}, {11, 0, 1, 63488}, {8, 9, 57, 0}, {7, 10, 49, 0}, {10, 5, 11, 0}, {7, 10, 41, 0}, {7, 9, 19, 0}, {12, 0, 1, 61440}, {8, 9, 27, 0}, {8, 10, 49, 0}, {11, 5, 11, 0}, {7, 13, 161, 0}, {7, 13, 155, 0}, {8, 9, 19, 0}, {13, 0, 1, 57344}, {8, 12, 111, 0}, {9, 9, 27, 0}, {11, 6, 13, 0}, {7, 14, 193, 0}, {12, 3, 3, 0}, {8, 13, 155, 0}, {11, 8, 37, 0}, {14, 0, 1, 49152}, {11, 8, 29, 0}, {7, 13, 55, 0}, {12, 5, 7, 0}, {8, 14, 193, 0}, {13, 3, 3, 0}, {7, 14, 77, 0}, {12, 7, 19, 0}, {15, 0, 1, 32768}}
var size_to_class8 = [smallSizeMax/smallSizeDiv + 1]uint8{0, 1, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23, 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, 29, 29, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31}
var size_to_class128 = [(_MaxSmallSize-smallSizeMax)/largeSizeDiv + 1]uint8{31, 32, 33, 34, 35, 36, 36, 37, 37, 38, 38, 39, 39, 39, 40, 40, 40, 41, 42, 42, 43, 43, 43, 43, 43, 44, 44, 44, 44, 44, 44, 45, 45, 45, 45, 46, 46, 46, 46, 46, 46, 47, 47, 47, 48, 48, 49, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 52, 52, 53, 53, 53, 53, 54, 54, 54, 54, 54, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 57, 57, 57, 57, 57, 57, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 60, 60, 60, 60, 60, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 62, 62, 62, 62, 62, 62, 62, 62, 62, 62, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66}
github: https://github.com/golang/go/blob/go1.13.5/src/runtime/sizeclasses.go
少し長めのコードが出てきました。
ここに、先ほど使われていた変数が全て存在するため、これでどういった結果になるかわかるようになります。
これで、処理と結果自体はわかりました。
ただ、一体この処理は何を目的としているのでしょうか？
これには、Goでベースとなっているmallocが関係します。
Goでのmallocについて
Goでは、TCMallocと呼ばれるmallocがベースとなっています。
このTCMallocの詳細についてはGoogleのブログをご覧ください。
ここでは、そのうち今回で特に重要なメモリ管理について注目します。
上記の図を見てください。
TCMallocでは、各オブジェクトをサイズによってクラスに分類します。
このクラスごとに空きオブジェクトを管理する連結リストが作られており、各オブジェクトはそこへ格納されることになります。
この性質を考慮した上で、 渡されたサイズ（引数のsize）を割り当てられるクラスに合わせて最適化しよう！ を実践したのがroundupsizeです。
これらを踏まえた上で、改めて最初のコードを見てみましょう。
package main
import "fmt"
func main() {
// int32の場合...
var a []int32
a = append(a, 0)
fmt.Printf("len=%d cap=%d\n", len(a), cap(a))
a = append(a, 0, 1, 2, 3)
fmt.Printf("len=%d cap=%d\n", len(a), cap(a))
// byteの場合...
var b []byte
b = append(b, 0)
fmt.Printf("len=%d cap=%d\n", len(b), cap(b))
}
---結果---
// newcap=(roundsize(1 * 4)/4)=4 となる
len=1 cap=2
// newcap=(roundsize(5 * 4)/4)=8 となる
len=5 cap=8
// newcap=roundsize(1)=8 となる
len=1 cap=8
capがどういった基準で確保されているかわかりましたね。
まとめ
今年もそろそろ終わりですね。
平和最後で令和元年な年に、「appendで新たに割り当てられる配列はもとのcapの2倍になるよう実装されているのだろう」といった漠然な認識を改めることができたことを、大変嬉しく思います。
それでは皆さん、良いお年を。