これまで数カ月にわたり、私たちはAtomのパフォーマンスの改善に取り組んできました。その結果、最適化するための課題として特に興味深いのが マーカ という構造体だと分かりました。マーカはバッファの内容が変更されても、バッファの論理的な領域を追跡することができます。例えば、以下の図で緑色のハイライトがかかった部分のマーカは、文字列を書き換えたとしても同じ領域に残り続けます。

マーカは、Atomの機能を幅広くサポートする基本的なプリミティブです。検索および置換を行う場合には、マーカを使うことで 検索結果のハイライト表示 ができます。スニペットの場合も、文字列を書き換える際にマーカを使い、 タブストップで移動する位置 を追跡することができます。さらにはスペルチェックの場合でも、マーカを使って スペルミスのある単語を抽出 したり、その単語を書き換える際の再チェックをしたりすることもできます。そもそもAtom自体がマーカを使って 選択やカーソルの機能を実装 しています。しかも、これはマーカ機能のほんの一部です。

しかし、ここ数回より前にリリースされたAtomでは、マーカのパフォーマンスは場合によっては厄介なものでもありました。例えば、検索および置換など、膨大な数のマーカを使う場合です。私たちはその問題を改善するために、ここ2カ月にわたって取り組んできたのですが、その内容が大変興味深いのでシェアすべきだと考えました。

なぜマーカの処理には時間がかかるのか

マーカのパフォーマンスを最適化するために私たちが行った方法を説明する前に、まずは 初期の頃のうまくいかなかった実装 を例に、何が悪かったのかを見ていきましょう。以前はバッファに変更をかけるたび、単純に全てのマーカを見直し、変更に従いマーカ位置をその都度計算していました。さらに悪いことに、効率的な範囲クエリを可能にしていたデータ構造の中で、それぞれのマーカの位置を更新していました。そのため、文字列のマーカを更新するのにかかる総コストが O(n*log(n)) （ n はマーカ総数）となってしまっていました。

マーカがそれほど多くない場合は、こうした作りになっていてもパフォーマンスは妥当でした。しかし、マーカの数が増えると、これが大きな問題となったのです。例えば、検索して置換を行う場合、検索結果をハイライト表示させるためマーカを使いますが、もし大きなファイルを対象に e で検索をかけたとしたらどうでしょうか。全てのキーストロークに対して何万、何十万というマーカが更新されるため、気の遠くなるような時間がかかり、うんざりすることでしょう。では、以下の図に示したAtom 0.198.0の CPUプロファイル をご覧ください。jQuery内でハイライト表示された全ての e に改行を入れたものです。このバージョンのAtomでは、実際にタイピングするのぐらい見苦しい状況です。

マーカの処理を速くした方法とは

私たちはマーカの処理数を広範囲にわたって減らすことで、この問題にじっくり取り組むことができました。例えば、検索結果に対してマーカを表示するのは、実際の画面に見えている範囲だけとすることもでき、それらが更新されるのはエディタがスクロールされたときとしました。とはいえ、マーカは非常に使用頻度の高い、便利に使える抽出機能です。このような重要なツールですから、極端な条件の下であっても、コストをかけずに簡単に使えるようにすることが必要でした。

最大の問題となっていたのは、「各マーカを絶対位置を表示させる」という単純な手法では、編集のたびに全てのマーカが見直されることになっていた点です。しかし、いつでも全てのマーカの正確な位置を把握する必要はありません。ただ実際に画面に見えている範囲でマーカがどこにあるのかということさえ分かれば十分なのです。それならば、画面が切り替わるタイミングでマーカの位置を計算できます。

訳注：バッファの変更に従いマーカを更新する際に必要となるコストは、画面に見えている分 だけに 対して線形にかかる

私たちは、マーカの処理をよりインクリメンタルに行う必要がありました。バッファに変更があるたび、むやみに全てのマーカの位置を算出するのではなく、情報が実際に必要とされるまで、まずは必要とする情報に関連付けられた処理の大部分を優先させる方法が必要だったのです。このため、実装を新たに変える必要がありました。

マーカを相対的に表記する

私たちは以下に示すダイアグラムから、問題を解決する重要な手がかりを得ました。文頭を編集すると、マーカがつけられた単語の位置は絶対的に変化します。しかし、 単語と単語の間 の距離は一定です。

マーカがつけられた単語と単語の間を編集しないかぎり、その単語間の距離は編集中も変わりません。この事実を利用することで、バッファに変更を加えた際に計算していたところのうち、その大部分について、計算する必要がなくなります。

今まで書いてきたとおり、私たちはマーカの状態を絶対的な位置として保持していました。

そうではなく、マーカの位置を単語と単語の間の距離でエンコードすることにしましょう。そうすることで、バッファを領域に細分化するのです。以下の図で示しているとおり、各領域は、その領域に何文字含まれるかを示す extent と、その領域に含まれるのがどのマーカなのかを示す marker id のセットと関連づけられています。

marker idは任意の方法で領域を超えて重複していてもよいということに注目してください。ある特定の領域に関連づけられているmarker idのセットには1つ以上のidが含まれるので、同じidが複数の連続した領域に関連づけられていることもあります。

効率的な更新方法

以下では、テキストを変更した際の影響を見るために、1つの領域のextentだけを更新する場合の例を挙げています。以下の図のように先頭の領域でextentが更新されることにより、あとに続く領域が（マーカの動きと連動して）正しい文字数分だけシフトしていることが分かるでしょう。

上記の実装における問題は、ある特定のマーカが入っている領域を探索するために、領域の始めから１つ１つ確認しながら、絶対的な位置を計算する必要があるということです。また、バッファに変更があった際にどの領域のextentを更新する必要があるのかということも探索しなければなりません。この方法を使えば、変更を加えたあとに全てのマーカを更新する必要がなくなります。解決に向けての取りかかりとしてはよさそうです。しかし、マーカの総数がn個ある場合、 O(n) の時間がかかります。

効率的な探索方法

最後のステップとして、以前のデータ構造で必要だった線形探索をしないで済むようにしましょう。これは単純なリストを平衡木に置き換えることによって実現します。平衡木を実装する方法は数多くあります。今回は、 B+木 をベースにしますが、それに少し手を加えたものを使いましょう。
どんな探索木にも当てはまる基本的な考え方ですが、木の上の方にあるノードは、その下にぶら下がっているノードの必須情報を 集約しています 。そのため、木の上から下に向かって探索していけば、木の大部分の探索を省略できるのです。この記事で例に挙げている領域木では、各内部ノードがその下にぶら下がる子ノードのextent全てを集約しており、子ノードのmarker idとも連動しています。先ほど示した、カラフルに重なり合ったマーカの探索木は、以下のようになります。

この構造を持つことで、様々な演算をさらに効率的に行うことができます。（O(n)ではなく O(log(n)) の速さになります）。テキストを挿入する際、更新が必要な領域を見つけるために、それぞれの領域に対して繰り返し処理を行う必要はありません。そうではなく、集約を利用して木の大部分の探索をスキップし、更新が必要なノードに直接アクセスできるのです。

例えば、22番目の位置に1文字挿入するとしましょう。その場合、目的とする位置を含むノードを上から下に探索することによって、22番目の位置を含んでいる領域に直接アクセスすることができます。

今挙げた例では小さな木を使ったので、大きな違いは見えません。しかし木が大きくなった場合にこの方法を使えば、以前の方法では計算しなければならなかった多数のノードをスキップできます。では、多くのマーカが存在するシナリオで、どれほどのノードをスキップできるかを実感するために、大きな木の例を見てみましょう。

ある特定のマーカがどの領域に存在するかを探す場合、木の上から下に向かって探索することができます。目的とするマーカを含む子ノードをたどり、オフセットの経過を追っていくのです。

範囲検索を行うこともできます。特定の領域と交わるマーカのセットをたどるのです。これは、膨大な数のマーカを全て処理するのではなく、実際に画面に見えているマーカのみに絞って処理する方法における最後のステップです。任意の数の更新をしながらエディタを再描画することで、画面に見えているマーカに対して効率的に検索をし、その領域のみを計算できるようになりました。計算する必要がないマーカに対しては、計算しません。

この場合について、 jquery.js の全てのハイライト済みの e に改行を入力した際のプロファイルを作ってみました。処理が終わるまでの合計時間は800ミリ秒だったのが約50ミリ秒まで短縮されました。

今回ご紹介したのは、私たちがマーカを最適化するために利用した方法の概略に過ぎません。しかしこの方法は完全な実装を検討する際のよい出発点となるはずで、その実装には、B木を管理する marker-index class 、そして補助的な詳細を扱う marker-store wrapper class が含まれてくることでしょう。完全な実装では、完全なマーカAPIをサポートするために、マーカの無効化、平衡木のメンテ、そしてアンドゥ・リドゥ時のマーカ状態の回復など、他にも多くのことを考慮しています。

まとめ

Atomにおいて、私たちが早期に最適化した機能は、DOMとのインタラクションの改善を考慮したものでした。近いうちに、レンダリングの改善もブログで発信していくつもりです。今のところ、システムのより深いレイヤ部分に焦点を当てて考え始めるための、十分な進捗を得られていると思います。ElectronでのNodeの統合は、重要なAtomのコンポーネントを、必要に応じてC++にドロップするというオプションを示してくれました。今回のマーカに関する徹底的な見直しは、よいアルゴリズムを単に実装することによって改善できるということを示す、好例となるでしょう。ここ数カ月の間に、Atomは以前と比べてかなり処理が速くなりました。今後もこのような最適化をシステムのそれぞれの場所に適用していけば、継続して改善していくことができると思います。