Virtual DOMのアルゴリズムが知りたくてvirtual-domのコードを読んだ話

DOM javascript

Reactの登場以来気になっていた、Virtual DOMアプローチの具体的な差分抽出手法について、virtual-domを読んで確認してみた。

Reactをいきなり読むのは面倒くさかった・ミニマムな実装から読みたかったというのが、こっちを選択した理由。Reactのアルゴリズムが参考にされているものの、Reactには存在する特定の最適化が入ってないかもしれないので、あくまでもReact系のVirtual DOMを実装するには最低限何が必要かを知る程度のものと判断してほしい。

virtual-domについて

ReactのVirtual DOM部分だけを切り出して再利用可能な形で再実装したライブラリ。elm-htmlとかMercuryといった箇所でvDOMインフラとして既に使われているので、まったくの趣味プロダクトという訳でもなくなっている。

README.md中での触れられている通り、Virtual DOM and diffing algorithmというコンセプトドキュメントをそのまま実装に落としたという感じで、実装自体はきわめて素朴。

実態としてはvtreeとvdomという依存パッケージのフロントエンドのような形式になっており、

  • virtual-dom: Virtual DOMの生成に使うh()という関数の提供と、関連パッケージのre-exportを行う
  • vdom: 出力されたパッチの適用と、Real DOMの出力を行う.
  • vtree: Virtual DOMの構造体とdiffの実装、パッチの出力を行う

のように、virtual-dom -> vdom -> vtreeのような依存関係になっている。

読んだリビジョン

全体的なコード感として、コード量自体は大したこと無いんだけど、コメントが少ないので読みにくい。最適化のためにこういうアプローチにしているのか、突貫作業の結果、こういうアプローチにしているのかよくわからん箇所も多い（Arrayではなく, Objectを数値をkeyとしたハッシュマップにしてリストとして取り扱っている箇所がある）。shapeを意識したコードにすることで高速化の余地もありそうだけど、そもそもコメントが無いのでその辺りの判断基準がわからない。ともすれば、実は何も最適化していないのかもしれない。whyの書かれたコメント重要な例ですね。この辺りはReactとはまったく対照的と言える。

可読性を考えると、TypeScriptとかRustとかgolangで再実装したくなってくる。

それと、テスト結果からは、どうもIE6もサポートしているらしい。たしかに、ES5相当の機能を使っている箇所は見当たらないので信頼しても良いとは思う（が、"use strict"も使わないとか、もう少しやりようはあるんでないの感もある）。

Virtual DOM 概観

構成要素

vDOMのtreeを構成する要素は基本的に2種類。VNodeかVTextの二種類しかない。他にもVWidgetとVThunkというtreeの構成要素があるんだけど、無くてもtreeもpatchも作れるし、具体的な生成方法とユースケースが見つからないので今回は取り扱わない。

VNodeは、ユニークidとして取り扱われるkeyプロパティを持つことが可能で、これを適切に設定してやることで後述する比較がより効率的になる実装となっている。が、必須ではない。 また、VNodeはcountプロパティを持っており、子孫ノードの数をこれ経由で取得できる。

ちなみにVTextはVNodeとは別物で、W3C DOMのように、TextがNodeインターフェースを持つということはない。要はいらんということなのでしょうな。なので、VTextの場合、単純な中身のテキスト比較で同一性の判定を行っている。

VPatchは、検出された差分をもとに生成されるパッチ情報。ここにあるように、要素単位でのノードの追加・削除・並び替えなどを表す。直和型でパターンマッチしたくなる感じの構造体ですね。

差分検出

参考元がVirtual DOM and diffing algorithmであり、それ自体がPerformance Calendar » React’s diff algorithmを元に記述されているので、当然と言えば当然であるが、アルゴリズムとしては、Event Delegationが無くツリー操作に限定している点をのぞけば、ほぼ同一。

ノードの変更

あるノードが変更された場合、原則として、そのノード以下すべてが新規ノードで置き換えられるようになっている（これはvtreeのパッチ生成だけでなくvdomの実装上の問題）。

だが、ノードのキーが同じかつ、localNameやnamespaceも同じ場合には、ノードの入れ替えではなくプロパティの更新のみで済ませることが可能.

ノードを階層ごとに比較

原則として、「rootからの階層が同じ」かつ「sibling内でのindexが同じ」ノード群を一塊と見なし比較を行うことで計算量O(n)で処理を済ませている。これは、比較するAB間でのすべてのノードを先頭から順に比較しようとすると、計算量がO(n3)となってしまうため。あくまでもツリーが極端に変更される（rootの子の構造がガラリと入れ替わる）ようなことが無いという前提で計算量を稼ぐ戦略。ツリー内のすべてのノードの変更履歴を追跡しているわけではなく、subtreeを別の位置（階層）に移動させるようなケースでは、移動されたsubtreeがすべて新規に生成されることになってしまい、差分描画する対象が増える。

各階層のsiblingの比較

各ノードのキーを元に、比較対象となるAとBの間でのノードの位置を検出し、Aでn番目のノードはbのk番目、のようなテーブルを作る。そして、並び替えの情報をパッチに持たせて、適用フェーズで並び替え。

キーが無くても並び替えできるけど新しい順序の構築の効率悪そう、というかキーを付けないケースがあるのでロジックややこしくなってる。

ちなみに消えた（消えるべき）ノードは別途削除用のパッチで消す。

ツリーをpreorderのリストとして取り扱う

パッチの適用箇所を高速かつ簡単に発見するために、ツリーは、preorderでの順番がindexとなる1次元リストとして見なされる。先述したように、各VNodeは保持している子孫ノードをcountプロパティ経由で取得できるため、リストをpreorderでトラバースする際、ノードAの隣のノードBのindexは、「Aのindex + A.count」で表現することができる。

生成したパッチを、このindexを添字にパッチのリストに対して追加することで、差分の適用先を的確かつ高速に発見できるというわけ（再帰も減らせる）。

パッチの適用

vdomのパッチの適用はReal DOMに対して直接行われる. 前述のパッチのリストに合わせて、DOMツリーをいったんpreorderのリストにし、それに対してパッチの適用処理を行う。

まとめ

  • 賢く変更結果を追跡し、変更箇所を最小限に留めるようなアルゴリズムではない
    • その分、探索時間を稼ぐ方向性
  • 断続的にDOMを変更していくのではなく、Window.requestAnimationFrame()などのタイミングで一気にバッチ処理的にDOMを変更することで描画への影響を減らすのが前提となっている
    • たしかVue.jsも似たようなアプローチだった気がする

だいたいこんな感じ。 そのうちReactも読んで固有の最適化パスとか持ってないか探してみたいけど、あれはあれで面倒くさそうな匂いがしてるので、どうしたものか……

追記: VWidgetについて

ツッコミを受けた。

diffアルゴリズムだけ気にしてて、それ以外興味なかったんで完全に失念していた……

VWidget

実装を見るに、Widgetとして独自のコンポーネントを定義できるものと思われる。

コードとして読む上で厄介なのは、VWidgetに関する定義は殆ど無く、vdomの実装からインターフェース（らしきもの）を読み取るしか無いということ（下のような感じ）：

逆に言えば、By designなインターフェース通りに値を返せば、内部的に何をしようが（Virtual-DOMを全く使わなくても）特に問題はない模様。