getElementById() の実装調査＆パフォーマンス計測

• 2011年7月9日
• JavaScript
• まとめ, 覚え書き

• 結論
• 背景
• 実装調査
• パフォーマンス計測
• 備考
• 関連リンク

結論

document.getElementById() が非効率で使えないという指摘を時々見かけるが、その実装や計測結果をみるとモダンブラウザーには当てはまらないと思う。ただ Internet Explorer 8 以前で少なくとも 100 回以上 getElementById() を呼び出すような場合はパフォーマンスを考慮する必要があるかも。

※ JavaScript プログラマーではないので思い込みや勘違いがあるかもしれません。適切でない記述などはコメントでお知らせください。

背景

AnimateImage のおかげで体系的に学んでもいないのに JavaScript を書いている近頃。Google の助言 (検索で得た情報) を参考にしていると document.getElementById() に対して次のような指摘を見かけることがある。

getElementById() は DOM ツリーを全探索して指定した id を持つ要素を返すため非常に効率が悪い。getElementById() を何度も呼ぶ必要がある場合は次のように実装すべき。

• getElementById() の戻り値 (element) をキャッシュする
• getElementById() を使わずに次のように実装する
  • コレクションプロパティ (anchors, forms, images, links など) を参照する
  • getElementsByTagName() メソッドを利用する
  • 手動で直接 DOM ツリーにアクセスする

もっともな指摘のようにもみえるが、少し考えてみると getElementById() がそんなイケてない実装とはとても思えない。戻り値のキャッシュで改善するのであれば API 側でハッシュマップを使用しているはず。

※ getElementById() の仕様によれば厳密にはブラウザーの実装依存。だけどメソッドを呼び出すたびにツリーを全探索するような実装は、コードレビュアーに呼び出されるかパフォーマンスバグ扱いされるレベル。

実装調査

ということで document.getElementById() がどのように実装されているか実際に調べてみた。

結論から言えば、オープンソースで確認できる範囲では getElementById() はすべてハッシュマップを使用して実装されていることが判明。

Mozilla Firefox

• getElementById() は mozilla::dom::nsDocument で実装されている
• ID を持つ要素は mIdentifierMap で管理されている
• mIdentifierMap は nsTHashtable として宣言されている

以上の点から Firefox ではハッシュテーブル (ハッシュマップ) を使用して getElementById() が実装されていることが分かる。

nsDocument.cpp

Element*
nsDocument::GetElementById(const nsAString& aElementId)
{
  if (!CheckGetElementByIdArg(aElementId)) {
    return nsnull;
  }

  nsIdentifierMapEntry *entry = mIdentifierMap.GetEntry(aElementId);
  return entry ? entry->GetIdElement() : nsnull;
}

nsDocument.h

nsTHashtable<nsIdentifierMapEntry> mIdentifierMap;

Google Chrome, Apple Safari (WebKit)

• getElementById() は WebCore::Document で実装されているが、その処理は TreeScope::getElementById() に委譲している
• ID を持つ要素は m_elementsById で管理されている
• m_elementsById は DocumentOrderedMap として宣言されている
• DocumentOrderedMap は内部的に HashMap を使用している

以上の点から Chrome と Safari でもハッシュマップを使用して getElementById() が実装されていることが分かる。

Document.cpp

Element* Document::getElementById(const AtomicString& id) const
{
    return TreeScope::getElementById(id);
}

TreeScope.cpp

Element* TreeScope::getElementById(const AtomicString& elementId) const
{
    if (elementId.isEmpty())
        return 0;
    return m_elementsById.getElementById(elementId.impl(), this);
}

TreeScope.h

private:
    DocumentOrderedMap m_elementsById;

参考：Java 6

org.w3c.dom.Document を implements している com.sun.org.apache.xerces.internal.dom.CoreDocumentImpl でもハッシュテーブル (ハッシュマップ) を使用して getElementById() が実装されている。

CoreDocumentImpl.java

protected Hashtable identifiers;

public Element getElementById(String elementId) {
    return getIdentifier(elementId);
}

public Element getIdentifier(String idName) {

    if (needsSyncData()) {
        synchronizeData();
    }

    if (identifiers == null) {
        return null;
    }
    Element elem = (Element) identifiers.get(idName);
    if (elem != null) {
        // check that the element is in the tree
        Node parent = elem.getParentNode();
        while (parent != null) {
            if (parent == this) {
                return elem;
            }
            parent = parent.getParentNode();
        }
    }
    return null;
} // getIdentifier(String):Element

• Java Platform, Standard Edition 6u23 Source Snapshot Releases

パフォーマンス計測

オープンソースでないブラウザーは getElementById() の実装が分からないため呼び出しコストも不明。そこで実際にパフォーマンス計測してみることにした。

テストケース

• test-getElementById.html

テストケースの内容は次の通り。詳細はソースを参照。

1. ユニークな ID を持つ span 要素を 10,000 個生成してドキュメントに挿入
2. 挿入された 10,000 個の span 要素を getElementById() で取得
3. getElementById() 呼び出しにかかった時間を計測して 10,000 で割る
4. 以降は [Run] ボタンを押すたびに getElementById() の計測のみを行う (span 要素は生成しない)

テスト結果

[*] Internet Explorer 10 Test Drive (Platform Preview 2.10)

以上の結果から Internet Explorer 8 以前は getElementById() のパフォーマンスが桁違いに低いことが分かる。ただ一番遅い Internet Explorer 6 でも 100 回呼び出して 0.5 秒なので、ソースの可読性や保守性を考えると無条件に getElementById() を使うべきでないとは断言できないと思う。

※ 計測値は getElementById() の 1 回あたりの呼び出し時間で、何回か試行した結果の平均値か収束値となっている。計測値は次のような項目により増減するため絶対値ではなく相対的に評価する必要がある。

• ドキュメントの要素数や DOM ツリーの構造
• プラットフォームの種別
• コンピューターのスペック
• テストケースのロジック
• 初回呼び出しか否か (初期化やキャッシュの有無)
• 計測誤差

備考

getElementById() のパフォーマンスに問題がないからといって、明らかに無駄な呼び出しをしても構わない理由にはならない。たとえば次のような実装 (同じ要素をループ内で取得) は JavaScript に限らずかなり恥ずかしいコード。

for (var i = 0; i < count; i++) {
    var elem = document.getElementById('foo');
    // elem に対する処理
}

関連リンク

getElementById() の仕様

• Document Object Model (HTML) Level 1 – getElementById
• Document Object Model Core – getElementById (DOM Level 2)
• Document Object Model Core – getElementById (DOM Level 3)
• document.getElementById – MDN Docs (日本語)
• getElementById Method (document, HTMLDocument Constructor)

getElementById() の実装

• javascript – What is the implementation of GetElementByID() ? – Stack Overflow
• dom – Javascript getElementById lookups – hash map or recursive tree traversal? – Stack Overflow

getElementById() のパフォーマンス

• Ajax 最適化 Tips – getElementById する前に – ありえるえりあ
• FireFox3とIE6で、Elementの取得において最高速なのは？ – 山本大＠クロノスの日記
• 12 Worried Engineers　 DOMアクセスの性能
• DOMにおけるメソッド呼び出しについて[完成版]・DOM操作をする場合の注意。 – namusyaka日記

JavaScript のパフォーマンス

• JavaScript と Ajax のパフォーマンスを最大にする
• 効率的な JavaScript – Dev.Opera