jaxen
  1. jaxen
  2. JAXEN-31

if jaxen stopped using lists it would be 37x faster

    Details

    • Type: Improvement Improvement
    • Status: Open Open
    • Priority: Major Major
    • Resolution: Unresolved
    • Affects Version/s: 1.0
    • Fix Version/s: 2.0
    • Component/s: None
    • Labels:
      None
    • Number of attachments :
      6

      Description

      The short story - I've rewritten jaxen to use a nodeset abstraction instead of a list to accumulate results. With the unit tests at nearly 100%, the performance test on dom4j runs in ~200ms on my 1GHz powerbook, compared to ~7400ms for the nightly jaxen build. The failing unit tests are for paths not covered in the performance test.

      The long story - I wrote an implementation of the draft ISO Schematron spec on top of Jaxen, instead of the more usual XSLT. The schematron spec is designed so this can be done, mainly for performance reasons. Once I had enough working I was able to compare jaxen with xalan on the 'screamatron' torture test, which is using schematron to validate the schematron 1.5 spec. I was suprised to find that jaxen was about 2x /slower/ than xalan, and marginally slower with a jdom navigator than a dom4j navigator. Looking at why it was so slow, it became clear that the problem was that throughout jaxen it's building lists of intermediate results to filter down, instead of generating the 'next' result on demand. There's comments about this in several places in the code, but the list thing is so ingrained it needs more than a little refactoring to fix.

      I decided to have a go. This change produces apis incompatible with previous versions of jaxen, so this will be a lump of code not a wee patch. I've basically cloned jaxen to 'org.jaxen2' to work on it. I'm nearly done with the changes, failing tests for the non-xpath extension functions which I havent implemented yet, patterns (not touched at all yet), and a couple of minor bugs.

      I'll post the code on jira once I'm done, but here's the gist of the changes I made:

      • Introduce a Nodeset abstraction instead of a list...
        public interface extends Iterator {
        Object current();
        int position();
        // use of last() replaces the internal iterator with an iterator over a list caching results.
        // it's basically a fallback on what jaxen used to do.
        int last();
        }
        the reason for this is obvious, eg you can just test 'hasNext()' to check the boolean value of a nodeset.
      • change the signature of Expr to allow the selection of a fast code path
        public interface Expr {
        // these require context because of variable/function refs only. see later.
        boolean isBoolean(Context ctx);
        boolean isNumber(Context ctx);
        boolean isString(Context ctx);
        boolean isNodeset(Context ctx);
        boolean booleanValue(Context ctx);
        double numberValue(Context ctx);
        String stringValue(Context ctx);
        Nodeset nodesetValue(Context ctx);
        // etc
        }
        this is really for my own sanity as there's so much code to maintain. Throughout jaxen, everything is untyped, so its fairly easy to (eg) pass a nodeSet when you meant to pass a node; there's instanceof checks, == null checks, and casts everywhere to deal with this. Once you put everything behind an interface like the one above, making objects responsible for their own casts, a lot of the code is simplified, eg addition is just expr1.numberValue(ctx) + expr2.numberValue(ctx). All but a couple of classes inherit from abstract base classes that implement all but one of those methods (eg StringExprBase leaves stringValue() abstract.)

      Variable/Function refs don't have a type without context in my version, and like Jaxen I look up functions, variables every time. This isn't smart - in xpath we can resolve all variable, function refs beforehand, and get faster code as a result. I'll probably change things so I have 'bound' and 'unbound' exprs, add 'BoundExpr bind(VariableContext,FunctionContext)'. I'll still need to pass these as members of Context to support the 'evaluate' extension function though.

      Another approach to the same concern that I didn't try is to pass in a typed context, eg 'StringContext', 'NodesetContext', etc (think of this as allowing things like perl's 'wantarray()'. That approach would make it easier to expand the number of supported types (eg for xpath2) in future, I'll try it once the tests pass.

      • moved all the functions to a single utility class
        public class Functions {
        String substring(String s, double start, double end);
        // etc
        }
        this makes it easier to unit test the xpath functions, since they are mostly context-independent. Functions that need a navigator get it passed as the first arg, functions that optionally use the context node instead of an argument have that function added as a method of Context. Incidentally I changed some of the unit tests to get mine to pass - in particular I changed the substring() tests back to match the spec (they don't currently).

      No function in my version returns null. (compare to eg the name, namespaceuri functions of Navigator). The xpath spec uses "" or an empty nodeset throughout, so do I, this gets rid of a lot of == null checks.

      Some of the bugs against the current version of jaxen are fixed by this code - eg the use of double throughout allows gt/lt comparisons of longs (bug jaxen-28), + both of the bugs I filed previously.

      I'd estimate I can finish this in the next week.

        Activity

        Hide
        Brian Ewins added a comment -

        Ok, I have gone one step further and turned off the sort whenever the location path only uses the parent, self, or child axes (a very common case). The theory here is that given a list of nodes X in document order, then X/parent::, X/self::, and X/child::* are also in document order; that a whole location path consisting of these axes is also ordered follows by induction. Other axes do not support this assertion, and removing the sort for them would trigger JAXEN-55. Do you agree with this analysis Elliotte?

        All tests still pass. The performance gains are back towards the title of this bug - XOMPerformance goes from 4.9s to 97ms on my machine. Its a shame I can't get this simple trick to work for descendant-or-self but this is quite a big win as it stands.

        Show
        Brian Ewins added a comment - Ok, I have gone one step further and turned off the sort whenever the location path only uses the parent, self, or child axes (a very common case). The theory here is that given a list of nodes X in document order, then X/parent:: , X/self:: , and X/child::* are also in document order; that a whole location path consisting of these axes is also ordered follows by induction. Other axes do not support this assertion, and removing the sort for them would trigger JAXEN-55 . Do you agree with this analysis Elliotte? All tests still pass. The performance gains are back towards the title of this bug - XOMPerformance goes from 4.9s to 97ms on my machine. Its a shame I can't get this simple trick to work for descendant-or-self but this is quite a big win as it stands.
        Hide
        Aleksander Adamowski added a comment -

        BTW, I've already started to adapt jBPM-BPEL to take advantage of Jaxen LazyLists:

        https://jira.jboss.org/jira/browse/BPEL-313

        Show
        Aleksander Adamowski added a comment - BTW, I've already started to adapt jBPM-BPEL to take advantage of Jaxen LazyLists: https://jira.jboss.org/jira/browse/BPEL-313
        Hide
        James Abley added a comment -

        Any more news on what's going on with this patch? Is it deemed worth incorporating into the project proper?

        I have a version of Brian Ewins' patch that I merged against trunk r1362. Performance for selectSingleNode seems a lot better, at least for XOMPerformance and JDOMPerformance. I haven't tested any further since I'm not really familiar with the codebase.

        Show
        James Abley added a comment - Any more news on what's going on with this patch? Is it deemed worth incorporating into the project proper? I have a version of Brian Ewins' patch that I merged against trunk r1362. Performance for selectSingleNode seems a lot better, at least for XOMPerformance and JDOMPerformance. I haven't tested any further since I'm not really familiar with the codebase.
        Hide
        Elliotte Rusty Harold added a comment -

        Brian, do you want me to apply the latest version of this patch and check it in (assuming the tests pass)? Or have you been able to restore your credentials?

        Show
        Elliotte Rusty Harold added a comment - Brian, do you want me to apply the latest version of this patch and check it in (assuming the tests pass)? Or have you been able to restore your credentials?
        Hide
        Paul Wagland added a comment -

        Is there any further news on this patch? From what I can read above, the tests now all pass, and it appears that the performance improvement is quite significant.

        Show
        Paul Wagland added a comment - Is there any further news on this patch? From what I can read above, the tests now all pass, and it appears that the performance improvement is quite significant.

          People

          • Assignee:
            Unassigned
            Reporter:
            Brian Ewins
          • Votes:
            5 Vote for this issue
            Watchers:
            5 Start watching this issue

            Dates

            • Created:
              Updated:

              Time Tracking

              Estimated:
              Original Estimate - 1 week
              1w
              Remaining:
              Remaining Estimate - 1 week
              1w
              Logged:
              Time Spent - Not Specified
              Not Specified