Help us understand the problem. What is going on with this article?

hash/maphashコードリーディング

hash/maphashコードリーディング

by shibukawa
1 / 22

お前誰よ

  • 渋川よしき
    • フューチャー株式会社で仕事してます
    • いろいろ本を書いたりしています
      • みなさん買ってくださっていますよね?
    • 今日は、家族がいろいろ体調を崩していて時間が取れなかったのでQiitaスライドで

今回の内容

フューチャー社内で行ったコードリーディングの勉強会の再演です。現在、標準ライブラリをみんなで読んで解説しています。
わたしは1.14で追加されたhash/maphashを説明しました。


1.14の変更

ここによると、1.14ではぼちぼち新しいメソッドやRISC-V実験サポート開始や、lock周りやdeferの高速化、テストが後処理ができるようになるなどがあるが、完全な新機能という点では、hash/maphashだけのようなので、ここを見てみることにします。


Readmeの説明

  • バイトシーケンスに対して、ランダムな文字列を生成する。ハッシュテーブルのようなデータ構造を自分で作る人向けに、任意の文字列やバイト列を、分散した数値に変換する。
  • ただし、sha256やsha512のような暗号目的には使えないとされています。64ビットでビット数が少ないので。

フォルダ構造

実体は1ファイル。

maphash.go
maphash_test.go
smhasher_test.go

テストを見る(maphash_test.go)

インタフェースのチェックはもう基本テクですね

// Make sure a Hash implements the hash.Hash and hash.Hash64 interfaces. |
var _ hash.Hash = &Hash{}
var _ hash.Hash64 = &Hash{}

仕様を確認

1文字ずつ入れても、3文字入れても結果は同じ

func TestHashGrouping(t *testing.T) {
    b := []byte("foo")
    h1 := new(Hash)
    h2 := new(Hash)
    h2.SetSeed(h1.Seed())
    h1.Write(b)
    for _, x := range b {
        err := h2.WriteByte(x)
        if err != nil {
            t.Fatalf("WriteByte: %v", err)
        }
    }
    if h1.Sum64() != h2.Sum64() {
        t.Errorf("hash of \"foo\" and \"f\",\"o\",\"o\" not identical")
    }
}

fooを[]byteで入れても、文字列で入れても結果は同じ。

func TestHashBytesVsString(t *testing.T) {
    s := "foo"
    b := []byte(s)
    h1 := new(Hash)
    h2 := new(Hash)
    h2.SetSeed(h1.Seed())
    n1, err1 := h1.WriteString(s)
    if n1 != len(s) || err1 != nil {
        t.Fatalf("WriteString(s) = %d, %v, want %d, nil", n1, err1, len(s))
    }
    n2, err2 := h2.Write(b)
    if n2 != len(b) || err2 != nil {
        t.Fatalf("Write(b) = %d, %v, want %d, nil", n2, err2, len(b))
    }
    if h1.Sum64() != h2.Sum64() {
        t.Errorf("hash of string and bytes not identical")
    }
}

テストを見る(smhasher_test.go)

ハッシュ関数に対する拷問テストのツールがあり、それをGoに移植しているとのこと。元はGoogle製で、非暗号的ハッシュ関数の性能(分散や、速度)を計測するらしい。

https://github.com/aappleby/smhasher

// Smhasher is a torture test for hash functions.
// https://code.google.com/p/smhasher/
// This code is a port of some of the Smhasher tests to Go.

内容的には、ハッシュの衝突を記録する構造体があって、循環する文字列、密度が薄い(Sparse)文字列、1ビットだけ変更した文字列で半数のビットが書き換わるか・・・といったテストがある模様。


テストコードで見つけた配慮。

    if runtime.GOARCH == "wasm" {
        t.Skip("Too slow on wasm")
    }
    if testing.Short() {
        t.Skip("Skipping in short mode")
    }

ここから実装の方を見ていきます


Hash構造体

type Hash struct {
    _     [0]func() // not comparable
    seed  Seed      // initial seed used for this hash
    state Seed      // current hash of all flushed bytes
    buf   [64]byte  // unflushed byte buffer
    n     int       // number of unflushed bytes
}

比較不能

本当かどうか試してみた。 https://play.golang.org/p/Obem8g4xdXm

確かに比較不能というコンパイルエラー。

./prog.go:16:23: invalid operation:
    a == b (struct containing [0]func() cannot be compared)

  • 固定長配列なら、中の要素が比較可能ならOK
  • スライスはダメ(nilとの比較のみ)
  • 単体の要素でも関数などは比較不能(nilとの比較のみ)
  • 単体の変数ならnilとの比較のみ可能、という具体的なエラーメッセージになるが、構造体にラップされており、その内部の要素に比較不能なものがあると、理由なく「比較不能」というメッセージになる

ハッシュの計算

Write()、WriteByte()、WriteString()があるが、どれもやっていることは変わらないので、シンプルなWriteByteで見てみる。

バッファ(64バイト)分データが溜まったらflush()メソッドを呼ぶ。その後はバッファにデータを積む。

hash.Hashインタフェースを満たすためのシグニチャになっているだけで、errorを返す宣言になっているが、エラーは絶対に発生しない。


// WriteByte adds b to the sequence of bytes hashed by h.
// It never fails; the error result is for implementing io.ByteWriter.
func (h *Hash) WriteByte(b byte) error {
    if h.n == len(h.buf) {
        h.flush()
    }
    h.buf[h.n] = b
    h.n++
    return nil
}

flush()は、rthashという関数を呼んでいる。溜まったバッファの値と、現在のstateの情報をわたし、現在のstateを更新する。現在のstate情報も参照するため、64バイトごとに同じデータを送っても、結果が循環することはない。

// precondition: buffer is full.
func (h *Hash) flush() {
    if h.n != len(h.buf) {
        panic("maphash: flush of partially full buffer")
    }
    h.initSeed()
    h.state.s = rthash(h.buf[:], h.state.s)
    h.n = 0
}

rthash関数はこんな実装。 unsafe.Sizeof(uintptr(0)) == 8 で64ビットかどうかを判定している模様。32ビットだと、上位ビットと下位ビットを計算してから合成して64ビットにしている。

func rthash(b []byte, seed uint64) uint64 {
    if len(b) == 0 {
        return seed
    }
    // The runtime hasher only works on uintptr. For 64-bit
    // architectures, we use the hasher directly. Otherwise,
    // we use two parallel hashers on the lower and upper 32 bits.
    if unsafe.Sizeof(uintptr(0)) == 8 {
        return uint64(runtime_memhash(unsafe.Pointer(&b[0]), uintptr(seed), uintptr(len(b))))
    }
    lo := runtime_memhash(unsafe.Pointer(&b[0]), uintptr(seed), uintptr(len(b)))
    hi := runtime_memhash(unsafe.Pointer(&b[0]), uintptr(seed>>32), uintptr(len(b)))
    return uint64(hi)<<32 | uint64(lo)
}

runtime_memhashは次のようになっています。実体のない関数定義にlinknameディレクティブ。これはunsafeがついているパッケージのみで利用でき、外部パッケージのプライベートな関数を呼び出すためのスタブ関数を生成してくれるとのこと。これにより、プライベート関数が呼び出せる。

https://sitano.github.io/2016/04/28/golang-private/

//go:linkname runtime_memhash runtime.memhash
//go:noescape
func runtime_memhash(p unsafe.Pointer, seed, s uintptr) uintptr

memhashの実体はアセンブリ言語で実装されている。各CPUごとの実装がある(memhashFallbackというGo実装もある)。

// func memhash(p unsafe.Pointer, h, s uintptr) uintptr
// hash function using AES hardware instructions
TEXT runtime·memhash(SB),NOSPLIT,$0-32
    CMPB    runtime·useAeshash(SB), $0
    JEQ noaes
    MOVQ    p+0(FP), AX // ptr to data
    MOVQ    s+16(FP), CX    // size
    LEAQ    ret+24(FP), DX
    JMP aeshashbody<>(SB)
noaes:
    JMP runtime·memhashFallback(SB)

最終的にはAES-NIという、TLS暗号の中で使われる最近のCPUで使われる専用命令でハッシュ計算をしていました。


まとめ

やっていることはシンプルで、mapで使われているハッシュ関数に公開APIがついた程度。完全な新機能を見ていたはずだが・・・

テストとか、中のテクニックはなかなか興味深いものもあったかも

明日からは役に立たない知識を中心にまとめました

future
ITを武器とした課題解決型のコンサルティングサービスを提供します
http://future-architect.github.io/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした