Bug 13233 – Need to implement an optimizing XPath evaluator

• Component: XML
• Status: NEW

[Alexey Proskuryakov]

There are many opportunities for XPath optimization that we are still missing.

Some work is still needed on micro-optimizing our implementation. For example, it's wasteful to implement a node-set as Vector<RefPtr>, as nodes won't go away during evaluation anyway (except for lazily created Attr nodes).

Many ideas for higher-level optimizations can be apparently borrowed from Mozilla, see <https://bugzilla.mozilla.org/show_bug.cgi?id=208172> and <http://www.fiveanddime.net/firefox-1.5-source/mozilla/extensions/transformiix/docs/optimized-xpath.html.html>.

[Alexey Proskuryakov]

Created attachment 13893 [details]
Romeo&Juliet performance test

Some XPath performance tests:

http://ejohn.org/apps/classname/xpath.html
http://www.andrewdupont.net/test/xpath/
http://www.asciiarmor.com/2004/11/13/java-xpath-10-engine-comparison-performance/

A simple JavaScript translation of the last one is attached; it could use some more attention, though.

[Sasha Firsov]

At the moment the WebKit XPath evaluation is outsider among of FF,IE,Opera. 
The performance is so bad, that exclude WebKit from Web 2.0 heavy service-oriented apps. Test for 100K "/root/el" in <root><el>123</el>...</root> takes several minutes in comparison to few seconds in other browsers. Accounting the browser freeze app looks failed. 
Accounting WekKit market share on such kind of apps, ways around will not be made and putting WebKit in row of unsupported browsers.

[Alexey Proskuryakov]

Realistic tests would go a long way towards improving WebKit XPath support. Iterating a single dimensional array (If I understood you correctly, that's your example) is hardly a task for XPath. Nor would be a topic for this bug, as it's likely a target for implementation micro-optimizations, not for an optimizing evaluator.

[Sasha Firsov]

Evaluator optimizing is the subject for Iterating a single dimensional array.
And it is a task for XPath evaluator optimization. Most of apps which utilizing web services working with flat array-like data XML. Picture galleries, search engines are just simple samples. You could use their JSON incarnation, but XPath is way more usable as filters over same data.

XPath optimisation is not so critical for UI DOM navigation, where numbers are sufficient(still few times slower of other browsers).

[Alexey Proskuryakov]

Created attachment 30812 [details]
first step

Implement some optimizations:
- avoid building full NodeSets to evaluate predicates, if possible;
- optimize "//" if there are no context sensitive predicates.

[Alexey Proskuryakov]

Created attachment 30817 [details]
Don't needlessly sort location path results

[Darin Adler]

Comment on attachment 30812 [details]
first step

> +            void addSubExpression(Expression* expr)
> +            {
> +                m_subExpressions.append(expr);
> +                m_isContextNodeSensitive = m_isContextNodeSensitive || expr->m_isContextNodeSensitive;
> +                m_isContextPositionSensitive = m_isContextPositionSensitive || expr->m_isContextPositionSensitive;
> +                m_isContextSizeSensitive = m_isContextSizeSensitive || expr->m_isContextSizeSensitive;
> +            }

How about using |= here?

r=me

[Darin Adler]

Comment on attachment 30817 [details]
Don't needlessly sort location path results

> +            NodeSet(const NodeSet& other) : m_isSorted(other.m_isSorted), m_subtreesAreDisjoint(other.m_subtreesAreDisjoint), m_nodes(other.m_nodes) { }
> +            NodeSet& operator=(const NodeSet& other) { m_isSorted = other.m_isSorted; m_subtreesAreDisjoint = other.m_subtreesAreDisjoint; m_nodes = other.m_nodes; return *this; }

You should instead delete these explicit definitions. The compiler defaults would work fine.

r=me

[Alexey Proskuryakov]

Comment on attachment 30812 [details]
first step

Committed revision 44306, clearing review flag.

> How about using |= here?

Not sure about that - it feels strange to use a binary operation with booleans.

[Darin Adler]

(In reply to comment #9)
> Not sure about that - it feels strange to use a binary operation with booleans.

I don't know why. The logical operations and binary operations both do the same thing with booleans, except for their short-circuiting properties. The binary operations aren't "raw bits" operations or anything like that.

[Alexey Proskuryakov]

Comment on attachment 30817 [details]
Don't needlessly sort location path results

Committed revision 44307, clearing review flag.

> You should instead delete these explicit definitions. The compiler defaults
> would work fine.

Done.

> I don't know why. The logical operations and binary operations both do the same
> thing with booleans, except for their short-circuiting properties.

It's not so good for BOOLs and Booleans, but OK, changed it when landing this patch.