DOMNodeInserted と DOMNodeRemoved に似た仕組みを IE でも使えるようにして、セレクタの実行結果をキャッシュする
セレクタ(id, tag, class, css, xpath)の実行速度を改善するには、2つの方法があります。
- ロジックを改善する
- キャッシュを使う
今日は2の方法について検討したことを書き残します。
心配事
キャッシュを使う上での心配事は「キャッシュが古くなったらどうするか、それをどうやって知るか?」です。
古くなったキャッシュはクリアしなければなりません。
DOM Level2 MutationEvents を使うと、ノードの挿入, 削除と、属性の更新 を取得できる
DOM Level2 MutationEvents という仕様があります。これらを活用するとDOMツリーが更新されたタイミングを監視できます。
DOMNodeInserted は ノードの挿入, DOMNodeRemoved は ノードの削除, DOMAttrModified は 属性の変更に対応しています。
各ブラウザ毎の実装状況を調べてみました。
<html><head><title>mutation event test</title></head><body> <input type="button" value="insert" onclick="insert()" /> <input type="button" value="remove" onclick="remove()" /> | js: <input type="button" value="mod1" onclick="mod1()" /> <input type="button" value="mod2" onclick="mod2()" /> <input type="button" value="mod3" onclick="mod3()" /> <input type="button" value="mod4" onclick="mod4()" /> | attr: <input type="button" value="mod11" onclick="mod11()" /> <input type="button" value="mod12" onclick="mod12()" /> <script> var g = 0; function id(id) { return document.getElementById(id); } function insert() { var n = document.createElement("div"); n.appendChild(document.createTextNode("insert")); document.body.appendChild(n); } function remove() { var n=id("my"); n && n.parentNode.removeChild(n); } function mod1() { var n=id("me"); n && (n.g = ++g); } function mod2() { var n=id("me"); n && (n.title = ++g); } function mod3() { var n=id("me"); n && (n.style.color = "#33" + (++g % 10)); } function mod4() { var n=id("me"); n && (n.innerHTML = n.innerHTML + ++g); } function mod11() { var n=id("me"); n && n.setAttribute("g", ++g); } function mod12() { var n=id("me"); n && n.setAttribute("title", ++g); } function fireAttrMod() { alert("M"); } // DOMAttrModified function fireInsert() { alert("I"); } // DOMNodeInserted function fireRemove() { alert("R"); } // DOMNodeRemoved window.onload = function() { if (!document.addEventListener) { return; } document.addEventListener("DOMAttrModified", fireAttrMod, false); document.addEventListener("DOMNodeInserted", fireInsert, false); document.addEventListener("DOMNodeRemoved", fireRemove, false); } </script> <pre> function insert() { var n = document.createElement("div"); n.appendChild(document.createTextNode("insert")); document.body.appendChild(n); } function remove() { var n=id("my"); n && n.parentNode.removeChild(n); } function mod1() { var n=id("me"); n && (n.g = ++g); } function mod2() { var n=id("me"); n && (n.title = ++g); } function mod3() { var n=id("me"); n && (n.style.color = "#33" + (++g % 10)); } function mod4() { var n=id("me"); n && (n.innerHTML = n.innerHTML + ++g); } function mod11() { var n=id("me"); n && n.setAttribute("g", ++g); } function mod12() { var n=id("me"); n && n.setAttribute("title", ++g); } </pre> <div id="my">hello</div><div id="me">mutation event</div></body></html>
| Method | Fx2 | Fx3 | Fx3.1 | Chrome | Safari3.1 | Opera9.27 | Opea9.61 |
| insert | I | I | I | I | I | I | I |
| remove | R | R | R | R+R | R+R | R | R |
| mod1 | - | - | - | - | - | - | - |
| mod2 | M+M | M | M | - | - | M | M |
| mod3 | M | M | M | - | - | M | M |
| mod4 | R+I | R+I | R+I | - | - | R+I | R+I |
| mod11 | M | M | M | - | - | M | M |
| mod12 | M | M | M | - | - | M | M |
IEは、DOMAttrModified, DOMNodeInserted, DOMNodeRemoved をサポートしていません。
WebKit(Safari,Chrome)は、DOMAttrModified を今のところサポートしていないようです(ソース上は、#if 0でコメントアウトされている)
void Element::dispatchAttrRemovalEvent(Attribute*) {
ASSERT(!eventDispatchForbidden());
#if 0
if (!document()->hasListenerType(Document::DOMATTRMODIFIED_LISTENER)) return;
ExceptionCode ec = 0;
dispatchEvent(new MutationEvent(DOMAttrModifiedEvent, true, false, attr, attr->value(),
attr->value(), document()->attrName(attr->id()), MutationEvent::REMOVAL), ec);
#endif
}
void Element::dispatchAttrAdditionEvent(Attribute *attr) {
ASSERT(!eventDispatchForbidden());
#if 0
if (!document()->hasListenerType(Document::DOMATTRMODIFIED_LISTENER)) return;
ExceptionCode ec = 0;
dispatchEvent(new MutationEvent(DOMAttrModifiedEvent, true, false, attr, attr->value(),
attr->value(),document()->attrName(attr->id()), MutationEvent::ADDITION), ec);
#endif
}
問題はIE
IEでこれらを実現する方法について調べました。
- DOMNodeInserted
var _age = 0; function insert(elm) { elm.style.behavior = "none"; ++_age; ((... cache clear ...)) } window.onload = function() { document.createStyleSheet().cssText = "*{behavior:expression(insert(this))}"; }
- DOMNodeInserted, DOMNodeRemoved
- document.all.length でノード数を調べることで検出します。事前に作成されているコレクションを参照するため、かなり高速です。
- このやり方では、挿入, 削除されたタイミングを動的に知ることはできません。
- Firefoxの標準準拠モード以外なら、ほぼ全てのモダンブラウザで使えます。
var _age = 0; var _nodes = 0; function CSSSelector(expr, context) { var modified = 0, nodes = document.all.length; if (nodes !== _nodes) { ++modified; _nodes = nodes; } if (modified) { ++_age; ((... cache clear ...)) } ... }
- DOMAttrModified は、document.documentElement.innerHTML を保存し、文字列を比較することで検出します。
- このやり方では、変更されたタイミングを動的に知ることはできません。
- オーバーヘッドが大きく(40ms〜50ms)万能ではありません。セレクタ用途には厳しいですが、用途を限定すればそれなりに使えます。
- 速度的なペナルティを避けるため、document.all.length と併用します。
var _age = 0; var _html = ""; var _nodes = 0; var _docRoot = document.documentElement || document.getElementsByTagName("html")[0]; function CSSSelector(expr, context) { var modified = 0, html, nodes = document.all.length; if (nodes !== _nodes) { ++modified; _nodes = nodes; } else { html = _docRoot.innerHTML; if (html.length !== _html.length || html !== _html) { ++modified; _html = html; } } if (modified) { ++_age; ((... cache clear ...)) } ... }
考察
ブラウザ毎に、以下のオペレーションが発生したときのシナリオを考え、問題の有無を切り分けます。
IE
- 新規ノードの挿入
- 既存ノードの削除
- document.all.length でセレクタ実行時に検出できる
- 問題なし
- document.all.length でセレクタ実行時に検出できる
- 既存ノードの移動(削除と挿入)
- 既存ノードの移動では CSS::expression が反応しない(elm.style.behavior = "none" 済みなので)
- 見かけ上はノード数が変化しないため document.all.length で検出できないが、innerHTML で検出できる
- オーバーヘッドを伴うため問題あり
- removeChild をフックすることで検出する方法もある。
(function(n){ var fn = n.removeChild; n.removeChild = function(oldChild) { ++_age; return fn(oldChild); } })(node);
- 既存ノードの属性変更
- innerHTML で検出できる
- オーバーヘッドを伴うため問題あり
- innerHTML で検出できる
心配事(キャッシュが古くなったらどうするか、それをどうやって知るか?)に対する答え
セレクタにキャッシュを組み込むとして、キャッシュはデフォルトでONなのかOFFなのか?
デフォルトONにすると、「属性変更時にユーザがキャッシュをクリアする必要がある」ことを周知しなければなりません。
デフォルトOFFは、確実に動作しますが、速度が 1/5 程度にまで落ち込むことが予想されます。
こうすれば良い?
function IDSelector(id, cache /* = false */) {}; function TagSelector(tagName, context /* = document */, cache /* = false */) {} function ClassSelector(className, context /* = document */, cache /* = false */) {} function CSSSelector(expr, context /* = document */, cache /* = false */) {}
- Firefox2,3 Opera, IE6, IE7, IE8 でキャッシュを使用する状態なら、ノードの挿入/削除,属性値の変更イベントを監視して、イベント fire でキャッシュを全てクリアする。
- AjaxやJavaScriptによるアニメーションを多用するサイトではキャッシュOFFにする必要がある。
- はてなのようなサイトではキャッシュONのままでOK。
- キャッシュOFFの状態でも現時点で最速だから無問題。
- キャッシュシステム全体をON/OFFできるようにする。
- QueryString(環境変数)で変更できるようにする。
<script id="uupaa-selector.js" src="uupaa-selector.js?cache=0"></script> // 0: CACHE OFF, 1: CACHE ON
-
- ユーザが意図的にキャッシュをクリアしたい場合に備えI/Fも提供する。
uuClass.Selector.clearCache = function() { _idCache = {}; _tagCache = {}; _classCache = {}; _cssCache = {}; ++_age; };
反省会
- IE で innerHTML を使わずに属性の変更を検出できれば、キャッシュの存在をユーザに見せなくても済むのに。
- 一応(↓)こういうコンボでMutationEventsをエミュレートできそうなんだけど(まだ試してない)。メモリとか速度的に大丈夫かなと心配でさ、他にもっと良い方法がないもんかと。
function _fakeMutationEvents(elm) { elm.style.behavior = "none"; (function(n) { var fn = n.removeChild; n.removeChild = function(oldChild) { // DOMNodeRemoved uuClass.Selector.clearCache(); return fn(oldChild); } })(elm); elm.attachEvent("onpropertychange", uuClass.Selector.clearCache); // DOMAttrModified uuClass.Selector.clearCache(); // DOMNodeInserted } window.onload = function() { document.createStyleSheet().cssText = "*{behavior:expression(_fakeMutationEvents(this))}"; }
-
-
- でも、onpropertychange って本来こういう用途な気もするし、これはこれで用法的にはOKなのかもね。onpropertychange がバブルアップしないのが痛い。
- ユーザが、キャッシュをONにした時点で富豪的な選択をしているわけだから、onpropertychange はありかも。
-
