【Go】Map複合キー「構造体キー vs 文字列キー」~ 検証レポート ~

はじめに

今回、Go言語におけるmapの複合キーの表現方法についてフォーカスを当てて検証を行ってみました。

あまり意識せず「型安全だから」という理由で構造体を複合キーに指定している方、そもそも構造体をキーにしていいことを知らない方、も意外と多いのかなと思います。

本記事では、複合キーの指定方法についての性能調査レポートをまとめましたので是非ご覧下さい。

1. 目的と背景

背景

Goのmapはランタイムのハッシュマップ実装、所謂runtime.hmapを内部で使用し、キーのハッシュ値計算と等価比較によって要素を特定します。

この時、キーの型によってランタイムが使用するハッシュ関数が異なります。

• string: runtime.strhash
  ⋯ 最適化されたバイト列ハッシュ
• int: runtime.memhash64
  ⋯ 8バイト固定長ハッシュ
• 構造体: コンパイラが各フィールドのハッシュを合成する関数を自動生成

本レポートでは上記の仕様を前提とさせていただきます。

実務で想定される複合キーの表現方法は主に以下の2つと想定して、検証を行おうと思います。

方法A: 文字列結合キー

key := strconv.Itoa(id) + ":" + code
m[key] = value  // map[string]T

方法B: 構造体キー

type CompositeKey struct { ID int; Code string }
m[CompositeKey{id, code}] = value  // map[CompositeKey]T

この時、

方法Aは文字列結合に伴うヒープアロケーションが発生します。
方法Bはアロケーションは不要ですが、コンパイラ生成のハッシュ関数が複数フィールドを逐次ハッシュします。

こういう前提がある以上、実用上高速なのはどちらなのか？ という問いは自明ではないですよね。

追加検証

主題とは異なりますが、興味深い結果が取れましたので以下も検証の対象に加えさせていただきます。

方法C: 構造体キー( 固定長データで構成 )

// 追加検証用：固定長データのみの構成
type IntPairKey struct { ID1 int; ID2 int } // 計16バイト

目的

そこで今回、以下3つの観点で実験を行ってみようと思います。

1. map[string]Tとmap[struct]Tの Insert / Lookup 性能を定量比較する
   （要は、文字列結合キーと構造体キーの配列プッシュと配列参照の性能調査）
2. 文字列キーの構築コストを含む現実的なシナリオと、構築コストを除外した純粋なマップ操作性能を分離して測定
3. 構造体キーのフィールド構成（int のみ / int+string 混合）が性能に与える影響を測定
   （追加検証の内容ですね）

わりと実務にあった内容かと。

2. 仮説と期待値

仮説

実際に検証を行う前に私なりの仮説を記載させていただきます。

"純粋なマップ操作" では

string キーがランタイム最適化されたハッシュ関数により構造体キーより高速と予測します。
※ この時、純粋なマップ操作において "キー構築コスト" は除外とさせていただきます。

"キー構築込みの現実シナリオ" では

構造体キーが文字列結合のアロケーションを回避するため逆転し、構造体キーが有利になると予測します。

期待値

ざっくりと計算したんですが、以下を期待値として実験を行ってみます。

「キー構築を含めるか否かでどの程度スコアが変わってくるか」についても注目いただけると面白いのかなと思っています。

Lookup（キー構築込み） では。

Key Type	ns/op	allocs/op	Note
string（結合）	高い	1+	文字列結合でアロケーション
CompositeKey	低い	0	スタック上で構築
IntPairKey	最も低い	0	固定長ハッシュのみ

Lookup（事前構築済みキー） では。

Key Type	ns/op	allocs/op	Note
string（事前構築）	低い	0	strhash 最適化
CompositeKey	同等〜やや高い	0	フィールド逐次ハッシュ
IntPairKey	最も低い	0	16B固定長

キー構築込みでは構造体キーが 20〜40% 高速、純粋なLookupでは文字列キーが 5〜15% 高速と予測します。

3. 検証

検証環境

Go: 1.25.7
OS/Arch: darwin/arm64
CPU: Apple M2

方法

以下、3つを動的要素として、testing.Bを活用し測定を行います。

1 キーの型

• string
• CompositeKey
• IntPairKey

1. 操作種別

• Insert
• Lookup

1. キー構築込み / 事前構築済み

条件

• マップサイズを10,000に固定
• mapの値の型はint固定

検証コード

1. サンプル

以下にて、構造体キーの型を定義しました。

文字列に関してですが、本検証ではカスタムでの定義は行わずに、Go言語標準のstring型を扱います。

以下にて、文字列キーの構築を行うユーティリティ関数を定義しました。

2. Insert測定

以下にて、Insert、所謂配列へのPushの挙動に絞った速度の測定を行います。

それぞれ、for文の中のコードを見ていただけるとイメージしやすいかと。

3. Lookup測定 ( キー構築込み )

以下にて、Lookup、所謂ハッシュ参照の挙動に絞った速度の測定を行います。
※ この際、キーの構築計算も含んだものを測定の対象としております。

4. Lookup測定 ( キー構築済み )

以下にて、Lookup、所謂ハッシュ参照の挙動に絞った速度の測定を行います。
※ この際、キーの構築計算を含まないものを測定の対象としております。

4. 結果

ベンチマーク

go test -bench . -benchmem -count 5

上記コマンドを実施した際の測定結果です。

goos: darwin
goarch: arm64
cpu: Apple M2

BenchmarkInsert_StringKey-8                       2269        524031 ns/op    596039 B/op     19933 allocs/op
BenchmarkInsert_StringKey-8                       2206        504951 ns/op    596035 B/op     19933 allocs/op
BenchmarkInsert_StringKey-8                       2337        513692 ns/op    596034 B/op     19933 allocs/op
BenchmarkInsert_CompositeKey-8                    6085        203327 ns/op    656004 B/op        33 allocs/op
BenchmarkInsert_CompositeKey-8                    5878        205149 ns/op    656004 B/op        33 allocs/op
BenchmarkInsert_CompositeKey-8                    5844        203578 ns/op    656004 B/op        33 allocs/op
BenchmarkInsert_IntPairKey-8                      8240        154514 ns/op    436867 B/op        33 allocs/op
BenchmarkInsert_IntPairKey-8                      8348        148614 ns/op    436868 B/op        33 allocs/op
BenchmarkInsert_IntPairKey-8                      8338        148924 ns/op    436868 B/op        33 allocs/op
BenchmarkLookup_StringKey-8                       2502        485267 ns/op    159168 B/op     19900 allocs/op
BenchmarkLookup_StringKey-8                       2538        496887 ns/op    159170 B/op     19900 allocs/op
BenchmarkLookup_StringKey-8                       2323        485527 ns/op    159168 B/op     19900 allocs/op
BenchmarkLookup_CompositeKey-8                    8520        145152 ns/op         0 B/op         0 allocs/op
BenchmarkLookup_CompositeKey-8                    8386        143515 ns/op         0 B/op         0 allocs/op
BenchmarkLookup_CompositeKey-8                    8484        146108 ns/op         0 B/op         0 allocs/op
BenchmarkLookup_IntPairKey-8                     12381         96671 ns/op         0 B/op         0 allocs/op
BenchmarkLookup_IntPairKey-8                     12685         95225 ns/op         0 B/op         0 allocs/op
BenchmarkLookup_IntPairKey-8                     12586         95651 ns/op         0 B/op         0 allocs/op
BenchmarkLookupPrebuilt_StringKey-8              12886         93339 ns/op         0 B/op         0 allocs/op
BenchmarkLookupPrebuilt_StringKey-8              10000        104068 ns/op         0 B/op         0 allocs/op
BenchmarkLookupPrebuilt_StringKey-8              12585         95645 ns/op         0 B/op         0 allocs/op
BenchmarkKeyBuild_String-8                        3634        331946 ns/op     38880 B/op      9900 allocs/op
BenchmarkKeyBuild_String-8                        3766        323424 ns/op     38880 B/op      9900 allocs/op
BenchmarkKeyBuild_String-8                        3805        318165 ns/op     38880 B/op      9900 allocs/op
BenchmarkKeyBuild_CompositeKey-8                407888          2971 ns/op         0 B/op         0 allocs/op
BenchmarkKeyBuild_CompositeKey-8                362750          2993 ns/op         0 B/op         0 allocs/op
BenchmarkKeyBuild_CompositeKey-8                413414          3009 ns/op         0 B/op         0 allocs/op
BenchmarkKeyBuild_IntPairKey-8                  399554          3128 ns/op         0 B/op         0 allocs/op
BenchmarkKeyBuild_IntPairKey-8                  406846          2984 ns/op         0 B/op         0 allocs/op
BenchmarkKeyBuild_IntPairKey-8                  408592          3017 ns/op         0 B/op         0 allocs/op

集計します

結果を表にまとめますね。

Insert ( キー構築込み )

Key Type	ns/op	B/op	allocs/op	vs string
string（結合）	514,225	596,036	19,933	baseline
CompositeKey	204,018	656,004	33	-60%
IntPairKey	150,684	436,868	33	-71%

Lookup (キー構築込み )

Key Type	ns/op	allocs/op	vs string
string（結合）	489,227	19,900	baseline
CompositeKey	144,925	0	-70%
IntPairKey	95,849	0	-80%

Lookup ( 事前構築済み — string のみ )

Key Type	ns/op	allocs/op	Note
string（構築込み）	489,227	19,900	キー構築コスト含む
string（事前構築）	97,684	0	純粋なマップ操作
差分	~391,000	19,900	≒ KeyBuild_String (324k)

構造体キーの事前構築ベンチマークは実施しておりません。
構築コストが ~3k ns/op（≒ゼロ）のため分離測定の意義がなく、スライス走査のノイズが混入するだけだったためです。

キー構築コスト ( 分離測定 )

Key Type	ns/op	allocs/op	vs string
string	324,512	9,900	baseline
CompositeKey	2,991	0	-99%
IntPairKey	3,043	0	-99%

分析

1. キー構築コストについて

文字列キーの構築コスト( ~324k ns/op )を構造体キーの構築コスト( ~3k ns/op )と比較すると約108倍でした。
この差は、strconv.Itoaを前提とした、整数→文字列変換と+演算子による文字列結合が都度、ヒープアロケーションを発生させることに起因すると推察します。
比較して、構造体リテラルはスタック上で構築されるためアロケーションが発生しないと読み取れます。

2. Lookup 全体に占めるキー構築コストの割合

Lookup 全体に占めるキー構築コストの割合を算出しました。

• string: 324k / 489k = 66% がキー構築
• CompositeKey: 3k / 145k = 2% がキー構築

いや、想定より文字列キー構築コストへの消費が大きいんですね。
マップ操作自体の性能以前の問題であることが確認できたかな、と思います。

3. 純粋マップ操作では何が最速なのか

事前構築済みキーで比較すると、string（~98k ns/op）は CompositeKey の Lookup（~145k ns/op）より 48%高速 でした。
これは仮説の「5-15%」を大幅に上回る差ですね。

原因はなにか？

あくまで自身の見解ですが、Goランタイムのハッシュ実装にあるのかなと。

• string:
  runtime.strhash が呼ばれる。
  arm64 では AES 命令を使ったハードウェアアクセラレーションが有効で、任意長のバイト列を高速にハッシュする
• CompositeKey:
  コンパイラが各フィールドのハッシュを合成する関数を自動生成する。
  int フィールドの memhash64 と string フィールドの strhash を逐次呼び出し、結果を XOR 等で合成する。
  この関数呼び出しのオーバーヘッドと合成処理が加算される。

この辺、まだ弱い部分ですので深堀って実験したいところです。知見ある方いればコメントいただければ。

4. IntPairKey は全シナリオで最速

IntPairKey（~96k ns/op）は事前構築済み string（~98k ns/op）とほぼ同等でした。

IntPairKey は 16 バイトの連続メモリですので、runtime.memhash が単一呼び出しで処理できますよね。
ポインタの間接参照が不要なため CompositeKeyより効率的なのかなと。

CompositeKeyの場合だと、string フィールド内のポインタ追跡が必要ですもんね。

5. 結論

仮説が立証できました！！
※ 少し仮説で過小評価しすぎてましたが...。

Go言語における複合キーには、構造体キーを使うべきです。

その理由は以下です。

1. 現実のコードではキー構築が毎回発生します。
   事前構築済みキーを使い回すケースは稀ですし、構築コストを含む総合性能が実用的な指標となります。
2. 構築込みでは構造体キーが 70-80% 高速 であり、性能差は仮説以上に大きいです。
3. 構造体キーは 型安全 であり、文字列キーのセパレータ衝突（例: "1:23" vs "12:3"）のリスクがありません。
4. フィールドが全て固定長（int のみ）の場合、IntPairKey のように更なる高速化が期待できます。

以下、仮説との乖離をまとめてます。

予測	実測	評価
構築込み: 構造体が 20-40% 高速	70-80% 高速	差を過小評価
純粋 Lookup: string が 5-15% 高速	string が CompositeKey より 48% 高速	差を過小評価
IntPairKey が全シナリオで最速	確認された	仮説通り

勿論、キー構築を除外できるシチュエーションを加味出来る場合は、文字列キーを複合キーとして扱うことも視野に入れていいかと。

※ だいぶ運用でカバーしたバッチ処理、とかじゃない限り想像しにくいシチュエーションかなと思います。

具体的には、キー構築込みのCSVファイルが設置されている、とかでしょうか。実は一回だけ経験あります...。

まとめ

今回は、複合キーにおける性能調査を行いました。

わかりやすい結果が出て良かったなぁと感じます。
それにしても文字列のキー構築コスト、だいぶなんですね。

今回、文字列のキー構築にstrconv.Itoaと+結合を用いました。
ただ、fmt.Sprintfはもっと実務コードで頻出するイメージです。

また、strings.Builder などを駆使すれば文字列構築自体のコストは下げられるのかな、とも思いますが、
結局マップのキーとして渡す際に string としてヒープアロケーションが発生するため、構造体キーのゼロ・アロケーションには敵わないのかなぁとも。

この辺り、今回計測してないので機会があったらまた記事にしてみようと思います。

本記事がどなたかの参考になれば幸いです。