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 main
import (
  "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を書いている方にとっては実装方法の勉強にもなると思うので、興味がある方は覗いてみてはいかがでしょうか。