Goコンパイラのお勉強（1） ~ゼロ幅の型によるメモリ利用の最適化と未定義動作 ~

はじめに
メモリアロケーションの回避
ゼロ幅の型（＝ゼロサイズの型）とは
アドレスの同一性に関する未定義動作
この最適化が有効な場面
おわりに
参考文献

はじめに

こんにちは。SRE の izzii です。最近は某フィットネスゲームが習慣だったり、ボルダリングを再開したり、登山シーズンが到来したりと心身ともに調子が良いです。

さてつい先日、Go のコンパイラによる最適化について勉強したまとめを社内で共有したところ、メンバーが面白がってくれたため、細かいところを自分の手で触ってみたり、Go Forum で質問を投稿したりした上で記事にしてみました。Go コンパイラの最適化について知りたいという方だけでなく、Go に慣れた方でも意外と知らない挙動を垣間見ることのできる内容かと思います。

github.com

を元にしているのですが、なかなかボリュームが大きくなりそうなので何個かの記事に分けます。本記事では「interface 値にゼロ幅の型を入れた場合にメモリアローケーションを回避する」という Go コンパイラの最適化と、とある未定義動作について見てみます。

[本記事] Goコンパイラのお勉強（1）~ゼロ幅の型によるメモリ利用の最適化と未定義動作~
[第 2 回] Goコンパイラのお勉強（2）~高階関数のためのインライン展開とエスケープ解析~
[第 3 回] Goコンパイラのお勉強（3）~配列の効率的な操作に関する最適化~

メモリアロケーションの回避

// https://github.com/golang/go/wiki/CompilerOptimizations

Putting a zero-width type in an interface value doesn't allocate.

ここでいう interface 値とは Go 1.18+ では any 型の値と言い換えられます。ゼロ幅の型とは go.dev

で定義されたゼロサイズの型のことです。実験の後に詳しく説明します。まずは具体的なユースケースを見てみましょう。gopher のみなさんは以下のようなコードをどこかで見た or 使ったことがあるのではないでしょうか？

// nums からユニークな値を uniqs のキーとして貯める処理

nums := []int{3,4,5,13,20,1,20,4}
uniqs := make(map[int]struct{}) // 空の struct 型を利用することを宣言

for _, n := range nums {
    if _, ok := uniqs[n]; ok {
        continue
    }
    uniqs[n] = struct{}{}
}

上の例では map の値として空の struct 型を利用することでメモリアロケーションを回避しています。

次に bool 型の配列と struct 型の配列を比較して実際にメモリアロケーションが回避されている様子を見てみましょう。map で比較しないのは、ハッシュ衝突を避けるためのメモリアロケーションが説明を面倒にしてしまう可能性があるためです。

まずは空の struct の場合

// go1.20.5 darwin/arm64

const M = 1024 * 1024

func printTotalAlloc() {
    var m runtime.MemStats
    runtime.ReadMemStats(&m)
    fmt.Printf("TotalAlloc = %v MiB\n", m.TotalAlloc/M)
}

func printCap[T any](a []T) {
    fmt.Printf("Capacity of Slice = %v\n", cap(a))
}

func printLen[T any](a []T) {
    fmt.Printf("Length of Slice = %v\n", len(a))
}

func printSize[T any](a []T) {
    fmt.Printf("Size of Slice = %v\n", unsafe.Sizeof(a))
}

func main() {
    a := make([]struct{}, M)
    printLen(a)       // Length of Slice = 1048576
    printCap(a)       // Capacity of Slice = 1048576
    printSize(a)      // Size of Slice = 24
    printTotalAlloc() // TotalAlloc = 0 MiB
}

次に bool 型の場合

// go1.20.5 darwin/arm64
.
.
.
func main() {
    a := make([]bool, M)
    printLen(a)       // Length of Slice = 1048576
    printCap(a)       // Capacity of Slice = 1048576
    printSize(a)      // Size of Slice = 24
    printTotalAlloc() // TotalAlloc = 1 MiB
}

ドンピシャな結果が出ました！

bool 型を利用した場合、1 MiB つまり 1024 * 1024 Byte 分のメモリアロケーションが発生しているのに対して、空の struct 型を利用した場合には余計なメモリアローケーションがありません。（注：あえてオーバーヘッド的に発生する細かいアロケーションを無視するように丸めてしまっています。）slice 自体はポインタと長さと容量の情報を持った 24 バイトの構造体でありサイズを持ちます。しかし長さと容量に関わらず slice の参照する中身に関してはメモリアロケートされません。

ゼロ幅の型（＝ゼロサイズの型）とは

ゼロ幅の型とはゼロサイズの型と同一であると前述しました。ゼロサイズのデータとはゼロよりも大きなサイズのフィールドを持たない struct や配列だと書かれています。

// https://go.dev/ref/spec#Size_and_alignment_guarantees

A struct or array type has size zero if it contains no fields 
(or elements, respectively) that have a size greater than zero. 
Two distinct zero-size variables may have the same address in memory.

何個か簡単な例を使って実験してみましょう。

// go1.20.5 darwin/arm64

func main() {
    // 空のstructはゼロサイズの型
    a := struct{}{}
    fmt.Println(unsafe.Sizeof(a)) // 0

    // 長さゼロの配列はゼロサイズの型
    b := [0]int{}
    fmt.Println(unsafe.Sizeof(b)) // 0

    // ゼロサイズの型を要素に持つ配列もゼロサイズの型
    var c [100]struct{}
    for i := 0; i < 100; i++ {
        c[i] = struct{}{}
    }
    fmt.Println(unsafe.Sizeof(c)) // 0

    // bool型の配列はサイズを持つ型
    var d [100]bool
    for i := 0; i < 100; i++ {
        d[i] = true
    }
    fmt.Println(unsafe.Sizeof(d)) // 100

    // slice はポインタと長さと容量を持つ構造体
    // ゼロサイズの型に当てはまらない
    e := make([]struct{}, 100)
    for i := 0; i < 100; i++ {
        e[i] = struct{}{}
    }
    fmt.Println(unsafe.Sizeof(e)) // 24
}

[100]struct{} がゼロサイズの型ということは、それを要素にした slice を作っても内容に関してはメモリアロートされません。

// go1.20.5 darwin/arm64

func main() {
    a := make([][100]struct{}, M)
    printLen(a)       // Length of Slice = 1048576
    printCap(a)       // Capacity of Slice = 1048576
    printSize(a)      // Size of Slice = 24
    printTotalAlloc() // TotalAlloc = 0 MiB
}

さらにいうと、空の struct と空の配列を組み合わせた型を作ってもそれはゼロ幅の型となります。

// go1.20.5 darwin/arm64

type MyStruct0 struct {
    x [0]int
}

type MyStruct1 struct {
    x MyStruct0
    y struct{}
}

func main() {
    a := MyStruct0{}
    fmt.Println(unsafe.Sizeof(a)) // 0

    b := MyStruct1{
        x: MyStruct0{},
        y: struct{}{},
    }
    fmt.Println(unsafe.Sizeof(b)) // 0

    var c [100]MyStruct1
    for i := 0; i < 100; i++ {
        c[i] = MyStruct1{
            x: MyStruct0{},
            y: struct{}{},
        }
    }
    fmt.Println(unsafe.Sizeof(c)) // 0
}

キモいですね。実用で出会うことはなさそうです。

ゼロ幅の型というのは

空の struct
空の配列
1 と 2 を要素に持つ配列や struct

であることを実際に見てみました。3. のような複雑なゼロ幅の型が利用できる場面を見る機会はないとは思いますが（笑）ただし慣習的には空の struct 型が使われるので、それを利用する方が可読性の高いコードが書けることでしょう。

アドレスの同一性に関する未定義動作

2014 時点での struct{} に関する記事

dave.cheney.net

に、以下のような実行例があるのですが

var a, b struct{}
fmt.Println(&a == &b) // true

私の環境（Go 1.20.5 darwin/arm64）においては正しくありません。

以下のようになります。

func main() {
    var a, b struct{}
    fmt.Println(&a == &b) // false
}

func main() {
    var a, b struct{}
    fmt.Println(&a == &b)  // true
    fmt.Printf("%p\n", &a) // 0x1172f60 *depends on env
    fmt.Printf("%p\n", &b) // 0x1172f60 *depends on env
}

キモいですね。（本日２回目）

先ほどの２つそれぞれを -gcflags="-m -N -l"でビルドした時を比較してみると、「ポインタを必要としない限りはスタック上の別々のアドレスに変数が入る」のに対して、「ポインタが必要になるとヒープの同一のアドレスにエスケープされる」のだろうなということが予測できます。

go build -gcflags="-m -N -l" -o output input.go
# command-line-arguments
./input.go:9:13: ... argument does not escape
./input.go:9:17: &a == &b escapes to heap

go build -gcflags="-m -N -l" -o output input.go
# command-line-arguments
./input.go:8:6: moved to heap: a
./input.go:8:9: moved to heap: b
./input.go:9:13: ... argument does not escape
./input.go:9:17: &a == &b escapes to heap
./input.go:10:12: ... argument does not escape
./input.go:11:12: ... argument does not escape

未定義動作かバグかわからなかったので Go Forum に報告してみることにしました。すると数時間で skillian 氏から回答をいただけました。Go のコミュニティあったけぇ。

forum.golangbridge.org

言語仕様として以下の二文が書かれており、つまり上の挙動は明確に保証はされていませんでした。

Pointers to distinct zero-size variables may or may not be equal.

Two distinct zero-size variables may have the same address in memory.

ちなみに自分の環境ではゼロ幅の型を持つ変数のアドレスは、型に関係なく同一になりました。（もちろんこの動作は保証されているわけではないけれど！）

func main() {
    var a struct{}
    var b [0]int
  // fmt.Println(&a == &b)  // 型が違うので比較はできません
    fmt.Printf("%p\n", &a) // 0x1172f60 *depends on env
    fmt.Printf("%p\n", &b) // 0x1172f60 *depends on env
}

この最適化が有効な場面

代表的なユースケースは以下かと思われます。この辺りは色々なウェブ上の記事で言及があるかと思いますのであっさりと。

1. map

本記事の最初に挙げた例です。キーに関してフラグ管理したいだけであれば、 map の値を struct{} にすると良いでしょう。

2. chan

チャネルが値を送信するのではなく、単にシグナルを送信するような場合に有効でしょう。例）サブゴルーチンの終了シグナルを待つメインゴルーチン。

import (
    "fmt"
    "time"
)

func main() {
    signal := make(chan struct{})

    go func() {
        time.Sleep(2 * time.Second)
        close(signal)
    }()

    fmt.Println("Waiting for signal...")
    <-signal
    fmt.Println("Received signal!")
}

3. interface の実装

状態を必要としない interface について、そのメソッド群を実装する型として空の struct 型を用いることができます。

type MyInterface interface {
    MyMethod()
}

type MyEmptyStruct struct{}

func (mes MyEmptyStruct) MyMethod() {
    fmt.Println("Do something")
}

func main() {
    var i MyInterface = MyEmptyStruct{}
    i.MyMethod() // Do something
}