Golang で Zero allocation な TinySegmenter 実装を作りました

前回、

TinySegmenter を TypeScript に移植してみた

という記事にもある様に TinySegmenter の TypeScript 実装を作った後、

TypeScript に TinySegmenter を移植できたんだから、Golang でも行けるやろ

と言う感じの軽い気持ちで TinySegmenter の Golang 実装を作り始めた んですが、色々やっている内に、

ライブラリ内では Zero Allocation であり、そこそこ高速 な TinySegmenter 実装

が出来たので共有しておきます：

nyarla/go-japanese-segmenter: A TinySegmenter implementation of golang but zero allocation inside this library

使い方

まぁ README.md を読んでくれ〜って感じでは有るんですが、おおよそ以下の様な感じで使えます：

package main

import (
    "fmt"
    "io"
    "strings"

    "github.com/nyarla/go-japanese-segmenter/defaults"
    "github.com/nyarla/go-japanese-segmenter/segmenter"
)

func main() {
    src := strings.NewReader("今日は良い天気ですね")
    dst := new(strings.Builder)
    dict := segmenter.BiasCalculatorFunc(defaults.CalculateBias)
    seg := segmenter.New(dst, src)

    for {
        err := seg.Segment(dict)

        if err != nil && err != io.EOF {
            panic(err)
        }

        if err == io.EOF {
            break
        }

        fmt.Println(dst.String())
        dst.Reset()
    }

    fmt.Println(dst.String())
    dst.Reset()

    // Output:
    // 今日
    // は
    // 良い
    // 天気
    // ですね
}

何故作ったか

まー実際のところ 作ったところで大して使う予定とかも無かった んですが、

技術力を磨くためのチャレンジ
気分転換
まぁ作っても無駄に終わることは無いだろうという予感

という辺りの理由から作業を始め、現実には 2 週間以上を掛けて今回の TinySegmenter 実装は出来上がりました。

で、今回の実装は少なくとも自分の手元では、

ikawaha/tinysegmenter.go

とほぼ同じ速度かちょっと早いぐらいで動いてるのですが、API も違うし同じ条件下でのベンチマークは取れてないので、環境によってはベンチマークの数値は変わると思います。

得られた知見

ちなみに今回の TinySegmenter 実装では、ikawaha さんの tinysegmenter 実装と同じ様な速度に追い付くために、下記の様な手法で速度の向上を狙いました：

辞書データを Map 等で保持せず、効率の良いコードを自動生成する
分析する文字列そのもののコピーを生成せずに効率よく処理する
API を調整し Zero Allocation に収まる形にする

なお自分が試した最適化の中では（1）が一番処理速度の向上に貢献しており、具体的な中身としては、

if A == a && B == b {
  ...
}

if A == a&& C == c {
   ...
}

と言う様なコードを、

if A == a {
  if B == b {
    ...
  }

   if C == c {
     ...
   }
}

と言う様な感じにマージすれば効率よくなるよね？みたいな素朴な考えに基づいて実装しています。

そしてさらに言えば、今回作った TinySegmenter 実装のリポジトリの中には、その辺りの作業を自動化するための golang スクリプトが含まれているため、それを使えば他の JSON 形式の辞書データからでも golang の source code を吐ける様になっています。

あと、開発途中で自分が実際ベンチマークを回して判った事ですが、どうも Golang の場合、

条件分岐の際に switch ~ case を使うよりも単発の if を使った方が早くなる
数値の比較は素直に == で比較した方が良い（bit 演算とかするとかえって遅くなる）

と言う様な事がありました。

その他工夫した点

また今回の TinySegmenter 実装では、ライブラリの汎用性を高めるために、

io.RuneReader と io.Writer を入出力に使う

という事をしていて、この辺りの影響で一度は処理速度が遅くなってたりもしたんですが、まぁ最終的にはなんとか速度を維持したままライブラリの汎用性も維持する、みたいな事が出来ました。

ちなみに自分が最初 TinySegmenter の実装を作り始めた時には API を

string 引数に取って []string を返す

と言う様な API にしてたんですが、この時には速度はともかく Zero allocation には出来てなかったし、 io.RuneReader を入力として使った結果、巨大なファイルでも bufio.Reader 経由で効率良く読み込めるのでは？という点も良くなったと思っています。

以上

今回の話はざっとこんな感じでした。

実際のところ、あと残り一部に switch ~ case を使っている箇所が有るので、そこを修正すると少しだけは早くなるかな？と思っているのですが、その他については自分が思い付く限りの手法は取っているので、自分の力だけではこれ以上はあまり早くならないかもなぁと思ってます。

また今回の TinySegmenter の実装の際、

何故、TinySegmenter.js のアルゴリズムは機能するのか

については、ほぼ理解出来ておらず（ぉぃ）自分は、

（TinySegmenter を）Golang に移植して API を調整して Zero allocation にした

というだけなので、まぁ自分に出来た辺りはここまでかなぁ、って感じですね。

ま、今回の TinySegmenter の実装は、最近メンタルがかなり下ってる中でも楽しみながらコードを書けたので、その点でもちゃんと出来上がって良かったな、と思ってます。はい。

カラクリスタ

ただの「人」の個人ブログ。人です

Golang で Zero allocation な TinySegmenter 実装を作りました

使い方

何故作ったか

得られた知見

その他工夫した点

以上