929950 - PCToLineNumber is slow

Status: NEW

(Core :: JavaScript Engine, defect, P3)

Description

[Jan de Mooij [:jandem]]

Peacekeeper has a bunch of jQuery tests that call querySelectorAll with an invalid string. This call then throws an exception and the DOM code calls JS::DescribeStack which calls PCToLineNumber for each frame.

PCToLineNumber is slow because it has to loop over the source notes to determine the line number. We should either store this info differently and use binary search or add a small cache.

According to Instruments, the domJQueryBasicFilters test in bug 922048 spends about 43 ms (~2%) in PCToLineNumber.

Comment 1

[Boris Zbarsky [:bzbarsky]]

Hmm.  Throwing an exception is generally considered a slow path that we don't optimize much.  :(  If peacekeeper is testing its performance, or more importantly if jQuery depends on its performance, we may want to reconsider that decision...

Comment 2

[Jan de Mooij [:jandem]]

(In reply to On vacation Oct 12 - Oct 27 from comment #1)
> Hmm.  Throwing an exception is generally considered a slow path that we
> don't optimize much.  :(

Do we really need the line numbers for all frames when we throw an exception? It's not clear to me what calls Exception::GetLocation and similar methods, but if we don't need line numbers in most cases we could store the pc or offset and call into the JS engine to get the line number the first time it's requested for a frame...

Comment 3

[Chris Peterson [:cpeterson]]

(In reply to Jan de Mooij [:jandem] from comment #0)
> Peacekeeper has a bunch of jQuery tests that call querySelectorAll with an
> invalid string. This call then throws an exception and the DOM code calls
> JS::DescribeStack which calls PCToLineNumber for each frame.

Is this a Peacekeeper bug? Or is the test really trying to measuring query error handling?

Comment 4

[André Bargull [:anba]]

(In reply to Chris Peterson (:cpeterson) from comment #3)
> Is this a Peacekeeper bug? Or is the test really trying to measuring query
> error handling?

There is no error in Chrome. All six queries return results when tested from the Chrome Developer Toolbar.

Comment 5

[Boris Zbarsky [:bzbarsky]]

> Or is the test really trying to measuring query error handling?

It's not error handling.  It's just that the way jQuery implements its extensions to selectors is by trying querySelector and if that throws an invalid selector error falling back on its own parsing.

Specifically, of these tests:

    $(".frontPageNewsItem:first");
    $(".frontPageNewsItem:last");
    $(".frontPageNewsItem div:not(.title)");
    $(".frontPageNewsItem:even");
    $(".frontPageNewsItem:eq(3)");
    $("body *:header");

Only the third one is a valid CSS selector.  All the rest are jQuery extensions.

Real-life code using those jQuery extensions would see the exceptions we see in this case...

I really wish querySelector(All) had used some other way to indicate an invalid selector (e.g. a false return value or something).

> All six queries return results when tested from the Chrome Developer Toolbar.

No, they don't.  Output from Chrome (32 dev, in case that matters):

  document.querySelector(":first")
  SyntaxError: Failed to execute query: ':first' is not a valid selector.

  $(".frontPageNewsItem:first")
  SyntaxError: Failed to execute query: '.frontPageNewsItem:first' is not a valid
  selector.

Comment 6

[Boris Zbarsky [:bzbarsky]]

But note that if you do the $(".frontPageNewsItem:first") thing on a page that has jQuery loaded, in Chrome, then of course it's calling jQuery code, not the devtools' built-in $() and then you get the jQuery behavior.  Same thing in Firefox.  document.querySelector(":first") will still throw nicely in Chrome even on such a page, of course.  Just like Firefox.

Comment 7

[André Bargull [:anba]]

(In reply to On vacation Oct 12 - Oct 27 from comment #5)
> > All six queries return results when tested from the Chrome Developer Toolbar.
> 
> No, they don't.  Output from Chrome (32 dev, in case that matters):

Just came to the same conclusion. Sorry for the noise.

Comment 8

[Luke Wagner [:luke]]

Boris, you said we spend about 2% of time in PCToLineNumber.  What % is spent anywhere under JSStackFrame::CreateStack?  That whole process seems full of slowness and allocation.

One idea is: what if we made a fast version of JS::DescribeStack that copies the minimal amount of information about the stack and then we change DOM exceptions to delay creating a proper callstack until someone actually asks for it; when they do, that's when we could do the PCToLineNumber and string munging etc.  Basically, this would be lazy callstacks.

More general question: for normal jQuery usage, would you estimate JSStackFrame::CreateStack is a significant % of overall time?

Comment 9

[Luke Wagner [:luke]]

Oops, I meant to ask Jan, since he filed.

Comment 10

[Boris Zbarsky [:bzbarsky]]

> What % is spent anywhere under JSStackFrame::CreateStack?

Note that there's a bunch of DOM-side work involved in throwing an exception too, which we should consider optimizing.  Need separate bugs on that.

Comment 11

[Jan de Mooij [:jandem]]

(In reply to Luke Wagner [:luke] from comment #8)
> Boris, you said we spend about 2% of time in PCToLineNumber.  What % is
> spent anywhere under JSStackFrame::CreateStack?  That whole process seems
> full of slowness and allocation.

Yup, it's like 6% under CreateStack. Of that, 73% is under DescribeStack. About half of that is PCToLineNumber, the other half is ScriptFrameIter and Vector methods. But also various malloc/free calls.

> One idea is: what if we made a fast version of JS::DescribeStack that copies
> the minimal amount of information about the stack and then we change DOM
> exceptions to delay creating a proper callstack until someone actually asks
> for it; when they do, that's when we could do the PCToLineNumber and string
> munging etc.  Basically, this would be lazy callstacks.

Yeah, I'd like to try this for PCToLineNumber first (see comment 2). There's also a bunch of malloc calls we can remove I think, will file bugs on that next week.

> More general question: for normal jQuery usage, would you estimate
> JSStackFrame::CreateStack is a significant % of overall time?

I doubt it, only if you call querySelector(All) a lot..

Comment 12

[Jan de Mooij [:jandem]]

Filed bug 932837 for optimizing JSStackFrame::CreateStack.

Comment 13

[Boris Zbarsky [:bzbarsky]]

For what it's worth, but 932837 basically implements comment 8 paragraph 2.

At that point, the actual DescribeStack call is where most of the work is.  And we're not even doing PCToLineNumber at that point!

Comment 14

[Jan de Mooij [:jandem]]

This also affects the profiler.

Bug 1245213 is a pathological case where we spend > 96% of the time in PCToLineNumber, because the page is loading a 15.2 MB JS file (no functions, PCToLineNumber is called with pc offset 1629977).

There must be some way to store the lineno/column info efficiently and allow us to use a binary search. I'll probably get back to this in the coming weeks/months, if nobody beats me to it, because it seems pretty important.

Comment 15

[Firefox Bug Husbandry Bot]

https://wiki.mozilla.org/Bug_Triage/Projects/Bug_Handling/Bug_Husbandry#Move_fix-optionals