934995 - Speed up querySelectorAll by doing less allocations

Status: RESOLVED FIXED

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

Description

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

Attachment: patch

I was wrong about nsAutoTArray. I can see some improvement if we do allocation
just once (in common cases).

gcc doesn't inline the template function without MOZ_ALWAYS_INLINE, yet in this case
inline makes lots of sense.

nsAutoTArray is unfortunately there even for the onlyFirstMatch case, but shouldn't 
be too bad, based on assembly.

https://tbpl.mozilla.org/?tree=Try&rev=1d6555cc2413

Comment 1

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 827393 [details] [diff] [review]
patch

We don't need the nsAutoTArray in the onlyFirstMatch case, do we?  What we should do instead is declare an nsAutoTArray in QuerySelectorAll and pass _that_ as the third arg to FindMatchingElements, so all the appending automatically happens to the nsAutoTArray in that case.  And then the querySelector case won't be affected at all.

As far as then putting the elements into the nsContentList, I'd rather expose something that takes an nsTArray and SwapElements() with it; this would be very fast if we had to heap-allocate our auto array, and much like your manual SetCapacity and append loop otherwise, right?

Comment 2

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

We can't do SwapElements since we want to collect elements as Element* but contentlist keeps them
alive as nsCOMPtr<Element>.

But I'll make that change to pass nsAutoTArray as param.

Comment 3

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

Though, that approach is slower in case there are id selectors and also in case someone passes
invalid selecter (jquery for example).

Need to do some template magic

Comment 4

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

Attachment: v2, more template magic

Compiler seems to optimize out that dummy for loop in case of
QuerySelector.

Comment 5

[Boris Zbarsky [:bzbarsky]]

> Though, that approach is slower in case there are id selectors 

Hmm.  Why?

> and also in case someone passes invalid selecter

Because in that case we do the auto array ctor/dtor even in cases when we're going to throw an exception, right?  We can address this with using a wrapper around a Maybe<nsAutoTArray> as the class to put stuff into.  That seems like it would be clearer than loops that we depend on optimizing away and AppendElement calls in both branches of an if.  

But I'd like to understand why this has any particular extra cost in the id case, any more than in any other case...

Comment 6

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

With id case I mean the code in FindMatchingElements which deals with id selectors.
Usually those should return zero or one results.

If we create nsAutoTArray in nsINode::QuerySelectorAll, we create and destroy it always, 
even if FindMatchingElements throws or returns just one result for the id selector.

Comment 7

[Boris Zbarsky [:bzbarsky]]

> Usually those should return zero or one results.

Ah, so we end up doing just the one append and one allocation and all the auto array stuff is pure overhead, ok.

So one option is to use a Maybe<nsAutoTArray>, only init it after the exception/id cases, and use a different API (AppendElementBatched or something?) for appending things when we want them appended to the AutoTArray in the AutoTArray case.  Does that make sense?

Comment 8

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

How is that better. We'd need to have
if (!onlyFirstMatch)
  maybeThing.construct();

That isn't really much different to
ElementHolder foo; (which is just a container for one null value.)

The if (onlyFirstMatch) { is already there in the loop. Not sure how the AppendElement in it makes it worse. The end of the method is very much no-op in onlyFirstMatch case and seems to be optimized out in onlyFirstMatch case.

Maybe<> isn't totally free either.

But I don't know... I've written this in few different ways and nothing is super pretty, but at least atm
I prefer the approach the patch has.

Comment 9

[Boris Zbarsky [:bzbarsky]]

> We'd need to have
>if (!onlyFirstMatch)
>  maybeThing.construct();

Nah, you'd construct it always but have the thing that the onlyFirstMatch case passes in have a no-op construct() method.

>Maybe<> isn't totally free either.

True...

>and seems to be optimized out in onlyFirstMatch case.

I'm just slightly worried about how much we can rely on that.

Would it help if we were more explicit about doing all that loop stuff if (!onlyFirstMatch)?  And in that case, could we even use a Collector class that has no methods on it, to make sure that code is not even being compiled in the onlyFirstMatch case?  I wonder whether that would compile....

Comment 10

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

Attachment: v3

The thing doesn't compile if SetCapacity etc aren't defined in the ElementHolder
(even if 'if (!onlyFirstMatch)' is used).

if (len) (where len is always 0) should be pretty strong hint to compiler to
optimize that out, and using length and not onlyFirstMatch let's us optimize out
the case there are no results and onlyFirstMatch is false.

Comment 11

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 828224 [details] [diff] [review]
v3

>+  void SetCapacity(uint32_t aCapacity) {}
>+  Element* ElementAt(uint32_t aIndex) { return nullptr; }

Maybe assert notreached for those?

r=me

Comment 12

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

Attachment: added one MOZ_CRASH

Comment 13

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

https://hg.mozilla.org/integration/mozilla-inbound/rev/1eeb08e557c2

Comment 14

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/1eeb08e557c2