お前誰よ
- 渋川よしき
- フューチャー株式会社で仕事してます
- いろいろ本を書いたりしています
- みなさん買ってくださっていますよね？
- 今日は、家族がいろいろ体調を崩していて時間が取れなかったのでQiitaスライドで
今回の内容
フューチャー社内で行ったコードリーディングの勉強会の再演です。現在、標準ライブラリをみんなで読んで解説しています。
わたしは1.14で追加されたhash/maphashを説明しました。
1.14の変更
- Go 1.14のリリースノート: https://tip.golang.org/doc/go1.14
- hash/maphash https://tip.golang.org/pkg/hash/maphash/
ここによると、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製で、非暗号的ハッシュ関数の性能（分散や、速度）を計測するらしい。
// 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がついているパッケージのみで利用でき、外部パッケージのプライベートな関数を呼び出すためのスタブ関数を生成してくれるとのこと。これにより、プライベート関数が呼び出せる。
//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がついた程度。完全な新機能を見ていたはずだが・・・
テストとか、中のテクニックはなかなか興味深いものもあったかも
明日からは役に立たない知識を中心にまとめました