[インデックス 10651] ファイルの概要
このコミットは、Go言語の標準ライブラリ bytes パッケージにおける Count、Index、Equal の各関数のパフォーマンスを向上させることを目的としています。特に、Equal 関数にはアセンブリ言語による最適化が導入され、Count および Index 関数には、一般的なケース（"easy" case）での検索効率を大幅に向上させるためのアルゴリズム変更が加えられました。これにより、特定の操作において顕著な速度向上が見られます。
コミット
commit 9b875bc037407b47c4922871390fbae8e3f16592
Author: Russ Cox <rsc@golang.org>
Date: Wed Dec 7 15:09:56 2011 -0500
bytes: faster Count, Index, Equal
Benchmarks are from GOARCH=amd64 on a MacPro5,1.
benchmark old MB/s new MB/s speedup
bytes_test.BenchmarkEqual32 452.89 891.07 1.97x
bytes_test.BenchmarkEqual4K 852.71 1700.44 1.99x
bytes_test.BenchmarkEqual4M 841.53 1587.93 1.89x
bytes_test.BenchmarkEqual64M 838.22 1578.14 1.88x
bytes_test.BenchmarkIndex32 58.02 48.99 0.84x
bytes_test.BenchmarkIndex4K 48.26 41.32 0.86x
bytes_test.BenchmarkIndex4M 48.20 41.24 0.86x
bytes_test.BenchmarkIndex64M 48.08 41.21 0.86x
bytes_test.BenchmarkIndexEasy32 410.04 546.82 1.33x
bytes_test.BenchmarkIndexEasy4K 849.26 14257.37 16.79x
bytes_test.BenchmarkIndexEasy4M 854.54 17222.15 20.15x
bytes_test.BenchmarkIndexEasy64M 843.57 11060.40 13.11x
bytes_test.BenchmarkCount32 57.24 50.68 0.89x
bytes_test.BenchmarkCount4K 48.19 41.82 0.87x
bytes_test.BenchmarkCount4M 48.18 41.74 0.87x
bytes_test.BenchmarkCount64M 48.17 41.71 0.87x
bytes_test.BenchmarkCountEasy32 433.11 547.44 1.26x
bytes_test.BenchmarkCountEasy4K 1130.59 14194.06 12.55x
bytes_test.BenchmarkCountEasy4M 1131.23 17231.18 15.23x
bytes_test.BenchmarkCountEasy64M 1111.40 11068.88 9.96x
The non-easy Count/Index benchmarks are a worst case input.
regexp.BenchmarkMatchEasy0_32 237.46 221.47 0.93x
regexp.BenchmarkMatchEasy0_1K 553.53 1019.72 1.84x
regexp.BenchmarkMatchEasy0_32K 693.99 1672.06 2.41x
regexp.BenchmarkMatchEasy0_1M 688.72 1611.68 2.34x
regexp.BenchmarkMatchEasy0_32M 680.70 1565.05 2.30x
regexp.BenchmarkMatchEasy1_32 165.56 243.08 1.47x
regexp.BenchmarkMatchEasy1_1K 336.45 496.32 1.48x
regexp.BenchmarkMatchEasy1_32K 302.80 425.63 1.41x
regexp.BenchmarkMatchEasy1_1M 300.42 414.20 1.38x
regexp.BenchmarkMatchEasy1_32M 299.64 413.47 1.38x
R=golang-dev, r, iant
CC=golang-dev
https://golang.org/cl/5451116
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/9b875bc037407b47c4922871390fbae8e3f16592
元コミット内容
bytes パッケージの Count、Index、Equal 関数を高速化するコミット。ベンチマーク結果が示されており、Equal は約2倍、Index と Count の「イージーケース」は約10倍から20倍の速度向上を達成しています。一方で、「ノンイージーケース」（ワーストケース入力）ではわずかな速度低下が見られます。また、regexp パッケージのベンチマークも改善されています。
変更の背景
Go言語の標準ライブラリは、そのパフォーマンスが非常に重要視されています。特に bytes パッケージは、文字列やバイトスライスを扱う多くのアプリケーションで頻繁に使用されるため、これらの基本操作の効率はシステム全体のパフォーマンスに大きな影響を与えます。
このコミットの背景には、bytes.Equal、bytes.Index、bytes.Count といった基本的なバイトスライス操作の実行速度をさらに向上させたいという明確な意図がありました。ベンチマーク結果が示すように、既存の実装ではまだ最適化の余地があり、特に大量のデータを扱う場合や、これらの関数が頻繁に呼び出されるシナリオにおいて、パフォーマンスのボトルネックとなる可能性がありました。
Equal 関数については、Go言語のポータブルな実装（Goで書かれたコード）に加えて、特定のアーキテクチャ（x86/amd64）向けにアセンブリ言語による最適化を導入することで、CPUの低レベルな命令を活用し、比較処理を極限まで高速化することが目指されました。
Index および Count 関数については、一般的な使用パターン（例えば、検索対象のバイトスライスが比較的短かったり、検索パターンがスライス内に早期に見つかる場合）において、より効率的なアルゴリズムを導入することで、大幅な速度向上を図ることが目的でした。同時に、ワーストケース（検索パターンがスライス内に存在しない、または非常に遅く見つかる場合）でのパフォーマンスへの影響も考慮し、全体的なバランスを取る必要がありました。
これらの最適化は、Go言語で書かれたアプリケーションが、より高速に、より少ないリソースで動作することを可能にし、特にネットワークプログラミング、データ処理、テキスト処理など、バイトスライス操作が中心となる分野でのGoの競争力を高めることに貢献します。
前提知識の解説
このコミットを理解するためには、以下の技術的な概念について基本的な知識があると役立ちます。
-
Go言語の
bytesパッケージ:- Go言語の標準ライブラリの一部で、バイトスライス（
[]byte）を操作するためのユーティリティ関数を提供します。 Equal(a, b []byte) bool: 2つのバイトスライスが等しいかどうかを比較します。Index(s, sep []byte) int:sの中でsepが最初に出現するインデックスを返します。見つからない場合は -1 を返します。Count(s, sep []byte) int:sの中でsepが重複せずに何回出現するかを数えます。IndexByte(s []byte, c byte) int:sの中でバイトcが最初に出現するインデックスを返します。
- Go言語の標準ライブラリの一部で、バイトスライス（
-
アセンブリ言語 (Assembly Language):
- CPUが直接実行できる機械語命令を、人間が読み書きしやすいようにニーモニック（記号）で表現した低レベルプログラミング言語です。
- 特定のCPUアーキテクチャ（例: x86, AMD64, ARM）に特化しており、ハードウェアの機能を最大限に引き出すために使用されます。
- Go言語では、パフォーマンスがクリティカルな部分（例: ランタイム、標準ライブラリの特定の関数）でアセンブリ言語が使用されることがあります。
-
x86/AMD64 アーキテクチャと
REP CMPSB命令:- IntelおよびAMDのCPUで広く使われている命令セットアーキテクチャです。
CMPSB(Compare String Byte):DS:SIが指すバイトとES:DIが指すバイトを比較し、フラグレジスタを更新します。ポインタは自動的にインクリメント/デクリメントされます。REP(Repeat Prefix):CMPSBなどの文字列操作命令の前に付けるプレフィックスで、CXレジスタが0になるまで命令を繰り返します。これにより、ループ処理をCPUレベルで非常に高速に実行できます。REP CMPSBは、メモリブロックの比較（memcmpに相当）に非常に効率的です。
-
Go言語のベンチマーク:
- Go言語には、コードのパフォーマンスを測定するための組み込みのベンチマーク機能があります。
go test -bench=.コマンドで実行され、関数の実行時間やメモリ割り当てなどを測定し、スループット（MB/s）などの指標で結果を表示します。- ベンチマーク名に
Easyが付いているものは、一般的な、または最適化が効きやすい入力パターンを指し、そうでないものはワーストケースやより複雑な入力パターンを指すことが多いです。
-
ポータブルな実装とアセンブリ実装:
- Go言語のコードは、異なるCPUアーキテクチャやOSで動作するように設計されています（ポータブル）。
- しかし、特定のアーキテクチャでは、Goで書かれたポータブルなコードよりも、そのアーキテクチャに特化したアセンブリ言語で書かれたコードの方がはるかに高速に動作する場合があります。
- このコミットでは、
Equal関数に対して、Goで書かれたequalPortableと、x86/amd64向けのアセンブリ実装が共存する形になっています。Goのコンパイラは、実行環境に応じて最適な実装を選択します。
これらの知識は、コミットがなぜ、どのようにパフォーマンスを向上させたのかを深く理解する上で不可欠です。
技術的詳細
このコミットにおけるパフォーマンス向上は、主に以下の2つのアプローチによって実現されています。
-
bytes.Equalのアセンブリ言語による最適化:- x86 (386) および AMD64 アーキテクチャ:
src/pkg/bytes/asm_386.sとsrc/pkg/bytes/asm_amd64.sに、Equal関数のアセンブリ実装が追加されました。 - この実装の核となるのは、
REP; CMPSB命令の使用です。REP(Repeat) プレフィックスは、続く命令をCXレジスタがゼロになるまで繰り返すことをCPUに指示します。CMPSB(Compare String Byte) 命令は、DS:SI（ソース）とES:DI（デスティネーション）が指すメモリ位置のバイトを比較し、結果に応じてCPUのフラグレジスタ（特にZF: Zero Flag）を設定します。比較後、SIとDIレジスタは自動的にインクリメント（またはデクリメント）されます。
Equal関数は、まず2つのバイトスライスの長さが異なる場合はfalseを返します。長さが同じ場合、REP; CMPSBを使用してバイトスライス全体を一度に比較します。この命令は、ループのオーバーヘッドをCPU内部で処理するため、GoのループやC言語のmemcmpよりもさらに高速なバイト比較を可能にします。- ベンチマーク結果 (
BenchmarkEqual*) は、このアセンブリ最適化により約1.9倍の速度向上を達成していることを明確に示しています。これは、CPUのネイティブな文字列比較命令を直接利用することの強力な効果です。 - ARM アーキテクチャ:
src/pkg/bytes/asm_arm.sでは、Equal関数がequalPortable（Goで書かれたポータブルな実装）に分岐するように変更されています。これは、当時のARMアーキテクチャにはx86/amd64のような効率的なmemcmpに相当するアセンブリ命令がまだ利用できなかったか、実装が複雑であったためと考えられます。したがって、ARM環境ではEqualのアセンブリ最適化は適用されず、Goのポータブルな実装が使用されます。
- x86 (386) および AMD64 アーキテクチャ:
-
bytes.Countおよびbytes.Indexのアルゴリズム改善:src/pkg/bytes/bytes.go内のCountとIndex関数が書き直されました。- 「イージーケース」の最適化: 以前の実装では、検索パターン (
sep) の最初のバイトが見つかるたびに、Equal関数を呼び出して完全なパターンマッチングを行っていました。新しい実装では、IndexByte関数（単一バイトの検索に特化しており、通常は非常に高速）を積極的に利用します。Index関数では、まずsepの最初のバイト (c) をIndexByteで検索します。これにより、sepの最初のバイトが見つかるまで、多くの不要な比較をスキップできます。Count関数でも同様に、IndexByteを使ってsepの最初のバイトを効率的に探し、その位置から完全なパターンマッチングを試みます。- このアプローチにより、検索パターンが頻繁に出現しない場合や、検索対象のデータが非常に大きい場合でも、
IndexByteが高速に次の検索開始位置を見つけるため、大幅なパフォーマンス向上が期待できます。
- ベンチマーク結果の解釈:
BenchmarkIndexEasy*およびBenchmarkCountEasy*のベンチマークでは、約10倍から20倍という驚異的な速度向上が見られます。これは、上記IndexByteを活用したスキップ戦略が、検索パターンが比較的早期に見つかる「イージーケース」において非常に効果的であることを示しています。- 一方で、
BenchmarkIndex*およびBenchmarkCount*（「ノンイージーケース」またはワーストケース）では、わずかな速度低下が見られます。これは、検索パターンが全く見つからない場合や、部分的なマッチングが頻繁に発生するようなワーストケースでは、IndexByteによるスキップがほとんど機能せず、むしろIndexByteの呼び出しオーバーヘッドが加わるためと考えられます。しかし、このわずかな低下は、「イージーケース」での大幅な向上によって十分に相殺されると判断されたのでしょう。
sepの長さが1の場合の最適化:Index関数では、sepの長さが1の場合にIndexByteを直接呼び出すように最適化されています。これは、単一バイトの検索が最も一般的なケースの一つであり、これに特化した高速パスを提供するためです。
これらの変更は、Go言語の bytes パッケージが提供する基本的な操作の効率を大幅に向上させ、Goで開発されるアプリケーションの全体的なパフォーマンスに貢献します。特に、Equal のアセンブリ最適化は、低レベルなメモリ操作のパフォーマンスを追求するGoの哲学を体現しています。
コアとなるコードの変更箇所
このコミットで変更された主要なファイルと関数は以下の通りです。
src/pkg/bytes/asm_386.s:TEXT ·Equal(SB):Equal関数の 32-bit x86 アセンブリ実装が追加されました。
src/pkg/bytes/asm_amd64.s:TEXT ·Equal(SB):Equal関数の 64-bit AMD64 アセンブリ実装が追加されました。
src/pkg/bytes/asm_arm.s:TEXT ·Equal(SB): ARM アーキテクチャ向けにequalPortable（Goで書かれた実装）に分岐するスタブが追加されました。
src/pkg/bytes/bytes.go:func Equal(a, b []byte) bool: 宣言が変更され、実際のGo実装はequalPortableに移動しました。Equalは外部（アセンブリ）実装を呼び出すようになりました。func equalPortable(a, b []byte) bool: 以前のEqualのGo実装がこの関数にリネームされました。func Count(s, sep []byte) int: アルゴリズムが大幅に書き直され、IndexByteを活用したスキップロジックが導入されました。func Index(s, sep []byte) int: アルゴリズムが大幅に書き直され、IndexByteを活用したスキップロジックと、sepの長さが1の場合の最適化が導入されました。
src/pkg/bytes/bytes_test.go:TestCompare:EqualPortableのテストが追加されました。BenchmarkIndexByte*:IndexByteのベンチマークが追加・修正されました。BenchmarkEqual*,BenchmarkEqualPort*:EqualとEqualPortableのベンチマークが追加されました。BenchmarkIndex*,BenchmarkIndexEasy*:Indexのベンチマークが追加・修正されました。BenchmarkCount*,BenchmarkCountEasy*:Countのベンチマークが追加されました。bmIndexByte,bmEqual,bmIndex,bmIndexEasy,bmCount,bmCountEasy: 新しいベンチマークヘルパー関数が追加されました。
src/pkg/bytes/export_test.go:var EqualPortable = equalPortable:equalPortable関数がテストのためにエクスポートされました。
コアとなるコードの解説
bytes.Equal のアセンブリ実装 (asm_amd64.s の例)
TEXT ·Equal(SB),7,$0
MOVL len+8(FP), BX // len (aの長さ) を BX にロード
MOVL len1+24(FP), CX // len1 (bの長さ) を CX にロード
MOVL $0, AX // AX を 0 に初期化 (戻り値 false)
MOVL $1, DX // DX を 1 に初期化 (戻り値 true)
CMPL BX, CX // a と b の長さを比較
JNE eqret // 長さが異なれば eqret へジャンプ (false を返す)
MOVQ p+0(FP), SI // p (aのポインタ) を SI にロード
MOVQ q+16(FP), DI // q (bのポインタ) を DI にロード
CLD // 方向フラグをクリア (SI/DI をインクリメント方向にする)
REP; CMPSB // SI と DI が指すバイトを CX 回比較
CMOVLEQ DX, AX // 比較結果が等しければ (ZF=1)、AX に DX (1) を移動 (true を返す)
eqret:
MOVB AX, ret+32(FP) // AX の下位バイトを戻り値に設定
RET // 関数から戻る
このアセンブリコードは、bytes.Equal 関数がどのように高速化されたかを示しています。
- まず、2つのバイトスライスの長さが比較されます。長さが異なる場合、即座に
falseが返されます。 - 長さが同じ場合、
REP; CMPSB命令が使用されます。これは、SIレジスタが指すメモリ（スライスaの開始アドレス）とDIレジスタが指すメモリ（スライスbの開始アドレス）を、CXレジスタに格納された長さの分だけバイト単位で比較します。 REP; CMPSBは、比較中に不一致が見つかった場合、またはすべてのバイトが比較された場合に停止します。- 比較が完了した後、
CMOVLEQ DX, AX命令は、比較結果が等しい（Zero Flagがセットされている）場合にのみAXレジスタに1（trueを意味する）を移動させます。それ以外の場合はAXは0のままです。 - 最終的に
AXの値が関数の戻り値として設定されます。
この REP; CMPSB 命令は、CPUが内部的に最適化されたループでバイト比較を実行するため、GoやCで書かれた同等のループよりもはるかに高速です。
bytes.Count のGo実装 (bytes.go の変更点)
func Count(s, sep []byte) int {
n := len(sep)
if n == 0 {
return utf8.RuneCount(s) + 1
}
if n > len(s) {
return 0
}
count := 0
c := sep[0] // 検索パターンの最初のバイト
i := 0
t := s[:len(s)-n+1] // 検索範囲を限定
for i < len(t) {
if t[i] != c { // 最初のバイトが一致しない場合
o := IndexByte(t[i:], c) // IndexByteで次の出現位置を高速検索
if o < 0 {
break // 見つからなければ終了
}
i += o // 見つかった位置までスキップ
}
// 最初のバイトが一致した、またはスキップしてきた場合
if n == 1 || Equal(s[i:i+n], sep) { // sepの長さが1か、完全一致の場合
count++
i += n // sepの長さ分だけ進む
continue
}
i++ // 一致しない場合は1バイト進む
}
return count
}
新しい Count 関数は、検索パターン sep の最初のバイト c を利用して、効率的に検索位置をスキップする戦略を採用しています。
sepの長さが0の場合（空のパターンを数える場合）は、UTF-8ルーンの数に1を加えたものを返します。sepの長さがsより長い場合は、0を返します。- メインのループでは、現在の位置
iのバイトがsepの最初のバイトcと異なる場合、IndexByte(t[i:], c)を呼び出して、cが次に出現する位置までiを一気に進めます。これにより、多くの不要なバイト比較をスキップできます。 cが見つかった、または現在の位置がcと一致する場合、sepの長さが1であれば即座にカウントし、そうでなければEqual(s[i:i+n], sep)で完全なパターンマッチングを行います。- マッチした場合、
countをインクリメントし、sepの長さ分だけiを進めて次の検索を開始します。 - マッチしなかった場合、
iを1バイトだけ進めて次のループを続けます。
この「IndexByte を使ったスキップ」戦略が、「イージーケース」での大幅な速度向上に貢献しています。
bytes.Index のGo実装 (bytes.go の変更点)
func Index(s, sep []byte) int {
n := len(sep)
if n == 0 {
return 0
}
if n > len(s) {
return -1
}
c := sep[0]
if n == 1 { // sepの長さが1の場合の最適化
return IndexByte(s, c)
}
i := 0
t := s[:len(s)-n+1]
for i < len(t) {
if t[i] != c { // 最初のバイトが一致しない場合
o := IndexByte(t[i:], c) // IndexByteで次の出現位置を高速検索
if o < 0 {
break // 見つからなければ終了
}
i += o // 見つかった位置までスキップ
}
// 最初のバイトが一致した、またはスキップしてきた場合
if Equal(s[i:i+n], sep) { // 完全一致の場合
return i // 見つかったインデックスを返す
}
i++ // 一致しない場合は1バイト進む
}
return -1 // 見つからなかった
}
Index 関数も Count 関数と同様に、IndexByte を活用したスキップ戦略を採用しています。
sepの長さが0の場合、0を返します。sepの長さがsより長い場合、-1を返します。- 重要な最適化:
sepの長さが1の場合、IndexByte(s, c)を直接呼び出します。これは、単一バイトの検索が非常に一般的であり、これに特化した高速パスを提供するためです。 - メインのループでは、
Countと同様に、sepの最初のバイトcをIndexByteで効率的に検索し、その位置までスキップします。 cが見つかった場合、Equal(s[i:i+n], sep)で完全なパターンマッチングを行います。- マッチした場合、現在のインデックス
iを返して終了します。 - マッチしなかった場合、
iを1バイトだけ進めて次のループを続けます。 - ループが終了しても見つからなければ、-1を返します。
これらの変更により、bytes パッケージの主要な文字列/バイトスライス操作が、特に一般的なシナリオにおいて大幅に高速化されました。
関連リンク
- Go言語の公式ドキュメント: https://golang.org/pkg/bytes/
- このコミットが属するGoの変更リスト (CL): https://golang.org/cl/5451116
参考にした情報源リンク
- Go言語のソースコード (特に
src/pkg/bytesディレクトリ) - x86/AMD64 アセンブリ命令セットリファレンス (例: Intel Software Developer's Manuals)
- Go言語のベンチマークに関するドキュメント
bytes.Equalのアセンブリ実装に関する議論 (GoコミュニティのメーリングリストやIssueトラッカー)