自動化された整数ハッシュ関数探索技術

 (github.com/skeeto)
3 ポイント 投稿者 GN⁺ 2024-05-06 | 1件のコメント | WhatsAppで共有
  • Hash Function Prospectorは、整数ハッシュ関数をランダムに大量生成してJITコンパイルし、avalancheの挙動を評価したうえで、現時点で最良の関数をC構文で出力するツール
  • 評価には、単一の入力ビットを反転させたときに平均して固定されたまま残る出力ビット数であるavalanche scoreを使用し、低いほど良く、理想値は0
  • 探索対象は32ビットと64ビットの整数ハッシュ関数で、JITコンパイラのためツールの実行はx86-64のみ対応だが、発見された関数は他の環境でも利用できる
  • 発見された主要な関数はxorshift-multiply-xorshift構成を使い、2ラウンドのlowbias32はMurmurHash3 32-bit finalizerよりわずかに低いbiasを示し、3ラウンドのtriple32は理論上のbias限界に近い
  • 正確なbias測定は32ビット関数に対して-Eと-eで実行でき、16ビットハッシュは別ツールhp16が担当し、Cの整数昇格規則に注意が必要

Hash Function Prospectorの役割

  • Hash Function Prospectorは、自動化された整数ハッシュ関数発見ツール
  • ランダムに数十億個の整数ハッシュ関数を生成し、それをJITコンパイルしたうえでavalancheの挙動を評価する
  • 生成された関数のうち、現時点で最も良い関数はC構文で出力される
  • 関連記事としてProspecting for Hash Functionsがリンクされている

評価基準と対応範囲

  • avalanche scoreは、入力ビットを1つ反転させたときに平均して固定されたまま残る出力ビット数
    • スコアは低いほど良い
    • 理想的にはすべての出力ビットが50%の確率で反転し、scoreは0になる
  • Prospectorは32ビットおよび64ビットの整数ハッシュ関数を生成できる
  • 全オプションは-hの使い方で確認するようになっている
  • JITコンパイラのため、ツール自体はx86-64のみ対応
    • ただし、発見されたハッシュ関数はどこでも利用できる

探索に使う可逆演算

  • 生成器は、選択された9種類の可逆演算から関数をランダムに構成する
  • 演算一覧は以下の通り
    • x = ~x
    • x ^= constant
    • x *= constant | 1
    • x += constant
    • x ^= x >> constant
    • x ^= x << constant
    • x += x << constant
    • x -= x << constant
    • x <<<= constant
    • x = bswap(x)
  • 技術的にはx = ~xはx ^= constantで表現できるが、そのXOR定数を生成器が偶然選ぶ可能性は低いため、別の演算として扱う

発見された32ビットハッシュ関数

  • 2ラウンド関数

    • 有用な発見関数群の1つは、2ラウンドのxorshift-multiply-xorshift構成
    • TheIronBornは組合せ最適化を使ってこの構成の既知の最適パラメータを見つけ、結果は[16 21f0aaad 15 d35a2d97 15] = 0.10760229515479501
    • lowbias32は32ビットの2ラウンド順列で、biasが低く、MurmurHash3 32-bit finalizerよりごくわずかに低いbiasを示す
    • lowbias32のexact biasは0.17353355999581582
    • 構成はProspectorが発見し、パラメータはhill climbingと遺伝的アルゴリズムで調整された
    • 逆関数lowbias32_rも提供されている
    • prospector32はProspectorだけを使って発見された関数
    • exact biasは0.34968228323361017
    • 前述のlowbias32よりbiasが大きい
    • 代替の乗算定数をランダム探索するには、次のようにパターンを指定する
    • ./prospector -p xorr:15,mul,xorr:12,mul,xorr:15

  • 3ラウンド関数

    • 同じ構成にmultiply-xorshiftラウンドをもう1つ追加すると、慎重に選んだパラメータで理論上のbias限界に到達できる
    • triple32のexact biasは0.020888578919738908
    • READMEでは、これをすべての32ビット整数のランダム順列のような完全なPRFと区別できないと説明している
    • 逆関数triple32_rも提供されている
    • 3ラウンド定数の一覧には、0.020888578919738908から約0.022984943828687553までの低biasな結果が含まれる
    • triple32の前にインクリメント演算を付けたtriple32incは、hash(0) = 0の問題を崩し、biasも少し低くする
    • exact biasは0.020829410544597495
    • 逆関数triple32inc_rは最後にx--を実行する

exact bias測定

  • -Eモードは、与えられたハッシュ関数のbiasを評価する
  • デフォルトでは、Prospectorはbiasを高速に評価するため推定値を使う
    • この推定は非決定的で、結果にはノイズが多い
  • 全探索でexact biasを測定するには-eオプションを使う
  • 検査する関数は2つの方法で定義できる
    • -pとパターンで定義
    • -lとhash()関数を含む共有ライブラリで定義
  • 共有ライブラリ方式により、Prospectorの制限された関数表現では表せないハッシュ関数もテストできる
  • デフォルト入力は32ビットハッシュ関数として扱われる
  • -8スイッチは64ビット関数を推定方式でテストする
    • 64ビットハッシュ関数は時間がかかりすぎるため、exact exhaustive testはない

16ビットハッシュ用hp16

  • 16ビットハッシュは制約が異なるため、別ツール**hp16**が提供されている
  • hp16は32ビット・64ビットのProspectorとは異なり完全に移植可能で、ほぼすべてのシステムで実行できる
  • hp16は128KiB s-boxの生成と評価も可能
  • 16ビットハッシュが高速な乗算命令を持たないマシンで必要になる場合があるため、探索中に特定の演算を省略するオプションもある
    • -m
    • -r

16ビットの結果とC実装上の注意点

  • 現時点までの16ビット結果例は以下の通り
    • 2ラウンドxorshift-multiply hash16_xm2: bias 0.0085905051336723701
    • 3ラウンドxorshift-multiply hash16_xm3: bias 0.0045976709018820602
    • 乗算なしのhash16_s6: bias 0.023840118344741465
  • 乗算なしのhash16_s6は、特定のxorshift-multiply形式と同一だと示されている
  • hp16 -Xn3で短時間探索した良好な3ラウンドxorshiftハッシュは、hp16 -Sの良好なs-boxに近い近似
  • 16ビット演算をCで書くときは、整数昇格規則に注意が必要
    • 例えば32ビット実装では、unsigned 16ビットのオペランドがsigned 32ビット整数に昇格されることがある
    • この場合、特定の状況で誤った結果になる可能性がある
    • このプログラムが出力するCコードは、必要な箇所で16ビット演算をunsigned intへ昇格するよう注意している

関連記事

1件のコメント

 
GN⁺ 2024-05-06
Hacker News のコメント

  • 個人的には面識はないが、彼のコードは気に入っている
    特に JSON ライブラリ https://github.com/skeeto/pdjson、オプション解析ライブラリ https://github.com/skeeto/optparse と https://github.com/skeeto/getopt、分岐なし UTF-8 デコーダ https://github.com/skeeto/branchless-utf8、ロックフリーのスタック https://github.com/skeeto/lstack、トライ木ライブラリ https://github.com/skeeto/trie が良い
    上記のプロジェクトがすべて The Unlicense で配布されているというライセンスの好みも気に入っている

    • Skeeto は伝説級だ。私の基準では Fabrice Bellard と同じレベルにいる
      GitHub で何年もフォローしているが、いつも興味深い小さくて奇妙なニッチツールをぽんぽん出してくる。たとえば Branchless UTF-8 が有名だ
    • 彼は elfeed https://github.com/skeeto/elfeed の作者でもある。“An Emacs web feeds client”で、そのミニマルな実装から多くの着想を得た

  • こんにちは、私が MurmurHash を作った者です。興味深い取り組みで、乗算・シフト・XOR 方式がこれほど長くうまく持ちこたえているのは面白い

    • XOR シフトは乗算の二つの弱点を相殺する。上位ビットにはそれより上で影響を与えるビットがなく、下位ビットにはそれより下で影響を受けるビットがない、という点だ
    • MurmurHash と同様に、これらも非暗号学的ハッシュを意図しているように見える
      ただし avalanche + bias のアイデアには、かなり抜けている部分があるように思う。たとえば最後に挙げられている triple32 関数の正確な bias は 0.020888578919738908 だが、FabriceNeyret2 が ShaderToy に実装すると、このような画像になる: https://www.shadertoy.com/view/WttXWX または https://i.imgur.com/qU2P5rx.png
      ところが単純なノーマルマップ勾配微分をしてみると、目に付く「結晶」状の線がかなり多く見える。こうした稜線状のものを指す技術用語がたぶんあるはずだ: https://i.imgur.com/IHWT1GM.png
      付け加えると、このアイデア全体はすでに5年ほど前のものではないかと思う: https://nullprogram.com/blog/2018/07/31/

  • 良いハッシュ関数を開発した経験から、自動ハッシュ探索のアイデアをよく考えていた
    こういう取り組みを見るのは素晴らしい。Frank J. T. Wojcik が作った古いハッシュテストスイートを大幅に改善し高速化した SMHasher3 とつなげて、出力結果を自動評価できるとよさそうだ。速度のためにテストの一部だけを使い、素早く失敗扱いにすることもできる
    64ビットや128ビットのハッシュへ拡張してもよいが、当然ながら探索空間はさらに大きくなる。関連して、Rain で使う値を選ぶために、64ビット素数の乗算における avalanche を測定する NodeJS コードを書いたこともある
    [Rain]: https://github.com/dosyago/rain
    [SMHasher3]: https://gitlab.com/fwojcik/smhasher3

  • これを RISC-V ビット操作拡張で使える演算へ一般化すると面白そうだ。将来それらの命令がもっと広く普及したときに使える強力な関数を見つけられるかもしれない
    キャリーなし乗算も可逆演算の集合を拡張でき、一部の既存ハードウェアでは高速だ。CRC もある程度関連するが、より広いハードウェア集合で利用でき、CLMUL が見つけられるものの厳密な部分集合であるはずだ
    ハッシュの用途の多くはハッシュ値の最下位ビットや最上位ビットだけを気にするので、最上位/最下位ビット区間の bias や、いくつかの数で割った余りを評価してみるのも興味深い。出力全体を基準にすると偏りがないように見える関数でも、出力全体を見ない指標や ASCII テキストのような非一様な入力では、良くなったり悪くなったりすることがある

  • なぜこれがすごくて、どこで使われるのか説明してもらえる？

    • ハッシュ関数を作るための命令列を生成し、そのハッシュ関数がどれくらい良いかを評価するツールに見える
      目標指標は、入力ビットが1つ変わったときに、できるだけ多くの出力ビットができるだけランダムのように変わるかどうかに置いているようだ。生成したものの中で最も良いハッシュ関数のCコードを出力する
      なので、ハッシュ関数が必要だが既存の関数が十分に良くないと思う場合や、ハッシュ関数を研究していて新しい構造のアイデアが必要なときに有用。コード生成自体もすごいし、ランダムにやるのはさらにすごい遺伝的プログラミングへの第一歩でもある。そして人間は約15年前から、コンピュータにCPUサイクルを消費させて、ほとんど使われないハッシュを計算させることが好きなようだ
    • こうした関数はハッシュテーブルに不可欠。関連する名前としてハッシュマップ、ハッシュセットもある
      ハッシュテーブルは、多くのアルゴリズムを単純かつ効率的に実装できるようにする優れたデータ構造。この効率は、データに対して小さく、例えば32ビットや64ビットで、ほぼ一意なハッシュを作れるかどうかに依存する
      例えばユーザー名をハッシュするとき、名前の先頭文字のASCIIコードだけを使うと、多くのユーザー名が同じ数値にマッピングされてうまく動作しない。これを衝突といい、衝突が多いとハッシュテーブルは非常に非効率になる
      より良い方法は、ユーザー名全体からビットを取り出して何らかの形で混ぜ合わせ、throwaway_1237とthrowaway_12373が互いに異なる数値になるようにすること。ハッシュ関数がこのマッピングを行い、avalanche性質は衝突を避ける仕事をどれくらいうまくこなすかを説明する
      通常、実際のハッシュ関数がどれくらい速いかと、衝突回避をどれくらいうまく行うかの間にはトレードオフがある。世界レベルのハッシュ関数は、奇妙な定数を掛けたり、XORしたり、シフトしたりするなど、かなり奇妙に見えるもので、人間がこうした難解な関数を見て性能を推測するのは非常に難しい
      このコードは複数のハッシュ関数をランダムに試し、互いに競わせる。うまくいけば、多くの言語やライブラリ全体で使われる中核的なデータ構造の実性能を改善できるので、すごい
    • 整数用のハッシュ関数なので、集合やマップで高速な整数ハッシュが必要なときに使える。関数同士が十分に異なる形で分岐するなら、Bloomフィルタ用の高速ハッシュも提供する

  • 数週間前にGoで1brcを実装したのだが https://github.com/infogulch/1brc-go、このリポジトリを見て、各観測所が衝突なしに自分のバケットへ入るようなカスタム完全ハッシュ関数を探してみようという着想を得た
    その後、プログラム開始前にデータに合わせてハッシュ関数をカスタマイズしてはいけないというルールを見て、このアイデアは取り下げた
    任意定数、開始値、乗算定数、シフト/ローテート量などを確認し、衝突バケット数と衝突数を基準に、それまでに見つかった最良の定数を出力するテスト装置を作った。充填率約40%で、たった1つのバケットに2つの値だけが衝突する程度まで減らせたと思う。興味深いことに、最も性能の良い定数群は他の定数とは無関係に似たシフト位置数を含んでいたので、結局それらの値はハードコードした

  • 独自の入力データ生成器を入れられるなら本当に面白そう。実際にはランダムなバイナリデータではなく、何らかの形で構造化されたデータが多く、その構造のおかげで非常に良いハッシュ関数を得られるかもしれない

  • 可逆演算に制限すると数学的に良い点はあるが、同時に多くのものを排除することにもなる
    似たようなことをしたときは、入力集合を事前に知っている完全ハッシュを考えていた。一般的なアプローチは定数配列を使うが、特に入力がすでに小さな整数なら、さらに圧縮できるか見たかった。当然、hash -= hash >> gap_indexのような形で可能
    そこで、おそらく100個ほどのプリミティブ演算のリストを使ってみた。一部は互いに重複しているが、個別に考えると有用なものだった。そのうち退屈して、プロジェクトとしては何もしなかった

    • 「可逆演算に制限すると数学的に良い点」というのは何で、この文脈で可逆演算はなぜ望ましいのか？

  • 正確に何をしているのかよく分からない。史上最高を探しているのか？ そうでないなら、実行するたびに最高値がなぜ変わるのかが気になる
    また、特定範囲の整数値、例えば10,000から200,000の間だけが出ると分かっているときに、その値を最適な個数のハッシュバケットへ入れる良いハッシュ関数を発見する仕組みを知っている人がいるのかも気になる

    • その実行で試した値の中の最高を見つけるために、値をランダムに試す方式
      1回の実行で探索空間をすべて調べ、絶対的な最適値を見つけるのは現実的に不可能で、試行順序もランダムなので実行ごとに値が変わることがある
      単に「良い」ハッシュが必要なら、ほぼ常に一般的なハッシュ関数を使うのが最善。数値が極端に大きく範囲が非常に小さいなら、最小値が再び0になるようにオフセットを適用して、より小さく高速なハッシュを使える。正確な範囲に対する「完璧な選択」を見つけたいなら、この種のランダムなアプローチが最も近いと思うし、テストをその区間で行うように変更すればよい

  • 2回の乗算に同じ定数を使えばコードサイズが小さくなり、計算も少し速くなるのではないかと気になる
    StackOverflowの回答も更新した: https://stackoverflow.com/questions/664014/what-integer-hash...