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

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

このコミットは、Go言語のランタイムにおけるマップ（map）のイテレーション（rangeループ）に関するパフォーマンス改善を目的としています。具体的には、空のマップをイテレートする際の処理を高速化しています。

変更されたファイルは以下の2つです。

  • src/pkg/runtime/hashmap.c: Goランタイムにおけるハッシュマップの実装に関連するC言語のソースファイルです。マップの初期化やイテレーションのロジックが含まれています。このコミットでは、マップイテレータの初期化関数に条件分岐が追加されています。
  • src/pkg/runtime/mapspeed_test.go: Goランタイムのマップのパフォーマンスを測定するためのベンチマークテストファイルです。このコミットでは、マップのイテレーションに関する新しいベンチマークテストが追加されています。

コミット

このコミットは、Goランタイムにおいて空のマップに対するrangeループのパフォーマンスを向上させます。ベンチマーク結果によると、空のマップのイテレーションが約79%高速化されています。

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

https://github.com/golang/go/commit/7b9df092618d593e29ff8e7a509a5ad110431439

元コミット内容

commit 7b9df092618d593e29ff8e7a509a5ad110431439
Author: Frederick Kelly Mayle III <frederickmayle@gmail.com>
Date:   Thu May 23 14:17:52 2013 -0700

    runtime: faster range on empty map
    
    benchmark                old ns/op    new ns/op    delta
    BenchmarkMapIter               191          190   -0.52%
    BenchmarkMapIterEmpty           22            4  -78.96%
    
    R=golang-dev, minux.ma, dvyukov, iant, khr
    CC=golang-dev
    https://golang.org/cl/9637043

変更の背景

Go言語では、map型は非常に頻繁に使用されるデータ構造です。for rangeループを使ってマップをイテレートする機能は、Goの強力な特徴の一つです。しかし、マップが空である場合でも、イテレーションの準備のために一定のオーバーヘッドが発生していました。

このコミットの背景には、空のマップに対するrangeループが、実際には何も処理しないにもかかわらず、不必要な初期化処理を実行しているという認識がありました。特に、空のマップを頻繁にイテレートするようなシナリオ（例えば、エラーハンドリングで空のマップが返される場合や、初期状態のデータ構造を扱う場合など）では、このオーバーヘッドが累積してパフォーマンスに影響を与える可能性がありました。

ベンチマーク結果が示すように、BenchmarkMapIterEmptyの実行時間が22nsから4nsへと大幅に短縮されており、これは空のマップのイテレーションが約79%高速化されたことを意味します。この改善は、Goアプリケーション全体のパフォーマンス、特にマップの利用が多いコードベースにおいて、わずかながらも積み重なる形で貢献します。

前提知識の解説

Go言語のmap型

Go言語のmapは、キーと値のペアを格納するハッシュテーブルの実装です。キーは一意であり、値は任意の型を持つことができます。mapは参照型であり、make関数で初期化されます。

m := make(map[string]int) // stringキーとint値を持つマップを作成
m["apple"] = 1
v := m["apple"] // 値の取得
delete(m, "apple") // 要素の削除

for rangeループとマップのイテレーション

Go言語では、for rangeループを使用してマップのキーと値をイテレートできます。

for key, value := range myMap {
    // keyとvalueを使った処理
}

マップのイテレーション順序は保証されません。

Goランタイム

Goランタイムは、Goプログラムの実行を管理するシステムです。ガベージコレクション、スケジューリング、プリミティブ型の操作、システムコールなど、Goプログラムが動作するために必要な低レベルの機能を提供します。src/pkg/runtimeディレクトリには、これらのランタイム機能のソースコードが含まれています。Goランタイムの多くの部分はC言語（またはGoのサブセットであるPlan 9 C）で書かれていますが、一部はGo言語自体で書かれています。

hashmap.c

src/pkg/runtime/hashmap.cは、Goランタイムにおけるハッシュマップ（map）の内部実装の一部を担うC言語のファイルです。マップの作成、要素の追加・削除、イテレーションの準備など、マップ操作の低レベルなロジックが含まれています。Goのmap操作は、最終的にこのC言語のコードにコンパイルされて実行されます。

mapspeed_test.go

src/pkg/runtime/mapspeed_test.goは、Goランタイムのマップ操作のパフォーマンスを測定するためのベンチマークテストが記述されたGo言語のファイルです。Goのtestingパッケージを利用して、特定の操作（マップの作成、要素の追加、イテレーションなど）にかかる時間を計測し、パフォーマンスの回帰を検出したり、改善の効果を評価したりするために使用されます。

技術的詳細

このコミットの技術的な核心は、Goランタイムのマップイテレータ初期化関数runtime·mapiterinitにおける条件分岐の追加です。

Go言語でfor rangeループを使ってマップをイテレートする際、内部的にはランタイムのruntime·mapiterinit関数が呼び出され、イテレーションに必要な準備が行われます。この関数は、イテレータの状態を初期化し、マップの要素を走査するための準備をします。

変更前は、runtime·mapiterinit関数は、マップのポインタhがnil（マップが初期化されていない状態）の場合にのみ早期リターンしていました。しかし、マップがnilではないが、count（要素数）が0である「空のマップ」の場合には、不要な初期化処理が実行されていました。

このコミットでは、以下の条件が追加されました。

-	if(h == nil) {
+	if(h == nil || h->count == 0) {

この変更により、hがnilであるか、またはh->countが0である（つまり、マップが空である）場合に、runtime·mapiterinit関数はすぐにit->key = nil; return;を実行して処理を終了するようになりました。

  • h == nil: マップ変数がnilである場合（例: var m map[string]int の初期状態）。
  • h->count == 0: マップが初期化されているが、要素が一つも追加されていない場合（例: m := make(map[string]int) の直後）。

この最適化により、空のマップに対してrangeループが実行された際に、イテレータの複雑な初期化ロジックや、ハッシュテーブルの内部構造を走査しようとする試みが完全にスキップされるようになります。これにより、CPUサイクルとメモリアクセスの両方が削減され、特に空のマップのイテレーションが頻繁に行われる場合に顕著なパフォーマンス向上をもたらします。

ベンチマーク結果のBenchmarkMapIterEmptyが示すように、この変更によって空のマップのイテレーションにかかる時間が大幅に短縮されました。一方、要素を持つマップのイテレーション（BenchmarkMapIter）にはほとんど影響がないことも確認されており、これは既存の動作に悪影響を与えずに特定のケースを最適化したことを示しています。

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

src/pkg/runtime/hashmap.c の runtime·mapiterinit 関数内の変更点:

diff --git a/src/pkg/runtime/hashmap.c b/src/pkg/runtime/hashmap.c
index 892f0a1700..959d6bc760 100644
--- a/src/pkg/runtime/hashmap.c
+++ b/src/pkg/runtime/hashmap.c
@@ -1355,7 +1355,7 @@ reflect·mapassign(MapType *t, Hmap *h, uintptr key, uintptr val, bool pres)\n void\n runtime·mapiterinit(MapType *t, Hmap *h, struct hash_iter *it)\n {\n-\tif(h == nil) {\n+\tif(h == nil || h->count == 0) {\n \t\tit->key = nil;\n \t\treturn;\n \t}\

src/pkg/runtime/mapspeed_test.go に追加されたベンチマークテスト:

diff --git a/src/pkg/runtime/mapspeed_test.go b/src/pkg/runtime/mapspeed_test.go
index a737c65dc6..13b57621d4 100644
--- a/src/pkg/runtime/mapspeed_test.go
+++ b/src/pkg/runtime/mapspeed_test.go
@@ -233,3 +233,24 @@ func BenchmarkNewEmptyMap(b *testing.B) {\n 	\t_ = make(map[int]int)\n \t}\n }\n+\n+func BenchmarkMapIter(b *testing.B) {\n+\tm := make(map[int]bool)\n+\tfor i := 0; i < 8; i++ {\n+\t\tm[i] = true\n+\t}\n+\tb.ResetTimer()\n+\tfor i := 0; i < b.N; i++ {\n+\t\tfor _, _ = range m {\n+\t\t}\n+\t}\n+}\n+\n+func BenchmarkMapIterEmpty(b *testing.B) {\n+\tm := make(map[int]bool)\n+\tb.ResetTimer()\n+\tfor i := 0; i < b.N; i++ {\n+\t\tfor _, _ = range m {\n+\t\t}\n+\t}\n+}\n```

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

### `src/pkg/runtime/hashmap.c` の変更

`runtime·mapiterinit` 関数は、Goの`map`に対する`for range`ループが開始される際に、ランタイムによって呼び出される内部関数です。この関数の目的は、マップのイテレーションに必要な内部状態（イテレータ構造体`it`）を初期化することです。

変更前のコード:
```c
if(h == nil) {
    it->key = nil;
    return;
}

これは、マップのポインタhがnil（Goのnilマップ）の場合に、イテレータのキーをnilに設定してすぐにリターンするというものでした。これは正しい動作ですが、make(map[K]V)で作成されたが要素が一つも追加されていない「空のマップ」の場合には、この条件に合致せず、イテレータの初期化処理が続行されていました。

変更後のコード:

if(h == nil || h->count == 0) {
    it->key = nil;
    return;
}

この変更では、既存のh == nilの条件に加えて、h->count == 0という条件が追加されました。

  • h: Hmap構造体へのポインタで、Goのマップの内部表現です。
  • h->count: Hmap構造体内のフィールドで、マップに現在格納されている要素の数を表します。

この新しい条件h->count == 0が追加されたことで、マップがnilであるか、またはマップに要素が一つも含まれていない（空である）場合に、イテレータの初期化処理が早期に終了するようになりました。これにより、空のマップに対するrangeループが、不必要な内部処理（例えば、バケットの走査やハッシュ計算の準備など）を実行することなく、即座に終了するようになり、パフォーマンスが向上します。

src/pkg/runtime/mapspeed_test.go の変更

このファイルには、マップのイテレーションのパフォーマンスを測定するための2つの新しいベンチマーク関数が追加されました。

  1. BenchmarkMapIter:

    func BenchmarkMapIter(b *testing.B) {
	m := make(map[int]bool)
	for i := 0; i < 8; i++ {
		m[i] = true
	}
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		for _, _ = range m {
		}
	}
}

    このベンチマークは、8つの要素を持つマップをイテレートする際のパフォーマンスを測定します。これは、一般的なマップイテレーションのシナリオをシミュレートし、最適化が既存の動作に悪影響を与えないことを確認するために使用されます。

  2. BenchmarkMapIterEmpty:

    func BenchmarkMapIterEmpty(b *testing.B) {
	m := make(map[int]bool)
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		for _, _ = range m {
		}
	}
}

    このベンチマークは、空のマップをイテレートする際のパフォーマンスを測定します。このベンチマークが、今回のコミットによるパフォーマンス改善の主要なターゲットであり、その効果を定量的に示すために使用されます。

これらのベンチマークは、Goのtestingパッケージのb.ResetTimer()とb.Nを使用して、指定された操作をb.N回繰り返し実行し、その平均実行時間をナノ秒単位で測定します。コミットメッセージに記載されているベンチマーク結果は、これらのテストが実際に実行され、改善が確認されたことを示しています。

関連リンク

参考にした情報源リンク

  • なし (提供されたコミット情報とGo言語の一般的な知識に基づいて解説を生成しました。)