テキストバッファの再実装

2018年3月23日 Peng Lyu, @njukidreborn

Visual Studio Code 1.21リリースには、速度とメモリ使用量の両面でパフォーマンスが大幅に向上した、まったく新しいテキストバッファ実装が含まれています。このブログ記事では、これらの改善につながったデータ構造とアルゴリズムをどのように選択し、設計したかについてお話ししたいと思います。

JavaScriptプログラムのパフォーマンスに関する議論では、通常、どの程度ネイティブコードで実装すべきかという議論が伴います。VS Codeのテキストバッファに関しては、これらの議論は1年以上前に始まりました。詳細な調査の結果、テキストバッファのC++実装は大幅なメモリ節約につながる可能性があることがわかりましたが、期待していたパフォーマンス向上は見られませんでした。カスタムのネイティブ表現とV8の文字列間で文字列を変換するコストは高く、我々の場合、C++でテキストバッファ操作を実装することで得られるパフォーマンスを損なってしまいました。この点については、この記事の最後で詳しく説明します。

ネイティブに移行しないことで、JavaScript/TypeScriptコードを改善する方法を見つける必要がありました。Vyacheslav Egorovによるこの記事のような示唆に富むブログ記事は、JavaScriptエンジンを限界まで活用し、可能な限りパフォーマンスを引き出す方法を示しています。低レベルのエンジントリックを使わなくても、より適したデータ構造と高速なアルゴリズムを使用することで、速度を1桁以上向上させることはまだ可能です。

以前のテキストバッファデータ構造

エディターのメンタルモデルは行ベースです。開発者はソースコードを行ごとに読み書きし、コンパイラは行/列ベースの診断を提供し、スタックトレースには行番号が含まれ、トークン化エンジンは行ごとに実行されます。単純ではありますが、VS Codeを支えるテキストバッファの実装は、Monacoプロジェクトを開始した最初の日からほとんど変わっていませんでした。行の配列を使用しており、一般的なテキストドキュメントは比較的小さいため、非常にうまく機能していました。ユーザーが入力すると、配列内で変更する行を特定して置換しました。新しい行を挿入すると、新しい行オブジェクトを行配列にスプライスし、JavaScriptエンジンが重い処理を代わりに実行してくれました。

しかし、特定のファイルを開くとVS Codeでメモリ不足のクラッシュが発生するという報告を受け続けました。例えば、あるユーザーは35MBのファイルを開くことができませんでした。根本原因は、そのファイルに行が多すぎたこと、1370万行でした。各行に対して`ModelLine`オブジェクトを作成し、各オブジェクトが約40～60バイト使用していたため、行配列はドキュメントを格納するために約600MBのメモリを使用していました。これは最初のファイルサイズの約20倍です！

行配列表現のもう一つの問題は、ファイルを開く速度でした。行の配列を構築するために、コンテンツを行区切りで分割する必要があり、それによって行ごとに文字列オブジェクトが得られました。分割自体がパフォーマンスを損なうことは、後述のベンチマークで確認できます。

新しいテキストバッファの実装を探す

古い行配列表現は、作成に時間がかかり、多くのメモリを消費しますが、高速な行ルックアップを提供します。理想的な世界では、ファイルのテキストのみを保存し、追加のメタデータは保存しません。そこで、より少ないメタデータを必要とするデータ構造を探し始めました。さまざまなデータ構造を検討した結果、ピーステーブルが良い候補であるとわかりました。

ピーステーブルを使用してメタデータが多すぎるのを避ける

ピーステーブルは、テキストドキュメント（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
}

ファイルが最初にロードされた後、ピーステーブルには`original`フィールドにファイル全体のコンテンツが含まれます。`added`フィールドは空です。`NodeType.Original`型の単一のノードがあります。ユーザーがファイルの末尾に入力すると、新しいコンテンツを`added`フィールドに追加し、ノードリストの末尾に`NodeType.Added`型の新しいノードを挿入します。同様に、ユーザーがノードの中央を編集すると、そのノードを分割し、必要に応じて新しいノードを挿入します。

以下の動画は、ピーステーブル構造でドキュメントを行ごとにアクセスする方法を示しています。2つのバッファ（`original`と`added`）と3つのノード（`original`コンテンツの途中に挿入されたことによる）があります。

Traditional piece table

ピーステーブルの初期メモリ使用量は、ドキュメントのサイズに近く、変更に必要なメモリは編集と追加されたテキストの数に比例します。したがって、通常、ピーステーブルはメモリを効率的に使用します。しかし、低メモリ使用量の代償として、論理行へのアクセスは遅くなります。例えば、1000行目のコンテンツを取得したい場合、ドキュメントの最初からすべての文字を繰り返し、最初の999行の改行を見つけ、次の改行まで各文字を読み込むしかありません。

より高速な行ルックアップのためのキャッシュの使用

従来のピーステーブルノードにはオフセットのみが含まれていましたが、行のコンテンツルックアップを高速化するために改行情報を追加できます。改行位置を保存する直感的な方法は、ノードのテキスト内で検出された各改行のオフセットを保存することです。

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]`を読み取ることで、行が開始および終了する相対オフセットを取得できます。ノードにいくつの改行があるかを知っているので、ドキュメント内のランダムな行にアクセスするのは簡単です。最初のノードから目的の改行が見つかるまで各ノードを読み取ります。

アルゴリズムはシンプルであり、文字ごとに反復するのではなく、テキスト全体をジャンプできるようになったため、以前よりも優れた動作をします。後でさらに改善できることがわかります。

文字列連結の罠を避ける

ピーステーブルは、ディスクからロードされた元のコンテンツ用と、ユーザーの編集用の2つのバッファを保持します。VS Codeでは、Node.jsの`fs.readFile`を使用してテキストファイルをロードし、64KBのチャンクでコンテンツを配信します。そのため、例えば64MBのファイルの場合、1000個のチャンクを受け取ることになります。すべてのチャンクを受け取った後、それらを1つの大きな文字列に連結し、ピーステーブルの`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のファイルをロードした場合、ピーステーブルには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個の要素があるとします。ノードを均等に分割すると、それぞれ約500個の要素を含む配列を持つ2つのノードが作成されます。線形メモリ空間を直接操作しているわけではないため、配列を2つに分割することはポインタを移動するよりもコストがかかります。

良いニュースは、ピーステーブルのバッファが読み取り専用（元のバッファ）または追加専用（変更されたバッファ）のいずれかであるため、バッファ内の改行が移動しないことです。`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

ピースツリー

このテキストバッファを「複数バッファピーステーブル、赤黒木、行モデルに最適化」と呼びたいところですが、毎日のスタンディングミーティングで、各自が90秒以内に何をしてきたかを共有する際に、この長い名前を何度も繰り返すのは賢明ではありません。そこで、私は単に「ピースツリー」と呼び始めました。これは、その内容を反映しています。

このデータ構造を理論的に理解することは一つですが、実際のパフォーマンスは別の問題です。使用する言語、コードが実行される環境、クライアントがAPIを呼び出す方法、およびその他の要因が結果に大きく影響する可能性があります。ベンチマークは包括的な全体像を提供できるため、オリジナルの行配列実装とピースツリー実装に対して、小・中・大ファイルでベンチマークを実行しました。

準備

結果を明確にするために、オンラインで現実的なファイルを探しました。

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. メモリ使用量

ピースツリーのロード直後のメモリ使用量は、元のファイルサイズに非常に近く、古い実装よりも大幅に低いです。最初のラウンドでは、ピースツリーの勝利です。

Memory usage

2. ファイルオープン時間

改行の検索とキャッシュは、ファイルを文字列の配列に分割するよりもはるかに高速です。

File opening

3. 編集

2つのワークフローをシミュレートしました。

ドキュメント内のランダムな位置で編集を行う。
順次入力する。

これらの2つのシナリオを模倣しようとしました: ドキュメントに1000個のランダムな編集または1000個の連続した挿入を適用し、各テキストバッファがどのくらいの時間を必要とするかを確認します。

Random edits

予想通り、ファイルが非常に小さい場合は行配列が有利です。小さな配列のランダムな位置にアクセスし、100～150文字程度の文字列を調整するのは非常に高速です。ファイルに多くの行（100k行以上）がある場合、行配列は詰まり始めます。大きなファイルでの連続挿入は、JavaScriptエンジンが大きな配列のサイズ変更に多くの作業を行うため、この状況を悪化させます。ピースツリーは、各編集が単なる文字列の追加といくつかの赤黒木操作であるため、安定した動作をします。

4. 読み込み

我々のテキストバッファにおいて、最もホットなメソッドは`getLineContent`です。これはビューコード、トークナイザー、リンク検出器、そしてドキュメントコンテンツに依存するほぼすべてのコンポーネントによって呼び出されます。リンク検出器のようにファイル全体を走査するコードもあれば、ビューコードのように連続する行のウィンドウのみを読み取るコードもあります。そこで、さまざまなシナリオでこのメソッドをベンチマークすることにしました。

1000回のランダム編集後、すべての行に対して`getLineContent`を呼び出す。
1000回の連続挿入後、すべての行に対して`getLineContent`を呼び出す。
1000回のランダム編集後、10個の異なる行ウィンドウを読み取る。
1000回の連続挿入後、10個の異なる行ウィンドウを読み取る。

Read all lines after random edits

ご覧ください、ピースツリーのアキレス腱が見つかりました。数千の編集が加えられた大きなファイルは、数千または数万のノードにつながります。行の検索が`O(log N)`であっても（Nはノード数）、行配列が享受していた`O(1)`よりもはるかに大きいです。

何千もの編集が行われることは比較的稀です。大きなファイルでよく現れる文字シーケンスを置換した後に、その状態になるかもしれません。また、`getLineContent`の各呼び出しはマイクロ秒単位の話なので、現時点では懸念していません。`getLineContent`の呼び出しのほとんどは、ビューレンダリングとトークン化からのもので、行コンテンツの後処理の方がはるかに時間がかかります。DOM構築とレンダリング、またはビューポートのトークン化は通常数十ミリ秒かかり、その中で`getLineContent`が占める割合は1%未満です。それでも、ノード数が多いなどの特定の条件が満たされた場合にバッファとノードを再作成する正規化ステップを最終的に実装することを検討しています。

結論と注意点

ピースツリーはほとんどのシナリオでライン配列を上回りますが、予想通りラインベースの検索は例外です。

学んだこと

この再実装から学んだ最も重要な教訓は、常に実際のプロファイリングを行うことです。ホットになると仮定したメソッドが、常に現実と一致しないことに気づきました。例えば、ピースツリーの実装を始めたとき、私は3つの原子操作である`insert`、`delete`、`search`のチューニングに集中しました。しかし、VS Codeに統合してみると、これらの最適化はどれも重要ではありませんでした。最もホットなメソッドは`getLineContent`でした。
CRLFまたは混合改行シーケンスの処理は、プログラマの悪夢です。 変更するたびに、キャリッジリターン/ラインフィード（CRLF）シーケンスを分割するか、新しいCRLFシーケンスを作成するかを確認する必要があります。ツリーのコンテキストで、考えられるすべてのケースを処理するのに、正しく高速なソリューションが得られるまでに何度か試行錯誤しました。
GCは簡単にCPU時間を食いつぶす可能性があります。 かつてのテキストモデルは、バッファが配列に格納されていると仮定しており、必要がない場合でも`getLineContent`を頻繁に使用していました。例えば、行の最初の文字の文字コードを知りたいだけの場合でも、まず`getLineContent`を実行し、それから`charCodeAt`を実行していました。ピースツリーでは、`getLineContent`は部分文字列を作成し、文字コードを確認した後、その行の部分文字列はすぐに破棄されます。これは無駄であり、より適切なメソッドを採用するよう取り組んでいます。

なぜネイティブではないのか？

冒頭でこの質問に戻ると約束しました。

要約：試してみましたが、うまくいきませんでした。

C++でテキストバッファ実装を構築し、ネイティブNodeモジュールバインディングを使用して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