Keyboard shortcuts

Press or to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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

このコミットは、Go言語のコンパイラ(gc)とランタイム(runtime)におけるマップ(ハッシュテーブル)の実装、および文字列比較の改善に焦点を当てています。具体的には、以下のファイルが変更されています。

  • src/cmd/6g/gen.c: コンパイラのコード生成フェーズに関連する微調整。
  • src/cmd/gc/sys.go: Goコンパイラがランタイム関数を呼び出すためのシステムコール定義。マップ操作関数のシグネチャが変更されています。
  • src/cmd/gc/sysimport.c: sys.goで定義されたシステムコールをコンパイラがインポートするためのC言語のソースファイル。型定義が更新されています。
  • src/cmd/gc/walk.c: コンパイラの「ウォーク」フェーズ、つまり抽象構文木(AST)を走査し、最適化やコード変換を行う部分。マップ操作の処理ロジックが大幅に変更されています。
  • src/runtime/runtime.c: GoランタイムのC言語実装。文字列比較関数が追加・変更されています。
  • src/runtime/runtime.h: Goランタイムのヘッダーファイル。新しい文字列比較関数の宣言が追加されています。

コミット

commit 4e8142c929bf285870aaa561d8bf47c94639b89b
Author: Ken Thompson <ken@golang.org>
Date:   Mon Jun 16 22:34:50 2008 -0700

    maps
    
    SVN=123089

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

https://github.com/golang/go/commit/4e8142c929bf285870aaa561d8bf47c94639b89b

元コミット内容

maps

変更の背景

このコミットの主な背景は、Go言語におけるマップ(ハッシュテーブル)の操作、特に要素の代入(mapassign)と削除(mapdelete)の内部的な処理を改善することにあります。初期のGo言語では、マップ操作は現在ほど洗練されておらず、コンパイラとランタイム間の連携も進化の途上にありました。

具体的には、マップへの値の代入において、キーが存在しない場合に新しいエントリを作成するのか、それとも既存のエントリを更新するのか、といったセマンティクスをより明確に、かつ効率的に扱う必要がありました。また、マップのキーや値の型に応じた適切なハッシュアルゴリズムや比較アルゴリズムを選択し、ランタイムに渡すための仕組みも整備する必要がありました。

mapassignmapassign1mapassign2に分割されたのは、Go言語のマップ代入が単なる値の代入だけでなく、value, ok := m[key]のような「存在チェック付き代入」のセマンティクスをサポートするためと考えられます。これにより、コンパイラは異なるシナリオに応じて適切なランタイム関数を呼び出すことができるようになります。

また、cmpstring関数の導入は、文字列の比較処理をランタイムレベルで効率的に行うための基盤を強化するものです。これはマップのキーとして文字列が使われる場合に、キーの比較性能に直接影響します。

前提知識の解説

Go言語のコンパイルプロセス(gc

Go言語の公式コンパイラであるgcは、複数のフェーズを経てソースコードを実行可能なバイナリに変換します。

  1. 字句解析と構文解析: ソースコードをトークンに分解し、抽象構文木(AST)を構築します。
  2. 型チェックとASTの変換(walkフェーズ): ASTを走査し、型チェックを行い、高レベルなGoの構文(例: forループ、map操作)を、より低レベルな中間表現(IR)に変換します。このフェーズで多くの最適化やセマンティックな変換が行われます。このコミットでsrc/cmd/gc/walk.cが大きく変更されているのは、このフェーズでマップ操作の変換ロジックが更新されたためです。
  3. SSA(Static Single Assignment)形式への変換と最適化: IRをSSA形式に変換し、さらに多くの最適化を適用します。
  4. コード生成: 最適化されたSSA形式から、ターゲットアーキテクチャの機械語コードを生成します。src/cmd/6g/gen.cはこのフェーズの一部です。

Goランタイム(runtime

Goランタイムは、Goプログラムの実行をサポートするC言語およびGo言語で書かれたライブラリです。ガベージコレクション、スケジューラ、マップやチャネルなどの組み込み型の実装、システムコールインターフェースなどが含まれます。コンパイラは、特定のGoの操作(例: マップの作成、アクセス、代入)を、ランタイムが提供するC言語関数への呼び出しに変換します。

Goのマップ(map

Goのマップはハッシュテーブルとして実装されており、キーと値のペアを格納します。マップの操作(作成、要素の追加/更新、要素の取得、要素の削除)は、コンパイラによってランタイム関数への呼び出しに変換されます。マップのキーは比較可能でなければならず、ハッシュ可能である必要があります。

sysパッケージとsysimport.c

Goコンパイラには、Go言語のソースコードからは直接アクセスできない、ランタイムが提供する低レベルな関数群を定義する「sys」パッケージという概念があります。src/cmd/gc/sys.goは、これらの関数のGo言語側のシグネチャを定義し、src/cmd/gc/sysimport.cは、これらの定義をコンパイラがC言語のコードとして利用できるようにするためのメカニズムを提供します。これにより、コンパイラはGoのソースコードを解析する際に、これらのランタイム関数の存在と型情報を認識できます。

ullmancalc

ullmancalcは、コンパイラの最適化フェーズで使用されるUllman数(Ullman number)を計算する関数です。Ullman数は、式の評価順序を決定し、レジスタ割り当てを最適化するために使用されるヒューリスティックな値です。このコミットでは、walk.c内でullmancalcの呼び出し位置が変更されており、これはマップ操作の変換ロジックの変更に伴う、式の評価順序の再調整を示唆しています。

技術的詳細

このコミットの核となる変更は、Goコンパイラがマップ操作をどのように中間表現に変換し、それがランタイムのどの関数にマッピングされるかという点にあります。

  1. マップ代入関数の分割 (sys.go, sysimport.c):

    • 以前はmapassign(hmap *map[any]any, any)という単一の関数だったものが、mapassign1(hmap *map[any]any, key any, val any)mapassign2(hmap *map[any]any, key any, val any, pres bool)に分割されました。
    • mapassign1は、単純なマップへの値の代入(例: m[key] = value)に対応します。
    • mapassign2は、マップへの値の代入と同時に、そのキーがマップに存在したかどうか(pres)を返すような、より複雑なシナリオ(Go言語の構文としては直接対応しないが、内部的な処理で必要となる場合がある)に対応するために導入された可能性があります。これは、マップの要素アクセスがvalue, ok := m[key]のように2つの戻り値を返すことと関連しているかもしれません。
    • sysimport.cでは、これらの新しい関数シグネチャに合わせて、sysパッケージの型定義が更新されています。これは、コンパイラがこれらの新しいランタイム関数を正しく認識し、型チェックを行うために不可欠です。
  2. walk.cにおけるマップ操作の変換ロジックの変更:

    • walktype関数内で、OINDEX(インデックスアクセス、例: m[key])の処理が大幅に書き換えられています。
    • 以前はisptrto(t, TMAP)でマップ型を識別し、mapop(n, top)を呼び出していましたが、新しいコードではswitch(t->etype)文が導入され、TMAPTSTRINGTARRAY/TDARRAY(動的配列)の各型に対して、より具体的な処理が記述されています。
    • TMAPの場合、キーの型チェックが強化され、OINDEXPTROINDEXに変換されるロジックが追加されています。これは、マップのインデックスアクセスがポインタ経由ではなく、直接的なマップ操作として扱われることを示唆しています。
    • mapop関数も大幅に拡張され、ONEW(マップの新規作成)、OINDEXPTR(マップの要素アクセス)、OAS(マップへの代入)の各操作に対応するコードが追加されています。
    • 特にOAS(代入)の場合、mapassign1mapassign2のどちらを呼び出すべきかを判断し、適切な引数を渡すロジックが実装されています。これにより、Goのソースコードにおけるマップ代入が、コンパイラによって適切なランタイム関数呼び出しに変換されるようになります。
    • algtype関数は、型のアルゴリズム(ハッシュ、比較など)を識別するための整数値を返します。このコミットでは、algtypeが返す値が変更されており、これはマップのキーや値の比較・ハッシュ処理の内部的な分類方法が調整されたことを意味します。
  3. 文字列比較関数の導入 (runtime/runtime.c, runtime/runtime.h):

    • runtime.ccmpstring(string s1, string s2)という新しいC言語関数が追加されました。この関数は2つの文字列を比較し、辞書順でs1 < s2なら-1、s1 > s2なら+1、等しいなら0を返します。
    • sys_cmpstring関数は、以前は文字列比較のロジックを直接含んでいましたが、このコミットでcmpstring関数を呼び出すように変更されました。これにより、文字列比較のロジックが共通化され、再利用性が向上します。
    • runtime.hにはcmpstring関数の宣言が追加され、他のランタイムコードから利用できるようになりました。
    • throw関数がstaticからvoidに変更されたのは、この関数が他のファイルからも呼び出される可能性があるため、リンケージを外部に公開する必要があったためと考えられます。

これらの変更は、Go言語のマップ実装が初期段階から成熟していく過程の一部であり、コンパイラとランタイムの連携を強化し、マップ操作の効率性と正確性を向上させるための重要なステップです。

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

src/cmd/gc/sys.go

--- a/src/cmd/gc/sys.go
+++ b/src/cmd/gc/sys.go
@@ -32,8 +32,8 @@ func	newmap(keysize uint32, valsize uint32,
 func	mapaccess1(hmap *map[any]any, key any) (val any);
 func	mapaccess2(hmap *map[any]any, key any) (val any, pres bool);
-func	mapdelete(hmap *map[any]any, key any);
-func	mapassign(hmap *map[any]any, any);
+func	mapassign1(hmap *map[any]any, key any, val any);
+func	mapassign2(hmap *map[any]any, key any, val any, pres bool);
 
 export
 	mal
@@ -64,7 +64,7 @@ export
 	newmap
 	mapaccess1
 	mapaccess2
-	mapdelete
-	mapassign
+	mapassign1
+	mapassign2
 
 	;

src/cmd/gc/walk.c

--- a/src/cmd/gc/walk.c
+++ b/src/cmd/gc/walk.c
@@ -442,41 +440,67 @@ print("%L walktype %O %d\n", n->op, top);
 	\twalktype(n->left, top);
 	\twalktype(n->right, Erv);
 
-\t\tullmancalc(n);\n
 	\tif(n->left == N || n->right == N)
 	\t\tgoto ret;
+\n
+\t\tdefaultlit(n->left);
 	\tt = n->left->type;
 	\tif(t == T)
 	\t\tgoto ret;
 
-\t\t// map\n
-\t\tif(isptrto(t, TMAP)) {\n
-\t\t\t*n = *mapop(n, top);\n
-\t\t\tgoto ret;\n+\t\t// left side is indirect\n+\t\tif(isptr[t->etype]) {\n+\t\t\tt = t->type;\n+\t\t\tn->op = OINDEXPTR;\n 	\t}\n 
-\t\t// right side must be an int\n-\t\tif(n->right->type == T)\n-\t\t\tconvlit(n->right, types[TINT32]);\n-\t\tif(n->left->type == T || n->right->type == T)\n-\t\t\tgoto ret;\n-\t\tif(!isint[n->right->type->etype])\n+\t\tswitch(t->etype) {\n+\t\tdefault:\n 	\t\tgoto badt;
+\n+\t\tcase TMAP:\n+\t\t\t// right side must map type\n+\t\t\tif(n->right->type == T) {\n+\t\t\t\tconvlit(n->right, t->down);\n+\t\t\t\tif(n->right->type == T)\n+\t\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tif(!eqtype(n->right->type, t->down, 0))\n+\t\t\t\tgoto badt;\n+\t\t\tif(n->op != OINDEXPTR)\n+\t\t\t\tgoto badt;\n+\t\t\tn->op = OINDEX;\n+\t\t\tn->type = t->type;\n+\t\t\tbreak;\n+\n+\t\tcase TSTRING:\n+\t\t\t// right side must be an int\n+\t\t\tif(top != Erv)\n+\t\t\t\tgoto nottop;\n+\t\t\tif(n->right->type == T) {\n+\t\t\t\tconvlit(n->right, types[TINT32]);\n+\t\t\t\tif(n->right->type == T)\n+\t\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tif(!isint[n->right->type->etype])\n+\t\t\t\tgoto badt;\n \t\t\t*n = *stringop(n, top);
-\t\t\tgoto ret;\n-\t\t}\n+\t\t\tbreak;\n+\t\t\t\n+\t\tcase TARRAY:\n+\t\tcase TDARRAY:\n+\t\t\t// right side must be an int\n+\t\t\tif(n->right->type == T) {\n+\t\t\t\tconvlit(n->right, types[TINT32]);\n+\t\t\t\tif(n->right->type == T)\n+\t\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tif(!isint[n->right->type->etype])\n+\t\t\t\tgoto badt;\n \n-\t\t// left side is array\n-\t\tif(isptr[t->etype]) {\n-\t\t\tt = t->type;\n-\t\t\tn->op = OINDEXPTR;\n+\t\t\tn->type = t->type;\n+\t\t\tbreak;\n 	\t}\n-\t\tif(t->etype != TARRAY && t->etype != TDARRAY)\n-\t\t\tgoto badt;\n-\t\tn->type = t->type;\n \t\tgoto ret;

src/runtime/runtime.c

--- a/src/runtime/runtime.c
+++ b/src/runtime/runtime.c
@@ -243,35 +267,7 @@ out:
 void
 sys_cmpstring(string s1, string s2, int32 v)
 {
-\tuint32 i, l;\n
-\tbyte c1, c2;\n
-\n
-\tl = s1->len;\n
-\tif(s2->len < l)\n
-\t\tl = s2->len;\n
-\tfor(i=0; i<l; i++) {\n
-\t\tc1 = s1->str[i];\n
-\t\tc2 = s2->str[i];\n
-\t\tif(c1 < c2) {\n
-\t\t\tv = -1;\n
-\t\t\tgoto out;\n
-\t\t}\n
-\t\tif(c1 > c2) {\n
-\t\t\tv = +1;\n
-\t\t\tgoto out;\n
-\t\t}\n
-\t}\n
-\tif(s1->len < s2->len) {\n
-\t\tv = -1;\n
-\t\tgoto out;\n
-\t}\n
-\tif(s1->len > s2->len) {\n
-\t\tv = +1;\n
-\t\tgoto out;\n
-\t}\n
-\tv = 0;\n
-\n-out:\n+\tv = cmpstring(s1, s2);\n \tFLUSH(&v);\n }

コアとなるコードの解説

src/cmd/gc/sys.go の変更

この変更は、Goコンパイラがランタイムのマップ操作関数をどのように認識するかを定義する部分です。

  • mapdeletemapassignという既存の関数定義が削除され、代わりにmapassign1mapassign2という新しい関数が追加されています。
  • mapassign1は、マップへの単純な値の代入(m[key] = value)に対応します。引数はマップ、キー、値です。
  • mapassign2は、より複雑な代入シナリオ、例えばキーの存在チェックを伴う代入(Go言語の構文では直接現れないが、内部的な処理で必要となる場合がある)に対応するために導入された可能性があります。引数はマップ、キー、値、そしてpres(存在するかどうかを示すブール値)です。 この変更により、コンパイラはマップへの代入操作を、そのコンテキストに応じてこれら2つの新しいランタイム関数のいずれかにマッピングするようになります。

src/cmd/gc/walk.c の変更

このファイルは、GoコンパイラのASTウォークフェーズにおける主要なロジックを含んでいます。

  • OINDEX (インデックスアクセス) の処理の再構築: 以前はisptrto(t, TMAP)でマップ型を識別していましたが、新しいコードではswitch(t->etype)文が導入され、TMAP(マップ)、TSTRING(文字列)、TARRAY/TDARRAY(配列/動的配列)の各型に対して、より明確で分離された処理が記述されています。
  • マップ型 (TMAP) の処理:
    • キーの型チェックが強化され、マップのキーと値の型が正しく一致しているかを確認します。
    • n->op = OINDEXPTR;という行は、インデックスアクセスがポインタ経由で行われることを示唆していますが、その後のn->op = OINDEX;への変更は、最終的にはより直接的なマップインデックス操作として扱われることを意味します。
  • mapop 関数の拡張:
    • mapop関数は、マップの作成 (ONEW)、要素アクセス (OINDEXPTR)、要素代入 (OAS) といったマップ関連の操作を、対応するランタイム関数呼び出しに変換する役割を担います。
    • 特にOAS(代入)の場合、mapassign1またはmapassign2のどちらのランタイム関数を呼び出すべきかを判断し、必要な引数(マップ、キー、値、場合によってはpresフラグ)を適切に構築して渡すロジックが追加されています。これにより、Goのソースコードで書かれたマップへの代入文が、コンパイラによって正確なランタイム関数呼び出しに変換されます。

src/runtime/runtime.c の変更

このファイルはGoランタイムのC言語実装です。

  • cmpstring 関数の導入:
    • cmpstring(string s1, string s2)という新しいC言語関数が追加されました。この関数は、2つの文字列s1s2をバイト単位で比較し、辞書順での大小関係に基づいて-1、0、+1を返します。これは、Goの文字列比較演算子(<, >, ==など)の基盤となる低レベルな実装です。
  • sys_cmpstring の変更:
    • 以前はsys_cmpstring関数内に直接文字列比較のロジックが記述されていましたが、この変更により、新しく導入されたcmpstring関数を呼び出すように簡素化されました。これにより、文字列比較のロジックがモジュール化され、ランタイム内で再利用可能になります。

これらの変更は、Go言語のマップと文字列の内部実装をより堅牢で効率的なものにするための重要なステップであり、コンパイラとランタイム間のインターフェースの進化を示しています。

関連リンク

参考にした情報源リンク

  • Go言語のソースコード(GitHubリポジトリ): https://github.com/golang/go
  • Go言語のコンパイラとランタイムの内部構造に関する一般的な知識。
  • Ullman数に関する情報(一般的なコンパイラ最適化の概念)。

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

このコミットは、Go言語のコンパイラ(gc)とランタイム(runtime)におけるマップ(ハッシュテーブル)の実装、および文字列比較の改善に焦点を当てています。具体的には、以下のファイルが変更されています。

  • src/cmd/6g/gen.c: コンパイラのコード生成フェーズに関連する微調整。
  • src/cmd/gc/sys.go: Goコンパイラがランタイム関数を呼び出すためのシステムコール定義。マップ操作関数のシグネチャが変更されています。
  • src/cmd/gc/sysimport.c: sys.goで定義されたシステムコールをコンパイラがインポートするためのC言語のソースファイル。型定義が更新されています。
  • src/cmd/gc/walk.c: コンパイラの「ウォーク」フェーズ、つまり抽象構文木(AST)を走査し、最適化やコード変換を行う部分。マップ操作の処理ロジックが大幅に変更されています。
  • src/runtime/runtime.c: GoランタイムのC言語実装。文字列比較関数が追加・変更されています。
  • src/runtime/runtime.h: Goランタイムのヘッダーファイル。新しい文字列比較関数の宣言が追加されています。

コミット

commit 4e8142c929bf285870aaa561d8bf47c94639b89b
Author: Ken Thompson <ken@golang.org>
Date:   Mon Jun 16 22:34:50 2008 -0700

    maps
    
    SVN=123089

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

https://github.com/golang/go/commit/4e8142c929bf285870aaa561d8bf47c94639b89b

元コミット内容

maps

変更の背景

このコミットの主な背景は、Go言語におけるマップ(ハッシュテーブル)の操作、特に要素の代入(mapassign)と削除(mapdelete)の内部的な処理を改善することにあります。初期のGo言語では、マップ操作は現在ほど洗練されておらず、コンパイラとランタイム間の連携も進化の途上にありました。

具体的には、マップへの値の代入において、キーが存在しない場合に新しいエントリを作成するのか、それとも既存のエントリを更新するのか、といったセマンティクスをより明確に、かつ効率的に扱う必要がありました。また、マップのキーや値の型に応じた適切なハッシュアルゴリズムや比較アルゴリズムを選択し、ランタイムに渡すための仕組みも整備する必要がありました。

mapassignmapassign1mapassign2に分割されたのは、Go言語のマップ代入が単なる値の代入だけでなく、value, ok := m[key]のような「存在チェック付き代入」のセマンティクスをサポートするためと考えられます。これにより、コンパイラは異なるシナリオに応じて適切なランタイム関数を呼び出すことができるようになります。

また、cmpstring関数の導入は、文字列の比較処理をランタイムレベルで効率的に行うための基盤を強化するものです。これはマップのキーとして文字列が使われる場合に、キーの比較性能に直接影響します。

前提知識の解説

Go言語のコンパイルプロセス(gc

Go言語の公式コンパイラであるgcは、複数のフェーズを経てソースコードを実行可能なバイナリに変換します。

  1. 字句解析と構文解析: ソースコードをトークンに分解し、抽象構文木(AST)を構築します。
  2. 型チェックとASTの変換(walkフェーズ): ASTを走査し、型チェックを行い、高レベルなGoの構文(例: forループ、map操作)を、より低レベルな中間表現(IR)に変換します。このフェーズで多くの最適化やセマンティックな変換が行われます。このコミットでsrc/cmd/gc/walk.cが大きく変更されているのは、このフェーズでマップ操作の変換ロジックが更新されたためです。
  3. SSA(Static Single Assignment)形式への変換と最適化: IRをSSA形式に変換し、さらに多くの最適化を適用します。
  4. コード生成: 最適化されたSSA形式から、ターゲットアーキテクチャの機械語コードを生成します。src/cmd/6g/gen.cはこのフェーズの一部です。

Goランタイム(runtime

Goランタイムは、Goプログラムの実行をサポートするC言語およびGo言語で書かれたライブラリです。ガベージコレクション、スケジューラ、マップやチャネルなどの組み込み型の実装、システムコールインターフェースなどが含まれます。コンパイラは、特定のGoの操作(例: マップの作成、アクセス、代入)を、ランタイムが提供するC言語関数への呼び出しに変換します。

Goのマップ(map

Goのマップはハッシュテーブルとして実装されており、キーと値のペアを格納します。マップの操作(作成、要素の追加/更新、要素の取得、要素の削除)は、コンパイラによってランタイム関数への呼び出しに変換されます。マップのキーは比較可能でなければならず、ハッシュ可能である必要があります。

sysパッケージとsysimport.c

Goコンパイラには、Go言語のソースコードからは直接アクセスできない、ランタイムが提供する低レベルな関数群を定義する「sys」パッケージという概念があります。src/cmd/gc/sys.goは、これらの関数のGo言語側のシグネチャを定義し、src/cmd/gc/sysimport.cは、これらの定義をコンパイラがC言語のコードとして利用できるようにするためのメカニズムを提供します。これにより、コンパイラはGoのソースコードを解析する際に、これらのランタイム関数の存在と型情報を認識できます。

ullmancalc

ullmancalcは、コンパイラの最適化フェーズで使用されるUllman数(Ullman number)を計算する関数です。Ullman数は、式の評価順序を決定し、レジスタ割り当てを最適化するために使用されるヒューリスティックな値です。このコミットでは、walk.c内でullmancalcの呼び出し位置が変更されており、これはマップ操作の変換ロジックの変更に伴う、式の評価順序の再調整を示唆しています。

技術的詳細

このコミットの核となる変更は、Goコンパイラがマップ操作をどのように中間表現に変換し、それがランタイムのどの関数にマッピングされるかという点にあります。

  1. マップ代入関数の分割 (sys.go, sysimport.c):

    • 以前はmapassign(hmap *map[any]any, any)という単一の関数だったものが、mapassign1(hmap *map[any]any, key any, val any)mapassign2(hmap *map[any]any, key any, val any, pres bool)に分割されました。
    • mapassign1は、単純なマップへの値の代入(例: m[key] = value)に対応します。
    • mapassign2は、マップへの値の代入と同時に、そのキーがマップに存在したかどうか(pres)を返すような、より複雑なシナリオ(Go言語の構文としては直接対応しないが、内部的な処理で必要となる場合がある)に対応するために導入された可能性があります。これは、マップの要素アクセスがvalue, ok := m[key]のように2つの戻り値を返すことと関連しているかもしれません。
    • sysimport.cでは、これらの新しい関数シグネチャに合わせて、sysパッケージの型定義が更新されています。これは、コンパイラがこれらの新しいランタイム関数を正しく認識し、型チェックを行うために不可欠です。
  2. walk.cにおけるマップ操作の変換ロジックの変更:

    • walktype関数内で、OINDEX(インデックスアクセス、例: m[key])の処理が大幅に書き換えられています。
    • 以前はisptrto(t, TMAP)でマップ型を識別し、mapop(n, top)を呼び出していましたが、新しいコードではswitch(t->etype)文が導入され、TMAPTSTRINGTARRAY/TDARRAY(動的配列)の各型に対して、より具体的な処理が記述されています。
    • TMAPの場合、キーの型チェックが強化され、OINDEXPTROINDEXに変換されるロジックが追加されています。これは、マップのインデックスアクセスがポインタ経由ではなく、直接的なマップ操作として扱われることを示唆しています。
    • mapop関数も大幅に拡張され、ONEW(マップの新規作成)、OINDEXPTR(マップの要素アクセス)、OAS(マップへの代入)の各操作に対応するコードが追加されています。
    • 特にOAS(代入)の場合、mapassign1mapassign2のどちらを呼び出すべきかを判断し、適切な引数を渡すロジックが実装されています。これにより、Goのソースコードにおけるマップ代入が、コンパイラによって適切なランタイム関数呼び出しに変換されるようになります。
    • algtype関数は、型のアルゴリズム(ハッシュ、比較など)を識別するための整数値を返します。このコミットでは、algtypeが返す値が変更されており、これはマップのキーや値の比較・ハッシュ処理の内部的な分類方法が調整されたことを意味します。
  3. 文字列比較関数の導入 (runtime/runtime.c, runtime/runtime.h):

    • runtime.ccmpstring(string s1, string s2)という新しいC言語関数が追加されました。この関数は2つの文字列を比較し、辞書順でs1 < s2なら-1、s1 > s2なら+1、等しいなら0を返します。
    • sys_cmpstring関数は、以前は文字列比較のロジックを直接含んでいましたが、このコミットでcmpstring関数を呼び出すように変更されました。これにより、文字列比較のロジックが共通化され、再利用性が向上します。
    • runtime.hにはcmpstring関数の宣言が追加され、他のランタイムコードから利用できるようになりました。
    • throw関数がstaticからvoidに変更されたのは、この関数が他のファイルからも呼び出される可能性があるため、リンケージを外部に公開する必要があったためと考えられます。

これらの変更は、Go言語のマップ実装が初期段階から成熟していく過程の一部であり、コンパイラとランタイムの連携を強化し、マップ操作の効率性と正確性を向上させるための重要なステップです。

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

src/cmd/gc/sys.go

--- a/src/cmd/gc/sys.go
+++ b/src/cmd/gc/sys.go
@@ -32,8 +32,8 @@ func	newmap(keysize uint32, valsize uint32,
 func	mapaccess1(hmap *map[any]any, key any) (val any);
 func	mapaccess2(hmap *map[any]any, key any) (val any, pres bool);
-func	mapdelete(hmap *map[any]any, key any);
-func	mapassign(hmap *map[any]any, any);
+func	mapassign1(hmap *map[any]any, key any, val any);
+func	mapassign2(hmap *map[any]any, key any, val any, pres bool);
 
 export
 	mal
@@ -64,7 +64,7 @@ export
 	newmap
 	mapaccess1
 	mapaccess2
-	mapdelete
-	mapassign
+	mapassign1
+	mapassign2
 
 	;

src/cmd/gc/walk.c

--- a/src/cmd/gc/walk.c
+++ b/src/cmd/gc/walk.c
@@ -442,41 +440,67 @@ print("%L walktype %O %d\n", n->op, top);
 	\twalktype(n->left, top);
 	\twalktype(n->right, Erv);
 
-\t\tullmancalc(n);\n
 	\tif(n->left == N || n->right == N)
 	\t\tgoto ret;
+\n
+\t\tdefaultlit(n->left);
 	\tt = n->left->type;
 	\tif(t == T)
 	\t\tgoto ret;
 
-\t\t// map\n
-\t\tif(isptrto(t, TMAP)) {\n
-\t\t\t*n = *mapop(n, top);\n
-\t\t\tgoto ret;\n+\t\t// left side is indirect\n+\t\tif(isptr[t->etype]) {\n+\t\t\tt = t->type;\n+\t\t\tn->op = OINDEXPTR;\n 	\t}\n 
-\t\t// right side must be an int\n-\t\tif(n->right->type == T)\n-\t\t\tconvlit(n->right, types[TINT32]);\n-\t\tif(n->left->type == T || n->right->type == T)\n-\t\t\tgoto ret;\n-\t\tif(!isint[n->right->type->etype])\n+\t\tswitch(t->etype) {\n+\t\tdefault:\n 	\t\tgoto badt;
+\n+\t\tcase TMAP:\n+\t\t\t// right side must map type\n+\t\t\tif(n->right->type == T) {\n+\t\t\t\tconvlit(n->right, t->down);\n+\t\t\t\tif(n->right->type == T)\n+\t\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tif(!eqtype(n->right->type, t->down, 0))\n+\t\t\t\tgoto badt;\n+\t\t\tif(n->op != OINDEXPTR)\n+\t\t\t\tgoto badt;\n+\t\t\tn->op = OINDEX;\n+\t\t\t\tn->type = t->type;\n+\t\t\tbreak;\n+\n+\t\tcase TSTRING:\n+\t\t\t// right side must be an int\n+\t\t\tif(top != Erv)\n+\t\t\t\tgoto nottop;\n+\t\t\tif(n->right->type == T) {\n+\t\t\t\tconvlit(n->right, types[TINT32]);\n+\t\t\t\tif(n->right->type == T)\n+\t\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tif(!isint[n->right->type->etype])\n+\t\t\t\tgoto badt;\n \t\t\t*n = *stringop(n, top);
-\t\t\tgoto ret;\n-\t\t}\n+\t\t\tbreak;\n+\t\t\t\n+\t\tcase TARRAY:\n+\t\tcase TDARRAY:\n+\t\t\t// right side must be an int\n+\t\t\tif(n->right->type == T) {\n+\t\t\t\tconvlit(n->right, types[TINT32]);\n+\t\t\t\tif(n->right->type == T)\n+\t\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tif(!isint[n->right->type->etype])\n+\t\t\t\tgoto badt;\n \n-\t\t// left side is array\n-\t\tif(isptr[t->etype]) {\n-\t\t\tt = t->type;\n-\t\t\tn->op = OINDEXPTR;\n+\t\t\tn->type = t->type;\n+\t\t\tbreak;\n 	\t}\n-\t\tif(t->etype != TARRAY && t->etype != TDARRAY)\n-\t\t\tgoto badt;\n-\t\tn->type = t->type;\n \t\tgoto ret;

src/runtime/runtime.c

--- a/src/runtime/runtime.c
+++ b/src/runtime/runtime.c
@@ -243,35 +267,7 @@ out:
 void
 sys_cmpstring(string s1, string s2, int32 v)
 {
-\tuint32 i, l;\n
-\tbyte c1, c2;\n
-\n
-\tl = s1->len;\n
-\tif(s2->len < l)\n
-\t\tl = s2->len;\n
-\tfor(i=0; i<l; i++) {\n
-\t\tc1 = s1->str[i];\n
-\t\tc2 = s2->str[i];\n
-\t\tif(c1 < c2) {\n
-\t\t\tv = -1;\n
-\t\t\tgoto out;\n
-\t\t}\n
-\t\tif(c1 > c2) {\n
-\t\t\tv = +1;\n
-\t\t\tgoto out;\n
-\t\t}\n
-\t}\n
-\tif(s1->len < s2->len) {\n
-\t\tv = -1;\n
-\t\tgoto out;\n
-\t}\n
-\tif(s1->len > s2->len) {\n
-\t\tv = +1;\n
-\t\tgoto out;\n
-\t}\n
-\tv = 0;\n
-\n-out:\n+\tv = cmpstring(s1, s2);\n \tFLUSH(&v);\n }

コアとなるコードの解説

src/cmd/gc/sys.go の変更

この変更は、Goコンパイラがランタイムのマップ操作関数をどのように認識するかを定義する部分です。

  • mapdeletemapassignという既存の関数定義が削除され、代わりにmapassign1mapassign2という新しい関数が追加されています。
  • mapassign1は、マップへの単純な値の代入(m[key] = value)に対応します。引数はマップ、キー、値です。
  • mapassign2は、より複雑な代入シナリオ、例えばキーの存在チェックを伴う代入(Go言語の構文では直接現れないが、内部的な処理で必要となる場合がある)に対応するために導入された可能性があります。引数はマップ、キー、値、そしてpres(存在するかどうかを示すブール値)です。 この変更により、コンパイラはマップへの代入操作を、そのコンテキストに応じてこれら2つの新しいランタイム関数のいずれかにマッピングするようになります。

src/cmd/gc/walk.c の変更

このファイルは、GoコンパイラのASTウォークフェーズにおける主要なロジックを含んでいます。

  • OINDEX (インデックスアクセス) の処理の再構築: 以前はisptrto(t, TMAP)でマップ型を識別していましたが、新しいコードではswitch(t->etype)文が導入され、TMAP(マップ)、TSTRING(文字列)、TARRAY/TDARRAY(配列/動的配列)の各型に対して、より明確で分離された処理が記述されています。
  • マップ型 (TMAP) の処理:
    • キーの型チェックが強化され、マップのキーと値の型が正しく一致しているかを確認します。
    • n->op = OINDEXPTR;という行は、インデックスアクセスがポインタ経由で行われることを示唆していますが、その後のn->op = OINDEX;への変更は、最終的にはより直接的なマップインデックス操作として扱われることを意味します。
  • mapop 関数の拡張:
    • mapop関数は、マップの作成 (ONEW)、要素アクセス (OINDEXPTR)、要素代入 (OAS) といったマップ関連の操作を、対応するランタイム関数呼び出しに変換する役割を担います。
    • 特にOAS(代入)の場合、mapassign1またはmapassign2のどちらのランタイム関数を呼び出すべきかを判断し、必要な引数(マップ、キー、値、場合によってはpresフラグ)を適切に構築して渡すロジックが追加されています。これにより、Goのソースコードで書かれたマップへの代入文が、コンパイラによって正確なランタイム関数呼び出しに変換されます。

src/runtime/runtime.c の変更

このファイルはGoランタイムのC言語実装です。

  • cmpstring 関数の導入:
    • cmpstring(string s1, string s2)という新しいC言語関数が追加されました。この関数は、2つの文字列s1s2をバイト単位で比較し、辞書順での大小関係に基づいて-1、0、+1を返します。これは、Goの文字列比較演算子(<, >, ==など)の基盤となる低レベルな実装です。
  • sys_cmpstring の変更:
    • 以前はsys_cmpstring関数内に直接文字列比較のロジックが記述されていましたが、この変更により、新しく導入されたcmpstring関数を呼び出すように簡素化されました。これにより、文字列比較のロジックがモジュール化され、ランタイム内で再利用可能になります。

これらの変更は、Go言語のマップと文字列の内部実装をより堅牢で効率的なものにするための重要なステップであり、コンパイラとランタイム間のインターフェースの進化を示しています。

関連リンク

参考にした情報源リンク

  • Go言語のソースコード(GitHubリポジトリ): https://github.com/golang/go
  • Go言語のコンパイラとランタイムの内部構造に関する一般的な知識。
  • Ullman数に関する情報(一般的なコンパイラ最適化の概念)。
  • Go maps are a fundamental data structure implemented as hash tables, providing efficient storage and retrieval of unordered key-value pairs.
  • Key details of their implementation include:
    • Underlying Structure Go maps are essentially a reference to a hash table. This hash table is composed of an array of "buckets."
    • Buckets and Entries Each bucket is designed to hold up to 8 key-value pairs.
    • Hashing and Collision Resolution When a key-value pair is added, a hash function generates a hash code for the key. The low-order bits of this hash determine which bucket the entry belongs to. To handle collisions (when multiple keys map to the same bucket), the bucket stores high-order bits of each hash to distinguish entries. If a bucket becomes full, "overflow buckets" are created and linked to the primary bucket to store additional entries.
    • Map Growth (Resizing) Go maps dynamically resize to maintain performance. When the number of entries relative to the number of buckets (known as the load factor, typically around 6.5) or the number of overflow buckets becomes too high, the map grows. This growth usually involves doubling the number of buckets and redistributing existing entries. This redistribution happens incrementally over time, not all at once, to avoid performance spikes. Recent Go versions (e.g., Go 1.24) have introduced optimizations inspired by Swiss Tables, where tables might split into two separate tables if capacity exceeds 1024 slots, further optimizing growth and distribution.
    • Internal Representation Internally, a Go map variable is a pointer to an hmap struct, which contains metadata about the map's state. For each unique map type declared in a program (e.g., map[string]int, map[string]http.Header), the Go compiler creates a maptype value. This maptype provides details about the key and element types, allowing the generic hmap implementation in the runtime to work efficiently across different map declarations.
    • Reference Type Behavior Maps in Go are reference types. When a map is passed to a function or assigned to another variable, a reference to the underlying hash table is shared. This means changes made through one reference will be reflected in others.
    • Key Requirements Keys in a Go map must be unique and of a "comparable" type. This includes basic types like int, float64, string, arrays, structs (if all their fields are comparable), and pointers. Types like slices, functions, or non-comparable arrays/structs cannot be used as map keys.
    • Unordered Iteration The order of elements when iterating over a Go map is not guaranteed and can vary.
    • Memory Management Go maps are designed with performance and memory efficiency in mind. They track whether keys and values can hold pointers, which helps optimize garbage collection. However, it's important to note that Go maps do not automatically shrink their allocated memory even after elements are deleted; they only grow.