520621 - XPath is much slower than Safari

Status: NEW

(Core :: DOM: Core & HTML, defect, P5)

Description

[Jeff Muizelaar [:jrmuizel]]

Ikea uses some XPath in a mouse over handler via an older version of prototype.

When you scroll the page this handler gets called and since it takes so long, scrolling becomes very slow.

The linked to URL has a version of this page along with a "Time" button that performs the operation.

In Safari/Chrome the operation takes about 16ms, in Firefox we take about 120ms which is long enough to cause a noticeable pause during scrolling.

Comment 1

[Olli Pettay [:smaug][[e-mail]]]

Based on a Shark profile, most of the time is spent in XPath engine.

Comment 2

[Jeff Muizelaar [:jrmuizel]]

I should also mention a couple more things:

First, the jist of what is slow here is (doSelectTimeTest):

                $$('a[rel]').each(function(element) {
                                var img = element.down("img");
                                count += 1;
                                });

In particular, the element.down() call is the one that takes 100+ ms

Second, Opera and IE are also not very good at this case.

Comment 3

[Olli Pettay [:smaug][[e-mail]]]

There are several problems.
- txStack is inefficient, because pop is used all the time so that the stack
  gets empty and that causes free calls, and next push will malloc.
- Recycler truncates strings, which will then get some value;
  way too much freeing/mallocing. Might be able to save some time if
  values were just assigned without truncating the old value first.
- Would it be possible to make LocationStep::fromDescendants iterative, not
  recursive? That might help in this case a bit.

Comment 4

[Olli Pettay [:smaug][[e-mail]]]

I believe bug 474369 made this significantly worse.
nsVoidArray does less mallocing/freeing when used the way txStack does.

Comment 5

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

(In reply to comment #3)
> There are several problems.
> - txStack is inefficient, because pop is used all the time so that the stack
>   gets empty and that causes free calls, and next push will malloc.

Yup, should do that.

> - Recycler truncates strings, which will then get some value;
>   way too much freeing/mallocing. Might be able to save some time if
>   values were just assigned without truncating the old value first.

Yup, should do that.

> - Would it be possible to make LocationStep::fromDescendants iterative, not
>   recursive? That might help in this case a bit.

Why would that be more performant? I do bet we can avoid a fair number of virtual calls while iterating over the tree though by making txXPathTreeWalker use nsINode::ChildIterator

Comment 6

[Olli Pettay [:smaug][[e-mail]]]

Attachment: not properly tested patch, nsVoidArray+string usage opts

Comment 7

[Olli Pettay [:smaug][[e-mail]]]

At least the patch reduces freeing/mallocing quite a bit.

Comment 8

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

(In reply to comment #4)
> I believe bug 474369 made this significantly worse.
> nsVoidArray does less mallocing/freeing when used the way txStack does.

I filed bug 520671 on this

Comment 9

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Would it make sense to measure typical stack sizes and use nsAutoTArray?

Comment 10

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

That probably would be a good idea, if I recall correctly we'll generally place fairly few objects on these stacks.

Though I really think we need to fix nsTArray as well.

Comment 11

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Changing nsTArray's behaviour is a tough call. If an array stays empty for a long time, then you want to have freed the buffer, otherwise you don't. nsTArray can't know this ahead of time on its own.

We could use nsExpirationTracker or something to free buffers after a delay but maybe that's overkill.

Comment 12

[Jeff Muizelaar [:jrmuizel]]

For fun, I ported the code to use querySelectorAll() and while we are much faster we still get beaten by Safari a fair amount:

http://people.mozilla.com/~jmuizelaar/p/xpath/query-selector/10609.html

Firefox: 43ms
Safari: 12ms

Comment 13

[Olli Pettay [:smaug][[e-mail]]]

Attachment: nsAutoTArray

naAutoTArray helps here

Comment 14

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Comment on attachment 404791 [details] [diff] [review]
nsAutoTArray

>diff --git a/content/xslt/src/base/txStack.h b/content/xslt/src/base/txStack.h
>--- a/content/xslt/src/base/txStack.h
>+++ b/content/xslt/src/base/txStack.h
>@@ -36,17 +36,17 @@
>  *
>  * ***** END LICENSE BLOCK ***** */
> 
> #ifndef txStack_h___
> #define txStack_h___
> 
> #include "nsTArray.h"
> 
>-class txStack : private nsTArray<void*>
>+class txStack : private nsAutoTArray<void*, 8>

This definitely makes it less likely that the badness will happen, but I'd really like to fix nsTArray. But that's bug 520671.

>diff --git a/content/xslt/src/xpath/txCoreFunctionCall.cpp b/content/xslt/src/xpath/txCoreFunctionCall.cpp

>-                    StringResult* strRes = nsnull;
>-                    rv = aContext->recycler()->getStringResult(&strRes);
>-                    NS_ENSURE_SUCCESS(rv, rv);
>-
>-                    *aResult = strRes;
>-                    txXPathNodeUtils::getLocalName(node, strRes->mValue);
>-
>-                    return NS_OK;
>+                    nsAutoString localName;
>+                    txXPathNodeUtils::getLocalName(node, localName);
>+                    return aContext->recycler()->getStringResult(localName,
>+                                                                 aResult);

This isn't very optimal either since we'll end up having to copy the data in the string. Is there no way to empty without making it drop its buffer? Could we add a function to nsTSubstring?

Comment 15

[Boris Zbarsky [:bzbarsky]]

> Is there no way to empty without making it drop its buffer?

Not for a non-auto string.  We should consider adding something, especially if we're sure we'll free the string expeditiously (say before evaluate() returns).

Comment 16

[Boris Zbarsky [:bzbarsky]]

Jeff, I can't tell exactly what the times in comment 12 are measuring; which of the js files linked from that page did you modify to make those measurements?

Comment 17

[Jeff Muizelaar [:jrmuizel]]

(In reply to comment #16)
> Jeff, I can't tell exactly what the times in comment 12 are measuring; which of
> the js files linked from that page did you modify to make those measurements?

The times are from running the following js added to 10609.html:

	function doSelectTimeTest() {
		var start = Date.now();
		var count = 0;
		$$('a[rel]').each(function(element) {
				var img = element.down("img");
				count += 1;
				});
		var end = Date.now();
		alert("selecting " + count + " took " + (end - start) + "ms");

	}

To port prototype to querySelectorAll I made the following change:

   findElements: function(root) {
     root = root || document;
+    var e = this.expression, results; 
+    if (root != document) {
+	    var oldId = root.id, id = $(root).identify();
+	    id = id.replace(/([\.:])/g, "\\$1");
+	    e = "#" + id + " " + e;
+    }
+    results = $A(root.querySelectorAll(e)).map(Element.extend);
+    root.id = oldId;
+
+    return results;
+
+
     if (this.xpath) return document._getElementsByXPath(this.xpath, root);
     return this.matcher(root);
   },

Comment 18

[Boris Zbarsky [:bzbarsky]]

Ah, I see.  I'd missed the "test" button.  Just profiled that; the querySelectorAll call only takes up 30% of the time there.  Want to file a jseng bug on the rest?

Comment 19

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Comment on attachment 404791 [details] [diff] [review]
nsAutoTArray

I think the nsAutoTArray change here is ok, but I don't like the string changes. We should fix the string API to allow clearing a string without freeing its buffer.

Comment 20

[Firefox Bug Husbandry Bot]

https://bugzilla.mozilla.org/show_bug.cgi?id=1472046

Move all DOM bugs that haven’t been updated in more than 3 years and has no one currently assigned to P5.

If you have questions, please contact :mdaly.