Shiki’s Weblog

ESウェブブラウザ通信 - インクリメンタル リフロー #1

2012/09/29 #ESウェブブラウザ通信

ESウェブブラウザ(escort)が先月からCSSレンダリング エンジンをインクリメンタル リフロー(DOMツリーを部分的に操作したときなどのブラウザの応答性を良くするために必要最小限の部分だけリフローを行う手法)に対応したものに改良中ということで、ブログの方は前回から少し時間があいてしまいました。今回は実装中のインクリメンタル リフローの話題のほかに、レイアウト処理の基本的な事項も合わせて紹介していこうと思います。
5月にこのブログでは、CSSのレンダリング処理は一般的に以下の4ステージで進んでいくことを紹介しました:
1. セレクター マッチング (selector matching)
2. スタイル再計算 (style recalculation)
3. リフロー (reflow)
4. リペイント (repaint)

escortのスタイル マッチングとスタイル再計算の実装については、そこでまとめておいたので、今回はリフローとリペイントについて簡単にまとめておきます。また現在実装が進んでいるインクリメンタル リフローについても説明していきます。

リフロー

DOMツリーからレンダー ツリー(あるいはボックス ツリー、レンダリング ツリーとも)を構築して、ボックスの位置を決めていく処理は一般的に レイアウト あるいは リフロー と呼ばれています。
レンダー ツリーはテーブルを除くと、以下の3タイプのボックスから構成されている木構造です:

CSS 2.1の仕様書では、ブロック ボックス、ブロック レベル ボックス、ブロック コンテナ ボックスと3種類のブロック系ボックスの用語を導入していますが、特に明確に区別する必要がない場合は単に「ブロック」と呼ぶ、ということになっています(9.2.1)。(ブロック ボックスはブロック レベル ボックスでもあり、通常ブロック レベル ボックスはブロック コンテナ ボックスなので、実際に区別しないといけない場合はそんなにありません。)
これら3種類のボックスは自由に親子関係になれるわけではありません:

ですので、ひとつのブロック要素の中にブロック要素とインライン要素が混在していた場合には、インライン要素に対応するインライン ボックス(とそれらをまとめるライン ボックス)をまとめて保持する匿名のブロック ボックスを生成する、というのがCSSの仕様です。
またCSS 2.1の仕様書では「匿名のインライン要素」という言葉が9.2.2.1で出てきますが、このあたりは難しく考えなくても、DOMツリー中のテキスト ノードはインライン ボックスに変換される、と考えた方が分かりやすいように思います。そしてインライン要素に設定されたスタイルはそれぞれのインライン ボックスに対して効果をもちます。実装においては、white-spaceプロパティの指定にともなう空白の除去や、空のインライン要素(ボーダーはあるかもしれない)の処理や、ネストしたインライン要素(スタイルが重複していく)の処理などがあるので、実際には多少複雑なところもあります。
escortでは、リフローの処理はさらに内部で3段階に分かれています:
1. ブロックを組み立てる,
2. 絶対配置ボックス以外のブロックを、ブロック中のライン ボックス、インライン ボックスを生成しながら、レイアウトしていく,
3. スタッキング コンテキストを辿りながら、絶対配置ボックスを、ブロック中のライン ボックス、インライン ボックスを生成しながら、レイアウトしていく。

狭義でリフローと言った場合には2.と3.の処理を指す場合があるようです。1.の処理のようなボックスの配置を決める前にボックスをまず生成するステップのことをMozillaのDavid Baronさんは"Frame construction"と呼んでいます(CSS 2.1で言うボックスのことをGeckoではFrameと呼んでいます。ただこれはBad nameとのこと)。CSS 2.1の仕様書の用語に合わせると、1.は"Block construction"といったところでしょうか。
画面上のウィンドウのサイズを変更したりしただけでは、ブロックの木構造には何も変化はおきないので、そういった場合は2.の手順から処理をはじめることによって全体の処理を軽くすることができます。そのためブロックの実装では、それぞれのブロックごとにその中にレイアウトするインライン レベルのDOMノードのリストを保持しています。
補足: 1.のステップで以前はブロック レベル ボックスと匿名ブロック ボックスだけを生成していたのですが、r2985,r2988の変更によって、現在は文字通りインライン ブロックやフローティング ボックスなどブロックになるものをすべて生成しています。

リペイント

リペイントは、従来はWindowオブジェクトごとにレンダー ツリーを描画用と作業用に2つずつ保持して、描画用のレンダー ツリーを元にOpenGLの命令を発行して画面に描画する、という方法を使っていました。
インクリメンタル リフローをサポートするようになると、レンダー ツリーが一旦構築されたあともレンダー ツリーは部分的に更新され続けていく事、加えてescortではリフローはメイン スレッドとは別のスレッドで実行されているので、レンダー ツリーを元にOpenGLの命令を発行しながらペイントする、という手法は簡単に使うことができなくなりました(スレッド間の排他制御などで複雑な実装になってしまうことが予想されます)。
そこで、r2934からr2936の変更によって、レンダー ツリーは作業用に1つだけ持つようにして、リペイントのためには描画用のレンダー ツリーを保持する代わりに描画済みのビットマップ(内部的にはOpenGLのテクスチャ)を保持するようにしました。
リペイントまでの手順としては、レンダー ツリーの更新が完了したら、いきなり画面上のウィンドウに描画するのではなく、まずはOpenGLのテクスチャにオフラインでレンダリングしていきます(この際、OpenGLのARB_framebuffer_object拡張を使っています)。実際のリペイントの際には単にこのテクスチャを画面上のウィンドウに貼り付けていきます。
これでGPUやCPUのリペイントに関する処理量も減ることになるのですが、代わりにメモリ(GPU側)の消費量は多くなっています。デスクトップPCではエントリークラスのGPUを搭載したビデオカードにも2GBといったメモリが搭載されるような時代になってきていますが、モバイルに関してはfacebookから、

Given the size of GPU buffers relative to the size of content consumed on devices nowadays, I doubt well get to a place where managing GPU can be left strictly to the browser in a reasonable amount of time.

というフィードバックが先日流れていましたね。

インクリメンタル リフロー

escortの場合、DOMツリーからレンダー ツリーを構築してペイントするまでの処理は、以前紹介した4ステージではなくて、以下のような5ステージとして捉えるのがわかりやすいと思います。
1. セレクター マッチング (selector matching)
2. スタイル再計算 (style recalculation)
3. ブロックの組み立て (block construction)
4. リフロー (reflow)
5. リペイント (repaint)

いずれにしても、何もないところからDOMツリーを元にレンダー ツリーを生成してペイントするまでには秒単位の時間がかかる場合も少なくありません。ですので動的にDOMツリーに変更を加えるようなダイナミックなHTMLページでは、毎回レンダー ツリーを再構築したりしていると実用的な応答速度を得ることはとても難しくなります。
実用的な応答速度を得るためには、構築済みのレンダー ツリーをできる限りそのまま利用して、必要な部分だけボックスを更新したり、追加したり、あるいは削除したりする インクリメンタル リフロー (参考:Geckoでの実装)と呼ばれている処理が重要になります。
余談:リンク先のモジラのページを見てみると、インクリメンタル リフローの考え方はDOMの登場よりも前から、モデムを使ってインターネットに接続していた頃のようにネットワーク接続が非常に低速だった時代に、サーバーから読み込めた部分から先に画面上に表示していく、といったテクニックの延長にできてきたもののようにも見えます。escortではそこまでアグレッシブなことはしていなくて、HTMLファイルや画像ファイルなど個々のファイルについては完全にロードが完了してからはじめて必要な処理を開始するようになっています。
DOMツリーに加えられる変更は、いまのところescortではmutation eventを使って捕捉しています(いずれDOM4のMutationObserverに置き換えないといけませんが)。実際に考慮しないといけない事象には次のようなものがあります。
1. テキスト ノードの内容が変更された
2. テキスト ノードが追加・削除された
3. DOM要素が追加・削除された
4. DOM要素の属性が変更された
5. スタイルのプロパティの値が変更された

1., 2.の場合のインクリメンタル リフローは比較的簡単で、一番単純な場合であれば、そのノードを含むブロックだけリフローして、あとはそれ以降のブロックの座標だけ更新すれば終わりになります()。 より複雑な場合になると、リフローしたブロック以降のブロックについてもリフローしたり(フローティング ボックスの高さの消費量が変わった場合など。)、それが絶対配置ボックスの包含ブロックの大きさに影響していれば、関連する絶対配置ボックスについてもリフローを行ったり()と、芋づる式にリフローが連鎖していく場合もあります。
1., 2.に関する実装については、r2968からブロックごとにdirtyビットを使って、リフローしたりしなかったりを制御しています。ややこしいのはマージンのつぶしやフローティング ボックスの高さの消費の途中経過など、フォーマッティング  コンテキストをリフローを行うボックスできちんと回復できるようになっていないといけない、といった点です。r2976では絶対配置されているボックスのコンテント エリアの大きさが変わっていなければリフローを抑制するようなっています。さらにr2990ではインライン ブロックやフローティング ボックスについてもインクリメンタルにリフローできるようになっています。
3.の場合、インクリメンタル リフローは、追加された要素についてはセレクター マッチングから処理をはじめないといけません。このときはマッチング済みの要素についてはセレクター マッチングの処理を省略するといった工夫が必要になります(セレクター マッチングがCSSの処理の中で一番重い処理だという点を忘れると大変です)。r3002でそのような基本的な処理が実装されています。また追加された要素がCSSカウンタを操作していたりする場合には、それ以降のボックスで使われている連番の値が変わって、これまたリフローが芋づる式に必要になる場合があります()。その制御がr3013で入っています。
補足: 長大なドキュメントでカウンタによる連番が使われてた場合、連番の振り直しとそれにともなうリフローにはそれなりの時間がかかる場合も想定できます。ワードプロセッサなどでは、連番はユーザーから指示があるまであえて振り直さない、アイドル タイムを使ってバックグラウンドで振り直してしばらくたってから正しく振り直して表示する、といった工夫がされていることがあります。escortでも、このあたりは今後もうひと工夫して実装を改良してみるかもしれません。
4., 5.の場合については、また次回以降でソースコードがレポジトリにコミットできてから紹介していきます。

まとめ

今回は現在escortで実装中のインクリメンタル リフローの話題のほかに、レイアウト処理の基本的な事項も合わせて紹介しました。次回は、インクリメンタル リフローの処理の続きを報告していく予定です。escort 0.2.3のリリースはそのあとになる予定です。