From: Sean Russell <ser@...>
Date: 2002-06-01T08:27:12+09:00
Subject: [REXML] Looking for XPath testers

Hi!

I've done some preliminary tests on a new implementation of XPath, and the 
results are encouraging.  Here are some times for a simple '//item' search.

Fast XPath preindexed :  0.021261
Fast XPath total      :  0.11213
Old XPath             :  1.460022

The new mechanism doesn't currently support much of the XPath spec, but even 
after everything is implemented, I don't expect it to slow down by an order 
of magnitude.  Even in the worst case (where you have to reindex every 
search), this should be faster than the current XPath implementation.  In 
most cases, where the document structure isn't changing, you'll only need 
to index once, and searches will be blindingly fast.  In addition, this new 
mechanism should bring XPaths to the streaming APIs (wahoo!).

There very well could be some really fundamental flaw in the algorithm which 
will mean that it won't be able to support the full XPath spec, but if 
there is, I can't see it yet.  In the meantime, I'm going to forge on 
ahead, because the benefits are obviously worth the risk.

What I'd like is some people who are willing to test this new mechansm as it 
evolves and give me good feedback on timings and accuracy of the matches.  
This will be a labor of love, folks... the number of XPath directives 
supported are very small, so if you want to help, be aware that you're 
working with limited functionality.  I'd rather get volunteers than throw 
this out in the wild because it will be difficult enough to go forward on 
this without having to answer a bunch of emails about how, no, FastXPath 
doesn't support that feature yet, please use the XPath class, blah, blah, 
blah.

If you're interested, read on, and then email me when you're done.

The old mechanism traversed the tree, matching path elements as it went.  
This was fairly slow, but it was relatively easy ("relatively", here, 
really means what it says -- it was by no means 'easy') to get the matches 
correct.

The new mechanism throws that all out, and builds up an index of a document.  
This only has to be done once, or every time the document changes.  My 
tests show that building this index every time is still faster than the old 
XPath search method.  Once you have the index, subsequent searches are 
extremely fast, given some caveats.  The new mechanism takes a path and 
turns it into an absolute path regular expression based on a series of 
rules.  A search then is just matching the regular expression against the 
index, and returning all of the results.

The real bitch will be that translation.  It won't be easy to translate most 
of the possible XPath grammer into regular expressions, and it will be 
plainly impossible to do some constructions.  Predicates, for example, will 
have to be dealt with on a node-by-node basis.  XPaths that are 
predominantly heavy with predicates will probably not be much faster than 
the old method, but it will almost certainly not be slower.

Right now the only path elements supported are:

        text()
        processing-instruction()
        comment()
        /
        //
        *
        NCNAME

So, you can search for '/a/b/c', '/', '//foo', '/x//y', '/a//c/text()', and 
so on.  Namespaces are supported, but only on the default namespaces.  IE,

        d = Document.new("<a x='foo'><b/><x:b/></a>")
        xpath.match( d, '//x:b' )

will only return the second 'b' element, as it should, but there is as yet 
no mechanism for remapping the namespaces.

There are bound to be bugs, but if you're willing to help, we can probably 
hammer this out in short order.

Thanks!

-- 
 |..  got brains?
<|>   
/|\   
/|    
 |