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

このコミットは、Go言語のコンパイラ（gc）において、struct型とarray型に対する等価性比較演算子（==）の実装を追加するものです。これにより、これらの型がGoのmapのキーとして使用できるようになります。変更は主にコンパイラの型チェック、コード生成、およびランタイムの補助関数に及びます。

コミット

commit 196b6630759c6f4125c22445dd5b6cfec5faf34b
Author: Russ Cox <rsc@golang.org>
Date:   Mon Dec 12 22:22:09 2011 -0500

    gc: implement == on structs and arrays
    
    To allow these types as map keys, we must fill in
    equal and hash functions in their algorithm tables.
    Structs or arrays that are "just memory", like [2]int,
    can and do continue to use the AMEM algorithm.
    Structs or arrays that contain special values like
    strings or interface values use generated functions
    for both equal and hash.
    
    The runtime helper func runtime.equal(t, x, y) bool handles
    the general equality case for x == y and calls out to
    the equal implementation in the algorithm table.
    
    For short values (<= 4 struct fields or array elements),
    the sequence of elementwise comparisons is inlined
    instead of calling runtime.equal.
    
    R=ken, mpimenov
    CC=golang-dev
    https://golang.org/cl/5451105

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

https://github.com/golang/go/commit/196b6630759c6f4125c22445dd5b6cfec5faf34b

元コミット内容

Goコンパイラ（gc）に、struct型とarray型に対する==演算子を実装します。これにより、これらの型をmapのキーとして使用できるようになります。この機能を実現するためには、コンパイラがこれらの型の等価性比較とハッシュ計算のための関数を生成し、ランタイムのアルゴリズムテーブルに登録する必要があります。

具体的には、[2]intのような「純粋なメモリ」として扱えるstructやarrayは、引き続きAMEMアルゴリズム（メモリ比較）を使用します。一方、stringやinterface値のような特殊な値を含むstructやarrayは、コンパイラによって生成された専用の等価性比較関数とハッシュ関数を使用します。

一般的なx == yの等価性比較は、ランタイムのヘルパー関数runtime.equal(t, x, y) boolによって処理され、この関数はアルゴリズムテーブル内の適切な等価性実装を呼び出します。

最適化として、フィールド数または要素数が少ない（4つ以下）structやarrayの場合、runtime.equalを呼び出す代わりに、要素ごとの比較シーケンスがインライン化されます。

変更の背景

Go言語では、mapのキーとして使用できる型は「比較可能（comparable）」である必要があります。Goの初期のバージョンでは、structやarrayはデフォルトでは比較可能ではありませんでした。これは、これらの複合型に対する効率的かつ意味的に正しい等価性比較とハッシュ計算のロジックがコンパイラとランタイムに実装されていなかったためです。

このコミットの主な動機は、structやarrayをmapのキーとして利用できるようにすることです。これにより、開発者はより表現力豊かなデータ構造をmapのキーとして使用できるようになり、Go言語の柔軟性と実用性が向上します。

この変更は、Go言語の型システムにおける重要な拡張であり、コンパイラとランタイムの密接な連携によって実現されています。特に、複合型の内部構造を考慮した比較ロジックの自動生成は、コンパイラの高度な機能を示しています。

前提知識の解説

このコミットの理解には、以下のGo言語およびコンパイラの概念に関する知識が役立ちます。

1. Goの型システムと比較可能性:

   • Goでは、すべての型が比較可能であるわけではありません。==演算子やmapのキーとして使用できる型は「比較可能」であると定義されます。
   • 数値型、文字列型、ブール型、ポインタ型、チャネル型は常に比較可能です。
   • インターフェース型は、その動的な型と値が比較可能であれば比較可能です。
   • スライス、マップ、関数は比較不可能です（nilとの比較を除く）。
   • このコミット以前は、structとarrayは、その要素がすべて比較可能であっても、デフォルトでは比較可能ではありませんでした。

2. mapのキー:

   • Goのmapはハッシュテーブルとして実装されており、キーの等価性を判断するためにキーのハッシュ値と等価性比較を使用します。したがって、mapのキーとして使用される型は比較可能である必要があります。

3. Goコンパイラ（gc）の役割:

   • gcはGoの公式コンパイラであり、Goのソースコードを機械語に変換します。
   • 型チェック: ソースコードの型がGoの仕様に準拠しているか検証します。このコミットでは、structやarrayの比較可能性に関する新しいルールが型チェック段階で適用されます。
   • コード生成: Goのソースコードから実行可能なバイナリを生成します。このコミットでは、structやarrayの比較・ハッシュのための特殊な機械語コードが生成されます。
   • ランタイムとの連携: コンパイラは、ガベージコレクション、スケジューリング、型情報など、Goプログラムの実行をサポートするランタイム（runtimeパッケージ）と密接に連携します。

4. Goランタイム（runtimeパッケージ）:

   • Goプログラムの実行環境を提供する低レベルのコードです。
   • 型情報（Type Descriptors）: ランタイムは、プログラム内の各型の構造に関する情報を保持しています。これには、型のサイズ、アライメント、ポインタの有無、そして比較やハッシュのためのアルゴリズムへのポインタなどが含まれます。
   • アルゴリズムテーブル（algarray）: ランタイムには、様々な型の比較やハッシュ計算のための関数ポインタを格納するテーブルが存在します。コンパイラは、必要に応じてこのテーブルにエントリを追加したり、既存のエントリを参照したりします。

5. unsafe.Pointer:

   • Goのunsafeパッケージは、型安全性をバイパスしてメモリを直接操作する機能を提供します。コンパイラやランタイムの内部では、パフォーマンスや低レベルの操作のためにunsafe.Pointerが頻繁に使用されます。このコミットでも、メモリ比較関数などで利用されています。

技術的詳細

このコミットは、Goコンパイラとランタイムの複数の層にわたる協調的な変更によって実現されています。

1. 型情報の拡張と分類 (algtype1, algtype):

   • src/cmd/gc/subr.cにalgtype1という新しい関数が導入されました。この関数は、与えられたGoの型がどのように比較・ハッシュされるべきかを分類します。
     • AMEM: 完全にメモリ比較で済む型（例: 整数、浮動小数点数、ポインタ、[2]intのような純粋なメモリ配列）。
     • ANOEQ: 比較不可能な型（例: 関数、マップ、スライス）。
     • ASTRING: 文字列型。
     • AINTER, ANILINTER: インターフェース型。
     • -1: structやarrayで、内部にstringやinterfaceなど特殊な比較ロジックを必要とする要素を含む場合。これらの型には、コンパイラが専用の比較・ハッシュ関数を生成する必要があります。
   • 既存のalgtype関数はalgtype1を利用するように更新され、型の幅（サイズ）に基づいてAMEM8, AMEM16などのより具体的なAMEMバリアントやANOEQバリアントを返します。

2. コンパイラによる関数生成 (genhash, geneq):

   • src/cmd/gc/subr.cにgenhashとgeneqという2つの重要な関数が追加されました。これらは、algtype1が-1を返した（つまり、特殊な比較・ハッシュが必要な）structやarray型に対して、Goのコードとして等価性比較関数とハッシュ関数を生成します。
   • genhash(Sym *sym, Type *t): 型tのハッシュ値を計算するヘルパー関数を生成します。
     • structの場合、フィールドを走査し、AMEMで比較可能なフィールドの連続ブロックにはmemhash（メモリハッシュ）を、それ以外のフィールド（string, interfaceなど）にはそれぞれの型に応じたハッシュ関数（hashforを通じて呼び出される）を適用します。
     • arrayの場合、要素を走査し、各要素に対してhashforを呼び出します。
   • geneq(Sym *sym, Type *t): 型tの2つの値が等しいかをチェックするヘルパー関数を生成します。
     • structの場合、フィールドを走査し、AMEMで比較可能なフィールドの連続ブロックにはmemequal（メモリ比較）を、それ以外のフィールドにはeqfield（フィールドごとの比較）やeqmem（メモリ比較のヘルパー）を適用します。
     • arrayの場合、要素を走査し、各要素に対してp[i] != q[i]のような比較を生成します。
   • これらの生成された関数は、コンパイル時にGoのコードとして扱われ、最終的に機械語にコンパイルされます。

3. ランタイムアルゴリズムテーブルへの登録 (reflect.c, runtime/alg.c):

   • src/cmd/gc/reflect.cのdalgsym関数が、genhashとgeneqによって生成された関数へのシンボル（ポインタ）をランタイムの型情報（_type構造体）内のアルゴリズムテーブルに登録するように変更されました。これにより、ランタイムは特定の型の比較やハッシュが必要になった際に、適切な関数を呼び出すことができます。
   • src/pkg/runtime/alg.cには、runtime.equalという新しいランタイムヘルパー関数が追加されました。これは、Goの==演算子がstructやarrayに対して使用された場合に、コンパイラが生成するコードから呼び出される汎用的なエントリポイントです。runtime.equalは、引数として渡された型の_type情報から適切なequal関数（alg->equal）を見つけ出し、それを実行します。

4. 型チェックとコード生成の調整 (typecheck.c, walk.c):

   • src/cmd/gc/typecheck.cのtypecheck関数は、==および!=演算子に対する型チェックロジックを更新しました。
     • structやarrayが比較可能であるか（algtype1の結果に基づいて）検証し、比較不可能な要素を含む場合はコンパイルエラーを発生させます。
     • スライス、マップ、関数がnil以外と比較された場合もエラーとします。
   • src/cmd/gc/walk.cのwalkcompare関数は、==および!=演算子のコード生成を担当します。
     • インライン化の最適化: フィールド数または要素数が4つ以下のstructやarray（かつ、要素が単純な型の場合）に対しては、runtime.equalを呼び出す代わりに、要素ごとの比較を直接インラインで生成します。これにより、関数呼び出しのオーバーヘッドを削減し、パフォーマンスを向上させます。
     • ランタイム呼び出し: より複雑なstructやarray、またはインライン化の条件を満たさない場合は、runtime.equalヘルパー関数を呼び出すコードを生成します。

5. DUPOKフラグの導入:

   • src/cmd/gc/go.hのNode構造体にdupokフィールドが追加されました。これは、コンパイラが生成する関数（特にgenhashやgeneqによって生成されるもの）が、リンカによって重複定義されても問題ないことを示すフラグです。これにより、異なるパッケージで同じ型の比較関数が生成されても、リンカがエラーを発生させないようになります。

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

このコミットにおける主要な変更は、以下のファイルに集中しています。

• src/cmd/gc/go.h: 型定義と新しい関数のプロトタイプ宣言。
• src/cmd/gc/builtin.c.boot: ランタイムの組み込み関数リストの更新。
• src/cmd/gc/reflect.c: ランタイム型情報とアルゴリズムテーブルの生成ロジック。特にdalgsym、typesymprefixの追加。
• src/cmd/gc/runtime.go: ランタイムヘルパー関数equalおよびmemequal群の宣言。
• src/cmd/gc/subr.c: 型の比較可能性を判断するalgtype1、algtype、そしてハッシュ関数を生成するgenhash、等価性比較関数を生成するgeneqの実装。
• src/cmd/gc/typecheck.c: ==演算子の型チェックロジックの更新。
• src/cmd/gc/walk.c: ==演算子のコード生成ロジック。特にwalkcompareの追加と、インライン化の最適化。
• src/pkg/runtime/alg.c: ランタイム側のruntime.equalの実装と、アルゴリズムテーブルの定義。
• test/cmp.go: structとarrayの比較可能性を検証する新しいテストケース。

コアとなるコードの解説

src/cmd/gc/subr.c - algtype1関数

int
algtype1(Type *t, Type **bad)
{
    // ... (省略) ...
    switch(t->etype) {
    case TINT8: case TUINT8: // ... プリミティブ型 ...
    case TPTR32: case TPTR64: case TCHAN: case TUNSAFEPTR:
        return AMEM; // メモリ比較でOKな型

    case TFUNC: case TMAP:
        if(bad) *bad = t;
        return ANOEQ; // 比較不可能な型

    case TSTRING:
        return ASTRING; // 文字列比較

    case TINTER:
        if(isnilinter(t))
            return ANILINTER; // nilインターフェース比較
        return AINTER; // インターフェース比較

    case TARRAY:
        if(isslice(t)) {
            if(bad) *bad = t;
            return ANOEQ; // スライスは比較不可
        }
        if(t->bound == 0)
            return AMEM; // 要素数0の配列はメモリ比較
        a = algtype1(t->type, bad); // 要素の型を再帰的にチェック
        if(a == ANOEQ || a == AMEM) {
            if(a == ANOEQ && bad)
                *bad = t;
            return a; // 要素が比較不可なら配列も比較不可、またはメモリ比較なら配列もメモリ比較
        }
        return -1;  // 特殊な比較が必要 (要素がstringやinterfaceなど)

    case TSTRUCT:
        if(t->type != T && t->type->down == T) {
            // フィールドが1つのstructは、そのフィールドと同じ比較ロジック
            return algtype1(t->type->type, bad);
        }
        ret = AMEM;
        for(t1=t->type; t1!=T; t1=t1->down) {
            a = algtype1(t1->type, bad);
            if(a == ANOEQ)
                return ANOEQ;  // 比較不可能なフィールドがあればstructも比較不可
            if(a != AMEM)
                ret = -1;  // メモリ比較以外のフィールドがあれば特殊な比較が必要
        }
        return ret; // すべてメモリ比較ならAMEM、そうでなければ-1
    }
    // ... (省略) ...
}

この関数は、Goの型tを受け取り、その型がどのように比較されるべきか（メモリ比較、文字列比較、インターフェース比較、またはコンパイラが生成する特殊な関数による比較）を決定します。structやarrayの場合、その内部のフィールドや要素を再帰的にチェックし、一つでも比較不可能な要素があればその複合型全体も比較不可能と判断します。また、stringやinterfaceなど、メモリ比較では不十分な要素が含まれる場合は-1を返し、コンパイラに専用の比較関数生成を促します。

src/cmd/gc/walk.c - walkcompare関数

static void
walkcompare(Node **np, NodeList **init)
{
    Node *n, *l, *r, *fn, *call, *a, *li, *ri, *expr;
    int andor, i;
    Type *t, *t1;
    static Node *tempbool;

    n = *np;
    // ... (省略) ...
    t = n->left->type;
    switch(t->etype) {
    default:
        return; // struct/array以外は既存のロジック
    case TARRAY:
        if(isslice(t))
            return; // スライスは比較不可
        break;
    case TSTRUCT:
        break;
    }

    // ... (省略: オペランドのアドレス取得と一時変数への格納) ...

    if(t->etype == TARRAY && t->bound <= 4 && issimple[t->type->etype]) {
        // 要素数4以下の単純な配列の場合、要素ごとの比較をインライン化
        for(i=0; i<t->bound; i++) {
            li = nod(OINDEX, l, nodintconst(i));
            ri = nod(OINDEX, r, nodintconst(i));
            a = nod(n->op, li, ri); // 各要素の比較ノードを生成
            if(expr == N)
                expr = a;
            else
                expr = nod(andor, expr, a); // 論理AND/ORで結合
        }
        // ... (省略) ...
        *np = expr; // 生成されたインライン比較コードに置き換え
        return;
    }

    if(t->etype == TSTRUCT && countfield(t) <= 4) {
        // フィールド数4以下のstructの場合、フィールドごとの比較をインライン化
        for(t1=t->type; t1; t1=t1->down) {
            li = nod(OXDOT, l, newname(t1->sym));
            ri = nod(OXDOT, r, newname(t1->sym));
            a = nod(n->op, li, ri); // 各フィールドの比較ノードを生成
            if(expr == N)
                expr = a;
            else
                expr = nod(andor, expr, a); // 論理AND/ORで結合
        }
        // ... (省略) ...
        *np = expr; // 生成されたインライン比較コードに置き換え
        return;
    }

    // インライン化できない場合、ランタイムヘルパー関数を呼び出す
    // ... (tempboolの初期化) ...
    call = nod(OCALL, eqfor(t), N); // eqfor(t)は適切な比較関数（memequalまたはgeneqで生成された関数）を返す
    // ... (引数の設定: eq *bool, size uintptr, x unsafe.Pointer, y unsafe.Pointer) ...
    *init = list(*init, call); // 関数呼び出しを初期化リストに追加

    if(n->op == OEQ)
        r = tempbool; // == なら結果はtempbool
    else
        r = nod(ONOT, tempbool, N); // != ならtempboolの否定
    // ... (省略) ...
    *np = r; // 結果ノードに置き換え
    return;

hard:
    // オペランドのアドレスが取れない場合（一時変数など）
    fn = syslook("equal", 1); // runtime.equalヘルパー関数を直接呼び出す
    l = n->left;
    r = n->right;
    // ... (引数の設定: typename(n->left->type), l, r) ...
    r = mkcall1(fn, n->type, init, typename(n->left->type), l, r);
    if(n->op == ONE) {
        r = nod(ONOT, r, N);
        typecheck(&r, Erv);
    }
    *np = r;
    return;
}

walkcompare関数は、structやarrayに対する==または!=演算子が出現した際に、実際に比較を行うコードを生成します。

• インライン化: 小さなarrayやstruct（要素/フィールドが4つ以下で、かつ単純な型の場合）に対しては、各要素/フィールドを個別に比較し、その結果を論理演算子で結合するコードを直接生成します。これにより、ランタイム関数呼び出しのオーバーヘッドを避けてパフォーマンスを向上させます。
• ランタイム呼び出し: インライン化の条件を満たさない、より大きなまたは複雑なarray/structに対しては、eqfor(t)によって取得される適切な比較関数（memequalまたはgeneqによって生成された関数）を呼び出すコードを生成します。この関数は、比較結果をtempboolという一時的なブールポインタに書き込みます。
• hardパス: オペランドが一時変数などでアドレスが直接取れない場合（例: f() == g()のような関数呼び出しの結果の比較）、最終手段としてランタイムの汎用ヘルパー関数runtime.equalを直接呼び出すコードを生成します。

これらの変更により、Go言語はstructとarrayの比較可能性を大幅に拡張し、mapのキーとしての利用を可能にしました。これは、Goの型システムとランタイムの進化における重要なマイルストーンです。

関連リンク

• Go言語の仕様: https://go.dev/ref/spec
• Goの比較可能性に関する公式ドキュメント: https://go.dev/ref/spec#Comparison_operators
• Goのmapに関する公式ドキュメント: https://go.dev/ref/spec#Map_types

参考にした情報源リンク

• Goのソースコード (特にsrc/cmd/gcとsrc/pkg/runtimeディレクトリ)
• Goのコンパイラとランタイムに関するブログ記事やドキュメント (一般的なGoの内部動作に関する情報)
• Gerrit Change-ID: https://golang.org/cl/5451105 (コミットに記載されているGerritのリンク)
• Goのunsafeパッケージに関するドキュメント: https://pkg.go.dev/unsafe
• Goの型システムに関する議論 (Goコミュニティのフォーラムやメーリングリスト)