getElementsByClassName Speed Comparison

Mark Finkle suggested that I do some speed testing, now that a native implementation of getElementsByClassName has landed in the Mozilla trunk (destined for Firefox 3).

So I went around and dug up all of the different, existing, implementations that I could find. Currently, implementations fall into one of three categories (with some straddling more than one):

  • Pure DOM
    This usually involves a calls to .getElementsByClassName("*") and traversing through all matched elements, analyzing each element’s className attribute along the way. Generally, the fastest method is to use a pre-compiled RegExp to test the value of the className attribute.
  • DOM Tree Walker
    Is a less-popular means of traversing DOM documents by setting some simple parameters, as specified by the DOM Level 2 Spec. For example, you could traverse through all text nodes in a document (something that you can’t easily do in any other way).
  • XPath
    The most recent technique, to be popularized, was the use of XPath to find elements by classname. The implementation is generally simple: Building a single expressions and letting the XPath engine traverse through the document, finding all the relevant elements.

I’ve chosen some implementations that were representative of each of these techniques.

Tree Walker

An implementation using the DOM Level 2 Tree Walker methods. Builds a generic filter function and traverses through all elements.

document.getElementsByClass = function(needle) {
  function acceptNode(node) {
    if (node.hasAttribute("class")) {
      var c = " " + node.className + " ";
       if (c.indexOf(" " + needle + " ") != -1)
         return NodeFilter.FILTER_ACCEPT;
    }
    return NodeFilter.FILTER_SKIP;
  }
  var treeWalker = document.createTreeWalker(document.documentElement,
      NodeFilter.SHOW_ELEMENT, acceptNode, true);
  var outArray = new Array();
  if (treeWalker) {
    var node = treeWalker.nextNode();
    while (node) {
      outArray.push(node);
      node = treeWalker.nextNode();
    }
  }
  return outArray;
}

The Ultimate getElementsByClassName

Uses a pure DOM implementation, tries to make some optimizations for Internet Explorer.

function getElementsByClassName(oElm, strTagName, strClassName){
    var arrElements = (strTagName == "*" && oElm.all)? oElm.all : 
        oElm.getElementsByTagName(strTagName);
    var arrReturnElements = new Array();
    strClassName = strClassName.replace(/\-/g, "\\-");
    var oRegExp = new RegExp("(^|\\s)" + strClassName + "(\\s|$)");
    var oElement;
    for(var i=0; i<arrElements.length; i++){
        oElement = arrElements&#91;i&#93;;      
        if(oRegExp.test(oElement.className)){
            arrReturnElements.push(oElement);
        }   
    }
    return (arrReturnElements)
}&#91;/js&#93;

<h3><a href="http://www.dustindiaz.com/getelementsbyclass">Dustin Diaz's getElementsByClass</a></h3>

A pure DOM implementation, caches the regexp, and is generally quite simple and easy to use.

[js]function getElementsByClass(searchClass,node,tag) {
	var classElements = new Array();
	if ( node == null )
		node = document;
	if ( tag == null )
		tag = '*';
	var els = node.getElementsByTagName(tag);
	var elsLen = els.length;
	var pattern = new RegExp("(^|\\s)"+searchClass+"(\\s|$)");
	for (i = 0, j = 0; i < elsLen; i++) {
		if ( pattern.test(els&#91;i&#93;.className) ) {
			classElements&#91;j&#93; = els&#91;i&#93;;
			j++;
		}
	}
	return classElements;
}&#91;/js&#93;

<h3><a href="http://prototypejs.org/">Prototype 1.5.0</a> (XPath)</h3>

Mixes an XPath and DOM implementation; using XPath wherever possible.

[js]document.getElementsByClassName = function(className, parentElement) {
  if (Prototype.BrowserFeatures.XPath) {
    var q = ".//*[contains(concat(' ', @class, ' '), ' " + className + " ')]";
    return document._getElementsByXPath(q, parentElement);
  } else {
    var children = ($(parentElement) || document.body).getElementsByTagName('*');
    var elements = [], child;
    for (var i = 0, length = children.length; i < length; i++) {
      child = children&#91;i&#93;;
      if (Element.hasClassName(child, className))
        elements.push(Element.extend(child));
    }
    return elements;
  }
};&#91;/js&#93;

<h3><a href="https://johnresig.com/blog/getelementsbyclassname-in-firefox-3/">Native, Firefox 3</a></h3>

A native implementation, written in C++; is a part of the current CVS version of Firefox, will be included in Firefox 3.

[js]document.getElementsByClassName

The Speed Results

For the speed tests I copied the Yahoo homepage into a single HTML file and used that as the test bed. They make good use of class names (both single and multiple) and is a considerably large file with lots of elements to consider.

You can find the test files, for each of the implementations, here:
https://johnresig.com/apps/classname/

Note: “XPath” is just Prototype’s implementation.

From these figures we can see that the native implementation of getElementsByClassName, in Firefox 3, is a full 8x faster than the XPath implementation. Additionally, it’s a stunning 77x faster than the fastest DOM implementation.

Note: These numbers have been revised from what was originally posted as the lazy-loading nature of document.getElementsByClassName wasn’t taken into account. The resulting arrays are completely looped-through now, making sure that all elements are accounted for.

Currently, Prototype has the best general-use implementation: Use XPath selectors wherever possible, fall back to fast DOM parsing.

Interestingly, only Prototype actually tries to implement the document.getElementsByClassName interface (all others do one-off names). However, Prototype doesn’t check to see if the document.getElementsByClassName property already exists, and completely overwrites the, incredibly fast, native implementation that Firefox 3 provides (oops!).

In all, the results are quite astounding. The native implementation is absolutely much faster than anything I could’ve imagined. It completely decimates all the other pieces of code. I can’t wait until this hits the general public – users will, absolutely, feel a significant increase in speed.

Posted: March 8th, 2007

Subscribe for email updates

25 Comments (Show Comments)


Comments are closed.
Comments are automatically turned off two weeks after the original post. If you have a question concerning the content of this post, please feel free to contact me.

Secrets of the JavaScript Ninja

Secrets of the JS Ninja

Secret techniques of top JavaScript programmers. Published by Manning.

Subscribe for email updates

John Resig Twitter Updates

@jeresig / Mastodon

Infrequent, short, updates and links.