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