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

このコミットは、Go言語の標準ライブラリにおけるハッシュ関数のメモリ割り当て効率を改善し、全体的なパフォーマンスを向上させることを目的としています。特に、Sum メソッドにおけるバイト列の追加処理を最適化し、ベンチマークコードをより正確な測定ができるように修正しています。

コミット

commit 9feddd0bae188825e01771d182b84e47b159aa30
Author: Pascal S. de Kloe <pascal@quies.net>
Date:   Tue Apr 10 15:15:39 2012 -0400

    hash: more efficient memory allocation
    
    Feed append the complete content at once.
    
    BenchmarkAdler32KB       1000000              2534 ns/op         404.05 MB/s
    BenchmarkCrc32KB          500000              4757 ns/op         215.26 MB/s
    BenchmarkCrc64KB          500000              4769 ns/op         214.70 MB/s
    BenchmarkFnv32KB         1000000              2417 ns/op         423.64 MB/s
    BenchmarkFnv32aKB        1000000              2408 ns/op         425.23 MB/s
    BenchmarkFnv64KB          500000              4262 ns/op         240.21 MB/s
    BenchmarkFnv64aKB         500000              4234 ns/op         241.83 MB/s
    
    R=iant, rsc, r, minux.ma
    CC=golang-dev
    https://golang.org/cl/5937053

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

https://github.com/golang/go/commit/9feddd0bae188825e01771d182b84e47b159aa30

元コミット内容

コミットメッセージは「hash: more efficient memory allocation」（ハッシュ：より効率的なメモリ割り当て）と簡潔に述べられています。具体的な変更内容は「Feed append the complete content at once.」（完全な内容を一度にappendに渡す）と説明されており、これがメモリ割り当ての効率化に繋がっていることが示唆されています。

ベンチマーク結果も含まれており、Adler32、CRC32、CRC64、FNV32、FNV64といった様々なハッシュアルゴリズムにおいて、処理速度（MB/s）が向上していることが示されています。これは、変更が実際にパフォーマンス改善に寄与していることを裏付けています。

変更の背景

Go言語のハッシュ関数は、入力データからハッシュ値を計算する際に、最終的なハッシュ値をバイト列として返す Sum メソッドを持っています。従来の Sum メソッドの実装では、ハッシュ値を構成する各バイトを append 関数を使って個別に既存のバイトスライスに追加していました。

Goの append 関数は、スライスの容量が不足した場合に新しいメモリを割り当ててスライスを拡張します。各バイトを個別に append すると、スライスの容量が何度も不足し、そのたびにメモリの再割り当てとデータのコピーが発生する可能性があります。これは、特にハッシュ値が複数のバイトで構成される場合に、不要なオーバーヘッドとなり、パフォーマンスの低下を招きます。

このコミットの背景には、この非効率なメモリ割り当てを解消し、ハッシュ計算の最終段階におけるパフォーマンスを向上させるという目的があります。

前提知識の解説

Go言語のスライスとappend関数

Go言語のスライスは、可変長シーケンスを表現するための強力なデータ構造です。スライスは内部的に配列へのポインタ、長さ（len）、容量（cap）を持っています。

append関数は、スライスに要素を追加するために使用されます。appendの動作は以下のようになります。

1. 容量の確認: appendはまず、既存のスライスの容量が新しい要素を追加するのに十分であるかを確認します。
2. 十分な容量がある場合: 新しい要素は既存の基底配列の末尾に追加され、スライスの長さが更新されます。メモリの再割り当ては発生しません。
3. 容量が不足する場合: appendは新しい基底配列を割り当て、既存の要素と新しい要素をその新しい配列にコピーします。この際、新しい容量は通常、元の容量の2倍（またはそれ以上）に設定され、将来の追加に備えます。このメモリの再割り当てとコピーの操作は、パフォーマンスに大きな影響を与える可能性があります。

可変引数（Variadic Functions）

Go言語では、関数が不定数の引数を受け取ることができる「可変引数」の機能があります。これは、引数リストの最後のパラメータの型に ... を付けることで実現されます。例えば、func foo(args ...int) のように定義された関数は、foo(1, 2, 3) のように複数の整数を引数として受け取ることができます。

append関数も可変引数を受け入れるように設計されており、append(slice, elem1, elem2, ...) のように複数の要素を一度に追加することができます。これにより、一度の append 呼び出しで複数の要素を追加する場合、Goランタイムは必要なメモリを一度に割り当てることができ、複数回の再割り当てを避けることができます。

ハッシュ関数とベンチマーク

ハッシュ関数は、任意のサイズの入力データから固定サイズの出力（ハッシュ値）を生成するアルゴリズムです。データの一貫性チェック、データ構造（ハッシュテーブル）の構築、暗号化など、様々な用途で利用されます。

ベンチマークは、プログラムの性能を測定するためのテストです。Go言語の testing パッケージには、ベンチマークテストを記述するための機能が組み込まれています。Benchmark 関数は *testing.B 型の引数を受け取り、b.N 回のループでテスト対象のコードを実行します。b.SetBytes は、ベンチマークが処理するバイト数を指定し、ns/op（操作あたりのナノ秒）や MB/s（秒あたりのメガバイト）などの指標を計算するのに役立ちます。b.ResetTimer() は、セットアップコードの時間を測定から除外するために使用されます。

技術的詳細

このコミットの主要な技術的変更点は、ハッシュ関数の Sum メソッドにおけるバイト列の追加方法の変更と、ベンチマークコードの改善です。

Sum メソッドの最適化

変更前は、Sum メソッド内でハッシュ値を構成する各バイト（例: s>>24, s>>16, s>>8, s）を append 関数を使って個別に in スライスに追加していました。

// 変更前 (例: Adler32のSumメソッド)
func (d *digest) Sum(in []byte) []byte {
	s := d.Sum32()
	in = append(in, byte(s>>24))
	in = append(in, byte(s>>16))
	in = append(in, byte(s>>8))
	in = append(in, byte(s))
	return in
}

このコードでは、appendが4回呼び出されています。もし in スライスの容量が各 append 呼び出しのたびに不足した場合、最大で4回のメモリ再割り当てとデータコピーが発生する可能性があります。

変更後は、Goの append 関数の可変引数機能を活用し、ハッシュ値を構成するすべてのバイトを一度の append 呼び出しで追加するように修正されました。

// 変更後 (例: Adler32のSumメソッド)
func (d *digest) Sum(in []byte) []byte {
	s := d.Sum32()
	return append(in, byte(s>>24), byte(s>>16), byte(s>>8), byte(s))
}

この変更により、appendは一度だけ呼び出され、必要なメモリ割り当て（もし必要であれば）も一度だけ行われます。これにより、メモリ再割り当ての回数が劇的に減少し、特に頻繁にハッシュ計算が行われるようなシナリオでのパフォーマンスが向上します。

ベンチマークコードの改善

ベンチマークコードも、より正確な測定ができるように修正されています。

変更前は、ベンチマークのセットアップで bytes.Buffer を使用したり、b.StopTimer() と b.StartTimer() を使って測定範囲を調整していました。また、Sum(nil) を呼び出していました。

// 変更前 (例: Adler32のBenchmarkGolden)
func BenchmarkGolden(b *testing.B) {
	b.StopTimer()
	c := New()
	var buf bytes.Buffer
	for _, g := range golden {
		buf.Write([]byte(g.in))
	}
	b.StartTimer()
	for i := 0; i < b.N; i++ {
		c.Write(buf.Bytes())
	}
}

変更後は、以下の点が改善されています。

1. b.SetBytes(1024): ベンチマークが1024バイトのデータを処理することを示すように設定されました。これにより、MB/s の計算がより正確になります。
2. 固定サイズの入力データ: data := make([]byte, 1024) で1KBの固定サイズのバイトスライスが作成され、ベンチマークの各イテレーションで同じデータが使用されるようになりました。
3. Sum メソッドの引数の最適化: in := make([]byte, 0, h.Size()) を使用して、Sum メソッドに渡すスライス in を事前に容量を確保した状態で作成しています。これにより、Sum メソッド内で append が呼び出される際に、ベンチマークループ内でメモリの再割り当てが発生するのを防ぎ、Sum メソッド自体の純粋なパフォーマンスを測定できるようになります。
4. h.Reset() の呼び出し: 各イテレーションの前にハッシュインスタンスをリセットすることで、前のイテレーションの状態が次のイテレーションに影響を与えないようにしています。
5. b.ResetTimer() の使用: b.StopTimer() と b.StartTimer() の代わりに b.ResetTimer() を使用することで、ベンチマークのセットアップにかかる時間を測定から除外する、より標準的で推奨される方法が採用されています。

これらのベンチマークの改善により、Sum メソッドの最適化による実際のパフォーマンス向上をより正確に測定できるようになりました。

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

このコミットでは、主に以下のファイルの Sum メソッドとベンチマークテストが変更されています。

• src/pkg/hash/adler32/adler32.go
• src/pkg/hash/adler32/adler32_test.go
• src/pkg/hash/crc32/crc32.go
• src/pkg/hash/crc32/crc32_test.go
• src/pkg/hash/crc64/crc64.go
• src/pkg/hash/crc64/crc64_test.go
• src/pkg/hash/fnv/fnv.go
• src/pkg/hash/fnv/fnv_test.go

src/pkg/hash/adler32/adler32.go の変更例

--- a/src/pkg/hash/adler32/adler32.go
+++ b/src/pkg/hash/adler32/adler32.go
@@ -75,11 +75,7 @@ func (d *digest) Sum32() uint32 { return finish(d.a, d.b) }
 
 func (d *digest) Sum(in []byte) []byte {
 	s := d.Sum32()
-	in = append(in, byte(s>>24))
-	in = append(in, byte(s>>16))
-	in = append(in, byte(s>>8))
-	in = append(in, byte(s))
-	return in
+	return append(in, byte(s>>24), byte(s>>16), byte(s>>8), byte(s))
 }
 
 // Checksum returns the Adler-32 checksum of data.

src/pkg/hash/adler32/adler32_test.go の変更例

--- a/src/pkg/hash/adler32/adler32_test.go
+++ b/src/pkg/hash/adler32/adler32_test.go
@@ -5,7 +5,6 @@
 package adler32
 
 import (
-	"bytes"
 	"io"
 	"testing"
 )
@@ -63,15 +62,19 @@ func TestGolden(t *testing.T) {
 	}
 }
 
-func BenchmarkGolden(b *testing.B) {
-	b.StopTimer()
-	c := New()
-	var buf bytes.Buffer
-	for _, g := range golden {
-		buf.Write([]byte(g.in))
+func BenchmarkAdler32KB(b *testing.B) {
+	b.SetBytes(1024)
+	data := make([]byte, 1024)
+	for i := range data {
+		data[i] = byte(i)
 	}
-	b.StartTimer()
+	h := New()
+	in := make([]byte, 0, h.Size())
+
+	b.ResetTimer()
 	for i := 0; i < b.N; i++ {
-		c.Write(buf.Bytes())
+		h.Reset()
+		h.Write(data)
+		h.Sum(in)
 	}
 }

同様の変更が、crc32, crc64, fnv パッケージの Sum メソッドとベンチマークテストにも適用されています。

コアとなるコードの解説

Sum メソッドの変更

Sum メソッドの変更は、Go言語の append 関数の特性を最大限に活用したものです。

• 変更前: in = append(in, byte(s>>X)) の形式で、ハッシュ値の各バイトを個別に in スライスに追加していました。これは、append が呼び出されるたびにスライスの容量チェックと、必要に応じたメモリ再割り当て・データコピーが発生する可能性がありました。特に、ハッシュ値が4バイト（uint32）や8バイト（uint64）の場合、それぞれ4回または8回の append 呼び出しが発生し、非効率でした。
• 変更後: return append(in, byte(s>>24), byte(s>>16), byte(s>>8), byte(s)) のように、ハッシュ値を構成するすべてのバイトを可変引数として一度の append 呼び出しに渡しています。これにより、Goランタイムは必要な最終的な容量を一度に計算し、もしメモリ再割り当てが必要であれば、それを一度だけ実行します。これにより、複数回のメモリ再割り当てとデータコピーのオーバーヘッドが削減され、パフォーマンスが向上します。

ベンチマークコードの変更

ベンチマークコードの変更は、測定の正確性を高めるためのものです。

• b.SetBytes(1024): ベンチマークが1024バイトのデータを処理することを明示的に宣言することで、MB/s の計算がより意味のあるものになります。
• data := make([]byte, 1024): 固定サイズの入力データを使用することで、ベンチマークの各実行が同じ条件で行われることを保証します。
• in := make([]byte, 0, h.Size()): Sum メソッドに渡すスライス in を事前に容量を確保して作成することで、Sum メソッド内部での append 呼び出しによるメモリ再割り当てがベンチマークの測定対象から除外されます。これにより、ハッシュ計算自体のパフォーマンスがより純粋に測定されます。もしこの最適化がなければ、Sum メソッド内の append がベンチマークループ内で毎回メモリを再割り当てすることになり、そのオーバーヘッドが測定結果に大きく影響してしまいます。
• h.Reset(): 各ベンチマークイテレーションの開始時にハッシュインスタンスをリセットすることで、前のイテレーションの状態が次のイテレーションに影響を与えないようにし、独立した測定を保証します。
• b.ResetTimer(): ベンチマークのセットアップコード（データの準備など）の時間を測定から除外するために使用されます。これにより、純粋なハッシュ計算の実行時間のみが測定されます。

これらの変更により、ベンチマーク結果はより信頼性が高く、Sum メソッドの最適化が実際にパフォーマンスに与える影響を正確に反映するようになりました。

関連リンク

• Go言語の append 関数に関する公式ドキュメントやチュートリアル
• Go言語の testing パッケージに関する公式ドキュメント
• Go言語のハッシュパッケージに関する公式ドキュメント

参考にした情報源リンク

• Go言語の公式ドキュメント: https://golang.org/doc/
• Go言語の bytes パッケージ: https://pkg.go.dev/bytes
• Go言語の hash パッケージ: https://pkg.go.dev/hash
• Go言語の testing パッケージ: https://pkg.go.dev/testing
• Go言語の append 関数に関する解説記事 (例: A Tour of Go - Slices): https://go.dev/tour/moretypes/13
• Go言語のベンチマークに関する解説記事 (例: Go by Example: Benchmarking): https://gobyexample.com/benchmarking