Tech

きっかけ Life is too short for a slow terminal を読んだ。 とりあえず「自分のzshも計測してみるか」となった。 流石にTerminalとかGPUパワーでFPS改善するとかフレームワーク使うのやめるだとか、ガッツリオリジナルコード書きまくるほどではないにしても明確にコレは駄目だというものがあれば改善したい。 先程の記事の筆者はoh-my-zshもpreztoも使わない主義で30msを達成しているが、私はp10kのUIを捨てるコストは払いたくなかったので、フレームワーク（zinit + p10k）は維持したまま改善できる部分だけ潰す方針にした。 まず計測 time zsh -i -c exit zsh -i -c exit 0.09s user 0.07s system 75% cpu 0.203 total 203ms。遅くはないが伸びしろがある気がする。 zprof で犯人を特定する .zshrc の先頭に： zmodload zsh/zprof 末尾に： zprof を追加して新しいシェルを開くと、関数ごとの所要時間テーブルが出る。上位30件だけ見れば十分。 zprof | head -n 30 num calls time self name ----------------------------------------------------------------------------------- 1) 1518 209.95 0.14 15.98% 153.70 0.10 11.70% :zinit-tmp-subst-zle 2) 60 107.81 1.80 8.20% 87.84 1.46 6.68% _zsh_autosuggest_async_request 3) 4 146.30 36.57 11.13% 67.91 16.98 5.17% _zsh_autosuggest_bind_widgets 4) 796 78.39 0.10 5.96% 67.84 0.09 5.16% _zsh_autosuggest_bind_widget 5) 34 98.12 2.89 7.47% 63.19 1.86 4.81% -fast-highlight-process 6) 2407 59.89 0.02 4.56% 59.89 0.02 4.56% .zinit-add-report ... zinit-tmp-subst-zle が1518回呼ばれていて1位。zinit がZLEウィジェットを差し替えるオーバーヘッドで、これはフレームワーク起因なので直接は触れない。 ...

参考 この記事は、以下の記事を読んで疑問に思ったことを調べた学習記録である。 Zennの検索スピードを5倍に高速化した話 記事では、Zennのサイト内検索をpg_trgm拡張を使って平均6倍、95パーセンタイルで4.25倍高速化した事例が紹介されている。 なぜ中間一致検索は遅いのか 通常、PostgreSQLでLIKE '%keyword%'のような中間一致検索を実行すると、BTreeインデックスが使えずフルスキャンが発生する。BTreeインデックスは文字列の前方一致には有効だが、中間一致では活用できない構造になっているためである。 データ量が増えると、このフルスキャンが深刻なパフォーマンスボトルネックになる。参考記事では、検索に1秒〜数秒かかる状態だったとのことだ。 n-gramインデックスの仕組み n-gramインデックスは、文字列をn文字ずつに分割してインデックス化することで、中間一致検索でもインデックスを効かせる仕組みである。 3-gramの例 「PostgreSQL」という文字列を3-gram（トライグラム）で分割すると以下のようになる。 __P, _Po, Pos, ost, stg, tgr, gre, reS, eSQL, QL_, L__ 先頭と末尾にはパディング文字（_）が付与される。 検索時の動作 「stgre」というキーワードで検索する場合： 検索キーワードを3-gramで分割: stg, tgr, gre インデックスからこれらすべてのトライグラムを含む文書を抽出 抽出された候補に対してRecheck処理を実行 重要なのは「いずれか」ではなく「すべて」のトライグラムが存在する文書が候補になる点である。もし「いずれか」だと、無関係な文書が大量に候補に含まれてしまう。 Recheck処理が必要な理由 n-gramインデックスでは、インデックスレベルでの検索後に必ずRecheck処理が必要になる。 具体例 以下のような状況を考える。 本文: 「小学校校長」 クエリ: 「小学校長」 3-gramで分割すると： 「小学校校長」→ 小学校, 学校校, 校校長 「小学校長」→ 小学校, 学校長 「小学校」が共通しているため、n-gramレベルでは「小学校校長」が候補として抽出される。しかし実際には「小学校長」という文字列は含まれていない。 このようなfalse positive（誤検出）を除外するため、インデックスで絞り込んだ候補に対して、実際に検索キーワードが含まれているかを厳密にチェックする必要がある。これがRecheck処理である。 pg_trgmとpg_bigmの選択 PostgreSQLには2つの主要なn-gram拡張がある。 pg_trgm: 3-gram方式、PostgreSQL本体にcontribとして付属 pg_bigm: 2-gram方式、サードパーティ製（NECが開発） 比較表 機能 pg_trgm pg_bigm エコシステム PostgreSQLコミュニティ サードパーティ ILIKE対応 ○ × 2文字以下の検索 × ○ Recheck無効化 × ○ インデックスサイズ 小 大（約2倍） なぜpg_trgmが選ばれたか 参考記事では、以下の理由でpg_trgmのみを採用している。 ...