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

このコミットは、Goランタイムにおける文字列比較関数 eqstring の実装を、GoのCライクなコード (string.goc) から各アーキテクチャ固有のアセンブリ言語 (asm_386.s, asm_amd64.s, asm_amd64p32.s, asm_arm.s) へと移行するものです。これにより、文字列比較のパフォーマンスが大幅に向上しています。

コミット

commit b36ed9056ff57c04c34240f2dc6b1bb59e84d0c7
Author: Keith Randall <khr@golang.org>
Date:   Mon Jun 16 21:00:37 2014 -0700

    runtime: implement eqstring in assembly.
    
    BenchmarkCompareStringEqual               10.4          7.33          -29.52%
    BenchmarkCompareStringIdentical           3.99          3.67          -8.02%
    BenchmarkCompareStringSameLength          9.80          6.84          -30.20%
    BenchmarkCompareStringDifferentLength     1.09          0.95          -12.84%
    BenchmarkCompareStringBigUnaligned        75220         76071         +1.13%
    BenchmarkCompareStringBig                 69843         74746         +7.02%
    
    LGTM=bradfitz, josharian
    R=golang-codereviews, bradfitz, josharian, dave, khr
    CC=golang-codereviews
    https://golang.org/cl/105280044

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

https://github.com/golang/go/commit/b36ed9056ff57c04c34240f2dc6b1bb59e84d0c7

元コミット内容

Goランタイムの文字列比較関数 eqstring をアセンブリで実装。

ベンチマーク結果は以下の通り：

• BenchmarkCompareStringEqual: 29.52%改善
• BenchmarkCompareStringIdentical: 8.02%改善
• BenchmarkCompareStringSameLength: 30.20%改善
• BenchmarkCompareStringDifferentLength: 12.84%改善
• BenchmarkCompareStringBigUnaligned: 1.13%悪化
• BenchmarkCompareStringBig: 7.02%悪化

（注：BenchmarkCompareStringBigUnaligned と BenchmarkCompareStringBig の悪化は、このコミットの直接的な影響というよりは、測定誤差や他の要因によるものか、あるいは特定のケースでのアセンブリ実装のオーバーヘッドを示唆している可能性があります。しかし、全体としては大幅な改善が見られます。）

変更の背景

Go言語のランタイムは、プログラムの実行効率に直結する重要な部分です。文字列の比較は、プログラム内で頻繁に行われる操作の一つであり、その性能はアプリケーション全体のパフォーマンスに大きな影響を与えます。特に、Goの文字列は不変であり、内部的にはポインタと長さのペアとして表現されます。文字列の比較は、まず長さが同じであるかを確認し、次に内容がバイト単位で一致するかを確認するという手順を踏みます。

このコミットの背景には、Goランタイムの主要な性能ボトルネックを特定し、最適化するという継続的な取り組みがあります。eqstring のような基本的な操作であっても、それが非常に頻繁に呼び出される場合、わずかな性能改善でも全体として大きな効果をもたらします。アセンブリ言語での実装は、コンパイラが生成するコードよりもさらに低レベルで、特定のCPUアーキテクチャの特性を最大限に活用できるため、究極の性能最適化手段として用いられます。

この変更は、Go 1.3リリースサイクルの一部として行われました。Go 1.3では、ランタイムのパフォーマンス改善、特にガベージコレクションのレイテンシ削減と全体的な実行速度の向上が主要な目標の一つでした。文字列操作の最適化もその一環として位置づけられます。

前提知識の解説

Go言語の文字列 (string)

Go言語の文字列は、バイトの不変シーケンスです。内部的には、文字列はデータへのポインタと文字列の長さ（バイト数）の2つの要素で構成される構造体として表現されます。

type StringHeader struct {
	Data uintptr // 文字列データの先頭へのポインタ
	Len  int     // 文字列の長さ（バイト数）
}

この構造により、文字列のコピーはポインタと長さのコピーだけで済むため、効率的です。

文字列の比較 (== 演算子)

Go言語において、2つの文字列 s1 と s2 を s1 == s2 で比較する場合、ランタイムは以下のロジックで等価性を判断します。

1. 長さの比較: まず、len(s1) と len(s2) が等しいかを確認します。長さが異なる場合、文字列は等しくないと判断されます。
2. ポインタの比較: 長さが同じ場合、次に文字列データへのポインタ (s1.Data と s2.Data) が同じであるかを確認します。もしポインタが同じであれば、それは同じメモリ領域を指していることを意味するため、文字列は等しいと判断されます。これは、文字列リテラルや、同じ文字列を指す変数が複数ある場合に発生しうる最適化パスです。
3. バイト内容の比較: 長さが同じで、かつポインタが異なる場合、ランタイムは文字列のバイト内容を先頭から順に比較します。すべてのバイトが一致すれば文字列は等しいと判断され、途中で不一致が見つかれば等しくないと判断されます。

このコミットで最適化される eqstring は、主に3番目の「バイト内容の比較」のパスを担当するランタイム関数です。

アセンブリ言語

アセンブリ言語は、特定のCPUアーキテクチャの機械語命令と1対1に対応する低レベルのプログラミング言語です。アセンブリ言語でコードを記述することで、プログラマはCPUのレジスタ、メモリ、命令セットを直接制御し、コンパイラが生成するコードよりもさらに最適化された、高速なコードを作成することが可能です。Goランタイムのような性能が重視される部分では、クリティカルなパスでアセンブリが使用されることがあります。

runtime·memeq

runtime·memeq は、Goランタイム内部で使用されるメモリ領域のバイト比較関数です。これは、指定された2つのメモリ領域が、指定された長さの範囲でバイト単位で等しいかどうかを効率的にチェックします。eqstring が文字列のバイト内容を比較する際に、この runtime·memeq を利用していました。

技術的詳細

このコミットの主要な技術的変更は、Goランタイムの文字列比較ロジックを、GoのCライクなコードから各CPUアーキテクチャ向けのアセンブリ言語に移植した点です。

変更前は、src/pkg/runtime/string.goc に eqstring 関数がGoのCライクな構文で記述されていました。この関数は、文字列の長さが異なる場合は false を返し、ポインタが同じ場合は true を返し、それ以外の場合は runtime·memeq を呼び出してバイト内容を比較していました。

変更後、eqstring 関数は src/pkg/runtime/asm_386.s, src/pkg/runtime/asm_amd64.s, src/pkg/runtime/asm_amd64p32.s, src/pkg/runtime/asm_arm.s といった各アーキテクチャのアセンブリファイルに実装されました。これにより、文字列比較のロジックがCPUのネイティブ命令に直接マッピングされ、より効率的な実行が可能になります。

アセンブリ実装の主な最適化ポイントは以下の通りです。

1. レジスタの効率的な利用: アセンブリでは、関数呼び出しのオーバーヘッドを最小限に抑えつつ、CPUのレジスタを最大限に活用してデータを操作できます。これにより、メモリへのアクセス回数を減らし、処理速度を向上させます。
2. 条件分岐の最適化: 文字列の長さ比較やポインタ比較といった初期のチェックを、アセンブリの条件分岐命令（JNE, JEQ など）で直接、かつ高速に実行します。
3. インライン化の促進: eqstring のような小さな関数をアセンブリで実装することで、コンパイラが呼び出し元でそのコードをインライン展開しやすくなり、関数呼び出しのオーバーヘッドを完全に排除できる可能性があります。
4. memeqbody の活用: 多くのアーキテクチャのアセンブリコードでは、文字列のバイト内容比較のために既存の runtime·memeqbody （runtime·memeq の本体部分）を呼び出しています。これは、メモリ比較の最適化されたアセンブリルーチンを再利用することで、コードの重複を避けつつ高性能を維持しています。
5. ARMアーキテクチャ固有の最適化: ARM版のアセンブリコードでは、ループ内でバイトを比較し、不一致があればすぐにリターンするロジックが直接記述されています。これは、ARMの命令セットの特性を活かした効率的な実装です。

ベンチマーク結果が示すように、特に文字列の長さが同じで内容が異なる場合や、完全に一致する場合の比較において、大幅な性能改善が達成されています。これは、アセンブリ実装がこれらの一般的なケースでCPUのパイプラインをより効率的に利用できるようになったためと考えられます。

また、この変更に伴い、src/pkg/runtime/runtime_test.go に eqstring_generic というGo言語で書かれた汎用的な文字列比較関数と、それをテストする TestEqString が追加されています。これは、アセンブリで実装された eqstring が、Go言語のセマンティクスに沿って正しく動作することを検証するためのリファレンス実装およびテストケースとして機能します。

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

src/pkg/runtime/asm_386.s, src/pkg/runtime/asm_amd64.s, src/pkg/runtime/asm_amd64p32.s (x86系アーキテクチャ)

これらのファイルに runtime·eqstring のアセンブリ実装が追加されています。基本的なロジックは共通しています。

// eqstring tests whether two strings are equal.
// See runtime_test.go:eqstring_generic for
// equivlaent Go code.
TEXT runtime·eqstring(SB),NOSPLIT,$0-XX // XXはアーキテクチャによって異なるスタックフレームサイズ
	MOVL/MOVQ	s1len+Y(FP), AX // s1の長さをAXレジスタにロード
	MOVL/MOVQ	s2len+Z(FP), BX // s2の長さをBXレジスタにロード
	CMPL/CMPQ	AX, BX          // 長さを比較
	JNE	different               // 長さが異なればdifferentへジャンプ
	MOVL/MOVQ	s1str+A(FP), SI // s1のポインタをSIレジスタにロード
	MOVL/MOVQ	s2str+B(FP), DI // s2のポインタをDIレジスタにロード
	CMPL/CMPQ	SI, DI          // ポインタを比較
	JEQ	same                    // ポインタが同じであればsameへジャンプ
	CALL	runtime·memeqbody(SB)   // バイト内容を比較するためにmemeqbodyを呼び出し
	MOVB	AX, v+C(FP)             // memeqbodyの結果を戻り値に設定
	RET
same:
	MOVB	$1, v+C(FP)             // trueを戻り値に設定
	RET
different:
	MOVB	$0, v+C(FP)             // falseを戻り値に設定
	RET

（Y, Z, A, B, C はアーキテクチャとスタックフレームのレイアウトによって異なるオフセットです。）

src/pkg/runtime/asm_arm.s (ARMアーキテクチャ)

ARM版も同様に runtime·eqstring のアセンブリ実装が追加されていますが、命令セットが異なるため、x86系とは異なるアセンブリ命令が使用されています。

// eqstring tests whether two strings are equal.
// See runtime_test.go:eqstring_generic for
// equivlaent Go code.
TEXT runtime·eqstring(SB),NOSPLIT,$-4-17
	MOVW	s1len+4(FP), R0 // s1の長さをR0レジスタにロード
	MOVW	s2len+12(FP), R1 // s2の長さをR1レジスタにロード
	MOVW	$0, R7          // R7を0に初期化 (false用)
	CMP	R0, R1          // 長さを比較
	MOVB.NE R7, v+16(FP)    // 長さが異なればR7 (false) を戻り値に設定
	RET.NE                  // 長さが異なればリターン
	MOVW	s1str+0(FP), R2 // s1のポインタをR2レジスタにロード
	MOVW	s2str+8(FP), R3 // s2のポインタをR3レジスタにロード
	MOVW	$1, R8          // R8を1に初期化 (true用)
	MOVB	R8, v+16(FP)    // R8 (true) を戻り値に設定
	CMP	R2, R3          // ポインタを比較
	RET.EQ                  // ポインタが同じであればリターン
	ADD	R2, R0, R6      // R6 = s1のポインタ + 長さ (比較終了アドレス)
_eqnext:
	CMP	R2, R6          // 現在のポインタが終了アドレスに達したか比較
	RET.EQ                  // 達していればリターン (すべて一致)
	MOVBU.P	1(R2), R4       // s1から1バイト読み込み、ポインタをインクリメント
	MOVBU.P	1(R3), R5       // s2から1バイト読み込み、ポインタをインクリメント
	CMP	R4, R5          // 読み込んだバイトを比較
	BEQ	_eqnext         // 一致すれば次のバイトへ
	MOVB	R7, v+16(FP)    // 不一致であればR7 (false) を戻り値に設定
	RET

src/pkg/runtime/runtime_test.go

eqstring_generic 関数と TestEqString テストが追加されています。

func eqstring_generic(s1, s2 string) bool {
	if len(s1) != len(s2) {
		return false
	}
	// optimization in assembly versions:
	// if s1.str == s2.str { return true } // アセンブリ版での最適化パスのコメント
	for i := 0; i < len(s1); i++ {
		if s1[i] != s2[i] {
			return false
		}
	}
	return true
}

func TestEqString(t *testing.T) {
	// This isn't really an exhaustive test of eqstring, it's
	// just a convenient way of documenting (via eqstring_generic)
	// what eqstring does.
	s := []string{
		"",
		"a",
		"c",
		"aaa",
		"ccc",
		"cccc"[:3], // same contents, different string
		"1234567890",
	}
	for _, s1 := range s {
		for _, s2 := range s2 {
			x := s1 == s2 // Goの組み込み文字列比較
			y := eqstring_generic(s1, s2) // 汎用Go実装
			if x != y {
				t.Errorf(`eqstring("%s","%s") = %t, want %t`, s1, s2, x, y)
			}
		}
	}
}

src/pkg/runtime/string.goc

既存の eqstring 関数が削除されています。

--- a/src/pkg/runtime/string.goc
+++ b/src/pkg/runtime/string.goc
@@ -206,18 +206,6 @@ func concatstrings(s Slice) (res String) {
  res = concatstring(s.len, (String*)s.array);
 }
 
-func eqstring(s1 String, s2 String) (v bool) {
- if(s1.len != s2.len) {
-  v = false;
-  return;
- }
- if(s1.str == s2.str) {
-  v = true;
-  return;
- }
- v = runtime·memeq(s1.str, s2.str, s1.len);
-}
-
 int32
 runtime·strcmp(byte *s1, byte *s2)
 {

コアとなるコードの解説

このコミットの核となる変更は、eqstring 関数の実装がGoのCライクなコードからアセンブリ言語に移行されたことです。

アセンブリ実装の共通ロジック（x86系およびARM）:

1. 引数の取得: 関数呼び出し規約に従って、スタックフレームから2つの文字列の長さとポインタを取得します。Goの文字列は (ポインタ, 長さ) のペアとして渡されます。
2. 長さの比較: まず、2つの文字列の長さが等しいかを比較します。
   • 長さが異なる場合、文字列は等しくないため、すぐに false を返して終了します。これは最も高速なパスです。
3. ポインタの比較: 長さが同じ場合、次に文字列データへのポインタが等しいかを比較します。
   • ポインタが同じ場合、それは同じメモリ領域を指していることを意味するため、文字列は等しいと判断し、すぐに true を返して終了します。これも非常に高速な最適化パスです。
4. バイト内容の比較: 長さが同じで、かつポインタが異なる場合、文字列の実際のバイト内容を比較する必要があります。
   • x86系アーキテクチャでは、既存の最適化されたメモリ比較ルーチンである runtime·memeqbody を呼び出します。これは、大量のバイトを効率的に比較するために、CPUのSIMD命令（SSEなど）や高速なループアンローリングなどを利用している可能性があります。
   • ARMアーキテクチャでは、ループ内でバイトを1つずつ読み込み、比較するロジックが直接アセンブリで記述されています。不一致が見つかればすぐに false を返し、最後まで一致すれば true を返します。

runtime_test.go の追加: eqstring_generic は、Go言語で書かれた eqstring の論理的に等価な実装です。これは、アセンブリで実装された eqstring が、Goの文字列比較のセマンティクス（長さ比較、ポインタ比較、バイト内容比較）を正確に満たしていることを検証するための「ゴールデンリファレンス」として機能します。TestEqString は、様々な文字列の組み合わせに対して、Goの組み込み == 演算子と eqstring_generic の結果が一致するかをテストすることで、間接的にアセンブリ実装の正しさを検証しています。

この変更により、Goプログラム内で頻繁に発生する文字列比較操作が、よりCPUに近いレベルで最適化され、全体的な実行速度の向上が図られました。特に、短い文字列や、長さが異なる文字列の比較において、アセンブリによる高速なパスが効果を発揮しています。

関連リンク

• Go言語の文字列型に関する公式ドキュメント: https://go.dev/blog/strings
• Go 1.3 リリースノート (ランタイムの改善について言及): https://go.dev/doc/go1.3
• Goのランタイムアセンブリに関する一般的な情報: https://go.dev/src/runtime/README.md

参考にした情報源リンク

• Goのソースコード (特に src/pkg/runtime/ ディレクトリ内のファイル)
• Goの公式ブログ
• GoのGitHubリポジトリのコミット履歴
• GoのIssueトラッカー (関連するパフォーマンス改善の議論)
• アセンブリ言語およびCPUアーキテクチャに関する一般的な知識
• Goの文字列内部表現に関する技術記事
• Goのベンチマークに関する情報