概要

人は人生に何度かTRIEを書くという．そんなわけで，何度目かのTRIEでsudachiのdarts-cloneをクローンしてみました．TRIEの記事は沢山あるので，ここではGoに移植してみて気づいた事をいくつか共有していきたいと思います．

今回の成果物： https://github.com/ikawaha/dartsclone

darts-clone

元ネタはこちら．Java版とPython版があります．

本家は https://github.com/s-yata/darts-clone ．丁寧な解説もいっぱいあるのでググってみてください．

とにかくやってみる

動作原理とか仕組みとか何も考えずにクローンしてみました．そのあとGOっぽくリファクタリングしてみました．訳も分からずJava版とPython版のコードをGoに落としてくのはなかなか面白かったです．

リファクタリング

実は darts-clone のGo版がすでにありました．作ってから気づいたんですけど（あるある

つ https://github.com/euclidr/darts

こちらは本家のC++版から clone されてるみたいなので，これと比べてみました．自分が作ったやつが遅いw

ベンチとって調べてみたところ，ダブル配列をbyte配列で扱うときと，unit32配列で扱うときとで同じように処理するために，関数をまとめて両方から呼んでたんですが，その関数呼び出しの分だけ遅い原因になっていたようです．これをそれぞれのケースでべた書きした関数に直して呼び出し減らすと速度は大体同じになりました．

変更前：

func (a MmapedDoubleArray) ExactMatchSearch(key string) (id, size int, err error) {
    return exactMatchSearch(a, key) // ← 共通処理でまとめてた
}

変更後：べた書きに変更

func (a MmapedDoubleArray) ExactMatchSearch(key string) (id, size int, err error) {
    nodePos := uint32(0)
    unit, err := a.at(nodePos)
    if err != nil {
        return -1, -1, err
    }
    for i := 0; i < len(key); i++ {
        nodePos ^= unit.offset() ^ uint32(key[i])
        unit, err = a.at(nodePos)
        if err != nil {
            return -1, -1, err
        }
        if unit.label() != key[i] {
            return -1, 0, nil
        }
    }
    if !unit.hasLeaf() {
        return -1, 0, nil
    }
    unit, err = a.at(nodePos ^ unit.offset())
    if err != nil {
        return -1, -1, err
    }
    return int(unit.value()), len(key), nil
}

これで比較してるプログラムと同性能になりましたが，比較してるプログラムの方が配列のインデックスチェックなどのエラーのチェックを端折ってるのでその分ちょっと速いです．でもまぁ，誤差範囲なのでこれはエラーチェックを入れることにしました．panicで停まるのは微妙ですしね・・・．

mmap 対応

sudachiはmmapで辞書を共有して省メモリで利用できるようになっています．そのためsudachiで使われているdarts-cloneはmmap対応されています．GOでもmmap対応していきます．linux系とwindowsで対応が変わってくるのでテストとかがちょっと面倒ですが，darts-cloneのダブル配列自体がbyte列になってるので素直に対応するだけでいけました．

ところがどうもmmapで読み込んだ場合の速度（1/10くらい）がでません．

mmap使わない場合はuint32の配列でダブル配列が表現されているんですが，mmapの時はこれがリトルエンディアンのbyte配列になっていて，ここからunit32の値を取り出していました．

最初書いてたコードはReaderつかって位置を指定してから，Read()で読み込んでたんですが，

    var ret uint32
    if err := binary.Read(r, binary.LittleEndian, &ret); err != nil {
        return 0, fmt.Errorf("read error, %v", err)
    }

この部分が遅かったみたいです．これを配列を直接指定して，

    if int(i+1)*unitSize > len(a.raw) {
        return 0, fmt.Errorf("index out of bounds")
    }
    ret := binary.LittleEndian.Uint32(a.raw[i*unitSize : (i+1)*unitSize])

で読み込んだら，mmap版も同等性能が出るようになりました．

ちなみに binary.LittleEndian.Uint32() の中身は，

func (littleEndian) Uint32(b []byte) uint32 {
    _ = b[3] // bounds check hint to compiler; see golang.org/issue/14808
    return uint32(b[0]) | uint32(b[1])<<8 | uint32(b[2])<<16 | uint32(b[3])<<24
}

なるほどシンプル．

あ，あと syscall は deprecated になってて，golang.org/x/sys を使えとのこと．しらんかった．

まとめ

sudachiのdarts-clone相当の github.com/ikawaha/darts-clone をリリースしました．これで辞書引きの下準備ができたのでボチボチとsudachiの移植をやっていきたいなと思います．

ちなみに去年から開発を阻んでいるあれやこれはSまでは行ったのですが，そこからは進めないという壁にぶつかっているので，そろそろクリアにしようかなという気分．これがなくなればめっちゃ開発進む気もする (^^ゞ

去年から開発を阻むあれやこれ→

Happy hacking!

人生で何度目かのダブル配列TRIEを書いた

概要

darts-clone

とにかくやってみる

リファクタリング

mmap 対応

まとめ