2012年5月17日木曜日

ESウェブブラウザ通信 - :hover擬似クラスの処理の高速化

前回は、ESウェブブラウザでCSSのレイアウト処理をマルチスレッド化して、リペイント処理をほぼ一定のフレームレートで実行できるようにしました。そしてひとつ宿題としていたのが:hover擬似クラスの処理方法でした。今回はその高速化について報告していきます。

問題点の整理


前回の時点では、マウス カーソルが位置している要素が変わると、:hover擬似クラスの適用に変更があるかもしれないということで、カスケーディング処理からやり直すような実装になっていました。そのためスクロールなどマウスを使った操作が非常に重く感じられる場合がありました。

この点について、CSS 2.1の仕様書5.11.3では、
User agents are not required to reflow a currently displayed document due to pseudo-class transitions.
という記載していています。:hoverで指定したスタイルについては、ブラウザはリフロー(再レイアウト)はしなくても良くて、colorプロパティーのようにペイント処理だけやり直せば対応できるようなプロパティーだけ処理する実装でも構わないということですね。

いずれにしてもカスケーディング処理から(=はじめから)やり直すような実装と言うのは実用にはならないので、今回はここを改善していきます。

CSSレイアウト処理の流れと用語の整理

One of the problems with browsers is that different browsers sort of invent different terminology and talk about things slightly differently. - David Baron, Fast CSS: How Browsers Lay Out Web Pages, March 11, 2012.
具体的な改善の内容を説明する前に、今回はCSSレイアウト処理の流れと用語の整理をしておこうと思います。今までこのブログでは、レイアウト処理の内部を「カスケーディング」、「レイアウト」、「レンダリング」の3段階にわけて説明していました。David Baronさんの上記の講演の中では、これらを"construct", "reflow/layout", "paint"という言葉で説明されています。

なかなかしっくりくる用語が見つからないなぁ、と思っていたところ、Google+でGoogle ChromeチームのPaul Irishさんがうまくステージの段階を説明されているのに気付きました。Paul Irishさんはレイアウト処理の内部を"selector matching", "style recalculation", "reflow", "repaint"と4段階にわけて説明されています。この用語を使うと、いろいろと内部の動作を説明しやすいので、今後はこのブログでも使っていきたいと思います(ただWebKit内部の動作とESブラウザ内部の動作は違うので、同じ用語を使っても意味しているところが100%同じにはならない場合もあると思いますので、その点は留意してください)。

"selector matching", "style recalculation", "reflow", "repaint"という4段階を図にしたものが下図になります。矢印がCSSのレンダリング処理の流れになります。今まで「カスケーディング」としていた処理は"selector matching"+"style recalculation"という処理に相当します。

CSSのレンダリング処理の流れ
各ステージで行う処理は次のようなものになります:

selector matching (セレクター マッチング): DOMツリー中の各要素に適用するスタイル ルールをスタイルシートから選び出してくる。
style recalculation (スタイル再計算): 各要素に適用されるスタイル ルールをカスケーディング順に適用して、各プロパティの計算値を計算する。
reflow (リフロー): DOMツリーからボックス ツリー(レンダー ツリー)を生成して、ボックスの位置やサイズを決める(このとき確定させたプロパティの値が解決値です)。
repaint (リペイント): リフローの終わったボックス ツリーをもとにグラフィックスの命令(ESウェブブラウザの場合はOpenGL)を呼び出して画面を更新する。
partial style recalculation (部分スタイル再計算): リフローを発生させないスタイル プロパティーについてのみ、style recalculationを実行する。

上図では"repaint"から以前のステージに戻っている矢印がある点に注意してください。例えば、GIFアニメを表示している場合は、"repaint"の処理だけを繰り返しつつアニメーションの各コマを切り替えて表示します。またウィンドウの大きさを変えたりした場合には、セレクターをマッチングさせた結果自体はそのまま再利用して"style recalculation"から処理を実行すれば正しい描画結果が得られます。これまでの「カスケーディング」としていた処理を2つに分けた方が良いのはこういった場面があるためです。

上図では、さらに"repaint"の横に"partial style recalculation"というボックスを追加しています。:hover擬似要素をCSS 2.1の仕様にそって高速に処理したい場合には、colorなどリフローを発生させない一部のスタイル プロパティーだけを"partial style recalculation"で再計算して直ちに"repaint"するというパスが使えます。

一般的にCSSの高速化という場合は、できる限り"repaint"から前のステージに戻って再処理する場面を減らすこと、という風に言えそうです。また"reflow"などもツリーのルートからリフローするのではなくて、ツリーの一部分だけリフローする、といった高速化が(ESウェブブラウザではまだですけれども)メジャーなブラウザでは行われています。

:hover処理の高速化


以上のようなことを踏まえて、:hover処理の高速化を行ったのがr2721です。 まだまだ高速化する余地はいろいろあるのですが、オーソドックスな実装になっていると思うので今回はこのテスト ページを例に内部の処理を説明していきます。

テスト ページ: どこもホバーしていない状態

セレクター マッチング


テストページをパースして生成したDOMツリーは次のようになります(テキストノードは省略しています):

テスト ページのDOMツリー
このツリーに対して、セレクター マッチングを行った結果が下図です。簡便のためbody要素以下の部分だけにしています。

テスト ページのDOMツリーにスタイル ルールをマッチさせたところ
r2721が今までと違うのは、セレクター マッチング処理の際には要素の上に実際にマウス カーソルがあるかどうかは気にせず、マッチする可能性があるセレクタを含んだスタイル ルールをすべて集めてくる点です。そうやって集めてきたスタイルが有効かどうかはスタイル再計算の際に改めてチェックします。このようにすることで、マウスカーソルを動かしただけでセレクター マッチングからやり直さないといけない、という従来の問題をまず回避しています。

スタイル再計算 (何もホバーされていない状態)


続いてスタイルの再計算に進みます。まずはどの要素もホバーされていない場合を見ていきます。集めたスタイル ルールで有効なものには印を、無効なものには×印をつけています。これを元にcolorの計算値を各スタイル ルールボックスの右上に示しています。colorの初期値はinheritで親のスタイル定義がない場合、ESウェブブラウザでは黒色になる点に注意してください。

スタイルの再計算 (何もホバーされていない状態)

実際の画面ともあっています:

テスト ページ: どこもホバーしていない状態

スタイル再計算 (#div1をホバーした状態)


今度はマウスが一番上の#div1要素にある場合を見てみます。今回はcolorプロパティーしか使っていないので、スタイル再計算の結果も部分スタイル再計算の結果も同じになります。

スタイルの再計算 (#div1をホバーした状態)
セレクタ #div1:hover が有効になって、div1のcolorがgreenになると同時に、div2とdiv3のcolorプロパティーはinheritのままなので、それらのcolorもgreenに変わっています。

テスト ページ: #div1をホバーした状態
繰り返しになりますが、大事な点は、マウスを動かしてもセレクター マッチングはやり直さない、という点です。またr2721では部分スタイル再計算の処理も入っているので、マウスを#div1要素の上にもっていくと次のリペイントの際には直ちに:hoverの結果が反映されます。さらに、r2721では並行してバックグラウンド スレッドに通常のスタイル再計算もさせるようにしています。そのためリフローが必要になるようなプロパティーを:hoverに指定していた場合にも、バックグラウンド スレッドの処理が完了しだいそれが画面に反映されます。

補足: 今回のテストでは通常のスタイル再計算は不要なのですが、そういう場合にバックグラウンド処理を開始しない、といった高速化処理は今後実装していきます。

スタイル再計算 (#div4をホバーした状態)


今度はマウスが4番目の#div4要素にある場合を見てみます。今回はp要素の2つのスタイル ルールがどちらも有効になりますが、セレクタのspecificityがより大きいdiv:hover + pルールが勝ってp要素のcolorは紫色になります。

スタイルの再計算 (#div4をホバーした状態)
実際の動作もこのようになります:

テスト ページ: #div4をホバーした状態
このようにセレクタのコンビネーターを使っていて、:hoverが右端にないようなセレクタを使っている場合でもスタイルの再計算ができる、という点がr2721の実装のよいところです。

補足: 実はr2709で、:hoverが右端にある場合に限定してr2721よりも全体的にはより高速に動作するような実装をテストしていました。ただこの#div4のようなケースに対応することが難しい、という問題があったのでした。

さらに進んだトピック


r2721ではスタイル マッチングの結果をスタイル ルールのリストとして各要素ごとに個別に保持しています。この方法ですと、より複雑なドキュメントでは、まったく同じルールのリストを保持している要素数が相当数ある場面が想定できます。Geckoでは、そのような場面を想定してドキュメント全体でルールを木構造で保持するルール ツリーを使って、メモリの消費量や計算量を抑える工夫がされています。ESウェブ ブラウザでもいずれルール ツリーのような手法を取り入れてみたいところですが、まだまだその他に直さないといけない箇所が残っているのでこれは今後の課題ということにしておきます。

まとめ


今回は:hover擬似クラスの処理の高速化について、CSSレイアウト処理の流れと合わせて報告しました。この考え方は、他の動的な擬似クラスセレクタや属性セレクタにも応用できそうです。また、今回の実装によって、ESウェブブラウザのセレクター マッチングとスタイル再計算の処理については、比較的オーソドックスなものになってきていると思います。そういうわけでいつもより詳細にその動作についてまとめてみました。

まだまだ最初のリリースに向けて課題が山積みになっていますが、次回もこのような感じで報告していきます。それから日々の進捗について、ChangeLogを見てもよくわからないという人がもしいましたら、Google+の方にも(あまりまとまりがないのですが)ちょこちょこと書き込んでいるので、そちらも参考にしてください。

2012年5月9日水曜日

ESウェブブラウザ通信 - CSSレイアウト処理のマルチスレッド化

前回は、HTTPリクエストの処理を別スレッドで実行させることによって、ブラウザのメインループの処理とは非同期にもっと効率よくサーバーからデータを取得してくるようになりました、という報告をしました。それを読んで、『サーバーから応答が帰ってきてから次のリクエストを出すのでは、リクエストの送信の時間分まだロスしているのでは?』と思われた方がいたら鋭いです。HTTP 1.1では規格上はサーバーからの応答を待つことなく先にリクエストをまとめて送ってしまうパイプライン処理についても規定されています。ただ規定と実世界での実装は別ということもあるみたいなのです[参考]。そういう流れで、最近話題のSPDYとかHTTPbisのことを見ていくとおもしろいのじゃないかな、と思います。

今回は前回課題の一つとして挙げたカスケーディングやレイアウトといった処理をメインのスレッドとは別のスレッドで実行させる、という処理がESウェブ ブラウザに入ったのでその報告です。

カスケーディングとレイアウトをバックグラウンドで処理


下図はr2695でのabout:画面ですが(r2694からabout URIスキームに対応しています)、右上の歯車のアイコンが以前と変わっていて、この歯車がページのロード中はくるくる回るようになりました。以前はブラウザが固まったように見えてしまっていた時間に、こういったアニメーションを表示することで、ユーザーにブラウザが処理中だということを伝えられるようにしたわけです。

r2695
このようなことが可能になったのは、 r2679以降の修正でカスケーディング処理とレイアウト処理が別スレッドで実行されるようになったためです。この場合のカスケーディング処理、レイアウト処理、レンダリング処理が各フレームごとのどのように実行されているかを示したものが下図になります。

カスケーディングとレイアウト処理の並列実行
ブラウザ内部では、メイン スレッドはレンダリング用のボックス ツリーを使って描画処理を行います。一方、バックグラウンド スレッドはレンダリング用のボックス ツリーには一切触れずに、新しい別のボックス ツリーを構築していきます。メイン スレッドはバックグラウンド スレッドの処理が完了すると、古いレンダリング用のボックス ツリーを破棄して、バックグラウンド スレッドが構築した新しいボックス ツリーにレンダリング用のボックス ツリーを切り替える、という処理を繰りかえしています。

この枠組みでは、レンダリングをほぼ一定の周期で実行できるので、GIFアニメ(r2681から対応しています)などをスムーズに表示することができます。実際に、ページのロード中に回っているナビゲーターの歯車もGIFアニメです。ナビゲーターはbeforeunloadイベントが発生してからloadイベントが発生するまで歯車の画像をpngの静止画からgifのアニメ画像にbackground-imageプロパティを使って変更しています(r2686)。

また前回実装したカスケーディング結果を再利用してレイアウトだけやり直す、という処理もマルチスレッドに対応させています(r2703)。例えば、上図のフレーム#10, #14ではレイアウトだけ再実行させている様子を示しています。この場合、それぞれ#12, #16から新しいレイアウト結果に表示が切り替わることになります。

上図フレーム#5, #6の部分では、バックグラウンド スレッドはカスケーディング処理が終わっても直ちにレイアウト処理は開始しないで、フレーム#6まで待っている様子を示しています。これは現状ESウェブ ブラウザではJavaScriptの実行はメイン スレッドだけに制限しているためです(一気にJavaScriptの並列実行まで進めてしまうとバグの切り分けが難しくなってしまうため)。そしてXBL2では、シャドーツリーがドキュメント内に展開されたあとで、xblEnteredDocument()メソッドを呼び出さないといけません。従来はカスケーディング処理中に呼び出していたのですが、それだとJavaScriptが並列に実行されてしまいます。そのため、カスケーディング処理が終わったらバックグラウンドスレッドは一旦ポーズします。そしてメインスレッドがxblEnteredDocument()メソッドを呼び出したあとで、レイアウト処理を再開するように制御しています。

なお上図では省略していますが、HTMLドキュメントのパース処理はまだメイン スレッドの側で行っています。そのため、大きなドキュメントのパース中はブラウザが止まったように見える時間があります。これも「JavaScriptの実行はメイン スレッドだけで」という制約からくるものです。バックグラウンドでのJavaScriptの実行については、Web Workersとの関連もあるので、どこかで見直すことにします。

また現状ではマウス カーソルが位置している要素が変わると、:hover擬似クラスの適用に変更があるかもしれないということで、カスケーディング処理からやり直すような実装になっています。そのためスクロールなどマウスを使った操作が非常に重く感じられる場合があります。この点については、CSS 2.1の仕様書5.11.3でも、
User agents are not required to reflow a currently displayed document due to pseudo-class transitions.
という記載があります。ユーザーにとって使い勝手が悪くなるようなことまでして、:hoverを忠実に実装しないといけない、ということではない、ということですね。このあたりの処理は高速化を試みると同時にうまい手の抜き方を見つけて実装する、ということも重要になってきそうです。

まとめ


今回はここまでです。 今回の枠組みに関しては、マルチスレッドと言ってもメイン スレッドから裏でこれをしておいて、という指示を出して、裏の処理が終わったらやはりメイン スレッドの側から結果を取得してくる(そのときはバックグラウンド スレッドは停止している)、ということなので、同期処理などで注意しないといけない箇所はそれほど多いわけではありません。それでもマルチスレッド対応ということでまだ修正が必要な部分が残っていたりしています。マルチスレッドのプログラムは、丁寧にチェックしておかないと予想外の場面でクラッシュしたりするのでやっぱり大変ですね。

次回は今回宿題にした:hover擬似クラスの処理の改善などから進めて行く予定です。