読者です 読者をやめる 読者になる 読者になる

callbackでiteratorっぽくcommon-prefix search を直したらちょっとパフォーマンスが改善した

golang Go言語

はじめに

ikawaha.hateblo.jp

これの続編です.callback関数を使うようにして,返値でヒープを使わないようにしたらパフォーマンスもちょっと改善しました.

背景

common-prefix search(共通接頭辞検索)とは「電気」「電気通信」「電気通信大学」というキーワードがあったときに, 入力が「電気通信大学大学院」だったら,これらの「電気」「電気通信」「電気通信大学」という共通の prefix を持ったキーワードを抽出する操作のことです.

形態素解析の辞書引きで,ある位置から始まる形態素の候補をすべて列挙するためにこの操作が実装されているんですが, 抽出されるキーワードごとにキーワードのidと長さを配列にして返していました.

そうすると,この返値の配列のメモリ確保で結構な量が確保されてはGCされるということを繰り返してしまうわけで...

というのが背景です.

golangiterator はない

ないです.channel 使うと一番それっぽくなる気がするんですけど,パフォーマンスは出ないみたいです. 今回は callback を利用する方法で改修してみました.

参考: Iterators in Go

変更点

before

// CommonPrefixSearch finds keywords sharing common prefix in an input
// and returns the ids and it's lengths if found.
func (d DoubleArray) CommonPrefixSearch(input string) (ids, lens []int) {
    var p, q int
    bufLen := len(d)
    for i, size := 0, len(input); i < size; i++ {
        p = q
        q = int(d[p].Base) + int(input[i])
        if q >= bufLen || int(d[q].Check) != p {
            break
        }
        ahead := int(d[q].Base) + int(terminator)
        if ahead < bufLen && int(d[ahead].Check) == q && int(d[ahead].Base) <= 0 {
            ids = append(ids, int(-d[ahead].Base))
            lens = append(lens, i+1)
        }
    }
    return
}

after

// CommonPrefixSearchCallback finds keywords sharing common prefix in an input
// and callback with id and length.
func (d DoubleArray) CommonPrefixSearchCallback(input string, callback func(id, l int)) {
        var p, q int
        bufLen := len(d)
        for i := 0; i < len(input); i++ {
                p = q
                q = int(d[p].Base) + int(input[i])
                if q >= bufLen || int(d[q].Check) != p {
                        break
                }
                ahead := int(d[q].Base) + int(terminator)
                if ahead < bufLen && int(d[ahead].Check) == q && int(d[ahead].Base) <= 0 {
                        callback(int(-d[ahead].Base), i+1)
                }
        }
        return
}

パフォーマンス

before

$ go test --bench .
PASS
BenchmarkAnalyzeNormal-4         10000        222285 ns/op
BenchmarkAnalyzeSearch-4          5000        290241 ns/op
BenchmarkAnalyzeExtended-4        5000        295677 ns/op
ok      github.com/ikawaha/kagome/tokenizer    21.251s

after

go test --bench .
PASS
BenchmarkAnalyzeNormal-4         10000        158133 ns/op
BenchmarkAnalyzeSearch-4         10000        227858 ns/op
BenchmarkAnalyzeExtended-4       10000        235153 ns/op
ok      github.com/ikawaha/kagome/tokenizer    22.270s

alloc_space

$ go tool pprof --alloc_space tokenizer.test fix_mem.prof
Entering interactive mode (type "help" for commands)
(pprof) top
1020.66MB of 1033.17MB total (98.79%)
Dropped 27 nodes (cum <= 5.17MB)
Showing top 10 nodes out of 44 (cum >= 7.50MB)
      flat  flat%   sum%        cum   cum%
  773.95MB 74.91% 74.91%   775.96MB 75.10%  github.com/ikawaha/kagome/tokenizer.Tokenizer.Analyze
  114.31MB 11.06% 85.97%   114.31MB 11.06%  bytes.makeSlice
   60.99MB  5.90% 91.88%    60.99MB  5.90%  strings.genSplit
   46.50MB  4.50% 96.38%    46.50MB  4.50%  encoding/binary.Read
   10.34MB  1.00% 97.38%    32.84MB  3.18%  github.com/ikawaha/kagome/internal/da.Read
    8.98MB  0.87% 98.25%    69.97MB  6.77%  github.com/ikawaha/kagome/internal/dic.NewContents
    3.31MB  0.32% 98.57%    20.31MB  1.97%  github.com/ikawaha/kagome/internal/dic.LoadConnectionTable
    2.28MB  0.22% 98.79%     9.28MB   0.9%  github.com/ikawaha/kagome/internal/dic.LoadMorphSlice
         0     0% 98.79%   117.31MB 11.35%  bytes.(*Buffer).ReadFrom
         0     0% 98.79%     7.50MB  0.73%  encoding/gob.(*Decoder).Decode

ちょっと改善した 🙌