Ever since we began the Dojo project, it's been our intention to collect the very best, most useful JavaScript and consolidate it into a single library that makes your applications better and easier to use. I'm excited to announce a new evolution in Dojo that continues this tradition: dojo.query

Over the last year jQuery, MochiKit, Prototype, and behavior.js have been emphasizing the importance of being able to easily query arbitrary HTML DOM structures via CSS-like syntax. The importance of these APIs hasn't been lost on us at Dojo, but the lack of efficiency in most of the available libraries gave us pause. We need a generalized query system that is both powerful yet fast enough to not endanger the user experience when used heavily.

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.

Luckily Jack Slockum's recent work has pointed the way to a query system that is fast enough for heavy use without waiting on the browser vendors to get their act together and give us a compact, powerful, and fast selector system. As a piece of engineering work, DomQuery is a beauty. It's fast, small, and has few dependencies. Without Jack's excellent example, I might have left the idea of a query system for Dojo on the shelf even longer. In particular, DomQuery starts to address some of the largest issues I had identified when investigating getElementsById:

• A generic system must have enough fast-path differentiation to keep queries that are known by webdevs to be fast running at something like "native" speed.
• It is not clear that the IE team has any plans to embrace XPath over the HTML DOM despite its clear utility and proven value. Assuming that there will continue to be bifurcation in browser-provided fast-paths for query syntaxes, it's reasonable to assume that CSS style selectors will most likely be made available natively everywhere. So what's the right query language subset for a JS library to support?
• Current systems get choked up on queries that potentially exhibit large "node blooms" in the intermediate phases of constructing the result set. Queries of the form "div div div" give most systems a hell of a time, reducing user trust in the system. Can we level out that anomaly?

The last part is critically important because it highlights how innocent looking queries can endanger the developer and user experience. Simple interfaces that allow you to hurt yourself easily may be worse than more complicated paths into the same functionality. API ease should scale with utility, but also with expected pain or speed tradeoffs. A dangerous API should look dangerous. The gauntlet is thus laid: can we go fast enough on hard queries to provide a trustable foundation for large-scale development?

Yes. We can.

With the recent DomQuery/jQuery debate as a backdrop, I started to investigate the relative performance of some of the more esoteric options. From caching behavior hacks on IE to XPath to getElementsById, everything was on the table. The results surprised me.

In many cases, the availability of XPath isn't necessarily a win until the complexity (node-bloom size) of a query outweighs what appears to be non-trivial startup costs for the query engine. On Firefox in particular, XPath queries can yield tremendous gains for generalized queries over all nodes with a particular attribute value or over queries that look like "div div div". Surprisingly, though, simpler queries such as "div div" may actually be at a loss to regular getElementsByTagName() attacks. Confoundingly, the results are also browser specific. Not all queries that run faster in XPath vs. DOM on Firefox run faster via XPath on Opera or the WebKit nightly builds. Nevertheless, for many of the hardest queries, deferring to XPath can yield results that are 2x-4x better than other approaches.

Of course, the 80% browser doesn't support XPath, but I'm personally over losing sleep to Microsoft's bad engineering and management decisions. If the IE team decides to get with the program and give us a good query engine, we'll use it. Until then, they get best effort. Their browser only deserves to look as good (or bad) as it really is, after all.

dojo.query

With those somewhat surprising findings in hand, it was time to build a better mouse trap. The result is dojo.query, an experimental module that is currently checked in to the Dojo trunk. The system has nearly zero Dojo dependencies and can therefore be safely dropped into older Dojo environments (perhaps even pre 0.4) without difficulty.

The API is straightforward:

// include the system
  dojo.require('dojo.query');

  // run some queries
  dojo.query('#id');
  dojo.query('div:first-child');
  dojo.query('code.example');
  dojo.query('.example');

All queries return an array of unique DOM nodes. Today this is just a "raw" array as I'm investigating what extensions make sense on the return object and what should instead be deferred to a layer on top of dojo.query such as dojo.behavior.

Today dojo.query only supports CSS 1-3 queries although support may be added for xpath-ish semantics if there's sufficient demand and I can justify the engineering time based on some hope that we can make what we do work on whatever fast path browsers eventually provide. The worst possible outcome would be to provided an interface that that browsers almost make obsolete.

How fast is "fast enough"?

Using the the test suite from DomQuery (but with a Dojo-based test runner system), we can show the relative performance of DomQuery, jQuery, and dojo.query. While clearly the slowest of the bunch, jQuery 1.1 provides the richest API today and there's no telling how providing a richer return object may affect the relative timings of dojo.query on the tests where all 3 systems are relatively close. In any case, these tests show raw performance of the node query engine and not much else. You can obviously write fast apps with a slow engine by using it less and write slow apps with a fast engine by writing obscene queries or doing expensive operations on the return.

But enough jibba-jabba. Gimmie data!:

IE 7:

IE 6

Firefox 2:

Safari 2.0:

Webkit Nightly (aka, "Leopard Safari"):

Opera 9:

So how'd we do? Generally, dojo.query is in the hunt with DomQuery or edges it out for raw DOM iteration. Like Jack's system dojo.query beats jQuery most of the time. dojo.query also shines on Firefox and Opera where asking questions of the DOM that would result in large "node blooms" can be sidestepped with XPath. Queries like ".thinger" and "div span span" help show how dramatic the difference can be.

Lest anyone get the wrong idea about all the "invalid" attribute tests in jQuery toward the bottom, the syntax used in the tests is generally the CSS selector variant of something that jQuery can probably support in another form. In most cases it would be possible to re-write the test to use a jQuery friendly selector to achieve the same thing.

Interestingly, it's clear that Opera and the Webkit Nightlies beat IE and Firefox for raw query performance across the board. DOM or XPath, ripping through node collections on Opera is blindingly fast. The currently shipping Safari is a dog, though. IE 6 also comes in with numbers that make IE 7's relatively pokey turnout look stellar. At somewhere between 2x and 3x faster, IE 7 is quite the improvement. It might even be something that Microsoft could crow about if IE's Open Source competition didn't make it look so feeble. Firefox isn't the fastest of the lot, but it still takes IE 7 to the woodshed on nearly every test. The gloves will really come off when the Webkit nightlies finally ship in official form.

Running all 3 libraries through the test system created by John Resig, we get results which are broadly in line. You can try them out for yourself. These larger/longer tests are here or on John's smaller test suite is here. Be warned that the test pages pull in a lot of script and do a lot of work. They can easily bog down your box for a good long while.

Getting The Code

dojo.query isn't going to be part of the 0.4.x line, and it's marked experimental for the time being. While I believe it to be correct for the cases it handles, the devil in systems like this is in the details. Furthermore, I'd like it to give more explicit guidance about when it encounters queries that it can't handle before calling it production ready.

You can get a ShrinkSafe'd copy of the library here but be sure to check back with what's in SVN frequently to get the latest, most correct version.

Also, remember that you can include a file like this with either a <script> tag somewhere after your main dojo.js file or with the usual dojo.require syntax. Either way, dropping dojo.query into your app is a snap.

It's Closures All The Way Down

I've kind of glossed over the details of how to make a system like this scream. Having a goal is the first step and being data-driven in optimization is the second. Jack Slockum's excellent DomQuery does a masterful job in reducing dominating factors. From not allocating intermediate arrays in hard cases to "compiling" down functions for future use on a particular query, DomQuery sets the bar very high. In many cases, matching or beating Jack's system proved to be very difficult and for some of the newer code in dojo.query (e.g., attribute selectors) there's still some way to go. With iterative development to tune performance a must, a couple of basic design decisions made evolving the system to meet performance targets easier.

At it's core, dojo.query uses closures as a way to keep query parsing from happening more than once. Instead of naively parsing and running the query each time or even creating a custom function from a string, dojo.query builds up a set of filtering functions in a functional programming style. The result is a system that can count on closure scope for caching intermediate variables of all sorts. It may not be a huge performance win, but the system "feels" more like idiomatic JavaScript and it's always possible to get line numbers when debugging problems. Explicit caching happens only at a coarse level. Full queries and filtering functions for query parts are the biggest recipients of direct memoization. Having the rest of the system be composed of functions that just generate functions simplifies the system greatly. Which is good, because adding another branch (XPath) adds some complexity.

As noted earlier, XPath turns out not to be a "win" on every query, even on the browsers where it can make a huge difference. To handle this, dojo.query adds a heuristic layer to the first-run parsing to figure out whether or not a query can and should be deferred to XPath. Because we can't plan for every query "shape" in the pre-processor and still be space-efficient, the heuristic is rather rough but in the future it will likely improve to handle cases where today it "punts" to regular DOM iteration. This kind of primordial "query optimizer" is likely going to be the focus of some continued development effort since anything we can improve in its heuristic is potentially a huge gain on browsers that give us a fast path. At the very least, the heuristic/optimizer layer gives us a straightforward place to plug in new back-ends when better browser fast-paths emerge or when the relative XPath/DOM performance metrics change between revs of the same browser. For instance, while the Webkit nightlies are very fast and support XPath, regular-old DOM traversal is relatively much faster on that browser than XPath. The optimizer layer lets us take that into account and do the "Right Thing" more often.

While there is some thrill in the hunt of building systems like this that are fast enough to enable fundamental changes in the way Dojo developers work, I wish it weren't necessary. The browser vendors are continuing to let us down, and every year that goes by without fast-path DOM queries, a unified behavior layer, real and portable parametric CSS, socket-like network connections, and unified 2D graphics support is opportunity lost. Sadly, while the IE team shoulders much of the blame for not shipping many of these features in any form, they're not alone in their culpability. I'm proud of dojo.query, but I wish I didn't have to be. Yet another chunk of useful javascript that will be shipped around the web ad-infinitum instead of being baked into the platform itself should make everyone sad.

Lastly, research and development for dojo.query is thanks to SitePen. If you like what Dojo and dojo.query are about, you'll love what SitePen can do (and help you do), for your applications.