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

このコミットは、Goコンパイラ（gc）におけるインターフェース値の比較（==および!=）の最適化に関するものです。具体的には、比較対象のインターフェース値が異なる具象型を持つ場合、実際のインターフェース比較ルーチンを呼び出すことなく、それらが明らかに等しくないと判断できるようにすることで、パフォーマンスを向上させています。これにより、err == io.EOFのような特定の値をテストする際の速度が約3倍に向上しました。

コミット

commit f91cc3bdbbdad81a4d2be5833a6a1816355d93e1
Author: Russ Cox <rsc@golang.org>
Date:   Sat Feb 11 00:19:24 2012 -0500

    gc: optimize interface ==, !=
    
    If the values being compared have different concrete types,
    then they're clearly unequal without needing to invoke the
    actual interface compare routine.  This speeds tests for
    specific values, like if err == io.EOF, by about 3x.
    
    benchmark                  old ns/op    new ns/op    delta
    BenchmarkIfaceCmp100             843          287  -65.95%
    BenchmarkIfaceCmpNil100          184          182   -1.09%
    
    Fixes #2591.
    
    R=ken2
    CC=golang-dev
    https://golang.org/cl/5651073

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

https://github.com/golang/go/commit/f91cc3bdbbdad81a4d2be5833a6a1816355d93e1

元コミット内容

gc: optimize interface ==, !=

If the values being compared have different concrete types,
then they're clearly unequal without needing to invoke the
actual interface compare routine.  This speeds tests for
specific values, like if err == io.EOF, by about 3x.

benchmark                  old ns/op    new ns/op    delta
BenchmarkIfaceCmp100             843          287  -65.95%
BenchmarkIfaceCmpNil100          184          182   -1.09%

Fixes #2591.

R=ken2
CC=golang-dev
https://golang.org/cl/5651073

変更の背景

Go言語において、インターフェース値の比較は、その内部構造のために比較的コストの高い操作でした。インターフェース値は、具象型（_typeポインタ）と値（dataポインタ）の2つの要素から構成されます。従来の比較では、これらの両方の要素を考慮する必要があり、特に具象型が異なる場合でも、完全な比較ルーチンが実行されていました。

このコミットの背景には、err == io.EOFのような一般的な比較シナリオにおいて、不必要な計算コストを削減したいという意図があります。io.EOFは特定の具象型を持つエラー値であり、errが異なる具象型を持つ場合、値が何であれ、両者は決して等しくなりません。このようなケースで早期に不等であると判断できれば、比較処理を大幅に高速化できます。

コミットメッセージに記載されているベンチマーク結果が示すように、BenchmarkIfaceCmp100（インターフェース比較のベンチマーク）で約65.95%の性能改善が見られ、これはインターフェース比較の最適化が実用的なアプリケーションのパフォーマンスに大きな影響を与えることを示しています。

前提知識の解説

Go言語のインターフェース

Go言語のインターフェースは、メソッドのシグネチャの集合を定義する型です。Goのインターフェースは、他の言語のインターフェースとは異なり、暗黙的に満たされます。つまり、ある型がインターフェースで定義されたすべてのメソッドを実装していれば、その型はそのインターフェースを満たします。

内部的には、Goのインターフェース値は2つのポインタで構成されます。

1. 型ポインタ (Type Pointer / _type / itab): インターフェース値が保持する具象型（concrete type）の情報を指します。これは、その具象型がインターフェースのメソッドをどのように実装しているかを示すテーブル（itab、interface table）へのポインタです。
2. データポインタ (Data Pointer / data): インターフェース値が保持する実際のデータ（具象型の値）を指します。

インターフェース値がnilである場合、両方のポインタがnilになります。

インターフェースの比較

Go言語では、インターフェース値は==または!=演算子を使用して比較できます。比較のルールは以下の通りです。

• 両方のインターフェース値がnilの場合: 等しいと判断されます。
• 片方がnilで、もう片方がnilでない場合: 等しくないと判断されます。
• 両方のインターフェース値がnilでない場合:
  • まず、両者の**具象型（型ポインタ）**が等しいかどうかが比較されます。具象型が異なる場合、それらのインターフェース値は等しくないと判断されます。
  • 具象型が等しい場合、次に両者のデータポインタが指す値が等しいかどうかが比較されます。この値の比較は、具象型の種類によって異なります（例: 構造体はフィールドごとに比較、スライスやマップは直接比較できないなど）。

このコミットの最適化は、上記の「具象型が異なる場合、それらのインターフェース値は等しくないと判断される」というルールを、より効率的にコンパイラが処理できるようにすることに焦点を当てています。

itab (Interface Table)

itabは、Goのランタイムがインターフェースの動的なディスパッチを効率的に行うために使用する内部データ構造です。特定の具象型が特定のインターフェースを実装している場合、その組み合わせに対応するitabが作成されます。itabには、具象型の情報、インターフェースの型情報、そしてインターフェースのメソッドが具象型のどのメソッドに対応するかを示す関数ポインタの配列が含まれています。インターフェース値の型ポインタは、このitabを指します。

Goコンパイラのバックエンド (5g, 6g, 8g)

Goのコンパイラは、ターゲットアーキテクチャごとに異なるバックエンドを持っています。

• 5g: ARMアーキテクチャ用
• 6g: AMD64 (x86-64) アーキテクチャ用
• 8g: x86 (32-bit) アーキテクチャ用

これらのバックエンドは、共通のフロントエンド（gc）によって生成された中間表現を受け取り、それぞれのアーキテクチャの機械語に変換します。このコミットでは、これらの複数のバックエンドのコード生成部分に修正が加えられています。

技術的詳細

この最適化の核心は、インターフェース値の比較において、まず具象型（itabポインタ）が異なるかどうかをチェックし、異なる場合は即座に不等であると判断するショートカットを導入することです。これにより、具象型の値の比較という、よりコストのかかる操作を回避できます。

具体的には、Goコンパイラのwalk.cファイル内のwalkexpr関数（式のウォーク処理を行う部分）が変更されています。インターフェースの等価性比較（OEQまたはONE）が検出された場合、以下のロジックが追加されます。

1. 比較対象の2つのインターフェース値から、それぞれのitab（型ポインタ）を取得します。これは新しい内部ノードタイプOITABによって表現されます。
2. これらのitabポインタが等しいかどうかを比較します。
   • もし元の比較がOEQ（等しい）であれば、itabが等しいこと（OEQ, OITAB(left), OITAB(right)）と、従来の完全なインターフェース比較の結果（r）の両方が真である場合にのみ真となるような論理AND（OANDAND）を構築します。
   • もし元の比較がONE（等しくない）であれば、itabが等しくないこと（ONE, OITAB(left), OITAB(right)）が真であるか、または従来の完全なインターフェース比較の結果（r）が真である場合に真となるような論理OR（OOROR）を構築します。

この新しい論理式は、コンパイラによって評価され、具象型が異なる場合は、データ値の比較を行うことなく、早期に結果を確定させることができます。

また、OITABという新しいノードタイプが導入され、コンパイラの各ステージ（型チェック、コード生成など）で適切に処理されるように、go.h、typecheck.c、cgen.c、gsubr.cなどのファイルが更新されています。

• src/cmd/gc/go.h: OITABという新しい列挙型が追加され、インターフェース値のitabワードを表すことが示されています。
• src/cmd/gc/typecheck.c: OITABノードの型チェックロジックが追加され、左辺がインターフェース型であることを確認し、結果の型をポインタ型（uintptr）に設定します。
• src/cmd/gc/walk.c: インターフェース比較の最適化ロジックが追加され、OITABノードが生成されます。
• src/cmd/{5g,6g,8g}/cgen.c および src/cmd/{5g,6g,8g}/gsubr.c: 各アーキテクチャのコードジェネレータにおいて、OITABノードを処理するためのコードが追加されています。これにより、インターフェース値からitabポインタを正しく抽出できるようになります。

この変更により、インターフェース比較の際に、まず具象型の比較という軽量なチェックを行い、それが失敗した場合はすぐに結果を返すことで、不要なランタイム呼び出しを削減し、パフォーマンスを向上させています。

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

このコミットにおけるコアとなるコードの変更は、主にGoコンパイラの以下のファイルに集中しています。

1. src/cmd/gc/walk.c: インターフェース比較の最適化ロジックが追加された主要なファイルです。
   • walkexpr関数内で、OEQ（等しい）またはONE（等しくない）のインターフェース比較が処理される部分に、新しいOITABノードを用いた条件分岐が追加されています。
2. src/cmd/gc/go.h: 新しい内部ノードタイプOITABの定義が追加されています。
3. src/cmd/gc/typecheck.c: OITABノードの型チェックロジックが追加されています。
4. src/cmd/{5g,6g,8g}/cgen.c: 各アーキテクチャのコード生成器において、OITABノードを処理するためのコードが追加されています。
5. src/cmd/{5g,6g,8g}/gsubr.c: 各アーキテクチャのコード生成器において、OITABノードに関連するアドレス計算やメモリ操作のサポートが追加されています。
6. src/pkg/runtime/runtime_test.go: インターフェース比較のパフォーマンスを測定するための新しいベンチマークテストが追加されています。

コアとなるコードの解説

src/cmd/gc/walk.c の変更

--- a/src/cmd/gc/walk.c
+++ b/src/cmd/gc/walk.c
@@ -1176,10 +1180,21 @@ walkexpr(Node **np, NodeList **init)
 	\targtype(fn, n->right->type);
 	\targtype(fn, n->left->type);
 	\tr = mkcall1(fn, n->type, init, n->left, n->right);
-\t\tif(n->etype == ONE) {
+\t\tif(n->etype == ONE)
 	\t\tr = nod(ONOT, r, N);
-\t\t\ttypecheck(&r, Erv);
-\t\t}\n
+\t\t
+\t\t// check itable/type before full compare.
+\t\tif(n->etype == OEQ)
+\t\t\tr = nod(OANDAND, nod(OEQ, nod(OITAB, n->left, N), nod(OITAB, n->right, N)), r);
+\t\telse
+\t\t\tr = nod(OOROR, nod(ONE, nod(OITAB, n->left, N), nod(OITAB, n->right, N)), r);
+\t\ttypecheck(&r, Erv);
+\t\twalkexpr(&r, nil);
+\n+\t\tn = r;
+\t\tgoto ret;
+\n+\t
 	\tn = r;
 	\tgoto ret;

この部分が最適化の主要なロジックです。

• mkcall1(fn, n->type, init, n->left, n->right): これは、インターフェース比較を行うランタイム関数への呼び出しを生成します。この呼び出しの結果がrに格納されます。
• if(n->etype == ONE): 元の比較が!=（等しくない）の場合、ランタイム関数の結果を否定します。
• // check itable/type before full compare.: ここからが新しい最適化ロジックです。
  • nod(OITAB, n->left, N): 左辺のインターフェース値からitabポインタを取得するノードを生成します。
  • nod(OITAB, n->right, N): 右辺のインターフェース値からitabポインタを取得するノードを生成します。
  • nod(OEQ, nod(OITAB, n->left, N), nod(OITAB, n->right, N)): 2つのitabポインタが等しいかどうかを比較するノードを生成します。
  • if(n->etype == OEQ): 元の比較が==の場合、
    • r = nod(OANDAND, ..., r);: itabが等しいこと AND ランタイム比較の結果が等しいこと、という論理ANDを構築します。これにより、itabが異なれば、ランタイム比較を実行するまでもなく結果がfalseになります。
  • else: 元の比較が!=の場合、
    • r = nod(OOROR, ..., r);: itabが等しくないこと OR ランタイム比較の結果が等しくないこと、という論理ORを構築します。これにより、itabが異なれば、ランタイム比較を実行するまでもなく結果がtrueになります。
• typecheck(&r, Erv); と walkexpr(&r, nil);: 新しく構築された式を型チェックし、再度ウォーク処理を行います。
• n = r; goto ret;: 最終的な結果をnに設定し、関数を終了します。

この変更により、コンパイラはインターフェース比較の際に、まず具象型の比較という軽量なチェックを行い、それが失敗した場合はすぐに結果を返すことで、不要なランタイム呼び出しを削減し、パフォーマンスを向上させています。

src/cmd/gc/go.h の変更

--- a/src/cmd/gc/go.h
+++ b/src/cmd/gc/go.h
@@ -484,6 +484,7 @@ enum
 	ODDD,
 	ODDDARG,
 	OINLCALL,	// intermediary representation of an inlined call
+\tOITAB,\t// itable word of interface value
 
 	// for back ends
 	OCMP, ODEC, OEXTEND, OINC, OREGISTER, OINDREG,

OITABという新しいノードタイプが追加されています。これは、インターフェース値のitab（型情報）部分を抽出するための内部表現です。

src/cmd/gc/typecheck.c の変更

--- a/src/cmd/gc/typecheck.c
+++ b/src/cmd/gc/typecheck.c
@@ -1304,6 +1304,16 @@ reswitch:
 	\t\tif(n->type == T)
 	\t\t\tgoto error;
 	\t\tgoto ret;
+\t\n+\tcase OITAB:\n+\t\tok |= Erv;\n+\t\ttypecheck(&n->left, Erv);\n+\t\tif((t = n->left->type) == T)\n+\t\t\tgoto error;\n+\t\tif(t->etype != TINTER)\n+\t\t\tfatal(\"OITAB of %T\", t);\n+\t\tn->type = ptrto(types[TUINTPTR]);\n+\t\tgoto ret;\n
 \n 	/*
 	 * statements

OITABノードが型チェックされる際のロジックが追加されています。OITABの左辺（n->left）がインターフェース型であることを確認し、結果の型をポインタ型（uintptr）に設定します。これにより、itabポインタが正しく扱われるようになります。

src/cmd/{5g,6g,8g}/cgen.c および src/cmd/{5g,6g,8g}/gsubr.c の変更

これらのファイルでは、各アーキテクチャのコード生成器がOITABノードを認識し、インターフェース値からitabポインタを抽出するための適切な機械語を生成するように修正されています。具体的には、インターフェース値のメモリレイアウトに基づいて、itabポインタが格納されているオフセットから値を読み出す処理が追加されています。

src/pkg/runtime/runtime_test.go の追加

// Copyright 2012 The Go Authors.  All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package runtime_test

import (
	"io"
	"testing"
)

var errf error

func errfn() error {
	return errf
}

func errfn1() error {
	return io.EOF
}

func BenchmarkIfaceCmp100(b *testing.B) {
	for i := 0; i < b.N; i++ {
		for j := 0; j < 100; j++ {
			if errfn() == io.EOF {
				b.Fatal("bad comparison")
			}
		}
	}
}

func BenchmarkIfaceCmpNil100(b *testing.B) {
	for i := 0; i < b.N; i++ {
		for j := 0; j < 100; j++ {
			if errfn1() == nil {
				b.Fatal("bad comparison")
			}
		}
	}
}

この新しいテストファイルは、インターフェース比較のパフォーマンスを測定するためのベンチマークを含んでいます。

• BenchmarkIfaceCmp100: errfn()（具象型が異なる可能性のあるエラー）とio.EOF（特定の具象型を持つエラー）の比較を100回繰り返すベンチマークです。このベンチマークが、コミットメッセージで示された大幅な性能改善（-65.95%）の恩恵を受けています。
• BenchmarkIfaceCmpNil100: io.EOFとnilの比較を100回繰り返すベンチマークです。このケースでは、itabの比較による最適化はほとんど効果がないため、性能改善もわずか（-1.09%）です。

これらのベンチマークは、最適化の効果を定量的に示すために追加されました。

関連リンク

• Go Issue 2591: https://github.com/golang/go/issues/2591
  • このコミットが修正したGoのIssueです。インターフェース比較のパフォーマンスに関する議論が含まれています。
• Go Code Review 5651073: https://golang.org/cl/5651073
  • このコミットに対応するGoのコードレビューページです。変更の詳細な議論や、レビュー担当者とのやり取りが含まれています。

参考にした情報源リンク

• Go言語のインターフェースの内部構造に関する一般的な情報源（例: Go公式ブログ、Goのソースコード解説記事など）
• Goコンパイラの内部構造に関する一般的な情報源（例: Goのコンパイラ設計に関するドキュメント、Goのソースコード解説記事など）
• Goのベンチマークテストの書き方に関する情報源
• Goのitabに関する詳細な解説記事
• Go言語のインターフェースの内部表現とitab:
  • Go Interfaces Under The Hood - Medium
  • Go Data Structures: Interfaces - The Go Programming Language
  • Go: The Design of Interfaces - The Go Programming Language
• Goコンパイラの構造:
  • Go Compiler Internals - The Go Programming Language
• Goのベンチマーク:
  • How to write benchmarks in Go - The Go Programming Language