テキストバッファの再実装
2018年3月23日 Peng Lyu, @njukidreborn
Visual Studio Code 1.21 リリースには、速度とメモリ使用量の両面で大幅にパフォーマンスが向上した、まったく新しいテキストバッファ実装が含まれています。このブログ記事では、これらの改善につながったデータ構造とアルゴリズムをどのように選択し、設計したかの経緯をお伝えしたいと思います。
JavaScript プログラムのパフォーマンスに関する議論では、通常、どの程度をネイティブコードで実装すべきかという議論が含まれます。VS Code のテキストバッファについては、1年以上前にこれらの議論が始まりました。詳細な調査の結果、テキストバッファの C++ 実装は大幅なメモリ節約につながる可能性があることがわかりましたが、期待していたパフォーマンスの向上は見られませんでした。カスタムのネイティブ表現と V8 の文字列の間で文字列を変換するのはコストがかかり、私たちの場合、C++ でテキストバッファ操作を実装することによって得られるはずのパフォーマンスが損なわれました。この点については、この記事の最後で詳しく説明します。
ネイティブ化しない場合、JavaScript/TypeScript コードを改善する方法を見つける必要がありました。 こちらの Vyacheslav Egorov 氏のブログ記事は、JavaScript エンジンを限界までプッシュし、可能な限り多くのパフォーマンスを引き出す方法を示しています。低レベルのエンジンのトリックを使わなくても、より適切なデータ構造とより高速なアルゴリズムを使用することで、1桁以上も速度を向上させることが可能です。
以前のテキストバッファのデータ構造
エディターのメンタルモデルは行ベースです。開発者はソースコードを1行ずつ読み書きし、コンパイラーは行/列ベースの診断を提供し、スタックトレースには行番号が含まれ、トークン化エンジンは行ごとに実行されます。単純ではありますが、VS Code を動かすテキストバッファの実装は、Monaco プロジェクトを開始した当初からほとんど変更されていません。行の配列を使用していましたが、一般的なテキストドキュメントは比較的小さいため、非常にうまく機能していました。ユーザーが入力しているとき、配列内で変更する行を見つけて置き換えました。新しい行を挿入するときは、新しい行オブジェクトを行配列にスプライスし、JavaScript エンジンが重い処理を行っていました。
しかし、特定のファイルを開くと VS Code で Out-Of-Memory クラッシュが発生するというレポートが届き続けました。たとえば、あるユーザーは 35 MB のファイルを開けませんでした。根本原因は、ファイルに行が多すぎること、1370 万行でした。各行に ModelLine オブジェクトを作成し、すべてのオブジェクトが約 40〜60 バイトを使用していたため、行配列はドキュメントを保存するために約 600MB のメモリを使用しました。これは、初期ファイルサイズの約 20 倍です！
行配列表現のもう1つの問題は、ファイルを開く速度でした。行の配列を構築するには、コンテンツを行区切りで分割して、行ごとに文字列オブジェクトを取得する必要がありました。分割自体がパフォーマンスを損なうことは、後でベンチマークで確認できます。
新しいテキストバッファの実装を見つける
古い行配列表現は、作成に時間がかかり、多くのメモリを消費する可能性がありますが、高速な行ルックアップを提供します。理想的な世界では、ファイルのテキストのみを保存し、追加のメタデータは保存しません。したがって、メタデータをあまり必要としないデータ構造を探し始めました。さまざまなデータ構造を検討した後、piece table が最初に始めるのに適した候補である可能性があることがわかりました。
piece table を使用してメタデータをあまり使用しないようにする
piece table は、テキストドキュメント（TypeScript のソースコード）に対する一連の編集を表すために使用されるデータ構造です。
class PieceTable {
original: string; // original contents
added: string; // user added contents
nodes: Node[];
}
class Node {
type: NodeType;
start: number;
length: number;
}
enum NodeType {
Original,
Added
}
ファイルが最初にロードされた後、piece table には original フィールドにファイルコンテンツ全体が含まれています。added フィールドは空です。NodeType.Original 型の単一ノードがあります。ユーザーがファイルの最後にタイプすると、新しいコンテンツを added フィールドに追加し、NodeType.Added 型の新しいノードをノードリストの最後に挿入します。同様に、ユーザーがノードの中央を編集すると、そのノードを分割し、必要に応じて新しいノードを挿入します。
以下の動画は、piece table 構造でドキュメントを1行ずつアクセスする方法を示しています。 2つのバッファ（original と added）と3つのノード（これは original コンテンツの中央への挿入によって引き起こされます）があります。
piece table の初期メモリ使用量はドキュメントのサイズに近く、変更に必要なメモリは編集回数と追加されたテキストに比例します。したがって、通常、piece table はメモリを有効に活用します。ただし、メモリ使用量を低く抑えるための代償として、論理行へのアクセスが遅くなります。たとえば、1000 行目のコンテンツを取得したい場合、ドキュメントの先頭からすべての文字を反復処理し、最初の 999 個の改行を見つけ、次の改行まで各文字を読み取るしか方法はありません。
より高速な行ルックアップのためにキャッシングを使用する
従来の piece table ノードにはオフセットのみが含まれていますが、行コンテンツのルックアップを高速化するために改行情報を追加できます。改行位置を格納する直感的な方法は、ノードのテキストで検出された各改行のオフセットを格納することです。
class PieceTable {
original: string;
added: string;
nodes: Node[];
}
class Node {
type: NodeType;
start: number;
length: number;
lineStarts: number[];
}
enum NodeType {
Original,
Added
}
たとえば、特定の Node インスタンスの 2 行目にアクセスする場合、node.lineStarts[0] と node.lineStarts[1] を読み取ることができます。これにより、行が開始および終了する相対オフセットが得られます。ノードに改行がいくつあるかを知っているので、ドキュメント内のランダムな行へのアクセスは簡単です。ターゲットの改行を含むノードが見つかるまで、最初のノードから順に各ノードを読み取ります。
アルゴリズムは単純なままであり、文字単位で反復処理するのではなく、テキストのチャンク全体をジャンプできるようになったため、以前よりも効果的です。後で、さらに改善できることがわかります。
文字列連結の罠を避ける
piece table は、ディスクからロードされた元のコンテンツ用のバッファと、ユーザー編集用の別のバッファの2つのバッファを保持します。 VS Code では、Node.js fs.readFile を使用してテキストファイルをロードしており、64KB チャンクでコンテンツを配信します。したがって、ファイルがたとえば 64 MB の場合、1000 個のチャンクを受信します。すべてのチャンクを受信した後、それらを1つの大きな文字列に連結して、piece table の original フィールドに格納できます。
これは V8 が邪魔をするまでは合理的です。 500MB のファイルを開こうとしたところ、使用していた V8 のバージョンでは、最大文字列長が 256MB であるため、例外が発生しました。この制限は将来の V8 バージョンで 1GB に引き上げられますが、それは問題を本当に解決するものではありません。
original バッファと added バッファを保持する代わりに、バッファのリストを保持できます。そのリストを短く保つことも、fs.readFile から返されるものからインスピレーションを得て、文字列連結を避けることもできます。ディスクから 64KB チャンクを受信するたびに、それを直接 buffers 配列にプッシュし、このバッファを指すノードを作成します。
class PieceTable {
buffers: string[];
nodes: Node[];
}
class Node {
bufferIndex: number;
start: number; // start offset in buffers[bufferIndex]
length: number;
lineStarts: number[];
}
平衡二分探索木を使用して行ルックアップを高速化する
文字列連結が不要になったことで、大きなファイルを開くことができるようになりましたが、これにより別の潜在的なパフォーマンスの問題が発生します。たとえば、64MB のファイルをロードすると、piece table には 1000 個のノードが含まれます。すべてのノードに改行位置をキャッシュしても、どの絶対行番号がどのノードにあるかはわかりません。行のコンテンツを取得するには、その行を含むノードが見つかるまで、すべてのノードを順番に調べる必要があります。この例では、探している行番号に応じて、最大 1000 個のノードを反復処理する必要があります。したがって、最悪の場合の時間計算量は O(N) です（N はノードの数です）。
各ノードに絶対行番号をキャッシュし、ノードのリストでバイナリ検索を使用すると、ルックアップ速度が向上しますが、ノードを変更するたびに、後続のすべてのノードにアクセスして行番号の差分を適用する必要があります。これは受け入れられませんが、バイナリ検索のアイデアは優れています。同じ効果を得るために、平衡二分探索木を活用できます。
ここで、ツリーノードを比較するためのキーとして、どのメタデータを使用するかを決定する必要があります。前述のように、ドキュメント内のノードのオフセットまたは絶対行番号を使用すると、編集操作の時間計算量が O(N) になります。時間計算量を O(log n) にしたい場合は、ツリーノードのサブツリーのみに関連するものが必要です。したがって、ユーザーがテキストを編集すると、変更されたノードのメタデータを再計算し、メタデータの変更を親ノードに沿ってルートまですべてバブルアップします。
Node に 4 つのプロパティ (bufferIndex、start、length、lineStarts) しかない場合、結果を見つけるのに数秒かかります。高速化するために、ノードの左サブツリーのテキスト長と改行カウントも格納できます。これにより、ツリーのルートからのオフセットまたは行番号による検索が効率的になります。右サブツリーのメタデータを格納することも同様ですが、両方をキャッシュする必要はありません。
クラスは次のようになります。
class PieceTable {
buffers: string[];
rootNode: Node;
}
class Node {
bufferIndex: number;
start: number;
length: number;
lineStarts: number[];
left_subtree_length: number;
left_subtree_lfcnt: number;
left: Node;
right: Node;
parent: Node;
}
さまざまな種類の平衡二分探索木の中で、赤黒木を選択しました。これは、より「編集」に適しているためです。
オブジェクトの割り当てを減らす
各ノードに改行オフセットを格納すると仮定します。ノードを変更するたびに、改行オフセットを更新する必要がある場合があります。たとえば、999 個の改行を含むノードがあるとします。lineStarts 配列には 1000 個の要素があります。ノードを均等に分割すると、2 つのノードが作成され、それぞれ約 500 個の要素を含む配列があります。線形メモリ空間で直接操作しているわけではないため、配列を 2 つに分割する方が、ポインターを移動するよりもコストがかかります。
朗報は、piece table のバッファは読み取り専用（元のバッファ）または追記のみ可能（変更されたバッファ）であるため、バッファ内の改行は移動しないことです。 Node は、対応するバッファ上の改行オフセットへの 2 つの参照を保持するだけで済みます。行うことが少なければ少ないほど、パフォーマンスは向上します。ベンチマークでは、この変更を適用すると、実装におけるテキストバッファ操作が 3 倍高速になることがわかりました。ただし、実際の実装については後ほど詳しく説明します。
class Buffer {
value: string;
lineStarts: number[];
}
class BufferPosition {
index: number; // index in Buffer.lineStarts
remainder: number;
}
class PieceTable {
buffers: Buffer[];
rootNode: Node;
}
class Node {
bufferIndex: number;
start: BufferPosition;
end: BufferPosition;
...
}
Piece tree
このテキストバッファを 「行モデル用に最適化された赤黒木によるマルチバッファ piece table」 と呼びたいと思います。しかし、毎日の朝会で、誰もが自分の近況を共有するのに 90 秒しか制限されていない場合、この長い名前を何度も繰り返すのは賢明ではありません。そこで、私は単にそれを 「piece tree」 と呼び始めました。これは、それが何であるかを反映しています。
このデータ構造を理論的に理解することは1つのことですが、現実世界のパフォーマンスは別のことです。使用する言語、コードが実行される環境、クライアントが API を呼び出す方法、およびその他の要因が結果に大きな影響を与える可能性があります。ベンチマークは包括的な全体像を提供できるため、元の行配列実装と piece tree 実装に対して、小/中/大ファイルでベンチマークを実行しました。
準備
結果を伝えるために、オンラインで現実的なファイルを探しました。
- checker.ts - 1.46 MB、26k 行。
- sqlite.c - 4.31MB、128k 行。
- ロシア語-英語バイリンガル辞書 - 14MB、552k 行。
手動でいくつかの大きなファイルを作成しました。
- 新しく開いた VS Code Insider の Chromium ヒープスナップショット - 54MB、3M 行。
- checker.ts X 128 - 184MB、3M 行。
1. メモリ使用量
ロード直後の piece tree のメモリ使用量は、元のファイルサイズに非常に近く、古い実装よりも大幅に低くなっています。最初のラウンドは、piece tree の勝利です。
2. ファイルのオープン時間
改行の検索とキャッシュは、ファイルを文字列の配列に分割するよりもはるかに高速です。
3. 編集
2 つのワークフローをシミュレートしました。
- ドキュメント内のランダムな位置で編集を行う。
- 順番に入力する。
これらの 2 つのシナリオを模倣しようとしました。1000 回のランダム編集または 1000 回の連続挿入をドキュメントに適用し、各テキストバッファに必要な時間を確認します。
予想どおり、ファイルが非常に小さい場合、行配列が勝利します。小さい配列内のランダムな位置にアクセスして、約 100〜150 文字の文字列を調整するのは非常に高速です。ファイルに行数が多い（10 万行以上）と、行配列は詰まり始めます。大きなファイルでの連続挿入は、JavaScript エンジンが大きな配列のサイズを変更するために多くの作業を行うため、状況を悪化させます。 piece tree は、各編集が文字列の追加といくつかの赤黒木操作であるため、安定した動作をします。
4. 読み取り
テキストバッファの場合、最もホットなメソッドは getLineContent です。これは、ビューコード、トークナイザー、リンク検出器、およびドキュメントコンテンツに依存するほぼすべてのコンポーネントによって呼び出されます。コードの一部は、リンク検出器のようにファイル全体を走査しますが、他のコードは、ビューコードのように連続した行のウィンドウのみを読み取ります。そこで、さまざまなシナリオでこのメソッドをベンチマークすることにしました。
- 1000 回のランダム編集を行った後、すべての行に対して
getLineContentを呼び出す。 - 1000 回の連続挿入を行った後、すべての行に対して
getLineContentを呼び出す。 - 1000 回のランダム編集を行った後、10 個の異なる行ウィンドウを読み取る。
- 1000 回の連続挿入を行った後、10 個の異なる行ウィンドウを読み取る。
ジャーン！ piece tree のアキレス腱を見つけました。大きなファイルで、1000 回の編集を行うと、数千または数万のノードにつながります。行のルックアップは O(log N) ですが、N はノードの数であり、行配列が享受していた O(1) よりも大幅に多くなります。
数千回の編集を行うことは比較的まれです。大きなファイルで一般的に発生する文字シーケンスを置き換えた後に発生する可能性があります。また、各 getLineContent 呼び出しはマイクロ秒単位で話しているので、現時点では心配していません。 getLineContent 呼び出しのほとんどは、ビューのレンダリングとトークン化からのものであり、行コンテンツの後処理の方がはるかに時間がかかります。 DOM の構築とレンダリング、またはビューポートのトークン化には通常数十ミリ秒かかり、そのうち getLineContent は 1% 未満しか占めていません。それにもかかわらず、最終的には正規化ステップを実装することを検討しています。正規化ステップでは、多数のノードなどの特定の条件が満たされた場合に、バッファとノードを再作成します。
結論と注意点
piece tree は、行ベースのルックアップを除いて、ほとんどのシナリオで行配列よりも優れたパフォーマンスを発揮します。これは予想どおりでした。
学んだ教訓
- この再実装から学んだ最も重要な教訓は、常に現実世界のプロファイリングを行うことです。ホットになるだろうという私の仮定が現実と一致しないことに気づくたびに、そう思いました。たとえば、piece tree の実装を開始したとき、
insert、delete、searchの 3 つのアトミック操作のチューニングに焦点を当てました。しかし、VS Code に統合したところ、これらの最適化はどれも重要ではありませんでした。最もホットなメソッドはgetLineContentでした。 CRLFまたは混合改行シーケンスの処理は、プログラマーの悪夢です。すべての変更について、キャリッジリターン/ラインフィード (CRLF) シーケンスを分割するかどうか、または新しい CRLF シーケンスを作成するかどうかを確認する必要があります。ツリーのコンテキストで、考えられるすべてのケースに対処するには、正しく高速なソリューションが得られるまで、数回の試行が必要でした。- GC は CPU 時間を簡単に食いつぶす可能性があります。以前のテキストモデルでは、バッファは配列に格納されていると想定しており、
getLineContentを頻繁に使用していましたが、場合によっては必要ありませんでした。たとえば、行の最初の文字の文字コードを知りたいだけの場合、最初にgetLineContentを使用してからcharCodeAtを実行しました。 piece tree では、getLineContentはサブストリングを作成し、文字コードを確認した後、行サブストリングはすぐに破棄されます。これは無駄であり、より適切なメソッドの採用に取り組んでいます。
ネイティブにしない理由
冒頭で、この質問に戻ると約束しました。
要約: 試しました。うまくいきませんでした。
C++ でテキストバッファ実装を構築し、ネイティブノードモジュールバインディングを使用して VS Code に統合しました。テキストバッファは VS Code で一般的なコンポーネントであるため、テキストバッファに対して多くの呼び出しが行われました。呼び出し側と実装の両方が JavaScript で記述されている場合、V8 はこれらの呼び出しの多くをインライン化できました。ネイティブテキストバッファを使用すると、JavaScript ⇔ C++ のラウンドトリップが発生し、ラウンドトリップの数を考えると、すべてが遅くなりました。
たとえば、VS Code の 行コメントの切り替え コマンドは、選択したすべての行をループ処理し、それらを1つずつ分析することによって実装されます。このロジックは JavaScript で記述されており、各行に対して TextBuffer.getLineContent を呼び出します。各呼び出しに対して、C++/JavaScript の境界を越えることになり、すべてのコードが上に構築されている API を尊重するために、JavaScript string を返す必要があります。
私たちの選択肢は単純です。 C++ では、getLineContent を呼び出すたびに新しい JavaScript string を割り当てるか（これは実際の文字列バイトをコピーすることを意味します）、V8 の SlicedString または ConstString 型を活用します。ただし、基になるストレージも V8 の文字列を使用している場合にのみ、V8 の文字列型を使用できます。残念ながら、V8 の文字列はマルチスレッドセーフではありません。
TextBuffer API を変更するか、JavaScript/C++ の境界コストを回避するためにより多くのコードを C++ に移動することで、これを克服しようとした可能性があります。しかし、私たちは同時に 2 つのことを行っていました。行配列とは異なるデータ構造を使用してテキストバッファを作成し、JavaScript ではなく C++ で作成していました。したがって、効果があるかどうかわからないものに半年を費やすのではなく、テキストバッファのランタイムを JavaScript に保持し、データ構造と関連するアルゴリズムのみを変更することにしました。私たちの意見では、これは正しい判断でした。
今後の作業
最適化する必要のあるケースがまだいくつかあります。たとえば、検索 コマンドは現在行単位で実行されていますが、そうすべきではありません。行サブストリングのみが必要な場合に、getLineContent への不要な呼び出しを回避することもできます。これらのさらなる最適化を段階的にリリースしていきます。これらのさらなる最適化がなくても、新しいテキストバッファ実装は、以前よりも優れたユーザーエクスペリエンスを提供し、最新の安定版 VS Code バージョンでデフォルトになりました。
ハッピーコーディング！
Peng Lyu, VS Code チームメンバー @njukidreborn