【ITニュース解説】Goも当然にMapよりSwitchが速い ― 制約によるコンパイル時最適化の威力

プログラムの性能を議論する際、計算量という考え方がよく用いられる。これは、処理するデータの量が増えたときに、実行時間がどれくらい増えるかを示す指標である。例えば、map（連想配列やハッシュマップとも呼ばれる）は、キーを指定して値を取り出す操作が平均O(1)であると言われる。これはデータの量がどれだけ増えても、値を取り出す時間はほぼ一定であることを意味する。一方、switch文は、与えられた値がどのcaseに一致するかを上から順に調べていくように見えるため、caseの数（N）に比例して時間がかかるO(N)だと考えられがちだ。この知識だけを基にすると、たくさんの選択肢の中から一つを選ぶ処理では、switch文よりもmapを使った方が高速だと結論付けてしまうかもしれない。しかし、実際のプログラムの世界では、この単純な比較が必ずしも正しくない場合がある。Go言語のコンパイラが行う「最適化」によって、switch文がmapよりもはるかに高速に動作することがあるのだ。

mapは、プログラムの実行中にキーと値のペアを自由に追加したり削除したりできる、非常に柔軟なデータ構造である。この柔軟性を実現するため、mapは内部でハッシュ関数という仕組みを使っている。キーをハッシュ関数にかけることで、データを格納する場所を高速に特定する。このおかげで平均O(1)の性能が実現されるが、ハッシュ値を計算するコストや、稀に異なるキーが同じハッシュ値になってしまう「ハッシュ衝突」を解決するための追加処理など、目に見えないオーバーヘッドが常に存在する。一方、switch文は、caseに書かれる値がプログラムをコンパイルする時点ですべて決まっているという大きな特徴がある。プログラムの実行中にcaseを増やしたり減らしたりすることはできない。この「コンパイル時に値が固定されている」という制約が、コンパイラによる強力な最適化を可能にする鍵となる。コンパイラは、私たちが書いたソースコードを機械が理解できる言葉に翻訳する役割を持つが、その際にコードを分析し、より効率的な実行形式に変換してくれるのだ。

Goのコンパイラは、switch文のcaseの値の並び方や種類に応じて、複数の最適化手法を使い分ける。もしswitch文が本当に上から順に値を比較する素朴な実装（線形探索）しかされないのであれば、その計算量はO(N)になる。しかし、コンパイラはもっと賢い方法を知っている。例えば、caseの値が「1, 2, 3, 4」のように連続した整数である場合、コンパイラは「ジャンプテーブル」という効率的な仕組みを生成することがある。これは、値そのものを配列のインデックス（添字）のように扱い、実行すべき処理が格納されているアドレスへ直接ジャンプする方式だ。配列の要素にアクセスする時間が常に一定であるように、ジャンプテーブルを使えば、caseの数に関わらず一回の操作で目的の処理にたどり着ける。この場合の計算量はO(1)となり、mapと同等か、ハッシュ計算などのオーバーヘッドがない分、さらに高速になる。また、caseの値が「10, 20, 50, 100」のように飛び飛びの整数であったり、アルファベット順に並んだ文字列であったりする場合、コンパイラは二分探索のロジックを生成することがある。これは、まず選択肢全体の中央の値と比較し、対象がそれより大きいか小さいかに応じて探索範囲を半分に絞り込む、という作業を繰り返す方法である。この方法を使えば、caseの数が倍になっても探索回数は1回増える程度で済み、計算量はO(log N)に抑えられる。これは、caseの数が1000個あっても約10回の比較で済むほど非常に効率的な探索方法であり、O(N)とは比べ物にならない速さを誇る。

このように、switch文はコンパイル時に条件がすべて判明しているという「制約」のおかげで、コンパイラが事前に最適な実行計画を立て、極めて効率的なコードを生成できる。対照的に、mapは実行時の柔軟性と引き換えに、コンパイル時最適化の恩恵を受けにくく、常に一定の実行時コストがかかる。したがって、プログラムを書く時点で分岐の条件がすべて固定されているのであれば、switch文を選択する方が多くの場合で高速な実行を期待できる。それは単にコードが読みやすくなるだけでなく、パフォーマンス上の利点も大きいのだ。もちろん、キーと値の対応を実行時に動的に変更する必要がある場合には、mapが最適な選択肢となる。「mapはO(1)、switchはO(N)」という計算量の知識は理論的な基礎として重要だが、それが実際のパフォーマンスにどう結びつくかは、コンパイラの最適化やデータ構造の内部実装といった、より深いレベルで決まる。表面的な計算量だけで技術選択を行うのではなく、その背景にある仕組みを理解し、状況に応じて最適な手段を選ぶことが、優れたシステムエンジニアになるための重要な一歩と言えるだろう。