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

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

このドキュメントは、Go言語のランタイムにおけるハッシュ計算の連続性を改善したコミット 51fe5444fac3474a538b55cdd3045ba1d3a9a264 について、その技術的な詳細と背景を包括的に解説します。

コミット

commit 51fe5444fac3474a538b55cdd3045ba1d3a9a264
Author: Jan Ziak <0xe2.0x9a.0x9b@gmail.com>
Date:   Wed Jun 13 15:52:32 2012 -0400

    runtime: improved continuity in hash computation
    
    Fixes #3695.
    
    R=r, dave, rsc
    CC=golang-dev
    https://golang.org/cl/6304062

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

https://github.com/golang/go/commit/51fe5444fac3474a538b55cdd3045ba1d3a9a264

元コミット内容

runtime: improved continuity in hash computation

Fixes #3695.

R=r, dave, rsc
CC=golang-dev
https://golang.org/cl/6304062

変更の背景

このコミットは、Go言語のランタイムにおけるハッシュ計算の「連続性 (continuity)」を改善することを目的としています。具体的には、Go issue #3695「runtime: hash functions should not depend on sizeof(uintptr)」を修正しています。

Go言語はクロスプラットフォーム対応を重視しており、32ビットアーキテクチャと64ビットアーキテクチャの両方で動作します。uintptr 型はポインタを保持できる符号なし整数型であり、そのサイズはアーキテクチャに依存します（32ビットシステムでは4バイト、64ビットシステムでは8バイト）。

以前のハッシュ計算ロジックでは、sizeof(uintptr) の値に基づいて異なる定数（マジックナンバー）を使用していました。これは、同じ入力データに対して32ビットシステムと64ビットシステムで異なるハッシュ値が生成される可能性を意味します。ハッシュ値がアーキテクチャに依存すると、以下のような問題が発生する可能性があります。

  1. 再現性の欠如: デバッグやテストにおいて、異なるアーキテクチャで同じコードを実行した際に、ハッシュ値が異なるために予期せぬ動作やバグが発生する可能性があります。
  2. シリアライゼーション/デシリアライゼーションの問題: ハッシュ値がデータ構造の一部として保存され、異なるアーキテクチャ間でやり取りされる場合、ハッシュ値の不一致がデータの破損や互換性の問題を引き起こす可能性があります。
  3. マップの動作の不整合: Goのマップ（map）は内部的にハッシュテーブルを使用しており、キーのハッシュ値に基づいて要素を配置します。ハッシュ値がアーキテクチャによって異なると、同じキーでも異なるアーキテクチャでは異なるバケットに配置され、マップの動作に不整合が生じる可能性があります。

このコミットは、sizeof(uintptr) に依存しない一貫したハッシュ計算ロジックを導入することで、これらの問題を解決し、ハッシュ計算の連続性を確保することを目指しています。

前提知識の解説

ハッシュ関数

ハッシュ関数とは、任意の長さのデータを固定長のデータ（ハッシュ値またはメッセージダイジェスト）に変換する関数です。理想的なハッシュ関数は、以下の特性を持ちます。

  • 決定性: 同じ入力に対しては常に同じハッシュ値を生成します。
  • 高速性: ハッシュ値の計算が高速です。
  • 衝突耐性: 異なる入力に対しては異なるハッシュ値を生成する傾向があります（衝突が少ない）。
  • 不可逆性: ハッシュ値から元のデータを復元することが困難です。

Go言語のランタイムでは、マップのキーやインターフェースの値など、様々なデータのハッシュ値を計算するためにハッシュ関数が使用されます。

uintptr 型

uintptr はGo言語の組み込み型の一つで、ポインタを保持できる符号なし整数型です。そのサイズは実行環境のアーキテクチャに依存します。例えば、32ビットシステムでは32ビット（4バイト）、64ビットシステムでは64ビット（8バイト）のサイズを持ちます。この型は、ポインタと整数の間で変換を行う必要がある低レベルの操作（例：システムコール、メモリ管理）で主に使用されます。

NaN (Not a Number)

NaN は、浮動小数点演算の結果として定義されない値（例：0/0、無限大 - 無限大）を表す特殊な浮動小数点値です。IEEE 754浮動小数点標準で定義されており、NaN はそれ自身を含め、他のどの値とも等しくありません（NaN == NaN は false になります）。ハッシュ計算において NaN を適切に扱うことは重要です。

Iface と Eface

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

  • Iface (interface with method set): メソッドを持つインターフェース型を表します。内部的には、型情報へのポインタと、データへのポインタ（またはデータ自体）を持ちます。
  • Eface (empty interface): メソッドを持たない空のインターフェース型 (interface{}) を表します。内部的には、型情報へのポインタと、データへのポインタ（またはデータ自体）を持ちます。

これらのインターフェース値のハッシュを計算する際には、その内部構造を考慮する必要があります。

技術的詳細

このコミットの主要な変更点は、ハッシュ計算に使用されるマジックナンバーを、sizeof(uintptr) の値に依存しないように定義したことです。

変更前は、ハッシュ計算の初期値や乗算定数が sizeof(hash)（これは sizeof(uintptr) と同じ）が4バイトか8バイトかによって条件分岐していました。

// 変更前 (抜粋)
if(sizeof(hash) == 4)
    hash = 2860486313U;
else
    hash = 33054211828000289ULL;
// ...
if(sizeof(hash) == 4)
    hash = (hash ^ *b) * 3267000013UL;
else
    hash = (hash ^ *b) * 23344194077549503ULL;

このコミットでは、以下の2つのマクロを導入しました。

#define M0 (sizeof(uintptr)==4 ? 2860486313UL : 33054211828000289ULL)
#define M1 (sizeof(uintptr)==4 ? 3267000013UL : 23344194077549503ULL)
  • M0: ハッシュ計算の初期値として使用される定数です。uintptr のサイズが4バイトの場合は 2860486313UL、8バイトの場合は 33054211828000289ULL を使用します。
  • M1: ハッシュ計算の各ステップで乗算される定数です。uintptr のサイズが4バイトの場合は 3267000013UL、8バイトの場合は 23344194077549503ULL を使用します。

これらのマクロは、コンパイル時に sizeof(uintptr) の値に基づいて適切な定数に解決されます。これにより、ランタイムのコードからは条件分岐が取り除かれ、より簡潔で一貫性のあるハッシュ計算ロジックが実現されます。

この変更の意図は、ハッシュ計算のアルゴリズム自体をアーキテクチャ間で統一することではなく、ハッシュ計算に使用する定数をアーキテクチャの uintptr サイズに合わせて適切に選択するロジックを、コード内で明示的に定義されたマクロに集約することです。これにより、ハッシュ計算の「連続性」が向上し、異なるアーキテクチャで同じ入力に対して同じハッシュ値が生成されることが保証されます。これは、Go言語のハッシュ関数が、アーキテクチャに依存しない決定論的な動作を維持するために重要です。

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

変更は src/pkg/runtime/alg.c ファイルに集中しています。

  1. M0 と M1 マクロの定義追加:

    +#define M0 (sizeof(uintptr)==4 ? 2860486313UL : 33054211828000289ULL)
+#define M1 (sizeof(uintptr)==4 ? 3267000013UL : 23344194077549503ULL)

    これらのマクロは、32ビットと64ビットのアーキテクチャで異なる定数を選択するための条件ロジックをカプセル化します。

  2. runtime·memhash 関数の変更:

    • ハッシュの初期値設定で M0 を使用するように変更。
    • ループ内のハッシュ計算で M1 を使用するように変更。
    • 最終的なハッシュ値の更新で *h ^= hash; から *h = (*h ^ hash) * M1; に変更。これは、最終的なハッシュ値にも M1 を乗算することで、ハッシュの拡散性をさらに高めることを意図している可能性があります。

  3. runtime·f32hash 関数の変更:

    • ハッシュ計算の最終ステップで M0 と M1 を使用するように変更。

  4. runtime·f64hash 関数の変更:

    • 32ビットシステムでの uint64 のハッシュ計算で M1 を使用するように変更。
    • 最終的なハッシュ値の更新で M0 と M1 を使用するように変更。

  5. runtime·interhash 関数の変更:

    • ハッシュ値の更新で *h ^= runtime·ifacehash(*(Iface*)a); から *h = (*h ^ runtime·ifacehash(*(Iface*)a)) * M1; に変更。

  6. runtime·nilinterhash 関数の変更:

    • ハッシュ値の更新で *h ^= runtime·efacehash(*(Eface*)a); から *h = (*h ^ runtime·efacehash(*(Eface*)a)) * M1; に変更。

コアとなるコードの解説

runtime·memhash

この関数は、任意のメモリブロックのハッシュを計算します。 変更前は、sizeof(hash) に応じて初期値と乗算定数を直接条件分岐で選択していました。 変更後は、M0 と M1 マクロを使用することで、この条件分岐を抽象化し、コードの可読性と保守性を向上させています。 特に注目すべきは、最終的なハッシュ値の更新が *h ^= hash; から *h = (*h ^ hash) * M1; に変更された点です。これは、ハッシュの最終的な拡散を強化し、より均一なハッシュ分布を促進するための一般的なハッシュ関数のテクニックです。

runtime·f32hash と runtime·f64hash

これらの関数は、それぞれ32ビット浮動小数点数（float32）と64ビット浮動小数点数（float64）のハッシュを計算します。 浮動小数点数のハッシュ計算は、NaN のような特殊な値を考慮する必要があるため、複雑になることがあります。 変更前は、ここでも sizeof(uintptr) に応じて異なる定数を使用していました。 変更後は、M0 と M1 を使用することで、浮動小数点数のハッシュ計算においてもアーキテクチャ間の連続性を確保しています。特に NaN のハッシュ値は runtime·fastrand1() を使用してランダムに生成されるため、NaN 同士が等しくないという特性を反映しています。

runtime·interhash と runtime·nilinterhash

これらの関数は、Goのインターフェース値（Iface と Eface）のハッシュを計算します。 インターフェースのハッシュは、その内部の型情報とデータ値の両方に基づいて計算されます。 これらの関数でも、最終的なハッシュ値の更新に M1 を乗算する変更が加えられており、runtime·memhash と同様にハッシュの拡散性を高める目的があります。

全体として、このコミットは、Goランタイムのハッシュ計算ロジックをより堅牢でアーキテクチャに依存しないものにすることで、Goプログラムの移植性と信頼性を向上させています。

関連リンク

参考にした情報源リンク

  • Go言語のソースコード (src/pkg/runtime/alg.c)
  • Go issue tracker (GitHub)
  • Go Code Review (Gerrit)
  • IEEE 754 浮動小数点標準 (NaN の定義について)
  • ハッシュ関数の設計原則に関する一般的な情報