この記事は後編の記事となります。
前編は こちら

全てを並列処理で実行

Servoプロジェクト（Quantum CSSの大元）は実験的なブラウザで、Webページのレンダリングの様々な部分を全て並列化しようとしています。これは、いったいどういう意味でしょうか。

コンピュータは脳のようなものです。考える部分（ALU）があり、その近くには短期記憶を司る部分（レジスタ）があります。これらはCPU上でグループ化されています。また、長期記憶を司るのがRAMです。

注釈：長期記憶（RAM）
短期記憶（レジスタ）
考える部分（ALU）

初期の頃のコンピュータでは、CPUを使って一度に1つのことしか考えられませんでした。しかし、この10年間で、複数のALUやレジスタをグループ化してコアにまとめて持つようになったことで、同時に複数のことを処理できるようになってきました。

注釈：コア

Quantum CSSは、別々のコアにわたるDOMノードのスタイル計算を分割することで、こうしたコンピュータの最新機能を利用しています。

これは、それぞれのコア上でツリーのブランチを分割するだけなので、簡単なことのように思えるかもしれません。しかし、実際には、いくつかの理由で思っているよりもはるかに大変です。1つにはDOMツリーがしばしば不均一であるという理由が挙げられます。これにより、コアの作業量に偏りが生じてしまうのです。

注釈：公平とは言えない

作業バランスをより均一にするために、Quantum CSSで使われているのがWork Stealing（仕事の窃盗）という技術です。DOMノードの処理時、コードは直接の子要素を取り、それらを1つ以上の”作業単位”に分割します。この作業単位は、キューに入れられます。

あるコアがキュー内の作業を完了すると、そのコアは別のキューで作業を探します。これにより、作業をバランスよく分割する方法を事前に考えなくても、作業バランスの均一性が確保できるようになるのです。

ほとんどのブラウザでは、これを正しく行うのは難しいでしょう。並列処理は困難な問題で、CSSエンジンは非常に複雑です。また、レンダリングエンジンの2つの複雑な部分、DOMとレイアウトの間に位置しています。従って、ちょっとしたことでバグが発生しますし、並列処理では、データ競合という、追跡が非常に難しいバグが発生することもあります。こうしたバグについては、 こちらの記事 で説明していますので、ぜひご覧ください。

何百何千人のエンジニアからコントリビューションを受ける場合、どうすればひるむことなく並列にプログラムすることができるでしょうか。そのために、Rustがあるのです。

Rustを使うことで、データ競合がないことを静的に確認できます。つまり、デバッグの難しいバグがコード内に入ってくるのを回避することができるようになるのです。コンパイラがそれを防ぎます。これについては、今後も記事でもっと詳しく書くつもりですが、現状では、 intro video about parallelism in Rust（Rustでの並列処理に関する紹介ビデオ） や more in-depth talk about work stealing（Work stealingに関する詳細トーク） が参考になると思います。

これにより、CSSスタイルの計算が、いわゆる厄介な並列処理の問題となり、並列処理の効率的な実行を妨げることはほとんどなくなります。一方で、これは直線的な速度向上に結びつき、例えば4つのコアがある場合、実行速度は4倍近くになります。

ルールツリーによるスタイル再計算の速度向上

それぞれのDOMノードに対して、CSSエンジンはセレクタマッチングを行うために全てのルールを実行する必要があります。ほとんどのノードでは、このマッチングが変わることはあまりありません。例えば、ユーザが親要素の上にホバーすると、その要素にマッチするルールが変更されることがあります。プロパティを継承するため、その子孫のスタイルを再計算する必要がありますが、それらの子孫にマッチするルールは恐らく変更されないでしょう。

子孫にどのルールがマッチしているかをメモすることができれば、セレクタマッチングを何度もやり直す必要はないと言えます。そして、それをするのが、Firefoxの以前のCSSエンジンから借用された、ルールツリーです。

CSSエンジンは、マッチするセレクタを見つけ出すプロセスを経て、それらを詳細度でソートします。そしてそこから、ルールがリンクされたリストを作成します。

このリストはツリーに追加されます。

CSSエンジンは、ツリー内のブランチ数を最小限に維持しようとするため、利用できるブランチをできるだけ再利用しようとします。

リスト内のセレクタのほとんどが既存ブランチのものと同じ場合は、同じパスに従います。しかし、進むうちにブランチ内に必要なルールがない場合も出てくるでしょう。その時のみ、新しいブランチが追加されます。

注釈：その時点でdiv#warningにマッチしないため、新規ブランチが作成される

DOMノードは最後に挿入されたルール（この例では div#warning のルール）へのポインタを取得します。これは最もはっきりとしたものです。

スタイルが再計算される時、エンジンは親要素に対する変更が子要素にマッチするルールを変更する可能性があるかどうかを素早く確認します。その可能性がない場合、どの子孫に対しても、ルールに到達するために、子孫ノード上のポインタをたどることができます。そこから、ツリーに沿ってルートまで戻り、詳細度の高いものから低いものまで、マッチするルールの完全なリストを取得可能です。つまり、セレクタのマッチとソートを完全にスキップできます。

これは、スタイルの再計算に必要な作業を減らすのに役立ちます。しかし、初期のスタイル設定時には依然として多くの作業が必要です。ノードが1万個ある場合は、セレクタを1万回マッチングさせなければなりません。しかし、それをスピードアップする方法があります。

スタイル共有キャッシュによる初期レンダリング（およびカスケード）の速度向上

数千のノードを持つページについて考えてみましょう。これらのノードの多くは同じルールにマッチします。例えば、Wikipediaの長いページを考えてみてください。メインコンテンツ領域の段落は、完全に同じルールにマッチし、全く同じ計算スタイルを持つはずです。

最適化をしない場合、CSSエンジンは各段落に対して、個別にセレクタマッチングし、スタイルを計算しなければなりません。しかし、スタイルが段落ごとに同じであることを証明する方法があれば、エンジンはその作業を1回行うだけで各段落のノードを同じ計算スタイルにすることができます。

これを行うのが、SafariとChromeに端を発するスタイル共有キャッシュです。ノードの処理が終了すると、計算されたスタイルがキャッシュに格納されます。そして、次のノードでスタイルを計算する前に、いくつかのチェックを実行して、キャッシュ内に利用できるものがあるかどうかを確認します。

チェックの内容は以下のとおりです。

• 2つのノードが同じID、クラスなどであるか。同じ場合、同じルールでマッチする。
• 例えばインラインスタイルなどのようなセレクタベースではないものについて、ノードは同じ値であるか。同じ値の場合、上のルールは上書きされないか、同じ方法で上書きされる。
• 両方の親要素が同一の計算されたスタイルオブジェクトを指しているか。指している場合、継承される値も同じになる。

注釈：Q：このpは前のpタグとスタイルを共有できるか？
A：できる

これらのチェックは、初期のスタイル共有キャッシュに当初から含まれていました。しかし、細かい事例では、スタイルがマッチしない場合も多く見られます。例えば、CSSルールで :first-child セレクタが使用されている場合、上記チェックでマッチするはずの結果でも、2つの段落がマッチしないことがあります。

WebKitとBlinkでは、このような場合にはスタイル共有キャッシュを諦め、キャッシュを使用しません。多くのサイトで新しいセレクタがどんどん使われるようになってくると、最適化はますますその効果を失っていきます。Blinkのチームは最近それを削除しました。しかし、こうした変化にスタイル共有キャッシュを対応させる方法があることが分かりました。

Quantum CSSで、以下の風変わりなセレクタを集めて、DOMノードに適用されるかどうかをチェックします。そして、結果を1と0で保存します。2つの要素が1か0で同じ場合、それらはマッチするはずです。

DOMノードが以前に計算されたスタイルを共有できる場合、ほとんど全ての作業をスキップすることができるでしょう。ページには同じスタイルを持つDOMノードが多数あることが多いため、このスタイル共有キャッシュはメモリを効果的に節約し、かつ作業スピードの向上にも貢献します。

まとめ

これは、FirefoxへのServo技術の最初の大きな技術移植です。移植プロセスの間に、最新で高性能なRustのコードをFirefoxのコアにいかに組み込むかについて多くのことを学びました。

ユーザにProject Quantumを直接体験していただく準備ができたことに、とても興奮しています。ぜひ試してください。また、 何か問題を見つけた時には 、お知らせいただければ幸いです。