Try Golang! 効率的なHashmapを実装するためにGoがしたこと
How the Go runtime implements maps efficiently
先日、Go Conference 2018 Springに参加してきました。キーノートはDave Cheney氏による、GoのHashmapはどのようにして効率的な実装を達成したのか、について（本記事のサブタイトルに、キーノートのタイトルを借用させていただきました）。復習も兼ねてHashmapの実装を覗いてみたので、簡単にまとめようと思います。
なお、英語のセッションだったので、正しく理解できていない部分があるかもしれません。お気付きの方は、ぜひご指摘ください。
Hashmapに関する他言語の問題点
Dave Cheney氏によると、C++とJavaのHashmapには、それぞれ以下のような問題点があるとのことです。
- C++: キーと値の組合せが異なるHashmapは、型としても全く別物となる。結果、コンパイル後のプログラムには、それぞれのHashmap実装が別物として含まれることになる。
- Java: プリミティブ型については、ラッパークラスを用いてHashmapを利用することとなる。結果、参照時のパフォーマンスが劣化する。
- Java: カスタムクラスをキーとした場合、
equalsメソッドとhashCodeメソッドの実装を誤ると、パフォーマンスが大きく劣化する。（場合によっては正しく動作しなくなる）
これらの問題を解消するために、Goではmaptypeというものが利用されています。
Hashmapの型情報を保持するmaptype
では、このmaptypeの実装を見てみましょう。
maptypeはruntime/type.go に、キー（key）と値（elem）の型をそれぞれ保持した構造体として定義されています。そしてこの型は、アルゴリズム（alg）というプロパティを持っています。
type maptype struct {
typ _type
key *_type
elem *_type
...
}type _type struct {
...
alg *typeAlg
...
}
このtypeAlgは、runtime/alg.goに定義されていて、内容としてはハッシュ値を返す関数（hash）と、等価かどうかを判定する関数（equal）を持つ構造体となっています。
type typeAlg struct {
// function for hashing objects of this type
// (ptr to object, seed) -> hash
hash func(unsafe.Pointer, uintptr) uintptr
// function for comparing objects of this type
// (ptr to object A, ptr to object B) -> ==?
equal func(unsafe.Pointer, unsafe.Pointer) bool
}int型やstring型等、もともと定義されている型については、下記のようにhash関数やequal関数が予め用意されています。構造体等は、コンパイル時に自動生成されるようです。構造体をイコールで比較すると中のプロパティの値まで見て判定してくれますが、この時に使用されるのも、この自動生成されたequal関数のようですね。なお、Goではこれらの関数をオーバーライドすることはできません。
func memhash8(p unsafe.Pointer, h uintptr) uintptr {
return memhash(p, h, 1)
}
...
func strhash(a unsafe.Pointer, h uintptr) uintptr {
x := (*stringStruct)(a)
return memhash(x.str, h, uintptr(x.len))
}
...
func memequal8(p, q unsafe.Pointer) bool {
return *(*int8)(p) == *(*int8)(q)
}
...
func strequal(p, q unsafe.Pointer) bool {
return *(*string)(p) == *(*string)(q)
}実際、runtime/hashmap.goの中でマップにアクセスする際などは、これらの関数が利用されています。なお、val := m[key]のようなコードはシンタックスシュガーで、実際に呼ばれているのは、下記の関数mapaccess1とのことです。（val, ok := m[key]の場合はmapaccess2）
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
...
alg := t.key.alg
hash := alg.hash(key, uintptr(h.hash0))
...
for ; b != nil; b = b.overflow(t) {
for i := uintptr(0); i < bucketCnt; i++ {
...
if alg.equal(key, k) {
...
}
}
}
return unsafe.Pointer(&zeroVal[0])
}実際はhashやequalの他にもmaptypeが保持する値を利用していますが、すべての型に対応し、かつ実体がひとつのマップを、ラッパークラスなどを用いずに実現した方法について、概略は掴めたのではないでしょうか。
どれくらい速いのか
色々な条件があると思うので、あくまで参考としてですが、GoとJavaで類似のコードを書いて、実行速度を比較してみました。まずはGoのコードです。値の設定と、キー指定の参照を10000回実施しています。マップの型は、Javaでラッパークラスを使用する必要があるintです。
// main.go
package mainimport (
"fmt"
"time"
)func main() { start := time.Now() m := make(map[int]int)
for i := 0; i < 10000; i++ {
m[i] = i
}
var ans int
for k := range m {
ans += m[k]
} end := time.Now() fmt.Printf("answer=%v, %f sec", ans, (end.Sub(start)).Seconds())
}
続いてJavaのコードはこんな感じ。
// Main.java
import java.util.*;public class Main {
public static void main(String[] args) { long start = System.currentTimeMillis(); Map<Integer, Integer> m = new HashMap<Integer, Integer>();
for (int i = 0; i < 10000; i++) {
m.put(i, i);
}
int ans = 0;
for (Integer key : m.keySet()) {
ans += m.get(key);
} long end = System.currentTimeMillis(); System.out.printf("answer=%d, %d ms", ans, end - start);
}
}
コンパイルして実行すると、結果はこうなりました。実行時間は多少ばらけますが、Goの方が速いと言っていいのかな、と。まぁそもそもランタイムかましているJavaと比較していいのかは置いといて。。
$ ./main
answer=49995000, 0.001030 sec
$ java Main
answer=49995000, 7 ms私自身、普段の業務の中で、言語の実装を深掘りすることはあまりないのですが、今回色々と見ることができ、新鮮で面白かったです。Goを書いている方にとっては実装方法の勉強にもなると思うので、興味がある方は覗いてみてはいかがでしょうか。
