Webパフォーマンスの時間計算量を左右するHTMLのDOMツリー

DOMツリー最適化でブースト！ 高速・効率的なWebページへの鍵を握ろう

2023年4月24日
著者: 竹洞 陽一郎

はじめに

今回は、Webパフォーマンスの基礎となる、HTMLの解析において特に重要なDOMツリーについて解説します。
HTMLのDOMツリーは、多くの人が用語として知っているでしょう。
しかし、木構造の複雑度がCSSやJavaScriptなどの後続処理の時間計算量に大きな影響を与えることについて、十分理解している人は意外と少ないかもしれません。

この記事では、DOMツリーがどのように構築され、その複雑度がWebパフォーマンスにどのような影響を及ぼすかを説明します。
また、効果的なDOMツリー最適化の方法や、それによって得られる恩恵についても触れていきます。
Web開発者は、これらの知識を活用して、より高速で効率的なWebページを提供することができるでしょう。

HTMLの解析とその重要性

WebブラウザによるHTMLの解析で構築されるDOMツリーは、その後に続くCSSやJavaScriptの時間計算量を大きく左右します。
多くの技術者は、Webパフォーマンスチューニングにおいて、プロトコルや画像などに焦点を当てることが一般的です。
しかし、Webパフォーマンスにおいて、DOMツリーは、Webページの計算の下地となる重要な要素であり、その最適化が求められます。

Webブラウザのパーサ(解析器)がHTMLマークアップを解釈する手順は以下の通りです。

1. ローディング

ブラウザは、サーバーからHTMLファイルを取得します。

2. トークン化

パーサは、HTMLをトークンに分割します。
これにより、HTMLの構造が明確になります。
主なトークンの種類には以下のものがあります。

• 開始タグ（例: <div>）
• 終了タグ（例: </div>）
• 属性名（例: class）
• 属性値（例: "container"）
• コメント（例: <!-- コメント -->）
• テキストノード（例: これはテキストです。）

3. 構文解析

パーサは、トークンをもとにDOM（Document Object Model）ツリーを構築します。
DOMツリーは、HTMLの要素とその階層構造を表現するデータ構造です。

4. DOMContentLoaded発火

ブラウザがHTML文書の読み込みと解析を完了し、DOMツリーを構築した時点で発生するイベントです。
このイベントは、HTML文書の解析が完了したことを示し、開発者がブラウザ上でJavaScriptを実行するための適切なタイミングを提供します。

木構造とは?

データ構造としての木構造は、階層的な関係を持つデータを表現するために使用されます。
ノード（節点）と枝（エッジ）で構成され、一つの根ノード（ルートノード）から始まり、枝分かれしていく構造を持っています。
各ノードは、他のノードとの親子関係や兄弟関係を持ちます。

木構造を用いることで、データ処理の高速化が期待できる場合があります。
以下に、木構造の利点と、それによるデータ処理の高速化についていくつかの例を挙げます。

探索の高速化

二分探索木（Binary Search Tree, BST）は、データの探索や挿入、削除を高速に行うことができる木構造です。
BSTでは、各ノードの左の子ノードは親ノードよりも小さく、右の子ノードは親ノードよりも大きいという条件が成り立ちます。
この性質を利用して、データの探索を効率的に行うことができます。

優先度付きキューの実現

ヒープ（Heap）は、特定の順序を持つデータを効率的に管理できる木構造です。
ヒープを用いることで、優先度付きキューを実現することができ、データの挿入や最大値・最小値の取得が高速に行えます。

文字列マッチングの高速化

トライ（Trie）は、文字列の集合を効率的に格納・検索できる木構造です。
トライを用いることで、文字列の探索や共通接頭辞の検出を高速に行うことができます。

グラフアルゴリズムの高速化

最小全域木（Minimum Spanning Tree, MST）アルゴリズムなど、木構造を利用することでグラフ上の問題を効率的に解決できます。

HTMLのDOM Treeにおける木構造

HTMLのDOMツリーは、データ構造としての木構造を使用していますが、上記で挙げた二分探索木（BST）、ヒープ、トライ、最小全域木（MST）などの特定の高速化手法は直接適用されていません。
DOMツリーを効率的に操作・処理するために、木構造に関する一般的なアルゴリズムや手法が用いられます。

DOMツリーは、HTML文書内の要素とその階層構造を表現するために使用されます。
DOMツリーの操作では、以下のような一般的な木構造の処理手法が用いられることがあります。

深さ優先探索（Depth-First Search, DFS）

このアルゴリズムでは、現在のノードから可能な限り深く探索を進め、進むことができなくなったら、直前のノードに戻って再び探索を続けるという方法が採用されています。
深さ優先探索の基本的な手順は以下の通りです。

1. 開始ノードを訪問し、そのノードを「訪問済み」とマークします。
2. 現在のノードに未訪問の隣接ノードがあれば、そのノードを選択し、手順1に戻ります。
3. 現在のノードに未訪問の隣接ノードがなければ、一つ前のノードに戻って手順2に戻ります。
4. 全てのノードが訪問済みになるか、または探索を開始したノードに戻るまで手順2と手順3を繰り返します。

深さ優先探索は、再帰的な方法やスタックを用いた非再帰的な方法で実装することができます。
木構造やグラフにおいて、全てのノードを効率的に探索することが可能であり、さまざまな問題に対して適用できます。
例えば、迷路の解決やグラフ上の経路探索に利用しますし、DOMツリーの操作にも利用するわけです。

幅優先探索（Breadth-First Search, BFS）

このアルゴリズムでは、開始ノードから各階層（レベル）ごとにノードを探索し、同じ階層のノードがすべて探索された後に次の階層へと進むという方法が採用されています。
幅優先探索の基本的な手順は以下の通りです。

1. 開始ノードを訪問し、そのノードを「訪問済み」とマークします。そして、開始ノードをキューに追加します。
2. キューが空でない場合、キューの先頭ノードを取り出し、そのノードに隣接する未訪問のノードをすべて訪問し、「訪問済み」にマークします。その後、これらのノードをキューに追加します。
3. キューが空になるまで手順2を繰り返します。

イベント伝播（Event Propagation）

イベント伝播（Event Propagation）は、DOM（Document Object Model）において、イベントが発生した際に、DOMツリーの要素に対してイベントがどのように伝達されるかを決定するプロセスです。
イベント伝播は主に、キャプチャリング（Capturing）フェーズ、ターゲット（Target）フェーズ、バブリング（Bubbling）フェーズの3つの段階で構成されます。

キャプチャリングフェーズ（Capturing Phase）

このフェーズでは、イベントはDOMツリーのルート要素からターゲット要素（イベントが発生した要素）へ向かって、順に伝播します。
この過程で、イベントリスナーがキャプチャリングフェーズで実行されるよう設定されている場合、それらが実行されます。

ターゲットフェーズ（Target Phase）

このフェーズでは、イベントがターゲット要素に到達し、その要素に設定されたイベントリスナーが実行されます。

バブリングフェーズ（Bubbling Phase）

このフェーズでは、イベントはターゲット要素からDOMツリーのルート要素へ向かって、順に伝播します。
この過程で、イベントリスナーがバブリングフェーズで実行されるよう設定されている場合、それらが実行されます。

イベント伝播により、特定の要素だけでなく、その親要素や子要素にもイベントリスナーを設定することができます。
これにより、イベントの取り扱いが柔軟になり、より効率的なイベント処理が可能となります。
ただし、イベント伝播が必要ない場合や、性能上の問題が発生する可能性がある場合には、イベントリスナー内でevent.stopPropagation() を使用してイベント伝播を停止することができます。

木構造としてのDOM Treeの複雑度計算

以上から、複雑な深い木構造のDOM Treeを作ってしまうと、計算処理の時間が長くなりそうだと分かりますね。
そこで、DOM Treeの木構造としての複雑度を計算してみましょう。
方法はいくつかありますが、一般的には以下の3つの指標を考慮することが多いです。

ノード数（Node Count）

木構造の複雑度を評価する最も単純な方法は、ノード数を数えることです。
ノード数が多いほど、木構造は複雑であると言えます。
ノード数をNとすると、木構造の複雑度はO(N)となります。

オーダー記法

オーダー記法（ビッグオー記法、Big-O notation）は、アルゴリズムの計算量や実行時間の増加率を表すために使用される数学的表記法です。
この記法では、入力サイズに対するアルゴリズムの実行時間やメモリ使用量の上限を示します。
"O" は、オーダー（Order: 命令）の略です。

O(N)

O(N)は、ここでは、アルゴリズムの時間計算量を表す表記法で、Nは問題のサイズを示しています。
O(N)のアルゴリズムは、問題のサイズ（入力データの数）に比例して実行時間が増加することを意味します。
DOMツリーに含まれる要素の数が多いほど、文書の構造が複雑であると言えます。
また、ノード数が多いほど、DOM操作やイベント処理などのパフォーマンスに影響があることがあります。

DOMツリー操作の例でO(N)の計算を説明します。
DOMツリー内の特定のクラス名を持つ要素の数をカウントする例です。
DOMツリー内の特定のクラス名を持つ要素をカウントするためには、以下の手順でアルゴリズムを実装することができます。

1. カウントを格納する変数countを作成し、0で初期化する。
2. DOMツリーを深さ優先探索（DFS）または幅優先探索（BFS）で走査し、各要素を1つずつ調べる。
3. 調べた要素が指定されたクラス名を持っていれば、countを1増やす。
4. DOMツリー内のすべての要素を調べ終わった時のcountが、その特定のクラス名を持つ要素の数である。

このアルゴリズムは、DOMツリー内のノード数（N）に比例して実行時間が増加します。
なぜなら、DOMツリー内のノード数が増えると、特定のクラス名を持つ要素をカウントするために調べるノードが増加するからです。
このようなアルゴリズムは、O(N)の時間計算量を持つと言われます。

この場合のNは、DOMツリー内の要素（ノード）の数を表します。
DOMツリーが大規模であるほど、アルゴリズムの実行時間が長くなることが予想されます。
横軸に問題のサイズ（入力データの数）N、縦軸に実行時間（または処理ステップ数）Tを取り、グラフが描くと以下のようになります。

深さ（Depth）

木構造の深さは、ルートノードから最も遠い葉ノードまでの最長経路の長さで定義されます。
深さが大きいほど、木構造は複雑であると言えます。
木構造の深さは、バランスが取れた二分木の場合、O(log N)となりますが、最悪の場合（線形リストのような形状）ではO(N)となります。

O(log N)

O(log N)は、ここではアルゴリズムの時間計算量を表す表記法です。
O(log N)のアルゴリズムは、問題のサイズ（入力データの数）について対数関数に従い実行時間が増加することを意味します。

DOMツリーの操作の例で、O(log N)の計算を説明します。
バランスが取れた二分木は、各ノードにおいて左側の子ノードが親ノードよりも小さく、右側の子ノードが親ノードよりも大きいという性質を持っています。
この性質を利用して、二分探索を行うことができます。

1. DOMツリーのルートノードを現在のノードとして設定する。
2. 現在のノードが特定の属性を持っているか確認する。
3. もし持っていれば、そのノードを返す。
4. もし持っていなければ、探索対象の属性が現在のノードの属性よりも小さければ、左の子ノードに移動し、大きければ右の子ノードに移動する。
5. 2-4の手順を繰り返す。特定の属性を持つノードが見つからなければ、そのようなノードは存在しないと判断する。

このアルゴリズムは、バランスが取れた二分木の高さがlog Nであるため、O(log N)の時間計算量を持ちます。
ただし、この例は実際のDOMツリー操作には適用できません。
DOMツリーは通常、バランスが取れた二分木のような構造ではないため、実際のDOMツリー操作ではO(log N)のアルゴリズムは一般的ではありません。

log Nは、数学的な概念である対数を表します。
対数は、ある数を別の数の何乗にすればその値になるかを示すもので、通常、logは底が10の対数を表すことが多いです。
しかし、計算機科学やアルゴリズムの分野では、底が2の対数（バイナリログ）が一般的です。

例えば、底が2の対数の場合、以下のような関係が成り立ちます。

• log₂(1) = 0
• log₂(2) = 1
• log₂(4) = 2
• log₂(8) = 3
• log₂(16) = 4

つまり、log Nは、Nを2の何乗で表現できるかを示す指標です。

アルゴリズムの時間計算量としてO(log N)が使われる場合、問題のサイズ（入力データの数）が増えても、実行時間が対数的にしか増加しないことを意味します。
このようなアルゴリズムは、効率的であり、大規模なデータセットに対しても高速に動作することが期待できます。
二分探索やバランスの取れた二分木構造（例えば、AVL木や赤黒木）の操作は、典型的なO(log N)のアルゴリズムの例です。

分岐係数（Branching Factor）

分岐係数は、各ノードが持つ子ノードの平均数を示します。
分岐係数が大きいほど、木構造は複雑であると言えます。
木構造において、最大の分岐係数をBとすると、複雑度はO(B^D)となります。
ここでDは木構造の深さを表します。

O(B^D)

O(B^D)は、ここでは時間計算量を表す表記法です。
O(B^D)のアルゴリズムは、分岐係数(B)に対して深さ(D）の指数で実行時間が増加することを意味します。

例えば、DOMツリー内のすべてのノードに対して特定の操作を実行するとします。
この場合、BはDOMツリーの各ノードの子ノード数（最大で平均的な子ノード数）、DはDOMツリーの深さ（根ノードから最も深い葉ノードまでのパスの長さ）です。

この操作の計算量は、各ノードの子ノードの数を掛けることで、次のレベルのノード数が計算されます。
これを、ツリーの深さにわたって繰り返します。
結果として得られる計算量は、O(B^D)になります。

例えば、ツリーの平均的な子ノード数が2で、深さが4の場合、全体の計算量はO(2^4)となります。
各レベルで子ノードが2倍になるため、最終的に16倍のノード数（計算量）になります。
この場合、各ノードに対して子ノードを順次処理し、さらにその子ノードの子ノードに対しても同様の処理を行うため、計算量が指数的に増加します。

DOMツリーの可視化で複雑度を把握する

HTMLのDOMツリーの複雑度を把握するには、グラフを作って可視化するのが一番手っ取り早いです。
静的なHTMLの場合は、DOM Tree VisualizerにHTMLのコードを張り付けると、下記のようなDOMツリーのグラフを作成してくれます。

JavaScriptなどを使って、Webブラウザ上でDOMツリーを動的に構築している場合は、DOM Tree Visualizerは使えないです。
メンテナンスが途切れていますがChromeのプラグインであるDOM node tree viewerを使うと表示できます。

人間、数字のような概念だけでは、自分が作っているものを理解できないものです。
以上のようなグラフ化ツールを使って可視化することで、自分が作っているHTMLのDOMツリーの複雑さを視覚で確認できるので、理解しやすいです。

DOMツリーの複雑度とCSSやJavaScriptのパフォーマンスは、スケートリンクの状態とスピードスケートやフィギュアスケートのパフォーマンスの関係に似ている

私の出身地である青森県八戸市では、小学校で冬になると校庭にスケートリンクが作られていました。
現在もこのような習慣が続いているかは分かりませんが、体育の授業で校庭のリンクでスケートを楽しんだことを覚えています。

スケートリンクを作るのは困難な作業で、表面の凸凹がスケート靴で滑ることを難しくさせ、転倒の原因となります。
先生方は毎日水を撒いて、表面が平らになるように凍らせる努力をしていました。

DOMツリーとCSSやJavaScriptの処理時間の関係は、スケートリンクとスピードスケートやフィギュアスケートのパフォーマンスに似ています。
DOMツリーはWebページ上の要素の階層構造を表現するデータ構造で、ブラウザがページのレイアウトやスタイルを計算する基盤です。
これは、スケーターたちがスケートリンク上でパフォーマンスを発揮するための氷の状態に似ています。

複雑なDOMツリーは、氷の表面がデコボコであったり、障害物が多いスケートリンクに例えられます。
スケーターたちは、滑ることが難しくなり、スピードスケートではタイムが遅くなり、フィギュアスケートでは技術の精度が低下することがあります。

一方、シンプルなDOMツリーは、氷の表面が滑らかで障害物が少ないスケートリンクに似ており、スケーターたちがより高いパフォーマンスを発揮できる環境が整っています。
DOMツリーの複雑度が低いほど、ブラウザはより効率的にCSSやJavaScriptの処理を行い、Webページのパフォーマンスが向上します。

Web開発者は、スケートリンクの管理者のように、DOMツリーの状態を最適化し、障害物を取り除くことで、ブラウザが最高のパフォーマンスを発揮できる環境を整えることが重要です。
つまり、Web開発者が効率的にHTML構造を整理し、不要な要素を削除することで、DOMツリーの複雑さが低減され、最終的にWebページのパフォーマンスが向上するのです。

まとめ

DOMツリー構築自体は、複雑でも、それほど時間はかからないかもしれません。
しかし、DOMツリーの複雑度は、それを基盤に実行されるCSSやJavaScriptの計算量を増大させ、実行速度に大きな影響を与えます。
もちろん、処理に使用されるアルゴリズムによっても計算量は変わりますが、基本的にDOMツリーの複雑度は低く抑えておくべきです。

DOMツリーの複雑度がCSSやJavaScriptの処理時間に影響することは、スケートリンクの状態がスピードスケートやフィギュアスケートのパフォーマンスに影響を与えることと似ています。
開発者は、スケートリンクの管理者のように、最適な状態を提供することでユーザーに最高のパフォーマンスを提供できるようにしましょう。