読者です 読者をやめる 読者になる 読者になる

anti scroll

ブラウザと小説の新しい関係を模索する

nehan.jsのセレクターマッチング処理を高速化

nehan.jsのセレクタのマッチング処理を高速化しました。

先日サポートした行末揃えは、有効にすると20%ほど遅くなりましたが、今回の修正によって15%ほど速くできたので、少し戻すことができました。

前々から、機会があったらやっておこうと思っていた処理でもあったし、ちゃんと効果があって良かったです。

最適化の内容

やっていることは単純で、セレクタのマッチング結果を(キャッシュできるものに限り)キャッシュしただけです。

ただしマッチ結果には、キャッシュしやすいものとしにくいものがあるので、その辺のことについてちょっと説明します。

属性セレクタのマッチング結果はキャッシュが困難

属性セレクタは、マークアップや親が同じでも、マークアップが現れる相対的な文脈によってマッチしたりしなかったりするので、常に同じ値が返ってくるとは限りません。

これに対応するためには、属性クラスの情報をキャッシュキーに盛り込む必要があります。

しかし例えば次のようなマークアップを考えてください。

<div>
  <p class="foo">text0</p>
  <p class="foo">text1</p>
  <p class="foo">text2</p>
</div>

<div>
  <p class="foo">text3</p>
  <p class="foo">text4</p>
  <p class="foo">text5</p>
  <p class="foo">text6</p>
</div>

ここでtext2text6を内容に含むpタグをそれぞれp2p6と名付けることにします。

さて、p2p6のキャッシュキーはどうなるでしょうか。

両者の特徴をフルに含んだキャッシュキーを設計するとなれば(擬似的な記述ですが)こんなかんじになりそうです。

// p2のキャッシュキー
div>p.foo[nth-child=2, first-of-type=false, last-child=true, last-of-type=true, ...]

// p6のキャッシュキー
div>p.foo[nth-child=3, first-of-type=false, last-child=true, last-of-type=true, ...]

殆ど同じキャッシュキーですが、nth-childの値だけが異なります。

しかし両者は木構造の位置として、性質的には殆ど同じものです(divの直下にあるpタグの最後の要素)。

なので、p2p6のどちらも、次のセレクタにマッチします。

div>p.foo:last-child{ font-size:2em }

しかし、nth-childの値が違うだけで、違うキャッシュキーとなるわけです。

これを同じキャッシュキーにするわけにはいきません。なぜなら属性クラスはnth-childを使っている「かも」しれないからです。 属性クラスをキャッシュして(他の場所で)再利用するなら、確実に属性クラスが表現しうる全ての特徴が一致している、という保証が必要なのです。

というわけで、仮にp2のマッチ結果をキャッシュしたところで、同じ結果がp6のマッチング時に再利用されることはありません。

キャッシュが効果的なのは、どれだけ再利用されるかにかかっているのですが、こうやってキャッシュが分散すると、ヒット率が落ちる上に容量も食うわけで、かえって性能を損ねるおそれが出てきます。

というわけで、キャッシュキーが分散しがちな属性セレクタについては、都度マッチする方針で統一しました。

ただし、属性クラスを含むセレクタは別の領域に保存しておくなどして、前もって検索範囲を狭めておく、というようなことはしています。

キャッシュできる属性クラスのセレクタを書く方法

しかし、上記のようなp2p6で、同じマッチ結果がキャッシュされるようなセレクタが書きたい! と思いませんか?

nehan.jsならこれができます。

nehan.jsでは、cssプロパティに関数値を設定できるので、先ほどと同じ場所(div>p.foo:last-child)を、属性クラスを使わずに指定することがでるのです。

例えば以下のように、属性クラスの判定を遅延評価の関数に追い出すことで、セレクタの詳細度が減った「キャッシュヒット率の高い」セレクタを宣言することができます。

"div>p.foo":{
  onload:function(ctx){
    if(ctx.isLastChild()){ // is last-child?
      return {fontSize:"2em"};
    }
    return null;
  }
}

大まかなものでマッチさせておくことでセレクタのマッチング結果をキャッシュさせ、last-childのような詳細で決まるスタイルについては、遅延評価で取得させるわけです。

一見すると、スタイル値の取得に際し関数呼び出しのオーバーヘッドが発生するように見えますが、これは属性クラスの条件判定をセレクタ検索時に計算するか、検索後に計算するかの差でしか無いので、性能差には結びつきません。

属性クラスバージョンと遅延評価バージョンの性能差

とはいえ、セレクタ数が少ないケースでは、どちらの書き方をしても、たいして性能の差はありませんでした。

字数が40万字、セレクタ数が5000個ぐらいのラインを超えると、さすがにキャッシュの効く遅延評価バージョンの方が22%ぐらい速かったですが…

マージ後のスタイル値はキャッシュ出来ないのか

マッチしたセレクタは、specificityの順にソートし、最終的なスタイル値へとマージされます。

この最終的なスタイル値をキャッシュできると更に良いのは言うまでもないことですが、nehan.jsではcssの値に関数を指定できる仕様がある関係上、これが難しくなっています。

関数値で指定された値は実行時に値が決まるサンクなので、ある特定のタイミングで呼ばれて返ってきた結果を、永続的な最終値としてキャッシュすることはできないからです。

そもそも仮にキャッシュしたとしても、スタイル構築で時間がかかるのは圧倒的にセレクタ検索の部分なので、大した効果は期待できないと思われます。