スライス容量拡張量がどのように決まるのか追った / 180709 LT

Transcript

1. ※(7/13追記)ブラッシュアップした内容で2018/7/13 のgolang.tokyoでLTしてきたので、そちらのスライド の方をご覧ください！ https://speakerdeck.com/kaznishi/180713-lt
2. スライス容量拡張量が どのように決まるのか追った 2018-07-09 Gopher道場 #2 LT大会 by kaznishi
3. 自己紹介 twitter: @kaznishi1246 サーバーサイド,インフラ PHP, Scala Go歴はほぼ1ヶ月(≒Gopher道場期間)
4. 今回のテーマ
5. スライスの容量がいっぱいの ときにappendで追加される容 量の話
6. 復習 スライスは配列の部分列への参照のためのデータ 構造 配列は固定長 容量が足りなくなった場合、容量が拡張された新 たな配列が作られ、参照先が切り替わる
7. 容量の拡張量は？
8. 容量の拡張量は？ 「プログラミング言語Go」より 「Goならわかるシステムプログラミング」より 拡張ごとに配列の大きさを倍にすることにより過 剰な回数の割り当てを避け、一つの要素の追加が 平均的に定数時間で済むことを保証しています。 “ “ もし、余裕がない状態でappend()を呼ぶと、cap() の2倍のメモリを確保し、今までの要素をコピー したうえで新しい要素を新しいメモリ領域に追加 します。 “ “
9. 確かめてみよう
10. Go Playgroundで確認 cap = 4 のとき https://play.golang.org/p/zPLWMUM2gzw OK
11. Go Playgroundで確認 cap = 5 のとき https://play.golang.org/p/eyPOVocDUc- 「12」！！！？？？
12. はて
13. goの実装を追ってみた
14. https://github.com/golang/go/blob/master/src/runti me/slice.go func growslice(et *_type, old slice, cap int) slice { ~略~ 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 } ~略~
15. ~略~ 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)
16. case isPowerOfTwo(et.size): var shift uintptr if sys.PtrSize == 8 { // Mask shift for better code generation. shift = uintptr(sys.Ctz64(uint64(et.size))) & } else { shift = uintptr(sys.Ctz32(uint32(et.size))) & } 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 = roundupsize(uintptr(newcap) * et.size) overflow = uintptr(newcap) > maxSliceCap(et.size) newcap = int(capmem / et.size) }
17. newcapに調整がかかってる
18. switch { case et.size == sys.PtrSize: ~略~ capmem = roundupsize(uintptr(newcap) * sys.PtrSize) ~略~ newcap = int(capmem / sys.PtrSize) default: ~略~ capmem = roundupsize(uintptr(newcap) * et.size) ~略~ newcap = int(capmem / et.size) } 確保メモリ = roundupsize(補正前スライス容量 x 要素サイズ) 補正後スライス容量 = 確保メモリ / 要素サイズ
19. roundupsize?
20. https://github.com/golang/go/blob/master/src/runti me/msize.go 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) }
21. roundupsizeというからにはキリの良いところまで メモリの確保量を切り上げているのだろうが、何 のための切り上げ？ class_to_size , size_to_class の'class'とは？
22. https://github.com/golang/go/blob/master/src/runti me/sizeclasses.go なんだろうこれは、という感じ
23. 「Goならわかるシステムプログラミング」より 小さなオブジェクトについては、より小さな単位 の「クラス」という分類で空きメモリのリストを 持っています。クラスからのメモリ取得では、リ クエストされたサイズに近いクラスの空きリスト があればそこからメモリを確保します。この場合 にはロックが不要であり、それだけ高速に処理で きます。 “ “
24. クラスという分類で空きメモ リリストを管理するため、キ リの良いところまで切り上げ をしている
25. 意味が掴めたところでnewcapの計算 結果を確かめてみる
26. 再掲
27. old.cap = 5 Go Playground環境においてはintのet.sizeは4, sys.PtrSizeも4 newcap := old.cap doublecap := newcap + newcap ~略~ if old.len < 1024 { newcap = doublecap } else { ~略~ case et.size == sys.PtrSize: ~略~ capmem = roundupsize(uintptr(newcap) * sys.PtrSize) ~略~ newcap = int(capmem / sys.PtrSize)
28. 計算してみたところ、ちゃんと結果が12になりまし た。 https://play.golang.org/p/oSn8GbSWVkK
29. まとめ スライスの容量拡張される際の新容量は、元容量 の大体2倍である。 (今回の話から省いたが、スラ イス長が大きい場合(1024が閾値)は大体1.25倍) きっちり2倍にならないのは、メモリ管理上キリの よいところまでメモリ確保量が切り上げされてい るからである。