100万ページの巨大projectでリンク記法を編集すると、入力毎に0.5秒ぐらい画面がフリーズする
IMEをオフにして複数文字を一気に打ち込むと、画面に反映されるまでつっかかる
500 msecぐらいフリーズする
1秒間に2文字しか入力できない
最低でも100 msec以下にしたい
1秒間に10文字打ち込める
Reactの描画時間などもあるので、1回の検索が50 msecぐらいで終わるようにしたい
入力→検索→描画更新→入力→検索...
backspaceキー押しっぱなしは使用頻度が高く、普通のキー入力よりも高速
できれば秒間20文字打ち込める速度で検索したい
1文字入力する毎に検索走らせているせい
N文字打ち込むと、全ページのリストをN回検索してて効率が悪い
https://gyazo.com/c44f8a4f2fffe493790713e7d170c6a6
修正
やった事
曖昧検索の改善
https://gyazo.com/af8134177c4ad52cf3aa338f1f1d1201
asearchの結果をcacheする
cache hitしなかった時、まずクエリの先頭3文字だけでasearchしてcacheし、それからクエリ全体でasearchする
キーワード検索のヒット数が10以下でasearchに100万件が引き継がれた場合の処理時間が、370 msec → 20 msec程度まで改善
キーワード検索の改善
https://gyazo.com/1e226fa61e8d53a4bc8bb122bf4bb677
ページタイトルの長さでソートするのをUIスレッドで毎回やってたが、事前にWorkerで済ませておくようにした
キーワード検索に100万件ヒットした時の処理時間が1000 msec → 600 msec程度まで改善
titleLcMap.has(page.titleLc)の呼び出し回数を削減
Mapが遅かった
600 msec → 150 msecに改善
1万件ヒットした時点で処理を中断する
150 msec → 1 msecに改善
そろそろ次は、リンク記法補完popupとsearch formで別の検索方法を実装するべきかもしれないshokai.icon
準備
計測前の考察
文字の入力をthrottleする？
scraまで打った時に検索すればいい
そういう安直なのは最後の手段にしておく
throttleすると操作感が気持ち良くならない
scraと一気に入力しても、sとscとscrとscraで4回結果が更新されるべき
高速に絞り込まれていくヌルヌル感が目眩となって楽しさを産む 操作性も悪くなる。入力後すばやくtabキーで選択している時に遅れてサジェストが更新されると、誤選択する
誤選択する可能性があるならフリーズしてくれてた方がマシ
scra react javaみたいなやつ
ちゃんと計測した結果、これはハズレだったshokai.icon
当然and条件が増えるほど重くなる
単純なクエリなら、さっさと5件見つかってくれてすぐ検索を終えられる
長く複雑なクエリは、なかなかマッチするページが見つからない
配列の最初から最後までしっかり探した上で、「1件だけありました」と表示する事になる
クエリが長い === 文字数が多い
タイトルの文字数がクエリの文字数以下のページは、絶対にマッチしないので判定する必要がない
これで検索対象を削れそうshokai.icon
そう単純でもないか。クエリの文字列が部分一致してるケースを考慮しないと
例えばscrap rapbo boxで検索したら「Scrapbox」にヒットしなければならない
こういうめんどくさいケースはヒットしなくてもいいかもな
計測
mainブランチ
sc ~ scra
40~50 msec
scra j~scra java
410 ~ 420 msec
scra j r~scra j reac
420~500 msec
sc ~ scra
22~24 msec
scra j~scra java
380~400 msec
scra j r~scra j reac
390~400 msec
あんまり変わらないなshokai.icon
https://gyazo.com/6ce95fb8c8560a0e756d4b734b625960
常に360~380 msecかかっている
キーワード検索にヒットした結果が10件以下の時、asearchで探しなおしている クエリが長くなるほどasearch任せになり、asearchで134万件フルスキャンして、常に360 msecかかる
134万件をしっかりasearchでフルスキャンするのをやめるつもりはないshokai.icon
こういうtypoしてもヒットするのが重要
https://scrapbox.io/files/652a3af7e3a99a001cdb402d.png
改善
asearchは文字数が増えるほどリストが絞られていくから、cacheが効きそうshokai.icon
この2つの結果は同じになる
scra javaでasearch
scra jでasearchしたリストを、scra javaでasearchしなおす
直近5件ぐらいをcacheしておこう
100万ページの配列から作られたcacheの配列を全件残しているとメモリリークしそうなのと
cacheが多すぎると最長で部分一致するクエリを探すのが大変になってきそうなので
部分一致でいいか
cacheヒットしたらそこから検索しなおす事でフルスキャン回数を抑えた
ヒットしたら1 msec以下でasearch完了するようになったshokai.icon
cacheから絞り込んだ結果をさらにcacheに入れる条件
1万件以上を捨てれた時だけcacheすると、大量に絞り込めた時の優秀なcacheが長く生き残る
https://gyazo.com/40676cb9653d1f8a357c10ee2bc270d6
かなり良いshokai.icon
backspaceキー押すとcacheヒットしないので重いのだshokai.icon
こうなる
[リンク記法の編集が重い]というリンクが既に書かれているとする
自分で書いてないので、cacheは温まっていない
backspaceキー押して[リンク記法の編集が重]になる
cacheが無いので370 msecかかる
さらにbackspaceキーで[リンク記法の編集が]になる
これもcacheが無いので370 msecかかる
遅いを追記し、[リンク記法の編集が遅い]にする
これはcacheが効いて、20 msecで表示される
先にクエリの先頭3文字ぐらいでasearchして、それからクエリ全体でもう一度asearchした方が、backspaceキーで削除した時のcacheヒット率よさそう
この2つの結果は同じ
リンク記法の編集が重いでasearch
リンクでasearchした結果を、さらにリンク記法の編集が重いでasearch
リンクの検索結果を大事にとっておくと後で役に立つ
中央の3文字ぐらいの方がdeleteキーで先頭から消した時も効く？
cacheヒットしなくてクエリが4文字以上の時、4〜6文字目の3文字で一旦検索するようにした
https://gyazo.com/ea35a7713e3603235ec897578891dd45
backspaceで削除した時もcacheにヒットしやすくなった
4~6文字目での検索はやめたshokai.icon
deleteキーで削除した時のcacheがうまくhitしなかったので
再検討の余地はあると思うが、ちょっと実装がややこしいのでそのうちやる
まずクエリの先頭3文字で検索し、それからクエリ全体を使って検索するようした
先頭3文字の検索にもcacheが効く
これを採用したshokai.icon
キーワード検索の時点で100万件ヒットすると1000 msecかかる
https://scrapbox.io/files/652a41f363e3df001c29b797.png
キーワード検索で10件以上ヒットしてるので、asearchは使用されない
たぶん100万件をタイトルの長さでソートした後、さらにクエリに前方一致したページを優先表示してるからだろうな
Worker側で事前にタイトルの長さ順でソートしておけば、UIスレッドでの100万件ソートを1回減らせる
現在はWorkerではupdated順でソートしている
Workerで、タイトル順でソートし、タイトルの長さが一致してるページ同士はupdatedでソートすればいい
UIスレッドでタイトル順ソートする必要がなくなり、前方一致だけ探せば済むようになる
590~600 msecになったshokai.icon
gen pagでキーワード検索(and検索)してる時に、gen pagで前方一致するページを探して優先表示しても意味ないと思う
genだけでやるべき？
これは保留
asearchと同じ様なcacheは、実装してみたが性能向上しなかったのでやめた
gもgeもgenもgen pもgen paもgen pagも100万件の結果になるのだから、それらのcacheから絞り込み検索しても、100万件が対象で、ほぼフルスキャンになる
計測した
キーワード検索で100万件ヒット 50~60 msec
その中から、先頭マッチしたものを優先するソート 40~60 msec
さらにそこから、現在表示してるページにしか書かれていないリンクを除外する処理 400~500 msec
特にQuickSearch.exists(title)が重いらしい
現在表示してるページにしか書かれていないリンクを除外する処理で使っている
code:src/client/js/stores/quick-search.js
exists(title) {
return this.titleLcMap.has(toTitleLc(title))
}
試しにこのexists(title)関数を参照しないようにしただけで450 msec縮んだ
code:diff
return this.search(text, splitter)
.filter(
page =>
- this.exists(page.title) &&
page.title !== Stores.Page.title &&
page.title !== text
)
https://gyazo.com/e56ec7bfc8efc86537e255ea9f26dfd4
Mapってこういうの爆速かと思ってたshokai.icon
いや、Map.has(key)ではなくtoTitleLc(title)が遅い可能性もあるな
なるべくQuickSearch.exists(title)の参照回数を減らした
.exists(title)ではなくtitleLcMap.has(page.titleLc)を使うようにした
実装した頃は各pageが.titleLcを持っていなかったが、今は持っているので
https://gyazo.com/f461a708a1eea55c05d3e545957f02e9
80 ~ 120 msecになった
さらに、キーワード検索の結果は1万件までしか返さないようにした
https://gyazo.com/1e226fa61e8d53a4bc8bb122bf4bb677
約1 msecになった。最高shokai.icon
検索の動作が微妙に変わった
これまでは、キーワードに前方一致したページは100万件の中から優先表示されていた
今後は1万件から探す事になる
まあ1万件あればいいだろうshokai.icon
for ofループ、Map.has、toTitleLc、どれが遅いんだろう？
まあいいか
ここまでを実装したshokai.icon
以下、実装してないアイディア
cacheのリセットタイミングを最適化したい
自分や他人のページ編集によってtitle changeやlinks changeがsocket.ioで送られてきて、それを取り込んで辞書をコンパイルし直したら、cacheをリセットする必要がある
[scra jav]と書くと、今まさにページ内にリンク記法が追加されていて、links changeが発行される
自分の編集をトリガーとして辞書コンパイルが行われるわけだ
そのページにしか存在しないリンク記法はリンク記法補完popupに表示しないのだから、候補に含める必要ないのでは？
search formのQuickSearchには表示するからダメ
大人数projectでは他人の変更も頻繁に送られてくるし、自分の編集だけ特別扱いしてもそんなに意味なさそう
IMEオフにして[scra java]とか書いてる時が一番気になる
1文字入力する毎に
links changeが発行され
リンク記法補完popupの検索も走り
そしてlinks changeがサーバーに受け入れられたら、aserachのcacheを破棄しなければならない
IMEオンの場合は、入力確定するまでlinks changeも検索も発生しない
links changeが含まれてる時だけ送信を遅らせるとか
雑にconst PUSH_DEBOUNCE_TIME = 1000にしたら、たしかにcache破棄の頻度が下がった
ほとんどcache hitするようになった
https://gyazo.com/40676cb9653d1f8a357c10ee2bc270d6
たまに380 msecかかっている所が、cacheが効いていない検索
しかし、const PUSH_DEBOUNCE_TIME = 1000だとガーッと入力し続けていると保存できなくて、status barが黄色く警告状態になる頻度が上がる
警告を頻繁にユーザーに見せると警告として機能しなくなる
SyncStoreの調整は今はやめておこうshokai.icon
とりあえず、cacheがあるだけで十分快適にはなった
特に、scra javとかスラスラと入力した時に全くつっかからなくなったのはうれしい
QuickSearchのcompileの頻度をほんの少し下げればいいか
そもそも大きいprojectではQuickSearchのcompile自体に時間がかかるので、cacheリセット頻度も下がってくれる？