[インデックス 17598] ファイルの概要

このコミットは、Goコンパイラ（cmd/gc）における内部マップ型（hashmapの内部構造を記述する偽の型）に対するハッシュ関数と等値関数（algs）の生成を停止することで、ビルド時間とバイナリサイズを削減することを目的としています。これらの内部型は、正確なガベージコレクション（Precise GC）のために生成されますが、それらに対するalgsの生成は不要であり、オーバーヘッドとなっていました。

コミット

commit 04c40c97c3a76368f878126259fb5d33e0515aaa
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Sat Sep 14 09:30:36 2013 +0200

    cmd/gc: don't generate algs for internal map types.
    
    Fake types describing the internal structure of hashmaps are
    generated for use by precise GC.
    
    Generating hash and eq functions for these fake types slows down
    the build and wastes space: the go tool binary size is 13MB
    instead of 12MB, and the package size on amd64 is 48.7MB instead
    of 45.3MB.
    
    R=golang-dev, daniel.morsing, r, khr, rsc, iant
    CC=golang-dev
    https://golang.org/cl/13698043

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/04c40c97c3a76368f878126259fb5d33e0515aaa

元コミット内容

cmd/gc: don't generate algs for internal map types.

このコミットは、Goコンパイラ（cmd/gc）が内部マップ型（ハッシュマップの内部構造を記述するために生成される偽の型）に対して、ハッシュ関数と等値関数（algs）を生成しないように変更します。これらの偽の型は正確なガベージコレクション（Precise GC）のために使用されますが、それらに対するalgsの生成はビルドを遅くし、スペースを浪費していました。具体的には、go toolバイナリのサイズが13MBから12MBに、amd64上のパッケージサイズが48.7MBから45.3MBに削減される効果がありました。

変更の背景

Go言語のマップ（map）は、内部的にはハッシュテーブルとして実装されています。ガベージコレクタ（GC）がメモリを正確に管理するためには、マップの内部構造、特にポインタがどこにあるかを正確に把握する必要があります。この目的のために、Goコンパイラ（cmd/gc）は、マップの内部構造を記述する「偽の型（fake types）」を生成していました。これらの偽の型は、GCがマップ内のポインタを正確にスキャンし、到達可能なオブジェクトを識別するために不可欠です。

しかし、これらの偽の型に対して、通常の型と同様にハッシュ関数（hash）と等値関数（eq）を生成することは、不要なオーバーヘッドを生み出していました。これらの関数は、マップのキーの比較やハッシュ計算に用いられるものであり、マップの内部構造を記述する偽の型自体が直接キーとして使用されることはありません。したがって、これらの関数を生成することは、ビルドプロセスの速度低下と、最終的なバイナリおよびパッケージサイズの増加につながっていました。

このコミットは、この不要なalgs生成を停止することで、ビルド効率の向上とバイナリサイズの削減を図ることを目的としています。

前提知識の解説

• Go言語のマップ（map）: Goのマップはキーと値のペアを格納するデータ構造で、内部的にはハッシュテーブルとして実装されています。キーは比較可能な型である必要があります。
• Goコンパイラ（cmd/gc）: Go言語のソースコードを機械語に変換する公式コンパイラです。Goのランタイムと密接に連携し、メモリ管理や並行処理の最適化を行います。
• ガベージコレクション（GC）: プログラムが動的に確保したメモリ領域のうち、もはや使用されない（到達不能な）領域を自動的に解放する仕組みです。GoのGCは「正確なGC（Precise GC）」として知られています。
• 正確なGC（Precise GC）: GCがメモリ内のどの値がポインタであり、どの値がポインタでないかを正確に識別できるGC方式です。これにより、GCはポインタをたどって到達可能なオブジェクトを正確にマークし、到達不能なオブジェクトのみを解放できます。不正確なGC（Conservative GC）と比較して、メモリリークのリスクが低く、より効率的なメモリ利用が可能です。
• ハッシュ関数（hash）と等値関数（eq）:
  • ハッシュ関数: 入力データ（この場合はマップのキー）を受け取り、固定長の数値（ハッシュ値）を生成する関数です。ハッシュテーブルでは、キーのハッシュ値を使ってデータが格納される場所を決定します。
  • 等値関数: 2つの値が等しいかどうかを判定する関数です。マップでは、キーの比較に用いられます。
  • Goコンパイラは、マップのキーとして使用される型に対して、これらの関数を自動的に生成または選択します。これらは内部的に「algs（algorithms）」と呼ばれます。
• 内部マップ型（Fake types describing the internal structure of hashmaps）: Goのマップは複雑な内部構造を持っています。例えば、hmap構造体や、キーと値を格納する「バケット（bucket）」などです。正確なGCがこれらの内部構造をスキャンし、ポインタを識別できるように、コンパイラはこれらの内部構造を表現する「偽の型」を生成します。これらの型はGoプログラマが直接扱うものではなく、コンパイラとランタイムの内部でのみ使用されます。

技術的詳細

Goの正確なGCは、メモリ内のすべてのポインタを正確に追跡する必要があります。マップの場合、その内部構造（hmapやバケット）には、キーや値へのポインタが含まれる可能性があります。GCがこれらのポインタを正しく識別し、到達可能性を判断するために、コンパイラはマップの内部構造を表現する特別な型情報を生成します。これらの型情報は、GCがメモリをスキャンする際のガイドとなります。

このコミット以前は、これらの内部マップ型に対しても、通常のユーザー定義型と同様にハッシュ関数と等値関数（algs）が生成されていました。しかし、これらの内部型は、Goプログラム内で直接マップのキーとして使用されることはありません。それらはGCが内部的にマップのメモリレイアウトを理解するためのメタデータに過ぎません。

したがって、これらの内部型に対してalgsを生成することは、以下の点で無駄でした。

1. ビルド時間の増加: 不要なコード生成とコンパイル処理が発生し、ビルド時間が長くなります。
2. バイナリサイズの増加: 生成されたalgsのコードが最終的なgo toolバイナリやコンパイル済みパッケージに含まれるため、ファイルサイズが不必要に大きくなります。コミットメッセージにあるように、go toolバイナリで1MB、amd64パッケージで3.4MBの削減効果がありました。

このコミットは、Type構造体にnoalgという新しいフィールドを追加し、このフィールドがセットされている型に対してはalgsの生成をスキップするようにコンパイラのロジックを変更することで、この問題を解決しています。具体的には、マップのバケット型（mapbucket）とマップのヘッダ型（hmap）を生成する際に、noalgフラグを1に設定します。これにより、algtype1関数（algsを生成するかどうかを決定する関数）がこれらの型に対してANOEQ（No Equality Algorithm）を返すようになり、不要なalgsの生成が抑制されます。

コアとなるコードの変更箇所

このコミットでは、以下の3つのファイルが変更されています。

1. src/cmd/gc/go.h
2. src/cmd/gc/reflect.c
3. src/cmd/gc/subr.c

それぞれの変更内容は以下の通りです。

src/cmd/gc/go.h Type構造体にnoalgという新しいuchar型のフィールドが追加されています。

--- a/src/cmd/gc/go.h
+++ b/src/cmd/gc/go.h
@@ -141,6 +141,7 @@ struct	Type
 {
 	uchar	etype;
 	uchar	nointerface;
+	uchar	noalg;
 	uchar	chan;
 	uchar	trecur;		// to detect loops
 	uchar	printed;

src/cmd/gc/reflect.c mapbucket関数とhmap関数内で、生成される型（bucketおよびh）のnoalgフィールドが1に設定されています。

--- a/src/cmd/gc/reflect.c
+++ b/src/cmd/gc/reflect.c
@@ -131,6 +131,7 @@ mapbucket(Type *t)
 		valtype = ptrto(valtype);
 
 	bucket = typ(TSTRUCT);
+	bucket->noalg = 1;
 
 	// The first field is: uint8 topbits[BUCKETSIZE].
 	// We don't need to encode it as GC doesn't care about it.
@@ -192,6 +193,7 @@ hmap(Type *t)
 
 	bucket = mapbucket(t);
 	h = typ(TSTRUCT);
+	h->noalg = 1;
 
 	offset = widthint; // count
 	offset += 4;       // flags

src/cmd/gc/subr.c algtype1関数内で、引数tのnoalgフィールドが1の場合に、ANOEQ（No Equality Algorithm）を返すように変更されています。

--- a/src/cmd/gc/subr.c
+++ b/src/cmd/gc/subr.c
@@ -547,6 +547,9 @@ algtype1(Type *t, Type **bad)
 	if(bad)
 		*bad = T;
 
+	if(t->noalg)
+		return ANOEQ;
+
 	switch(t->etype) {
 	case TANY:
 	case TFORW:

コアとなるコードの解説

このコミットの核心は、Goコンパイラが内部的に使用する型情報にnoalgという新しいフラグを導入し、このフラグが設定されている型に対しては、ハッシュ関数と等値関数（algs）の生成をスキップするようにした点です。

1. Type構造体へのnoalgフィールド追加 (src/cmd/gc/go.h): Type構造体は、Goコンパイラが型情報を表現するために使用する内部データ構造です。ここにnoalgという1バイトのフラグが追加されました。このフラグは、その型に対してalgs（ハッシュ関数と等値関数）を生成する必要があるかどうかを示すために使用されます。noalgが1の場合、algsは生成されません。

2. 内部マップ型生成時のnoalg設定 (src/cmd/gc/reflect.c): reflect.cファイルには、Goのマップの内部構造を表現する型（mapbucketとhmap）を生成する関数が含まれています。

   • mapbucket(Type *t): マップのバケット（キーと値を格納する内部配列）を表す構造体型を生成します。
   • hmap(Type *t): マップのヘッダ（マップ全体のメタデータを含む構造体）を表す構造体型を生成します。 これらの関数内で、新しく生成されるbucket型とh型（どちらもType構造体のインスタンス）のnoalgフィールドが1に設定されます。これにより、これらの内部型はalgsの生成対象から除外されるようになります。

3. algtype1関数でのnoalgチェック (src/cmd/gc/subr.c): subr.cファイルには、Goコンパイラの様々なユーティリティ関数が含まれており、その中にalgtype1関数があります。この関数は、与えられた型tに対してどのようなalgsが必要かを決定します。 変更後、algtype1関数はまずt->noalgが1であるかどうかをチェックします。もし1であれば、その型にはalgsが不要であると判断し、ANOEQ（Algorithm No Equality - 等値アルゴリズムなし）を返します。これにより、後続のalgs生成ロジックがスキップされ、ビルド時間とバイナリサイズの削減が実現されます。

この一連の変更により、Goコンパイラは、正確なGCのために必要な内部マップ型情報を引き続き生成しつつも、それらの型に対して不要なハッシュ関数や等値関数を生成する無駄を省くことができるようになりました。

関連リンク

• Go言語のマップの内部実装に関する記事:
  • Go maps in action - The Go Programming Language
  • Understanding Go maps: an in-depth guide
• Goのガベージコレクションに関する記事:
  • Go's Garbage Collector: A Comprehensive Guide
  • Go: The Good, Bad and Ugly of Garbage Collection
  • Go's new GC: Less latency, more throughput

参考にした情報源リンク

• https://github.com/golang/go/commit/04c40c97c3a76368f878126259fb5d33e0515aaa
• Web search results for "Go cmd/gc internal map types precise GC hash eq functions algs" (provided by the tool)
  • go.dev
  • medium.com
  • stackoverflow.com
  • cheney.net
  • thefortunedays.com
  • programmingeeksclub.com
  • dev.to
  • golang.org
  • go.dev (internal/abi/type.go)