dean.edwards.name/weblog/2006/03/faster/

Faster DOM Queries

Alex Russell, head honcho of the Dojo Foundation, suggests a hideous hack to speed up DOM queries. Why does he want to do this? He wants behavioral extensions to be applied as quickly as possible and he has a point. For a good user experience the code to support a web interface should be applied as quickly as possible. A delay can lead to an unresponsive interface, confusing the user about what works and what doesn’t. So, while I think speeding up DOM queries is a worthy aim, I think that his “id hack” is a step too far. I am supposed to be a standards advocate after all.

There are alternatives.

Let’s examine the problem.

There are two possible causes for any lag before behavioral extensions can be applied:

  1. Waiting for the page to fully load
  2. Walking the DOM to find matching elements, classes and attributes

DOMContentLoaded

The first problem we can tackle by applying my onload hack. I’ll use the example of Ben Nolan’s Behaviour:

Behaviour._apply = Behaviour.apply;
Behaviour.apply = function() {
	if (this.applied) return;
	this.applied = true;
	this._apply();
};
if (document.addEventListener) {
	document.addEventListener("DOMContentLoaded", function() {
		Behaviour.apply();
	}, false); // <== Thanks Anne!
}
/*@cc_on @*/
/*@if (@_win32)
    document.write("<script defer src=ie_onload.js><"+"/script>");
/*@end @*/

This will provide an improvement in responsiveness for a majority of users.

XPath

The second problem, the sluggishness of DOM walking, we will solve on a browser by browser basis. Some browsers (Mozilla and Opera 9) support XPath queries via JavaScript. As luck would have it I recently came across an abandoned script (written by Joe Hewitt) that converts CSS selectors to XPath queries. Perfect! Let’s use it. XPath is much faster than using a DOM query. :-)

if (document.evaluate) {
    document.write("<script src=getElementsBySelector_xpath.js><"+"/script>");
}

Internet Explorer

But what about Internet Explorer? I love hacking that browser. So:

/* CSS */
div.widget {
	behavior: expression(Selectors.store("div.widget", this));
}
/* JavaScript */
var Selectors = {
	cache: {},
	...
	store: function(selector, element) {
		// called from the CSS expression
		// store the matched DOM node
		this.cache[selector].push(element);
		element.runtimeStyle.behavior = "none";
	},
	...
}

This piece of CSS and JavaScript leverages the speed of IE’s internal CSS engine. It is pretty fast. About four times faster than a DOM query. After messing about with the above code for a while I came up with an improved getElementsBySelector for Internet Explorer. I have to point out that the benefits of this approach are only available on page load. But that is good enough for most situations.

To illustrate this technique properly I’ve created an extended version of Behaviour:

I’ve combined these files into a single compressed file which includes a test page:

http://dean.edwards.name/my/behaviors/behaviour+/behaviour+.zip

Please note that I am illustrating a technique for faster DOM queries. This is not an exercise in writing a better behavior library.

Limitations

Conclusion

Comments (40)

Leave a comment

Just to be clear. You don’t have to write any CSS to make this solution work. All of the required expressions are created by JavaScript and are removed on completion.

  • Comment by: -dean
  • Posted:

Dean:

Freaking brilliant. I had started down the XPath road for FF and was actually working on a prototype of the expression hack you outline and trying to figure out a way to make it work without an external HTC. I’ll be rewriting dojo.behavior around these techniques ASAP. As far as I can tell, we’re still f’d on Safari though = \

Fantastic work.

Regards

Yeah. Nothing good works on Safari. ;-)

  • Comment by: -dean
  • Posted:

Dean, why you will not implement all these goodness for your really brilliant cssQuery? I mean XPath… ;)

  • Comment by: FataL
  • Posted:

@FataL – that’s a good idea. cssQuery already has a caching option which improves performance. I could easily add XPath support. Not sure how I’d handle the expression hack though…

  • Comment by: -dean
  • Posted:

I tried to see if //*[@id="foo"] would be a better performing alternative to getElementById, but Firefox throws exceptions on me. Could it be that document.evaluate is only available after the the DOM is fully loaded?

  • Comment by: Martin Bialasinski
  • Posted:

I wouldn’t say that my getElementsBySelector script is abandoned exactly. I use it in the FireBug extension to perform filtering of elements by CSS in the source inspector. Glad to see you’re getting some use from it beyond that!

  • Comment by: Joe Hewitt
  • Posted:

Having never resorted to Behaviour myself, I suppose this might not solve all the problems it addresses, but if the event registration is what eats our time, couldn’t we often just listen in on events to the document object and determine via event.target whether they should fire off a behaviour or not, using our (Behaviour-internal) registry of what-event-goes-where?

Viable or not, it’s something I’d at least try if I had bucketloads of event handlers and felt abandoned by the W3C about doing it their way.

Oooh, very interesting indeed. I shall have to have a play with this stuff…

Oh and yes, behaviour is the leakiest thing ever – but still fantasmagorical :)

  • Comment by: Olly
  • Posted:

Wow! It is really good stuff and it has a performance estimate compared to good old DOM queries! Thank you for these nuggets of wisdom.

@Joe – I’m loving the Firebug extension BTW. :-)

  • Comment by: -dean
  • Posted:

Re your comment that Behaviour leaks like a sieve, work is going on to fix that over on google groups.

  • Comment by: Olly
  • Posted:

I cant seem to get the test page to work correctly in internet explorer, does anyone else have this problem?

  • Comment by: Joshua Richardson
  • Posted:

[...] ness of it, but knows that we need faster DOM work. He played with XPath as a solution and his work concluded: DOM queries on Firefox seem pretty quick XPath is about 150% faster than [...]

@Joshua – I seem to have broken the test page. Now I can only get it to work on IE in only limited circumstances. Maybe this isn’t such a good solution after all. :-(

  • Comment by: -dean
  • Posted:

I’ve realised what the problem is now. I’ll update the test page later today. The solution does work after all. :-)

  • Comment by: -dean
  • Posted:

Nice! I just wish it was the same for all browsers. I hate the fact that we have to write different code for different browsers.

“For a good user experience the code to support a web interface should be applied as quickly as possible.”

Isn’t that the browser’s job? I don’t feel it is – or should be – the responsibility of the coder.

Even as your last commentor stated, “I just wish it was the same for all browsers.”

To me, this seems to be just another ‘hideous hack’ that should be a browser-maker fix, not ours.

  • Comment by: praetorian
  • Posted:

you can make the Behavior not leak, simply add the following to your test.html page:

	var myrules = {
		'table.test td' : function(element) {
			element.onmouseover = function() {
				this.style.backgroundColor = "yellow";
			},
			element.onmouseout = function() {
				this.style.backgroundColor = "";
			}
			element = null; // by setting this IE will not leak :) 
		}
	};	
	Behaviour.register(myrules);
  • Comment by: Lucky
  • Posted:

another issue you may want to address is a cascaded inheritence?

    var myrules = {
        'td': function(element) {
          element.expando = "yes";
        },
        'table.test td' : function(element) {
          if (typeof element.expando == "yes")
            element.cascadedProperly = true;
        }
    };

The table.test td elements will not receive the default “td” rule first, and then have the other. Simply due to the reuse of css “behavior” property.

If it is desired that each applicable selector get applied, you can just set a unique css property value in your code, and IE will apply each instance. I have a full example of this, and a “test-cascading” page if you wish me to send your way?

  cssText.push(selector +"{unique-"+ index +":expression(....
  • Comment by: Lucky
  • Posted:

@Lucky – unfortunately this is not a very efficient mechanism. The expression associated with a custom CSS property is constantly evaluated until you deliberately remove the expression using removeExpression. This is true even if you remove the style sheet that contains the rule! The behavior property works because you can override it using runtimeStyle.

I mention the problem of only being able to apply one behavior per element in my original post. Both DHTML Behaviors and XBL share this limitation (as far as CSS bindings are concerned).

  • Comment by: -dean
  • Posted:

with a custom CSS property is constantly evaluated until you deliberately remove the expression using removeExpression.

I thought this too, but it doesn’t seem to be the case that the expression gets called again, within my testing page, runs very smoothly as well.

  • Comment by: Lucky
  • Posted:

Posted up an example (using updated getElementsBySelector_ie.js), if you would look over sometime.

Another nice concept might be to just leave the expression in place, so that any newly created elements would apply it dynamically. Sort of like lightweight HTC. However, not sure how the mozilla counterpart of such a setup would go? Can’t imagine creating/binding an XBL DOM via JS instead of directly wiring it to an XML url.

  • Comment by: Lucky
  • Posted:

[...] Convert CSS selectors to XPath queries (via Dean Edwards’s Faster DOM Queries) I’ve only just got round to reading this: it’s great! Joe Hewitt [...]

I tried to integrate this into my existing use of Behaviour and rules, but I ran into a problem. One of my rules was being applied to the wrong CSS selectors! For example, I had this rule:

'div.myCSS'			: function(element) {
	element.onmousedown = function() {
		alert(this.id + " " + this.className)
		// do stuff, etc
		// ...
	}
}

Normally, this alert should pop only when I click on divs that go <div class=”myCSS”>, right? But it appeared when I clicked on *other* divs, which I confirmed with the alert itself (this.className should have displayed “myCSS” and didn’t). This only happened using the Xpath selectors, when I removed it, it worked again. Any idea of why this happened? Am I missing something or is this a bug in the getElementBySelector_xpath library? Thanks.

  • Comment by: Morrigan
  • Posted:

“Yeah. Nothing good works on Safari.”

Two months later, the nightly builds of WebKit boast XPath support. Things are getting interesting.

Two issues in the IE‘s solution.

First Selectors.tidy(); is sometimes called before IE could actually finish the CSS rendering part at the statement ‘ this.styleSheet.cssText = cssText.join("\n"); ‘. It is found to occur when you have simpler codes such as the following var s='', myrules = { '.R1' : function(element) { s+=element.id+','; } }; Subsequently, errors are produced for all references to this.cache, since its contents would’ve been cleared in the call to Selectors.tidy();

My fix to this issue was simply a pospone in a fraction of time to the statements of tidy as follows (tested with some 7500 elements which successfully run for 27 seconds):

	tidy: function() {
		// clean up after behaviors have been applied
		var self=this;
		setTimeout( function() {
				delete self.cache;
				self.styleSheet.cssText = "";
				self=null; // clean-up (why rely on IE's GC?)
			}, 10);
	}

Second, if alert boxes were used (or any action that makes IE to reapply the behaviors) in the target ‘callback’ function then the contents of cache items are duplicated. So the target ‘callback’ function would be called twice the original number of times.

I even tried a RegExp fix but that was of no use:

// Add only when not present.
if(!this.cache[index].join(' ').match(new RegExp('\\b'+index+'\\b')))
	this.cache[index].push(element);

Any ideas on the second issue, Dean? Anyone?

By the way, I must thank you for sharing your brilliant work! My Best Regards!!

  • Comment by: Md. Sheriff, Drivestream
  • Posted:

No problems, now!

I just realized that I was mistakenly going for the key string, but the real check should be over the value part which is turns out to the element.

Here is the updated code!

		if (!inArray(this.cache[index], element, true))
			this.cache[index].push(element);

...
...

function inArray(array, value, strict) {
	for (var i=0; i < array .length; i++ )
		if ( (strict?array[i]===value:array[i]==value) )
			return true;

	return false;
}

And yes, the issue is solved.. You will no more have duplications of the same element.

Hope these two bug-fixes are useful. Modified file: getElementsBySelector_ie.js

  • Comment by: Md. Sheriff, Drivestream
  • Posted:

@Md Sherriff – Thanks for this. I have since refined this technique to address the problems you mention. The new solution eliminates duplicates and can be called after the document has loaded too.

  • Comment by: -dean
  • Posted:

I’ll blog about the improved solution later. :-)

  • Comment by: -dean
  • Posted:

[...] de adds yet another layer of meaning when I’m interpreting it. For instance take any blog post from Dean Edwards and you’ll notice that after the [...]

[...] er web developer: Really easy field validation with Prototype Prototype class: FastInit() Faster DOM Queries Writing: Writing Tips for Non-Writers Who Don’t Want to Work at Writing [...]

[...] rting a CSS selector to an XPath expression. Dean Edwards, picking up where Joe left off, used that function as part of an addon to Behaviour, illustrating several tactics that can be use [...]

Is there still activity on this topic?

I made an attempt on breaking the limitation of only one behavior per element:

I just added an second array (sidCache –> selector id cache) to store every selector contained on the page:


sidCache: [],

In the ‘register’ part i put each selectors into the array:


this.sidCache[index] = selector.replace(/./, "");

When it comes to ‘store’ i run through the array. If the elements className contains a selector it’s pushed into the cache:


		for (var i=0; i < this.sidCache.length; i++) 
		{
		    if (i != index)
		    {
		        if (element.className.search(this.sidCache[i]) != -1)
		        {this.cache[i].push(element);}
            }
}

Delete the sidCache on cleanup and that’s it. Now every single behavior defined for an element is being properly applied.

It’s very simple indeed and I don’t know if this is really a good approach. Nonetheless it seems to work perfectly for me. Behavior is still being applied about six times faster then without your brilliant peace of work.

I hope you can give me some feedback on my solution and it’s possible limitations. Thank’s for that!

Regards!

  • Comment by: rob
  • Posted:

[...] It’s an important goal, and ensuring that simple-looking queries don’t “hurt” disproportionately is a difficult task. After some initial work with my admittedly grotty getElementsById hack, my outlook wasn’t bright. Other systems weren’t looking much better. Using the behavior: expression(); hack degrades page performance something fierce and can’t be made synchronous, a key requirement to meet developer ease-of-use goals. Requiring a callback for every query result is a no-go. [...]

[...] Faster DOM Queries (tags: DOM XPath) [...]

For people that want to use the speedier code AND make it work on Safari (just ignore IE code, so no speedup), use conditional to check for typical IE code:

// this object will manage CSS expressions used to query the DOM
var Selectors;
if (document.createStyleSheet) Selectors = {
	styleSheet: document.createStyleSheet(),
	cache: {},
	length: 0,

	register: function(sheet) {
		// create the CSS expression and add it to the style sheet
		var cssText = [], index;
		for (var selector in sheet) {
			index = this.length++;
			// have to store by index too as the expression hack does not like
			//  spaces in strings for some strange reason
			this.cache[index] = this.cache[selector] = [];
			cssText.push(selector + "{behavior:expression(Selectors.store(" + index + ",this))}");
		}
		this.styleSheet.cssText = cssText.join("\n");
	},

	store: function(index, element) {
		// called from the CSS expression
		// store the matched DOM node
		this.cache[index].push(element);
		element.runtimeStyle.behavior = "none";
	},

	tidy: function() {
		// clean up after behaviors have been applied
		delete this.cache;
		this.styleSheet.cssText = "";
	}
}
if (Selectors) {
	// override getElementsBySelector
	document._getElementsBySelector = document.getElementsBySelector;
	document.getElementsBySelector = function(selector) {
		if (!Selectors.cache || /\[/.test(selector)) { // attribute selectors not supported by IE5/6
			return document._getElementsBySelector(selector);
		} else { // use the cache
			return Selectors.cache[selector];
		}
	};
	// override Behaviour's register function
	Behaviour._register = Behaviour.register;
	Behaviour.register = function(sheet) {
		Selectors.register(sheet);
		// call the old register function
		this._register(sheet);
	}
}

[...] Faster DOM Queries Apr 10, 06 Alex Russell, head honcho of the Dojo Foundation, suggests a hideous hack to speed up DOM queries. Why does he want to do this? He wants behavioral extensions to be applied as quickly as possible and he has a point. For a good user experience the code to support a web interface should be applied as quickly as possible. [...]

VTD-XML is a lot faster than DOM in both parsing, and XPath, memory usage is a lot lower, but it is not yet available in browsers… :(

  • Comment by: jzhang
  • Posted:

[...] Via Ajaxian descubro una solución para disponer de una versión rápida (casi como la nativa ) de querySelector() en Internet Explorer 4+. Muy similar a la propuesta por Dean Edwards en 2006. [...]

Leave A Comment

Line and paragraph breaks automatic, email address never displayed. Some HTML allowed.