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

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

このコミットは、Go言語のマップにおいて浮動小数点数（float32, float64）および複素数（complex64, complex128）をキーとして使用できるようにするための修正です。具体的には、これらの型がマップのキーとして適切に機能するように、コンパイラ（gc）とランタイム（runtime）におけるハッシュおよび等価性チェックのロジックが更新されました。これにより、Go言語のマップがIEEE 754浮動小数点標準の特性（例: +0と-0の等価性、NaNとNaNの非等価性）を正しく扱えるようになります。

コミット

commit 408f0b1f7459ebcbc74ad5936950072796fe449a
Author: Russ Cox <rsc@golang.org>
Date:   Thu Jan 26 16:25:07 2012 -0500

    gc, runtime: handle floating point map keys
    
    Fixes #2609.
    
    R=ken2
    CC=golang-dev
    https://golang.org/cl/5572069

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

https://github.com/golang/go/commit/408f0b1f7459ebcbc74ad5936950072796fe449a

元コミット内容

gc, runtime: handle floating point map keys

Fixes #2609.

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

変更の背景

Go言語のマップは、キーのハッシュ値と等価性に基づいて要素を格納・検索します。しかし、浮動小数点数（float32, float64）や複素数（complex64, complex128）は、IEEE 754浮動小数点標準の特性により、通常の整数型とは異なる等価性ルールを持ちます。

主な問題点は以下の通りです。

  1. +0と-0の等価性: IEEE 754では、正のゼロ（+0）と負のゼロ（-0）は異なるビット表現を持ちますが、数値としては等しいとみなされます（+0 == -0はtrue）。マップのキーとしてこれらを扱う場合、異なるビット表現を持つにもかかわらず同じエントリを指す必要があります。
  2. NaN（Not a Number）の非等価性: NaNは、いかなる値とも等しくないと定義されています。これにはNaN自身も含まれます（NaN == NaNはfalse）。したがって、異なるNaN値はもちろん、同じビット表現を持つNaNであっても、マップのキーとしては異なるエントリとして扱われるべきです。しかし、通常のハッシュ関数や等価性チェックでは、ビット表現が同じであれば同じものとみなしてしまう可能性があります。
  3. 既存のマップ実装の限界: このコミット以前のGoのマップ実装では、浮動小数点数や複素数をキーとして使用する際に、これらの特殊なケースを適切に処理できていませんでした。その結果、+0と-0が異なるキーとして扱われたり、NaNが予期せぬ動作を引き起こしたりするバグ（Issue 2609）が存在していました。

このコミットは、これらの問題を解決し、浮動小数点数および複素数をGoマップのキーとして安全かつ正確に使用できるようにするために導入されました。

前提知識の解説

Go言語のマップの内部動作

Go言語のマップ（map）はハッシュテーブルとして実装されています。マップにキーと値を格納・検索する際には、以下の2つの主要な操作が行われます。

  1. ハッシュ関数 (Hashing): キーのハッシュ値を計算します。このハッシュ値は、マップ内部のバケット（データを格納する場所）を決定するために使用されます。異なるキーが同じハッシュ値を持つことはありますが（ハッシュ衝突）、ハッシュ値が異なればキーも必ず異なります。
  2. 等価性チェック (Equality Check): ハッシュ値が同じバケットに複数のキーが格納されている場合、実際に目的のキーと一致するかどうかを比較するために等価性チェックが行われます。このチェックは、キーの実際の値に基づいて行われます。

マップのキーとして使用できる型は、比較可能（comparable）である必要があります。これは、その型の値に対して==演算子と!=演算子が定義されており、かつその比較が決定論的（deterministic）であることを意味します。

IEEE 754 浮動小数点標準

Go言語のfloat32とfloat64は、IEEE 754浮動小数点標準に準拠しています。この標準は、浮動小数点数の表現と演算に関する国際的な標準です。マップのキーとして浮動小数点数を扱う上で特に重要な特性は以下の通りです。

  • 正のゼロ (+0) と負のゼロ (-0):
    • float32やfloat64には、+0.0と-0.0という2つのゼロ表現が存在します。
    • これらはビット表現が異なりますが、IEEE 754の比較規則では+0.0 == -0.0はtrueとなります。
    • マップのキーとして使用する場合、これらは同じキーとして扱われ、同じエントリにマッピングされる必要があります。
  • 非数 (NaN - Not a Number):
    • NaNは、0/0やsqrt(-1)のような不正な演算結果を表すために使用される特殊な浮動小数点値です。
    • IEEE 754の最も重要な特性の一つは、NaNはいかなる値とも等しくないという点です。これにはNaN自身も含まれます。つまり、NaN == NaNは常にfalseです。
    • NaNには様々なビット表現が存在し、それらはすべてNaNとみなされます。
    • マップのキーとして使用する場合、NaNは常に異なるキーとして扱われるべきです。つまり、map[NaN] = "value"とした後、別のNaN（たとえビット表現が同じでも）で検索しても、その値は取得できません。これは、NaNがマップのキーとして「役に立たない」ことを意味しますが、標準の動作に準拠するためにはこの挙動が必要です。

複素数型 (complex64, complex128)

Go言語の複素数型は、実部と虚部がそれぞれ浮動小数点数で構成されています。

  • complex64はfloat32の実部と虚部を持ちます。
  • complex128はfloat64の実部と虚部を持ちます。 したがって、複素数をマップのキーとして扱う場合も、その実部と虚部が持つ浮動小数点数の特性（+0/-0、NaN）を考慮する必要があります。

技術的詳細

このコミットは、Goコンパイラ（gc）とランタイム（runtime）の両方に変更を加えて、浮動小数点数および複素数をマップのキーとして適切に扱えるようにしています。

  1. コンパイラ (src/cmd/gc) の変更:

    • go.h: 新しい型定数 AFLOAT32, AFLOAT64, ACPLX64, ACPLX128 が追加されました。これらは、コンパイラが浮動小数点数および複素数型を識別し、それらに特化したハッシュおよび等価性関数を生成するために使用されます。
    • subr.c:
      • algtype1関数が修正され、TFLOAT32, TFLOAT64, TCOMPLEX64, TCOMPLEX128 型に対して、それぞれ対応する新しい型定数（AFLOAT32など）を返すように変更されました。これにより、コンパイラはこれらの型がマップのキーとして使用される際に、特別な処理が必要であることを認識します。
      • hashfor関数が修正され、新しい型定数に対応するランタイムのハッシュ関数（runtime.f32hash, runtime.f64hash, runtime.c64hash, runtime.c128hash）をルックアップするように変更されました。
      • genhash関数に、ハッシュ計算における乗算器（mul）の適用ロジックが追加されました。これは、ランタイムのmemhash関数で使用されるものと同じ乗算器であり、ハッシュ値の品質を向上させます。

  2. ランタイム (src/pkg/runtime) の変更:

    • alg.c:
      • 等価性チェック関数:
        • runtime.f32equal, runtime.f64equal: 浮動小数点数の等価性をチェックする関数が追加されました。これらはGoの==演算子のセマンティクスに従い、+0 == -0をtrueとし、NaN == NaNをfalseとします。
        • runtime.c64equal, runtime.128equal: 複素数の等価性をチェックする関数が追加されました。これらは実部と虚部の両方について浮動小数点数の等価性ルールを適用します。
      • ハッシュ関数:
        • runtime.f32hash, runtime.f64hash: 浮動小数点数のハッシュ関数が追加されました。
          • +0と-0は同じハッシュ値（0）を生成するようにします。
          • NaNに対しては、runtime.fastrand1()を使用してランダムなハッシュ値を生成します。これは、NaNが常に異なるキーとして扱われるべきであるという特性を反映しています。NaNが同じハッシュ値を持つと、マップの内部で長いハッシュチェーンが発生し、パフォーマンスが低下する可能性があるため、ランダムなハッシュ値を与えることでこれを回避します。
          • それ以外の通常の浮動小数点数については、そのビット表現を基にハッシュ値を計算します。
        • runtime.c64hash, runtime.c128hash: 複素数のハッシュ関数が追加されました。これらは実部と虚部それぞれに対して対応する浮動小数点数のハッシュ関数を呼び出し、それらを組み合わせて最終的なハッシュ値を生成します。
      • runtime.algarray: 新しく追加された浮動小数点数および複素数用のハッシュ関数と等価性チェック関数が、runtime.algarrayに登録されました。これにより、Goのランタイムがこれらの型をマップのキーとして扱う際に、適切な関数を呼び出すことができるようになります。
    • runtime.c: runtime.check関数に、NaNの比較に関するテストが追加されました。これは、NaN == NaNがfalseであることを確認するためのものです。
    • runtime.h: enumに新しい型定数 AFLOAT32, AFLOAT64, ACPLX64, ACPLX128 が追加されました。

  3. テスト (test/map.go) の追加:

    • testfloat関数が追加され、浮動小数点数および複素数をマップのキーとして使用した場合の挙動を検証する包括的なテストケースが含まれています。
    • 特に、+0と-0が同じキーとして扱われること、およびNaNが異なるキーとして扱われること（len(m)の増加）がテストされています。

これらの変更により、GoのマップはIEEE 754標準に準拠した浮動小数点数および複素数のキーを正しく処理できるようになりました。

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

  • src/cmd/gc/go.h: 浮動小数点数および複素数用の新しい型定数の追加。
  • src/cmd/gc/subr.c: コンパイラが浮動小数点数および複素数型を認識し、対応するランタイムハッシュ関数を呼び出すためのロジックの修正。ハッシュ計算における乗算器の追加。
  • src/pkg/runtime/alg.c: 浮動小数点数および複素数用のハッシュ関数と等価性チェック関数の実装、およびruntime.algarrayへの登録。
  • src/pkg/runtime/runtime.c: NaNの比較に関するランタイムチェックの追加。
  • src/pkg/runtime/runtime.h: 浮動小数点数および複素数用の新しい型定数の追加。
  • test/map.go: 浮動小数点数および複素数をマップキーとして使用する際の挙動を検証するテストケースの追加。

コアとなるコードの解説

src/cmd/gc/go.h および src/pkg/runtime/runtime.h

enum
{
	// ... 既存の型定数 ...
	AINTER,
	ANILINTER,
	ASLICE,
	AFLOAT32,  // float32型を表す新しい定数
	AFLOAT64,  // float64型を表す新しい定数
	ACPLX64,   // complex64型を表す新しい定数
	ACPLX128,  // complex128型を表す新しい定数

	BADWIDTH	= -1000000000,
};

これらのヘッダーファイルに、float32, float64, complex64, complex128 を識別するための新しい列挙型定数が追加されました。これらはコンパイラとランタイムが特定の型に対して特別な処理を行う必要があることを示すマーカーとして機能します。

src/cmd/gc/subr.c

algtype1 関数

Type* algtype1(Type *t, Type **bad) {
    // ... 既存のロジック ...
    case TINT:
    case TUINT:
    case TUINTPTR:
    // ... 以前はここに浮動小数点数と複素数があったが削除された ...
    case TBOOL:
    case TPTR32:
    case TPTR64:
    case TCHAN:
    case TUNSAFEPTR:
        return AMEM; // メモリ比較で十分な型

    case TFUNC:
    case TMAP:
        if(bad)
            *bad = t;
        return ANOEQ; // 比較できない型

    case TFLOAT32:
        return AFLOAT32; // float32はAFLOAT32として扱う
    case TFLOAT64:
        return AFLOAT64; // float64はAFLOAT64として扱う
    case TCOMPLEX64:
        return ACPLX64;  // complex64はACPLX64として扱う
    case TCOMPLEX128:
        return ACPLX128; // complex128はACPLX128として扱う

    case TSTRING:
        return ASTRING; // 文字列はASTRINGとして扱う
    // ... 既存のロジック ...
}

algtype1関数は、与えられたGoの型tがマップのキーとしてどのように扱われるべきか（どのようなハッシュ/等価性アルゴリズムを使用すべきか）を決定します。この変更により、浮動小数点数と複素数型がAMEM（単純なメモリ比較）ではなく、それぞれ専用のアルゴリズムタイプ（AFLOAT32など）として分類されるようになりました。これにより、ランタイムがこれらの型に対して特別なハッシュおよび等価性関数を呼び出すことが可能になります。

hashfor 関数

Sym* hashfor(Type *t) {
    // ... 既存のロジック ...
    case ASTRING:
        sym = pkglookup("strhash", runtimepkg);
        break;
    case AFLOAT32:
        sym = pkglookup("f32hash", runtimepkg); // float32のハッシュ関数をルックアップ
        break;
    case AFLOAT64:
        sym = pkglookup("f64hash", runtimepkg); // float64のハッシュ関数をルックアップ
        break;
    case ACPLX64:
        sym = pkglookup("c64hash", runtimepkg);  // complex64のハッシュ関数をルックアップ
        break;
    case ACPLX128:
        sym = pkglookup("c128hash", runtimepkg); // complex128のハッシュ関数をルックアップ
        break;
    default:
        sym = typesymprefix(".hash", t);
        break;
}

hashfor関数は、特定の型tのハッシュ計算に使用されるランタイム関数を決定します。この変更により、AFLOAT32などの新しい型定数に対応する、ランタイムに実装された専用のハッシュ関数（例: runtime.f32hash）が参照されるようになりました。

genhash 関数

void genhash(Sym *sym, Type *t) {
    // ... 既存のロジック ...
    // *h *= mul
    // Same multipliers as in runtime.memhash.
    if(widthptr == 4)
        mul = 3267000013LL;
    else
        mul = 23344194077549503LL;
    n->nbody = list(n->nbody,
        nod(OAS,
            nod(OIND, nh, N),
            nod(OMUL, nod(OIND, nh, N), nodintconst(mul))));
    // ... 既存のロジック ...
}

genhash関数は、コンパイラがハッシュ関数を生成する際に使用されます。この変更は、ハッシュ値の計算中に特定の乗算器（mul）を適用するロジックを追加しています。これは、ランタイムのmemhash関数で使用されているものと同じ乗算器であり、ハッシュの分布を改善し、衝突を減らすことでマップのパフォーマンスを向上させることを目的としています。

src/pkg/runtime/alg.c

等価性チェック関数

void runtime·f32equal(bool *eq, uintptr s, void *a, void *b) {
    USED(s);
    *eq = *(float32*)a == *(float32*)b; // Goのfloat32の==演算子を使用
}

void runtime·f64equal(bool *eq, uintptr s, void *a, void *b) {
    USED(s);
    *eq = *(float64*)a == *(float64*)b; // Goのfloat64の==演算子を使用
}

void runtime·c64equal(bool *eq, uintptr s, void *a, void *b) {
    Complex64 *ca, *cb;
    USED(s);
    ca = a;
    cb = b;
    *eq = ca->real == cb->real && ca->imag == cb->imag; // 実部と虚部をそれぞれ比較
}

void runtime·c128equal(bool *eq, uintptr s, void *a, void *b) {
    Complex128 *ca, *cb;
    USED(s);
    ca = a;
    cb = b;
    *eq = ca->real == cb->real && ca->imag == cb->imag; // 実部と虚部をそれぞれ比較
}

これらの関数は、マップのキーとして使用される浮動小数点数および複素数の等価性をチェックします。Goの==演算子のセマンティクスに従い、+0と-0は等しいと判断され、NaNは自身を含めいかなる値とも等しくないと判断されます。複素数の場合は、実部と虚部の両方が等しい場合にのみ全体が等しいと判断されます。

ハッシュ関数

void runtime·f32hash(uintptr *h, uintptr s, void *a) {
    uintptr hash;
    float32 f;

    USED(s);
    f = *(float32*)a;
    if(f == 0)
        hash = 0;  // +0, -0 は同じハッシュ値0
    else if(f != f)
        hash = runtime·fastrand1();  // NaNはランダムなハッシュ値
    else
        hash = *(uint32*)a; // それ以外はビット表現をハッシュ値として使用
    *h ^= (*h ^ hash ^ 2860486313U) * 3267000013U; // 最終的なハッシュ計算
}

void runtime·f64hash(uintptr *h, uintptr s, void *a) {
    uintptr hash;
    float64 f;
    uint64 u;

    USED(s);
    f = *(float32*)a; // ここはfloat64の間違い？元のコードではfloat32になっているが、f64hashなのでfloat64が正しいはず
    if(f == 0)
        hash = 0;   // +0, -0 は同じハッシュ値0
    else if(f != f)
        hash = runtime·fastrand1();  // NaNはランダムなハッシュ値
    else {
        u = *(uint64*)a; // float64のビット表現
        if(sizeof(uintptr) == 4) // 32bitシステムの場合
            hash = ((uint32)(u>>32) ^ 2860486313) * (uint32)u;
        else // 64bitシステムの場合
            hash = u;
    }
    if(sizeof(uintptr) == 4)
        *h = (*h ^ hash ^ 2860486313U) * 3267000013U;
    else
        *h = (*h ^ hash ^ 33054211828000289ULL) * 23344194077549503ULL; // 最終的なハッシュ計算
}

void runtime·c64hash(uintptr *h, uintptr s, void *a) {
    USED(s);
    runtime·f32hash(h, 0, a); // 実部のハッシュ
    runtime·f32hash(h, 0, (float32*)a+1); // 虚部のハッシュ
}

void runtime·c128hash(uintptr *h, uintptr s, void *a) {
    USED(s);
    runtime·f64hash(h, 0, a); // 実部のハッシュ
    runtime·f64hash(h, 0, (float64*)a+1); // 虚部のハッシュ
}

これらのハッシュ関数は、浮動小数点数および複素数の特性を考慮してハッシュ値を生成します。

  • +0と-0は同じハッシュ値（0）を生成することで、マップ内で同じエントリにマッピングされるようにします。
  • NaNは、NaN != NaNという特性を反映するために、runtime.fastrand1()によってランダムなハッシュ値を生成します。これにより、異なるNaN値がマップ内で異なるエントリとして扱われることが保証されます。また、同じNaN値であっても、検索のたびに異なるハッシュ値が生成されるため、マップのルックアップは失敗します。これはIEEE 754のNaNのセマンティクスに合致しています。
  • 複素数のハッシュは、実部と虚部それぞれの浮動小数点ハッシュを組み合わせて計算されます。

runtime.algarray

runtime·algarray[] = {
    // ... 既存のアルゴリズム ...
    [AINTER]	{ runtime·interhash, runtime·interequal, runtime·interprint, runtime·intercopy },
    [ANILINTER]	{ runtime·nilinterhash, runtime·nilinterequal, runtime·nilinterprint, runtime·nilintercopy },
    [ASLICE]	{ runtime·nohash, runtime·noequal, runtime·memprint, runtime·slicecopy },
    [AFLOAT32]	{ runtime·f32hash, runtime·f32equal, runtime·memprint, runtime·memcopy }, // float32のアルゴリズムを登録
    [AFLOAT64]	{ runtime·f64hash, runtime·f64equal, runtime·memprint, runtime·memcopy }, // float64のアルゴリズムを登録
    [ACPLX64]	{ runtime·c64hash, runtime·c64equal, runtime·memprint, runtime·memcopy },  // complex64のアルゴリズムを登録
    [ACPLX128]	{ runtime·c128hash, runtime·c128equal, runtime·memprint, runtime·memcopy }, // complex128のアルゴリズムを登録
    // ... 既存のアルゴリズム ...
}

runtime.algarrayは、Goの各型がマップのキーとして使用される際に、どのハッシュ関数、等価性チェック関数、プリント関数、コピー関数を使用するかを定義するテーブルです。この変更により、新しく実装された浮動小数点数および複素数用の関数がそれぞれの型定数に対応付けられ、ランタイムがマップ操作時に適切な関数をディスパッチできるようになりました。

test/map.go

func testfloat() {
    // Test floating point numbers in maps.
    // Two map keys refer to the same entry if the keys are ==.
    // The special cases, then, are that +0 == -0 and that NaN != NaN.

    {
        var (
            pz   = float32(0)
            nz   = math.Float32frombits(1 << 31) // -0.0
            nana = float32(math.NaN())
            nanb = math.Float32frombits(math.Float32bits(nana) ^ 2) // 異なるビット表現のNaN
        )

        m := map[float32]string{
            pz:   "+0",
            nana: "NaN",
            nanb: "NaN",
        }
        // +0と-0が同じキーとして扱われることを確認
        if m[nz] != "+0" {
            fmt.Println("float32 map does not treat -0 and +0 as equal for read")
        }
        m[nz] = "-0" // -0で書き込むと+0のエントリが更新される
        if m[pz] != "-0" {
            fmt.Println("float32 map does not treat -0 and +0 as equal for write")
        }
        // NaNがルックアップできないことを確認
        if _, ok := m[nana]; ok {
            fmt.Println("float32 map allows NaN lookup (a)")
        }
        if _, ok := m[nanb]; ok {
            fmt.Println("float32 map allows NaN lookup (b)")
        }
        // NaNが異なるキーとして扱われるため、マップの長さが増えることを確認
        if len(m) != 3 { // 初期状態: +0, nana, nanb の3エントリ
            fmt.Println("float32 map should have 3 entries:", m)
        }
        m[nana] = "NaN" // 新しいNaNを追加するとエントリが増える
        m[nanb] = "NaN" // 新しいNaNを追加するとエントリが増える
        if len(m) != 5 { // +0, nana(1), nanb(1), nana(2), nanb(2) の5エントリ
            fmt.Println("float32 map should have 5 entries:", m)
        }
    }
    // float64, complex64, complex128についても同様のテストが続く
}

test/map.goに追加されたtestfloat関数は、このコミットの変更が正しく機能していることを検証するための重要なテストです。特に、+0と-0がマップキーとして等価に扱われること、そしてNaNが常に非等価に扱われ、異なるNaN値がマップ内で異なるエントリとして格納されることを確認しています。これにより、GoのマップがIEEE 754浮動小数点標準のセマンティクスに厳密に準拠していることが保証されます。

関連リンク

参考にした情報源リンク