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

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でメモリ不足（Out-Of-Memory）のクラッシュが発生するという報告が届き続けていました。例えば、あるユーザーは35 MBのファイルを開くことができませんでした。根本原因は、そのファイルに行が多すぎること、つまり1370万行あったことです。各行にModelLineオブジェクトを作成し、各オブジェクトが約40～60バイトを使用するため、行配列はドキュメントを保存するために約600MBのメモリを消費していました。これは元のファイルサイズの約20倍です！

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

新しいテキストバッファの実装を見つける

古い行配列表現は、作成に多くの時間を要し、多くのメモリを消費しますが、行のルックアップは高速です。理想的な世界では、ファイルのテキストのみを保存し、追加のメタデータは保存しないでしょう。そこで、より少ないメタデータを必要とするデータ構造を探し始めました。様々なデータ構造を検討した結果、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構造でドキュメントを行ごとにアクセスする方法を示しています。これには2つのバッファ（originalとadded）と3つのノードがあります（これはoriginalコンテンツの途中に挿入が行われたことによって発生します）。

Traditional piece table

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のチャンクでコンテンツを配信します。したがって、例えば64MBのような大きなファイルの場合、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 tree

このテキストバッファを「複数バッファピースツリー、行モデルに最適化済み」と呼びたいのですが、毎日のスタンドアップミーティングでは、各自が90秒という制限時間内で自分の進捗を共有しなければならないため、この長い名前を何度も繰り返すのは賢明ではありません。そこで、私は単に「piece tree」と呼び始めました。これが実態を反映しています。

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

準備

結果を伝えるために、私は現実的なファイルをオンラインで探しました。

checker.ts - 1.46 MB, 26k 行。
sqlite.c - 4.31MB, 128k 行。
ロシア語-英語バイリンガル辞書 - 14MB, 552k 行。

そして、手動でいくつか大きなファイルを作成しました。

新しく開いたVS Code InsiderのChromiumヒープスナップショット - 54MB, 300万行。
checker.ts X 128 - 184MB, 300万行。

1. メモリ使用量

piece treeのロード直後のメモリ使用量は、元のファイルサイズに非常に近く、以前の実装よりも大幅に少なくなっています。第1ラウンド、piece treeの勝利です。

Memory usage

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

改行を見つけてキャッシュする方が、ファイルを文字列の配列に分割するよりもはるかに高速です。

File opening

3. 編集

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

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

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

Random edits

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

4. 読み取り

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

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

Read all lines after random edits

TA-DA、piece treeの弱点を発見しました。1000回の編集が行われた大規模なファイルは、数千から数万のノードにつながります。行のルックアップはO(log N)（Nはノード数）ですが、これは行配列が享受していたO(1)よりもはるかに遅いです。

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

結論と注意点

piece treeは、ほとんどのシナリオでライン配列を上回るパフォーマンスを発揮しますが、予想通り、行ベースのルックアップは例外です。

学んだ教訓

この再実装が私に教えてくれた最も重要な教訓は、常に実際のプロファイリングを行うことです。私がどのメソッドがホットになるかについて立てた仮説が、毎回現実に合致しないことが分かりました。例えば、piece treeの実装を開始したとき、私は3つのアトミック操作、つまりinsert、delete、searchのチューニングに集中しました。しかし、VS Codeに統合してみると、それらの最適化はどれも重要ではありませんでした。最もホットなメソッドはgetLineContentだったのです。
CRLFまたは混合改行シーケンスの処理は、プログラマーにとって悪夢です。変更のたびに、キャリッジリターン/ラインフィード（CRLF）シーケンスを分割するか、新しいCRLFシーケンスを作成するかを確認する必要があります。ツリーのコンテキストで、考えられるすべてのケースに対処するには、正しく高速なソリューションが見つかるまで数回の試行を要しました。
GCは簡単にCPU時間を食い尽くすことがあります。私たちのテキストモデルは、バッファが配列に格納されていると仮定しており、必要がない場合でも頻繁にgetLineContentを使用していました。例えば、行の最初の文字の文字コードを知りたいだけの場合、まずgetLineContentを呼び出してからcharCodeAtを実行していました。piece treeでは、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