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

このコミットは、Go言語のランタイムにおける文字列の等価性比較処理のパフォーマンスを大幅に改善することを目的としています。特に、文字列の長さが異なる場合、文字列のポインタが同一である場合、そして文字列の内容が完全に一致する場合の比較処理を最適化し、ベンチマークで最大85%以上の性能向上を達成しています。

コミット

commit 77f3e189d2bd4eb015235d200ca75803e45c87ef
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Sun Aug 5 21:35:41 2012 +0200

    runtime: faster string equality.
    
    benchmark                                old ns/op    new ns/op    delta
    BenchmarkCompareStringEqual                     51           35  -30.20%
    BenchmarkCompareStringIdentical                 51            7  -85.71%
    BenchmarkCompareStringSameLength                25           18  -28.29%
    BenchmarkCompareStringDifferentLength            2            2   +1.46%
    
    R=golang-dev, rsc
    CC=golang-dev, remy
    https://golang.org/cl/6450092

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

https://github.com/golang/go/commit/77f3e189d2bd4eb015235d200ca75803e45c87ef

元コミット内容

runtime: faster string equality.

benchmark                                old ns/op    new ns/op    delta
BenchmarkCompareStringEqual                     51           35  -30.20%
BenchmarkCompareStringIdentical                 51            7  -85.71%
BenchmarkCompareStringSameLength                25           18  -28.29%
BenchmarkCompareStringDifferentLength            2            2   +1.46%

R=golang-dev, rsc
CC=golang-dev, remy
https://golang.org/cl/6450092

変更の背景

Go言語において、文字列の比較は非常に頻繁に行われる操作です。特に、ハッシュマップのキーとして文字列を使用する場合や、大量の文字列データを処理するアプリケーションでは、文字列比較の性能が全体のパフォーマンスに大きく影響します。

このコミット以前のGoランタイムでは、文字列の等価性比較は、まず文字列の長さを比較し、次にバイト列を先頭から順に比較するという一般的なアプローチが取られていました。しかし、このアプローチにはいくつかの最適化の余地がありました。

同一文字列の比較: 同じ文字列リテラルや、同じ文字列変数を比較する場合、それらはメモリ上の同じアドレスを指している可能性があります。この場合、バイト列を比較するまでもなく、ポインタの同一性だけで等価性を判断できます。
長さが異なる文字列の比較: 長さが異なる文字列は、内容がどうであれ決して等しくありません。このチェックは非常に高速に行えるため、バイト列比較の前にこのチェックを行うことで、不要な処理をスキップできます。
コンパイラによる最適化の機会: コンパイラが文字列比較のパターンを認識し、より効率的なランタイム関数を呼び出すことで、生成されるコードの効率を向上させることができます。

これらの背景から、文字列比較のホットパスを特定し、より効率的なアルゴリズムとコンパイラのサポートを導入することで、Goプログラム全体の性能向上を図る必要がありました。

前提知識の解説

Go言語の文字列の内部表現

Go言語の文字列は、不変（immutable）なバイト列として扱われます。内部的には、文字列は以下の2つの要素で構成される構造体として表現されます。

ポインタ (pointer): 文字列のバイト列が格納されているメモリ上の先頭アドレスを指します。
長さ (length): 文字列のバイト長を示します。

この構造により、文字列のコピーはポインタと長さのコピーだけで済むため、非常に効率的です。また、文字列は不変であるため、複数の文字列変数が同じメモリ領域を共有しても安全です。

Goコンパイラ (`gc`) の役割

gcはGo言語の公式コンパイラです。Goのソースコードを機械語に変換する過程で、様々な最適化を行います。このコミットでは、gcが文字列の等価性比較演算子（==や!=）を、より最適化されたランタイム関数呼び出しに変換するよう変更されています。これにより、開発者が意識することなく、コンパイラが自動的に高性能な比較ロジックを適用できるようになります。

Goランタイムの役割

Goランタイムは、Goプログラムの実行をサポートする低レベルのコード群です。ガベージコレクション、スケジューリング、プリミティブ型の操作など、Goプログラムの基盤となる機能を提供します。文字列の比較のような基本的な操作も、ランタイム内の関数として実装されています。このコミットでは、ランタイム内の文字列比較関数が直接変更され、性能が向上しています。

文字列比較の基本的なアルゴリズム

一般的な文字列比較のアルゴリズムは以下のステップで行われます。

長さの比較: 2つの文字列の長さが異なる場合、それらは等しくないと判断されます。
バイト列の比較: 長さが同じ場合、文字列の先頭から1バイトずつ比較し、異なるバイトが見つかった時点で等しくないと判断されます。すべてのバイトが一致すれば、等しいと判断されます。

ベンチマークの読み方

Goのベンチマークは、go test -bench=. コマンドで実行され、関数の実行にかかる時間（ns/op - ナノ秒/操作）や、割り当てられたメモリ量（B/op - バイト/操作）、割り当て回数（allocs/op - 割り当て/操作）などを測定します。

old ns/op: 変更前の操作あたりの平均ナノ秒。
new ns/op: 変更後の操作あたりの平均ナノ秒。
delta: 性能変化の割合。負の値は性能向上を示します。

このコミットのベンチマーク結果は、特にBenchmarkCompareStringIdenticalで大幅な改善が見られ、同一文字列の比較が非常に高速になったことを示しています。

技術的詳細

このコミットの主要な技術的改善点は、Goコンパイラとランタイムが連携して文字列の等価性比較を最適化する新しいアプローチを導入したことです。

`eqstring`関数の導入と最適化ロジック

新しいランタイム関数 eqstring(s1 String, s2 String) (v bool) が src/pkg/runtime/string.goc に導入されました。この関数は、従来のバイト列比較の前に、以下の最適化ステップを実行します。

長さの比較:
```
if(s1.len != s2.len) {
    v = false;
    return;
}
```
これは最も基本的な最適化であり、長さが異なる文字列は決して等しくないため、すぐにfalseを返します。
ポインタの同一性チェック:
```
if(s1.str == s2.str) {
    v = true;
    return;
}
```
これはこのコミットの最も重要な最適化の一つです。もし2つの文字列がメモリ上の同じアドレスを指している場合（つまり、同じ文字列リテラルや、同じ文字列変数を参照している場合）、それらは内容も完全に同一であると保証されます。このチェックは非常に高速であり、バイト列比較のコストを完全に回避できます。
バイト列の比較: 上記の高速パスで結果が出なかった場合のみ、従来のバイト列比較が実行されます。
```
l = s1.len;
for(i=0; i<l; i++)
    if(s1.str[i] != s2.str[i]) {
        v = false;
        return;
    }
v = true;
```
このループは、文字列の長さ分だけバイトを比較し、異なるバイトが見つかればfalseを返し、最後まで一致すればtrueを返します。

コンパイラ (`gc`) による最適化された`eqstring`呼び出しへの変換

src/cmd/gc/walk.c は、Goコンパイラのセマンティック分析と中間コード生成を担当する部分です。このファイルへの変更により、コンパイラはGoソースコード内の文字列の等価性比較演算子（OEQ for ==, ONE for !=）を、新しく導入されたランタイム関数eqstringの呼び出しに変換するようになりました。

変更前は、文字列比較はcmpstring（文字列の辞書順比較を行う関数）を呼び出し、その結果と0を比較する形で行われていました。変更後は、eqstringを直接呼び出すようになり、さらに長さの比較を明示的に追加することで、より効率的なコードが生成されます。

特に注目すべきは、OEQ（等しい）とONE（等しくない）の扱いが異なる点です。

OEQ (s1 == s2): len(s1) == len(s2) && eqstring(s1, s2) と変換されます。これは、まず長さが等しいことを確認し、その後にeqstringを呼び出すという論理積（AND）の形式です。eqstring内部でも長さチェックは行われますが、コンパイラレベルで先に長さチェックを行うことで、より効率的なコード生成が可能になる場合があります。
ONE (s1 != s2): len(s1) != len(s2) || !eqstring(s1, s2) と変換されます。これは、長さが異なるか、またはeqstringの結果がfalseである場合にtrueを返すという論理和（OR）の形式です。

このコンパイラ側の変更により、Go開発者は特別なコードを書くことなく、文字列比較の性能向上を享受できるようになりました。

ランタイムの`strequal`におけるポインタ同一性チェックの追加

src/pkg/runtime/alg.c は、Goの型ごとの等価性比較ロジックを定義するファイルです。runtime·strequal関数は、Goの内部で文字列型の値の等価性をチェックするために使用されます。この関数にも、eqstringと同様にポインタの同一性チェックが追加されました。

if(((String*)a)->str == ((String*)b)->str) {
    *eq = true;
    return;
}

これにより、Goの内部的な文字列比較（例えば、マップのキー比較など）においても、同一ポインタの文字列は高速に等しいと判断されるようになりました。

ベンチマーク結果が示す性能向上

コミットメッセージに記載されているベンチマーク結果は、これらの最適化が実際に大きな効果をもたらしたことを明確に示しています。

BenchmarkCompareStringEqual: 内容が等しい異なる文字列の比較。30.20%の性能向上。これは主にeqstring内の長さチェックとバイト列比較の効率化によるものです。
BenchmarkCompareStringIdentical: ポインタが同一の文字列の比較。**85.71%**という驚異的な性能向上。これはeqstringおよびruntime·strequalに導入されたポインタ同一性チェックが直接的に寄与しています。
BenchmarkCompareStringSameLength: 長さが同じで内容が異なる文字列の比較。28.29%の性能向上。これもeqstring内のバイト列比較の効率化によるものです。
BenchmarkCompareStringDifferentLength: 長さが異なる文字列の比較。ほぼ変化なし（+1.46%）。これは、変更前も長さチェックが非常に高速であったため、これ以上の大きな改善の余地がなかったことを示しています。

これらの結果は、Goランタイムにおける文字列比較のホットパスが効果的に最適化されたことを裏付けています。

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

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

src/pkg/runtime/string.goc: 新しいランタイム関数 eqstring の実装。
src/cmd/gc/walk.c: コンパイラが文字列の等価性比較を eqstring の呼び出しに変換するロジックの変更。

`src/pkg/runtime/string.goc` の変更

--- a/src/pkg/runtime/string.goc
+++ b/src/pkg/runtime/string.goc
@@ -204,6 +204,26 @@ func cmpstring(s1 String, s2 String) (v int32) {
 	v = cmpstring(s1, s2);
 }
 
+func eqstring(s1 String, s2 String) (v bool) {
+	uint32 i, l;
+
+	if(s1.len != s2.len) {
+		v = false;
+		return;
+	}
+	if(s1.str == s2.str) {
+		v = true;
+		return;
+	}
+	l = s1.len;
+	for(i=0; i<l; i++)
+		if(s1.str[i] != s2.str[i]) {
+			v = false;
+			return;
+		}
+	v = true;
+}
+
 int32
 runtime·strcmp(byte *s1, byte *s2)
 {

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

--- a/src/cmd/gc/walk.c
+++ b/src/cmd/gc/walk.c
@@ -1021,27 +1021,34 @@ walkexpr(Node **np, NodeList **init)\n 		goto ret;\n 	}\n 
-		// prepare for rewrite below
 	if(n->etype == OEQ || n->etype == ONE) {
+			// prepare for rewrite below
 			n->left = cheapexpr(n->left, init);
 			n->right = cheapexpr(n->right, init);
-		}
 
-		// sys_cmpstring(s1, s2) :: 0
-		r = mkcall("cmpstring", types[TINT], init,
-			conv(n->left, types[TSTRING]),
-			conv(n->right, types[TSTRING]));
-		r = nod(n->etype, r, nodintconst(0));
+			r = mkcall("eqstring", types[TBOOL], init,
+				conv(n->left, types[TSTRING]),
+				conv(n->right, types[TSTRING]));
 
-		// quick check of len before full compare for == or !=
-		if(n->etype == OEQ || n->etype == ONE) {
-			if(n->etype == OEQ)
+			// quick check of len before full compare for == or !=
+			if(n->etype == OEQ) {
+				// len(left) == len(right) && eqstring(left, right)
 				r = nod(OANDAND, nod(OEQ, nod(OLEN, n->left, N), nod(OLEN, n->right, N)), r);\
-			else
+			} else {
+				// len(left) != len(right) || !eqstring(left, right)
+				r = nod(ONOT, r, N);
 				r = nod(OOROR, nod(ONE, nod(OLEN, n->left, N), nod(OLEN, n->right, N)), r);\
+			}
 			typecheck(&r, Erv);\n 			walkexpr(&r, nil);\n+		} else {
+			// sys_cmpstring(s1, s2) :: 0
+			r = mkcall("cmpstring", types[TINT], init,
+				conv(n->left, types[TSTRING]),
+				conv(n->right, types[TSTRING]));
+			r = nod(n->etype, r, nodintconst(0));
+		}
+
 		typecheck(&r, Erv);\n 		if(n->type->etype != TBOOL) fatal("cmp %T", n->type);\n 		r->type = n->type;\n```

## コアとなるコードの解説

### `src/pkg/runtime/string.goc` の `eqstring` 関数

この関数は、Goランタイムにおける文字列の等価性比較の新しい実装です。

*   `func eqstring(s1 String, s2 String) (v bool)`: 2つの`String`型の引数`s1`と`s2`を受け取り、それらが等しいかどうかを示す`bool`値を返します。
*   `if(s1.len != s2.len)`: 最初に文字列の長さを比較します。長さが異なる場合、文字列は等しくないため、即座に`false`を返して処理を終了します。これは非常に高速なチェックです。
*   `if(s1.str == s2.str)`: 次に、文字列の内部ポインタを比較します。もしポインタが同一であれば、それは同じメモリ上の文字列を指していることを意味するため、内容も完全に同一であると判断し、即座に`true`を返します。このチェックは、特に同じ文字列リテラルや、同じ文字列変数を繰り返し比較するシナリオで大きな性能向上をもたらします。
*   `for(i=0; i<l; i++) if(s1.str[i] != s2.str[i])`: 上記の高速パスで結果が出なかった場合のみ、文字列のバイト列を先頭から1バイトずつ比較します。異なるバイトが見つかった時点で`false`を返します。
*   `v = true;`: ループが最後まで実行され、すべてのバイトが一致した場合、文字列は等しいと判断され`true`を返します。

この`eqstring`関数は、最も頻繁に発生するケース（長さが異なる、またはポインタが同一）を優先的に処理することで、全体的な文字列比較の性能を向上させています。

### `src/cmd/gc/walk.c` の文字列比較変換ロジック

この部分の変更は、Goコンパイラがソースコード内の`==`や`!=`といった文字列比較演算子を、ランタイムの`eqstring`関数呼び出しにどのように変換するかを定義しています。

*   `if(n->etype == OEQ || n->etype == ONE)`: 現在処理しているノードが文字列の等価性比較（`==`または`!=`）であるかをチェックします。
*   `n->left = cheapexpr(n->left, init); n->right = cheapexpr(n->right, init);`: 比較対象の左右のオペランドを評価し、必要に応じて一時変数に格納するなどして、後続の処理で効率的に利用できるようにします。
*   `r = mkcall("eqstring", types[TBOOL], init, conv(n->left, types[TSTRING]), conv(n->right, types[TSTRING]));`: ここが重要な変更点です。従来の`cmpstring`の呼び出しに代わり、新しく導入された`eqstring`関数を呼び出す中間コードを生成します。`eqstring`は`bool`型を返すため、`types[TBOOL]`が指定されています。
*   **`OEQ` (`==`) の場合**:
    `r = nod(OANDAND, nod(OEQ, nod(OLEN, n->left, N), nod(OLEN, n->right, N)), r);`
    これは、`len(left) == len(right) && eqstring(left, right)`という論理式を構築しています。コンパイラが明示的に長さの比較を追加することで、ランタイムの`eqstring`が呼び出される前に、Goのコードレベルで長さが異なるケースを排除できる可能性があり、さらなる最適化の機会を提供します。
*   **`ONE` (`!=`) の場合**:
    `r = nod(ONOT, r, N); r = nod(OOROR, nod(ONE, nod(OLEN, n->left, N), nod(OLEN, n->right, N)), r);`
    これは、`len(left) != len(right) || !eqstring(left, right)`という論理式を構築しています。`OEQ`の場合と同様に、コンパイラが長さの比較を先行させることで、効率的なコード生成を促します。
*   `typecheck(&r, Erv); walkexpr(&r, nil);`: 生成された中間コードの型チェックと、さらなる最適化のためのウォーク処理を行います。

このコンパイラ側の変更により、Goのソースコードで`s1 == s2`と書かれた場合でも、内部的にはこれらの最適化されたランタイム関数呼び出しと論理式に変換され、高性能な文字列比較が実現されます。

## 関連リンク

*   Go CL (Change List) 6450092: [https://golang.org/cl/6450092](https://golang.org/cl/6450092)

## 参考にした情報源リンク

*   Go言語の公式ドキュメント (文字列の内部表現、コンパイラ、ランタイムに関する一般的な情報)
*   Go言語のソースコード (特に `src/pkg/runtime/string.goc`, `src/cmd/gc/walk.c`, `src/pkg/runtime/alg.c` の関連部分)
*   Go言語のベンチマークに関する一般的な情報

Keyboard shortcuts

comemo