Tech Racho エンジニアの「?」を「!」に。
  • Ruby / Rails以外の開発一般

[DOM] Rangeを作りすぎて激重になった話

DOMの規格にはRangeというクラスがあります。ドキュメント上の選択範囲などを表すのに便利なクラスです。
ついさっき、このクラスにまつわるパフォーマンス問題を解決したので記事に残そうと思います。

removeChild()が重い?

とあるDOM操作を行う処理のパフォーマンスが悪い、というチケットが立てられたのが発端でした。
最初にその部分を実装したのが私で、そこまでチューニングをしっかりしていた訳ではなかったのでまあそんなこともあるかな、と思いながらとりあえずパフォーマンス計測を行ってみたところ、appendChild()が実行時間の9割以上を占めているという結果でした。

appendChild()がなんでそんなに遅いんだろう?
appendChild()は親ノードの子のリスト末尾に1個ノードを追加するだけの処理です。普通に考えてこれだけではそこまで遅くなるとは思えない。
appendChild()と言っても、あるノードの中から別のノードに移動する処理だったので、内部ではノードを外す処理とノードを追加する処理が行われることになります。そこで、実際に重いのがどこなのか突き止めるため、removeChild()を行ってからappendChild()を行う処理に変更すると、removeChild()appendChild()よりずっと重いという結果が出てきました。

(同じような状況の再現コードでパフォーマンス計測を行ったもの)

その時点では、removeChild()appendChild()にここまで大きな差が出る理由は見当がつきませんでした。

const span = document.createElement('span');
const text = document.createTextNode('test');
const t = Date.now();
for(let i = 0; i < 100000; ++i) {
  span.appendChild(text);
  span.removeChild(text);
}
console.log(Date.now() - t);

実際、上記のような、単にappendChild()removeChild()を繰り返すだけの単純な計測コードだと以下のような結果になり、removeChild()が若干重いかという感じではあるものの、せいぜい2倍程度の差です。

同じように計測コードを問題の起きているページにも埋め込んで実行してみましたが、それだけではappendChild()removeChild()の実行時間はやはり同じでした。
ところが、チケットで問題となったDOM操作を行うと、その後同じ計測コードの実行でremoveChild()が重くなるのです。不可解な現象です。

Rangeが原因だった

まあタイトルにある通りなので当然なのですが、問題の発生する処理は実行中に何個もRangeを作成していました。
そのRangeを作成している箇所の前で実行を中断した場合と、その後まで実行した場合とで、計測コードのパフォーマンスに大きな差が生まれました。つまりRangeを作るとパフォーマンスが悪くなる訳です。
ここには、RangeLive(生きている)オブジェクトであることが関わっていました。

Live(生きている)オブジェクトとは

DOMの仕様には、いくつかLiveという言葉が登場します。例えば、HTMLCollectionはMDNの説明を見てみると、

HTML DOM 内の HTMLCollection は生きて (live) います。それらは元になった document が変更された時点で自動的に更新されます。

という文言があります。HTMLCollectionは例えばgetElementsByClassName()の戻り値ですが、これが生きているというのがどういうことかと言うと、DOMツリーが更新されると勝手に中身が変わるということです。
getElementsByClassName()で取り出したHTMLCollectionなら、そのクラス名を持たない要素は含まれないので、クラス名を付けたり外したりするとHTMLCollectionの中身も増えたり減ったりする訳です。

Node.childNodesなどもNodeListのLiveオブジェクトですが、Rangeもまたそれらの一種です。
ただ、getElementsByClassName()childNodesなどで扱うHTMLCollectionNodeListは、そもそもDOMツリーが内部的に持っている配列を単に参照しているだけのものなので、DOM構造が変われば自動的に更新されますが、更新にかかる追加のコストはありません。
一方、Rangeが生きているというのはどういうことかというと、DOMツリーが変更される度に、そのドキュメントに関連付けられたRange全てに関して、変更を反映する必要があります。つまり、更新が発生した時に生きているRangeが多ければ多いほど、更新処理が重くなるということです。

Rangeの存在がremoveChild()のパフォーマンスに影響を与えてappendChild()に影響しない理由は、おそらくですがappendChild()Rangeの指す位置が変わることがないからでしょう。Rangeが指すのはノードとそのオフセット(親要素なら子ノードのリストの位置、テキストノードならテキスト位置)ですが、appendChildは子ノードのリストの末尾に追加するだけなのでそれらが変わることがありません。一方、removeChild()の場合は、Rangeが指しているノードそのものが取り外されたり、Rangeの指すオフセットより前のノードが外されてオフセットがずれたりするので、変更を反映する必要が生まれるのです。

Rangeオブジェクトと言えどいつかはGCにかけられるのだから、どこからも参照されなくなればいつかは死にます。とは言え、実際に問題が発生している以上、GCに回収されないままのRangeが残っていて、それがまだ生きている扱いになっていることは想像に難くありません。

Rangeの殺し方

Rangeが生きているのが原因なのだから、殺してしまえ。
私の中の首領(ドン)が囁きました。何の組織の首領なのか、それは分かりません。

さて、Rangeにはdetach()という、いかにもそれっぽいメソッドがあります。MDNにはこう書いてあります。


developer.mozilla.orgより

なるほどこれを使えばいいのか!

残念でした。
detach()は使えません。WHATWGのLiving Standardにおける定義の方を見てみれば

The detach() method, when invoked, must do nothing.
DOM Standardより

と書いてあります。MDNの方でも個別ページを見に行けば同じことが書いてあります。つまり、これは互換性のために残された機能で、昔は使えたかもしれませんが今では使えない訳です。

ではどうすれば良いのだろう?

detachはそもそも何をやっていたのか、同じような処理を発生させることはできないのか。
それを探るため、調査班はアマゾンの奥地Chromiumのソースコードに飛んだ。

void Range::Dispose() {
  // A prompt detach from the owning Document helps avoid GC overhead.
  owner_document_->DetachRange(this);
}

Dispose()というのは、ちゃんと確認した訳ではないですがおそらくGCがオブジェクトを削除する時に呼び出す関数のはずです。
owner_document_->DetachRange(this); というのはいかにもそれっぽいですね。おそらく昔はこの処理がdetach()で公開されていたのでしょう。
DetachRange()の処理対象オブジェクトはowner_document_なのですね。owner_document_は要するにRangeが指すノードのownerDocumentと同じものでしょう。

はて。ということは。
RangeownerDocumentの異なるノードを指すようにすれば、owner_document_が切り替わるのではないか?
owner_document_が切り替わる時に、DetachRange()が呼ばれるのではないか?
実際、setStart()などのコードを追ってみますと、owner_document_が異なる場合に更新をかける処理(SetDocument())が呼ばれています。

if (ref_node->GetDocument() != owner_document_) {
  SetDocument(ref_node->GetDocument());
  did_move_document = true;
}

つまり、Rangeを完全に殺すことはできなくても、ダミーのDocumentを作ってそちらを指すようにすることは可能なのではないでしょうか。

という訳で、こんなコードを用意してみました。

let dummyDocument: Document | undefined;
export function releaseRange(range: Range) {
  dummyDocument = dummyDocument || document.implementation.createDocument(null, 'dummy', null);
  range.setStart(dummyDocument, 0);
}

Rangeを利用していた部分で、もう使わなくなったRangeに関して全てreleaseRangeを呼ぶようにしてみました。
releaseとか言いつつ別にここですぐにRangeオブジェクトが削除されるわけではないのですが、これ以降再利用しないことを示したかったのでこういう名前になっています。

この関数を呼ぶとRangeオブジェクトはdummyDocumentにアタッチされ、ページのdocument以下のツリーの変更があっても更新されません。そのうちGCに回収されるはずです。

それで実際に挙動はどうなったかと言うと、見事にパフォーマンスが改善されました。めでたしめでたし。

実際にRangeを増やした時に時間がかかることを体感できるよう以下のサンプルを用意しました。試してみてください。
1000くらいの値を入れれば十分な差が出ます。あまり大きな値を入れるとRangeを作成するだけでメモリが大量に必要になるので注意してください。



関連記事

TypeScriptにヤバい機能が入りそうなのでひとしきり遊んでみる


CONTACT

TechRachoでは、パートナーシップをご検討いただける方からの
ご連絡をお待ちしております。ぜひお気軽にご意見・ご相談ください。