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

このコミットは、Goランタイムにおける32ビットマシン上でのfloat64型のハッシュ計算の不具合を修正するものです。具体的には、float64値をハッシュ化する際に、その下位32ビットを乗算に使用していたことが問題でした。特に、小さな整数値がfloat64として表現される場合、その下位32ビットが0になることが多く、ハッシュの衝突を引き起こしやすかったため、この計算方法が変更されました。

コミット

commit facee93a8627881ae39abda13cba115274fe20cf
Author: Russ Cox <rsc@golang.org>
Date:   Mon Feb 6 11:24:34 2012 -0500

    runtime: fix float64 hash on 32-bit machine
    
    Multiplying by the low 32 bits was a bad idea
    no matter what, but it was a particularly unfortunate
    choice because those bits are 0 for small integer values.
    
    Fixes #2883.
    
    R=ken2
    CC=golang-dev
    https://golang.org/cl/5634047

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

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

元コミット内容

runtime: fix float64 hash on 32-bit machine

Multiplying by the low 32 bits was a bad idea
no matter what, but it was a particularly unfortunate
choice because those bits are 0 for small integer values.

Fixes #2883.

変更の背景

この変更は、Goランタイムが32ビットアーキテクチャ上でfloat64（倍精度浮動小数点数）のハッシュ値を計算する際に発生していた不具合を修正するために行われました。

問題の核心は、ハッシュ計算ロジックにおいて、float64値を構成する64ビットのデータのうち、下位32ビットを乗数として使用していた点にありました。float64はIEEE 754標準に基づいており、64ビットで数値を表現します。特に、小さな整数値（例: 1.0, 2.0など）がfloat64として表現される場合、そのバイナリ表現の下位32ビットがすべて0になることがよくあります。

元のハッシュ計算式では、この下位32ビットを乗数として使用していたため、下位32ビットが0であるfloat64値に対しては、乗算結果が0になり、ハッシュ値の多様性が失われ、多くの異なるfloat64値が同じハッシュ値を持つ「衝突」が発生しやすくなっていました。ハッシュ衝突が多いと、ハッシュテーブル（Goのmap型など）のパフォーマンスが著しく低下する可能性があります。

この問題は、Goの内部イシュートラッカーで#2883として報告されており、このコミットはその修正を目的としています。

前提知識の解説

1. float64 (倍精度浮動小数点数)

float64は、Go言語における倍精度浮動小数点数を表す型です。IEEE 754標準に従って64ビットで数値を表現します。この64ビットは、符号部、指数部、仮数部に分かれており、非常に広範囲の数値を高い精度で表現できます。

2. ハッシュ関数とハッシュテーブル

• ハッシュ関数: 任意のサイズのデータを固定サイズのビット列（ハッシュ値）に変換する関数です。理想的なハッシュ関数は、異なる入力に対して異なるハッシュ値を生成し、ハッシュ値が均等に分布するように設計されます。
• ハッシュテーブル: ハッシュ関数を用いてキーと値を対応付けるデータ構造です。Go言語のmap型はハッシュテーブルの一種です。ハッシュテーブルでは、キーのハッシュ値を使ってデータが格納される場所を決定します。ハッシュ衝突（異なるキーが同じハッシュ値を持つこと）が少ないほど、データの検索、挿入、削除が高速になります。

3. 32ビットマシンと64ビットマシン

• 32ビットマシン: CPUが一度に処理できるデータ幅が32ビットのアーキテクチャです。ポインタやuintptr型も32ビット幅になります。
• 64ビットマシン: CPUが一度に処理できるデータ幅が64ビットのアーキテクチャです。ポインタやuintptr型も64ビット幅になります。

この違いは、uint64のような64ビットの値を32ビット環境で扱う際に重要になります。32ビット環境では、64ビットの値を直接レジスタに格納できないため、2つの32ビットレジスタに分割して扱うなどの工夫が必要です。

4. ビット演算子

• >> (右シフト): ビットを右に指定された数だけシフトします。u >> 32は、uint64型のuを右に32ビットシフトし、上位32ビットを下位に移動させます。
• ^ (XOR: 排他的論理和): 2つのビットが異なる場合に1を、同じ場合に0を返します。ハッシュ関数では、異なるビット列を混ぜ合わせることで、ハッシュ値の分布を均一にする目的でよく使用されます。
• * (乗算): 数値の乗算です。ハッシュ関数では、値を「拡散」させる目的で使われることがありますが、特定の入力パターンで0になるなどの問題を引き起こす可能性もあります。

5. Goランタイム (alg.c)

alg.cはGoランタイムの一部であり、Goの組み込み型（プリミティブ型）のハッシュ計算アルゴリズムなどが実装されています。このファイルはC言語で書かれており、Goプログラムの実行を支える低レベルな処理を担っています。

技術的詳細

このコミットの技術的詳細は、float64のハッシュ計算ロジックの変更に集約されます。

元のコードでは、32ビットマシン上でfloat64（uint64として扱われるu）のハッシュを計算する際に、以下の式を使用していました。

hash = ((uint32)(u>>32) ^ 2860486313) * (uint32)u;

この式には2つの問題がありました。

1. *(uint32)u の問題: uはuint64ですが、(uint32)uとキャストすることで、uの下位32ビットのみが取得されます。前述の通り、小さな整数値がfloat64として表現される場合、uの下位32ビットが0になることが多く、その結果、*(uint32)uが0になります。ハッシュ計算において0を乗算すると、結果が0になるか、ハッシュ値の多様性が失われ、衝突が増加します。
2. 乗算の性質: ハッシュ関数において乗算は値を拡散させるために使われることがありますが、特定の定数との乗算は、入力値のパターンによってはハッシュ衝突を誘発しやすい場合があります。

新しいコードでは、この式が以下のように変更されました。

hash = ((uint32)(u>>32) * 3267000013UL) ^ (uint32)u;

この変更により、以下の点が改善されました。

1. 乗算対象の変更: (uint32)(u>>32)（uの上位32ビット）に3267000013ULという新しい定数を乗算しています。この定数は、ハッシュ値の分布を均一にするために選ばれた大きな素数である可能性が高いです。
2. XOR演算の導入: (uint32)u（uの下位32ビット）との結合に、乗算ではなくXOR演算を使用しています。XOR演算は、ビットレベルで値を混ぜ合わせるのに非常に効果的であり、ハッシュ衝突を減らし、ハッシュ値の均一な分布を促進します。これにより、下位32ビットが0であっても、ハッシュ値全体が0になることを防ぎ、ハッシュの品質が向上します。

この修正により、32ビットマシン上でのfloat64のハッシュ計算がより堅牢になり、特に小さな整数値のfloat64表現におけるハッシュ衝突の問題が解消されました。

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

変更はsrc/pkg/runtime/alg.cファイル内のruntime·f64hash関数にあります。

--- a/src/pkg/runtime/alg.c
+++ b/src/pkg/runtime/alg.c
@@ -271,7 +271,7 @@ runtime·f64hash(uintptr *h, uintptr s, void *a)\n 	else {\n 		u = *(uint64*)a;\n 		if(sizeof(uintptr) == 4)\n-\t\t\thash = ((uint32)(u>>32) ^ 2860486313) * (uint32)u;\n+\t\t\thash = ((uint32)(u>>32) * 3267000013UL) ^ (uint32)u;\n \t\telse\n \t\t\thash = u;\n \t}\

コアとなるコードの解説

変更された行は、sizeof(uintptr) == 4、つまり32ビットマシンである場合のfloat64のハッシュ計算ロジックです。

• 変更前:

  hash = ((uint32)(u>>32) ^ 2860486313) * (uint32)u;
  

  この行では、u（float64をuint64として解釈したもの）の上位32ビットを右シフトし、特定の定数2860486313とXOR演算を行った後、その結果とuの下位32ビット（(uint32)u）を乗算していました。問題は、uが小さな整数値の場合に(uint32)uが0になり、ハッシュの品質が低下することでした。

• 変更後:

  hash = ((uint32)(u>>32) * 3267000013UL) ^ (uint32)u;
  

  この行では、計算方法が大きく変更されています。

  1. uの上位32ビット（(uint32)(u>>32)）に、新しい定数3267000013ULを乗算しています。この定数は、ハッシュ値の分布を改善するための「マジックナンバー」として機能します。ULサフィックスは、このリテラルがunsigned long型であることを示しており、32ビット環境ではuint32に相当します。
  2. その結果と、uの下位32ビット（(uint32)u）をXOR演算で結合しています。これにより、下位32ビットが0であっても、ハッシュ値全体が0になることを防ぎ、ハッシュの多様性が確保されます。XORはビットを効果的に混ぜ合わせるため、ハッシュ衝突の可能性を低減します。

この修正により、32ビット環境におけるfloat64のハッシュ計算がより堅牢で均一な分布を持つようになり、ハッシュテーブルのパフォーマンスが向上しました。

関連リンク

• Go Change-list: https://golang.org/cl/5634047

参考にした情報源リンク

• Go Change-list: https://golang.org/cl/5634047
• IEEE 754 (浮動小数点数): https://ja.wikipedia.org/wiki/IEEE_754 (一般的な情報源として)
• ハッシュ関数: https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E9%96%A2%E6%95%B0 (一般的な情報源として)