{"action":"created","issue":{"url":"https://api.github.com/repos/ikawaha/kagome/issues/75","repository_url":"https://api.github.com/repos/ikawaha/kagome","labels_url":"https://api.github.com/repos/ikawaha/kagome/issues/75/labels{/name}","comments_url":"https://api.github.com/repos/ikawaha/kagome/issues/75/comments","events_url":"https://api.github.com/repos/ikawaha/kagome/issues/75/events","html_url":"https://github.com/ikawaha/kagome/issues/75","id":143150440,"number":75,"title":"Too much memory allocation in CommonPrefixSearch","user":{"login":"suzuken","id":491428,"avatar_url":"https://avatars.githubusercontent.com/u/491428?v=3","gravatar_id":"","url":"https://api.github.com/users/suzuken","html_url":"https://github.com/suzuken","followers_url":"https://api.github.com/users/suzuken/followers","following_url":"https://api.github.com/users/suzuken/following{/other_user}","gists_url":"https://api.github.com/users/suzuken/gists{/gist_id}","starred_url":"https://api.github.com/users/suzuken/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/suzuken/subscriptions","organizations_url":"https://api.github.com/users/suzuken/orgs","repos_url":"https://api.github.com/users/suzuken/repos","events_url":"https://api.github.com/users/suzuken/events{/privacy}","received_events_url":"https://api.github.com/users/suzuken/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2016-03-24T04:54:44Z","updated_at":"2016-03-30T09:50:32Z","closed_at":"2016-03-30T09:48:00Z","body":"Hi @ikawaha san. I try to run kagome on long running purpose, and find some memory allocation in tokenizer.\r\n\r\n    -> % go test -v ./tokenizer -run=^$ -bench=. -benchmem -benchtime=2s -memprofile=prof.mem | tee mem.0\r\n    PASS\r\n    BenchmarkAnalyzeNormal-8           20000            140704 ns/op           19179 B/op        581 allocs/op\r\n    BenchmarkAnalyzeSearch-8           20000            185009 ns/op           19178 B/op        581 allocs/op\r\n    BenchmarkAnalyzeExtended-8         20000            180695 ns/op           18240 B/op        582 allocs/op\r\n    ok      github.com/ikawaha/kagome/tokenizer     15.453s\r\n\r\nAnd reading it by pprof\r\n\r\n    -> % go tool pprof --alloc_space tokenizer.test prof.mem\r\n    Entering interactive mode (type \"help\" for commands)\r\n    (pprof) top\r\n    1699.93MB of 1711.81MB total (99.31%)\r\n    Dropped 19 nodes (cum <= 8.56MB)\r\n    Showing top 10 nodes out of 45 (cum >= 14.28MB)\r\n          flat  flat%   sum%        cum   cum%\r\n      796.54MB 46.53% 46.53%  1046.54MB 61.14%  github.com/ikawaha/kagome/internal/dic.IndexTable.CommonPrefixSearch\r\n      406.58MB 23.75% 70.28%  1454.63MB 84.98%  github.com/ikawaha/kagome/tokenizer.Tokenizer.Analyze\r\n         250MB 14.60% 84.89%      250MB 14.60%  github.com/ikawaha/kagome/internal/da.DoubleArray.CommonPrefixSearch\r\n      114.91MB  6.71% 91.60%   114.91MB  6.71%  bytes.makeSlice\r\n       59.99MB  3.50% 95.11%    59.99MB  3.50%  strings.genSplit\r\n          47MB  2.75% 97.85%       47MB  2.75%  encoding/binary.Read\r\n       10.34MB   0.6% 98.46%    31.84MB  1.86%  github.com/ikawaha/kagome/internal/da.Read\r\n        8.98MB  0.52% 98.98%    68.97MB  4.03%  github.com/ikawaha/kagome/internal/dic.NewContents\r\n        3.31MB  0.19% 99.17%    16.81MB  0.98%  github.com/ikawaha/kagome/internal/dic.LoadConnectionTable\r\n        2.28MB  0.13% 99.31%    14.28MB  0.83%  github.com/ikawaha/kagome/internal/dic.LoadMorphSlice\r\n\r\nAnd see allocation in each line.\r\n\r\n    (pprof) list CommonPrefixSearch\r\n    Total: 1.67GB\r\n    ROUTINE ======================== github.com/ikawaha/kagome/internal/da.DoubleArray.CommonPrefixSearch in /Users/ke-suzuki/src/github.com/ikawaha/kagome/internal/da/da.go\r\n         250MB      250MB (flat, cum) 14.60% of Total\r\n             .          .    101:           if q >= bufLen || int(d[q].Check) != p {\r\n             .          .    102:                   break\r\n             .          .    103:           }\r\n             .          .    104:           ahead := int(d[q].Base) + int(terminator)\r\n             .          .    105:           if ahead < bufLen && int(d[ahead].Check) == q && int(d[ahead].Base) <= 0 {\r\n         123MB      123MB    106:                   ids = append(ids, int(-d[ahead].Base))\r\n         127MB      127MB    107:                   lens = append(lens, i+1)\r\n             .          .    108:           }\r\n             .          .    109:   }\r\n             .          .    110:   return\r\n             .          .    111:}\r\n             .          .    112:\r\n    ROUTINE ======================== github.com/ikawaha/kagome/internal/dic.IndexTable.CommonPrefixSearch in /Users/ke-suzuki/src/github.com/ikawaha/kagome/internal/dic/index.go\r\n      796.54MB     1.02GB (flat, cum) 61.14% of Total\r\n             .          .     61:}\r\n             .          .     62:\r\n             .          .     63:// CommonPrefixSearch finds keywords sharing common prefix in an input\r\n             .          .     64:// and returns the ids and it's lengths if found.\r\n             .          .     65:func (idx IndexTable) CommonPrefixSearch(input string) (lens []int, ids [][]int) {\r\n             .      250MB     66:   seeds, lens := idx.Da.CommonPrefixSearch(input)\r\n             .          .     67:   for _, id := range seeds {\r\n             .          .     68:           dup, _ := idx.Dup[int32(id)]\r\n      351.02MB   351.02MB     69:           list := make([]int, 1+dup, 1+dup)\r\n             .          .     70:           for i := 0; i < len(list); i++ {\r\n             .          .     71:                   list[i] = id + i\r\n             .          .     72:           }\r\n      445.52MB   445.52MB     73:           ids = append(ids, list)\r\n             .          .     74:   }\r\n             .          .     75:   return\r\n             .          .     76:}\r\n             .          .     77:\r\n             .          .     78:// Search finds the given keyword and returns the id if found.\r\n\r\n\r\n---\r\n\r\nFor reducing allocation, it is prefer to use `append` without creating new slice. Do you have any ideas to reduce allocation in `DoubleArray.CommonPrefixSearch` and `IndexTable.CommonPrefixSearch` ? For example,\r\n\r\n```go\r\nfunc (d DoubleArray) CommonPrefixSearch(input string) (ids, lens []int) {\r\n\tvar p, q int\r\n\tbufLen := len(d)\r\n\tids = make([]int, 0, SOME_FIXED_SIZE)\r\n\tlens = make([]int, 0, SOME_FIXED_SIZE)\r\n\tfor i, size := 0, len(input); i < size; i++ {\r\n\t\tp = q\r\n\t\tq = int(d[p].Base) + int(input[i])\r\n\t\tif q >= bufLen || int(d[q].Check) != p {\r\n\t\t\tbreak\r\n\t\t}\r\n\t\tahead := int(d[q].Base) + int(terminator)\r\n\t\tif ahead < bufLen && int(d[ahead].Check) == q && int(d[ahead].Base) <= 0 {\r\n\t\t\tids = append(ids, int(-d[ahead].Base))\r\n\t\t\tlens = append(lens, i+1)\r\n\t\t}\r\n\t}\r\n\treturn\r\n}\r\n```\r\n\r\nmay be reduce allocation in many cases, but I'm not sure how `SOME_FIXED_SIZE` should be defined.\r\n"},"comment":{"url":"https://api.github.com/repos/ikawaha/kagome/issues/comments/203352811","html_url":"https://github.com/ikawaha/kagome/issues/75#issuecomment-203352811","issue_url":"https://api.github.com/repos/ikawaha/kagome/issues/75","id":203352811,"user":{"login":"ikawaha","id":4232165,"avatar_url":"https://avatars.githubusercontent.com/u/4232165?v=3","gravatar_id":"","url":"https://api.github.com/users/ikawaha","html_url":"https://github.com/ikawaha","followers_url":"https://api.github.com/users/ikawaha/followers","following_url":"https://api.github.com/users/ikawaha/following{/other_user}","gists_url":"https://api.github.com/users/ikawaha/gists{/gist_id}","starred_url":"https://api.github.com/users/ikawaha/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ikawaha/subscriptions","organizations_url":"https://api.github.com/users/ikawaha/orgs","repos_url":"https://api.github.com/users/ikawaha/repos","events_url":"https://api.github.com/users/ikawaha/events{/privacy}","received_events_url":"https://api.github.com/users/ikawaha/received_events","type":"User","site_admin":false},"created_at":"2016-03-30T09:50:32Z","updated_at":"2016-03-30T09:50:32Z","body":"```\r\n$ go tool pprof --alloc_space tokenizer.test fix_mem.prof\r\nEntering interactive mode (type \"help\" for commands)\r\n(pprof) top\r\n1020.66MB of 1033.17MB total (98.79%)\r\nDropped 27 nodes (cum <= 5.17MB)\r\nShowing top 10 nodes out of 44 (cum >= 7.50MB)\r\n      flat  flat%   sum%        cum   cum%\r\n  773.95MB 74.91% 74.91%   775.96MB 75.10%  github.com/ikawaha/kagome/tokenizer.Tokenizer.Analyze\r\n  114.31MB 11.06% 85.97%   114.31MB 11.06%  bytes.makeSlice\r\n   60.99MB  5.90% 91.88%    60.99MB  5.90%  strings.genSplit\r\n   46.50MB  4.50% 96.38%    46.50MB  4.50%  encoding/binary.Read\r\n   10.34MB  1.00% 97.38%    32.84MB  3.18%  github.com/ikawaha/kagome/internal/da.Read\r\n    8.98MB  0.87% 98.25%    69.97MB  6.77%  github.com/ikawaha/kagome/internal/dic.NewContents\r\n    3.31MB  0.32% 98.57%    20.31MB  1.97%  github.com/ikawaha/kagome/internal/dic.LoadConnectionTable\r\n    2.28MB  0.22% 98.79%     9.28MB   0.9%  github.com/ikawaha/kagome/internal/dic.LoadMorphSlice\r\n         0     0% 98.79%   117.31MB 11.35%  bytes.(*Buffer).ReadFrom\r\n         0     0% 98.79%     7.50MB  0.73%  encoding/gob.(*Decoder).Decode\r\n```\r\n"}}