Implications of Using XPath on Speed

Posted by & filed under , .

This is something that I have discovered recently looking through some (old) code — and it occurred to me that XPath is so powerful and easy to use that quite often programmers might forget the price paid for something this powerful. Don’t get me wrong, I’m not saying XPath is worthless (on the contrary!), if anything looking at this code recently it became a bit of a worry for me the fact that I’m using the damn thing all the time, as I said, occasionally forgetting the “cost” implications in terms of execution time. Which is why I put together this as a reminder to everyone about this — as occasionally you might want to go around XPath to get that extra bit of oomph in your app.

As I said, I spotted this in some (relatively) old code — and I guess at the time because I was in a rush it didn’t occur to me. To simplify the matter so I don’t have to go through all the details of what the original code did (there’s a lot more to it than I’m presenting here to be honest, but I’m isolating only the XML/xpath part of it), consider this situation: you are required to parse an XML file with the following structure:

<item name="1" description="Description for 1" />
<item name="2" description="Description for 2" />
<item name="3" description="Description for 3" />

The format of the data and values are irrelevant for the purpose of this — they can be any literal value. The code you’re writing has to go through all the <item> elements and create a corresponding object with 2 properties : name and description (so for each <item> you create a new object).

There are of course numerous ways of doing this — JAXB, writing your own SAX parser, XPath etc. SAX parser to be honest ensures a fast parsing of the data and allows you the management of memory to a certain degree (e.g. you can decide to keep/drop the data based on various factors), however, if you’re not constrained so much by the speed of the parsing (which was the case with the code I mentioned), using XPath to extract the item nodes is good enough.

So you can prepare an XPathExpression in a manner similar to this:

XPathFactory xfactory = XPathFactory.newInstance();
XPath xpath = xfactory.newXPath();
XPathExpression xpathItem = xpath.compile("/data/item");

Then simply use the generated expression to retrieve all the nodes matching it:

NodeList nodes = (NodeList)xpathItem.evaluate(doc, XPathConstants.NODESET);

This return a list of Node instances (elements in fact based on the above XML structure) and then you can iterate through each one of them and create a new object with the name and description properties from the XML element. Since I do like using this approach (it’s done in very few lines as you can see) and the speed of the parsing (even for a document containing 1,000’s of elements) is acceptable, I will keep this constant throughout the code I’m including here. The only difference is in the way we extract the attributes for each element and create the objects based on those.

So if you look at the attached code, the performText() method parses the XML file only once in the manner shown above and then iterates through the list of nodes and for each node creates a new instance of Item based on the attributes of the current element. Extraction of the attributes has been implemented in 2 ways:

  • by simply using DOM methods: once we have an Element, we can simply call getAttribute(attributeName) and retrieve the attribute value as a String;
  • by using XPath expressions: we’re creating 2 XPath expressions as shown below and then evaluate them against the current Element:
XPathExpression xpathAttrName = xpath.compile("@name");
XPathExpression xpathAttrDesc = xpath.compile("@description");
String name = (String)xpathAttrName.evaluate(element, XPathConstants.STRING);
String desc = (String)xpathAttrDesc.evaluate(element, XPathConstants.STRING);

(We are in fact traversing the node about 10 times using each method and then printing out the timings (in nanoseconds) — so we can eliminate the initial hit (due to class loading) and things like GC interfering with the execution.)

Now you will notice that in terms of lines of code there isn’t much of a difference — so based on that alone there’s no reason why we should go for one or the other. Since we’ve used XPath to extract the nodes though it seems somewhat natural to use XPath for retrieving the attributes values (at least it did to me in the old code I was referring to 😉 ).

For the purpose of testing this, I’ve written a quick bash script to generate an XML file — it simply has a running counter and generates an <item&;gt tag at each iteration. Simply run it and pipe the output to a file to generate the XML file:

# - generates a simple XML file for our test
echo ""
for i in {1..100}; do
    echo ""
echo ""

e.g. > file.xml — then use that file name as a parameter to our XPathTest class.

Running the above test on an XML file with 100 elements, 10 times for each test (one using DOM — Processor 0 — and one using XPath — Processor 1) renders the following results:

Processor 0

Processor 1

Now to make it easier to analyze this data, I’ve put it in an Excel spreadsheet — and looking at the 90% percentile (which eliminates spikes) we’re getting the following:

  • DOM: ~0.5 ms
  • XPath: ~55 ms

Which means an order of magnitude of nearly 100! So going the XPath way means every single “processing” of an element takes 100 times more! (Bear in mind that this processing involves simply traversing an in-memory DOM — there is no disk access, no database access etc in either of the cases!)
Now even if your program is not time-critical, by simply taking a (lazy) approach like this means you’re slowing down your code about 100 times! (I’m only gonna say this: 3 minutes or half an hour to complete?) And that extra time is not actually spent in waiting for resources (disk, network etc) but it is actually spend in execution cycles! So even if you are running your program as a batch once a week or whatever the schedule, it means that during the execution of this you will be stepping on other processes’ toes, if those processes need CPU too.

Of course, if your XML file has a max of 5 lines or so, this is futile to a certain extent, as you would have gained a few miliseconds, so no major achievement there. But what if it’s not the case and you’re dealing with slightly larger files, or maybe you are dealing with small files but run this on a tight schedule (every 5 minutes perhaps?) in a farm of servers — you are wasting every 5 minutes valuable CPU cycles! And all it takes is just 2 simple changes — sounds crazy, but well worth it!

Attached is the Java code and the shell script used for this.