🌟

Go 1.21と1.22でスライスの cap が異なるケース

2024/03/06に公開

以下のコードは、Go 1.21と1.22で出力結果が異なる。issue

package main

type foo struct {
  f1 uint64
  f2 uint64
  f3 *uint64
}

func main() {
  var s []foo
  for i := 0; i < 17; i++ {
    s = append(s, foo{})
  }
  println(cap(s))
  // Go1.21: 32
  // Go1.22: 37
}

https://go.dev/play/p/zhqC58zpkhC

これについて内容を調べたのでメモ。

スライスの拡張

スライスは以下のように「基となる配列 array」「長さ len」「容量 cap」からなるデータ構造。

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

https://github.com/golang/go/blob/go1.22.1/src/runtime/slice.go#L15-L19

詳しいの内部構造の話は、Go 公式ブログの Go Slices: usage and internals を参照。

容量が一杯になったスライスを拡張するのは、growslice 関数で行われている。growslice 関数は、

oldPtr: 基となる配列へのポインタ
newLen: 新しい長さ(古い長さ + 追加される要素数)
oldCap: 古い容量
num: 追加される要素数
et: 要素のデータ型

を引数に受け取り、新しい slice を返す。

拡張はいくつかのステップを踏んで行われる。

まず、nextslicecap 関数で newLen と oldCap から、新しいスライスの適切な容量を計算する。ここで行われていることは以下の通り。

newLen が oldCap の2倍よりも大きいならそれを採用
oldCap が、閾値(256)より小さいなら、oldCap の2倍を採用
上記以外の場合、小さいスライスは2倍、大きいスライスはゆっくり大きくなる(具体的には1.25倍)よう newCap を計算
- newCap の初期値は oldCap
- newcap += (newcap + 3*threshold) >> 2
  - newCap=256: (256 + 3*256) >> 2 = 256。よって2倍
  - newCap=512: (512 + 3*256) >> 2 = 832。よって1.625倍
  - newCap=768: (768 + 3*256) >> 2 = 1152。よって1.5倍
  - newCap=1024: (1024 + 3*256) >> 2 = 1472。よって1.4375倍
  - newCap=1280: (1280 + 3*256) >> 2 = 1792。よって1.4倍
  - ...
- newCap が newLen を超過するかオーバーフローするまで
算出した newCap がオーバーフローしていたら newLen、していなければ newCap を採用

その後、要素のデータ型に応じて新しいスライスの len と cap のメモリサイズを計算する。
型の種類ごとにそれぞれ何を行っているかは今回とあまり関係ないのでスキップし、cap のメモリサイズを計算している roundupsize 関数について見ていく。

Go のメモリ管理と roundupsize

roundupsize 関数の具体的な処理の内容の前に、Go のメモリ管理(ヒープ)について軽くおさらいする。

効率的なメモリ管理の実現のため、Go のランタイムは色々なサイズで事前にアロケーションしておき、オブジェクトを割り当てるときはそれら事前にアロケーションした領域をうまく使い回している。

色々なサイズで事前にアロケーションされるものは src/runtime/sizeclasses.go で定義されているとおり67種類存在し、これらを「サイズクラス」という。
オブジェクトのサイズから適切なサイズクラスを対応させて割り当てることでメモリの利用効率を上げている。サイズクラスに対応できないくらい大きいオブジェクトの場合サイズクラスを用いずに直接アロケート処理が行われるが、ここも今回の話とはあまり関係していないのでスキップ。

参考：Goのメモリ管理

話を roundupsize 関数に戻す。短い関数なので以下に全体をコピペ。

func roundupsize(size uintptr, noscan bool) (reqSize uintptr) {
  reqSize = size
  if reqSize <= maxSmallSize-mallocHeaderSize {
    // Small object.
    if !noscan && reqSize > minSizeForMallocHeader { // !noscan && !heapBitsInSpan(reqSize)
      reqSize += mallocHeaderSize
    }
    // (reqSize - size) is either mallocHeaderSize or 0. We need to subtract mallocHeaderSize
    // from the result if we have one, since mallocgc will add it back in.
    if reqSize <= smallSizeMax-8 {
      return uintptr(class_to_size[size_to_class8[divRoundUp(reqSize, smallSizeDiv)]]) - (reqSize - size)
    }
    return uintptr(class_to_size[size_to_class128[divRoundUp(reqSize-smallSizeMax, largeSizeDiv)]]) - (reqSize - size)
  }
  // Large object. Align reqSize up to the next page. Check for overflow.
  reqSize += pageSize - 1
  if reqSize < size {
    return size
  }
  return reqSize &^ (pageSize - 1)
}

ここで行われている処理は以下の通り。32K-8 バイト(maxSmallSize - mallocHeaderSize)以下の小さなオブジェクトについてのみ見てみると、

noscan フラグが false かつサイズが minSizeForMallocHeader より大きい場合、 mallocHeaderSize がサイズに追加される
最終的なサイズは、特定のサイズクラスに基づいて決定する
- divRoundUp 関数で、オブジェクトのサイズを8(smallSizeDiv)で除算(切り上げ)
- size_to_class8 配列で、オブジェクトを対応するサイズクラスにマッピング
- class_to_size 配列で、サイズクラスから対応するメモリブロックのサイズを取得

例えば、サイズが100のオブジェクトの場合、

divRoundUp(100, 8) = 13
size_to_class8[13] = 9
class_to_size[9] = 112

より、最終的なサイズは112になる。

ここで、サイズに追加している mallocHeaderSize とは何か？

allocheaders

roundupsize 関数はもう一つ定義されていて、こちらには mallocHeaderSize は登場しない。

func roundupsize(size uintptr, noscan bool) uintptr {
  if size < _MaxSmallSize {
    if size <= smallSizeMax-8 {
      return uintptr(class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]])
    } else {
      return uintptr(class_to_size[size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]])
    }
  }
  if size+_PageSize < size {
    return size
  }
  return alignUp(size, _PageSize)
}

https://github.com/golang/go/blob/go1.22.1/src/runtime/msize_noallocheaders.go

こちらで小さいオブジェクト(32KB未満)の場合に行われている処理は、メモリ管理で見た通り、対応するサイズクラスから実際の割り当てサイズを決定するのみ。これの前に見た roundupsize 関数での「mallocHeaderSize の追加」は行われていない。

これら2つの roundupsize 関数は、ビルドタグ goexperiment.allocheaders によってビルド対象が制御されている。allocheaders が有効のときは mallocHeaderSize の追加が行われ、無効のときは行われない。

allocheaders とは 38ac7c41aa54306c0bdc04a092838103a7d09997 で実装された新しいメモリ管理の要素で、512バイト以上のオブジェクトのメモリアロケーション時に、オブジェクトの型情報の管理のための8バイトのヘッダーが付与されるようになった。先に見た mallocHeaderSize はこのヘッダーの長さ。

これが Go 1.22で導入されたことで、冒頭のコードの結果が Go 1.21と1.22で異なっている。何が起こっているかというと、24バイト(uint64, uin64, uintptr)の要素を持ち len, cap がそれぞれ16あるスライスに append を行うとき、

1.21
- 拡張前の cap が256未満なのでまずは単純に cap を2倍に拡張(24*16*2=768)
- 768バイトのオブジェクトはサイズクラス30に対応するため、roundupsize 関数での切り上げ(別のサイズクラスへの対応)が発生しない
- 新しい cap は、768/24=32
1.22
- 拡張前の cap が256未満なのでまずは単純に cap を2倍に拡張(24*16*2=768)
- 768は allocheaders の基準値である512バイトを超えるので、ヘッダー分の長さ mallocHeaderSize が追加されて768+8=776
- 776は別のサイズクラス31の896に切り上げ
- 新しい cap は、896/24=37.333...より37

その他

冒頭のコードについて、ポインタ型だったフィールドを非ポインタ型にすると、Go 1.22でも結果は32になる。

package main

type foo struct {
  f1 uint64
  f2 uint64
  f3 uint64
}

func main() {
  var s []foo
  for i := 0; i < 17; i++ {
    s = append(s, foo{})
  }
  println(cap(s))
  // Go1.21: 32
  // Go1.22: 32
}

これは非ポインタ型になったことで mallocHeaderSize
の追加が行われなかったため。roundupsize 関数で用いられる noscan フラグは、要素のデータ型がポインタを含まない場合に true になり、noscan が false のときにヘッダー分の追加が行われうる。

スライスの拡張

Go のメモリ管理と roundupsize

allocheaders

その他

Discussion