Last Comment Bug 756864 - avoid quadratic cost of JS_GetFramePC in XPCJSStackFrame::CreateStack when the stack is very deep
: avoid quadratic cost of JS_GetFramePC in XPCJSStackFrame::CreateStack when th...
Status: RESOLVED FIXED
[js:p3]
: perf, regression
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: Trunk
: x86 Windows 7
: -- normal (vote)
: mozilla16
Assigned To: Luke Wagner [:luke]
:
Mentors:
Depends on:
Blocks: 596460 602129
  Show dependency treegraph
 
Reported: 2012-05-20 06:59 PDT by Alice0775 White
Modified: 2012-06-24 20:08 PDT (History)
5 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
Zip file, Semi-reduced html (316.33 KB, application/x-zip)
2012-06-19 20:01 PDT, Alice0775 White
no flags Details
cap quadratic behavior of JS_GetFramePC (8.64 KB, patch)
2012-06-20 12:41 PDT, Luke Wagner [:luke]
bhackett1024: review+
Details | Diff | Review
cut the stack size in half (1.74 KB, patch)
2012-06-20 13:05 PDT, Luke Wagner [:luke]
no flags Details | Diff | Review
build less XPCOM stack objects (857 bytes, patch)
2012-06-20 16:32 PDT, Luke Wagner [:luke]
bhackett1024: review+
Details | Diff | Review

Description Alice0775 White 2012-05-20 06:59:28 PDT
http://hg.mozilla.org/mozilla-central/rev/642d1a36702f
Mozilla/5.0 (Windows NT 6.1; WOW64; rv:15.0) Gecko/15.0 Firefox/15.0a1 ID:20120519030527

a slow script warning if I try to close the thumbnail picture by clicking x mark

Steps to reproduce:

1. open http://www.offique.com/diffrient-world-humanscale.html
2. click on a thumbnail of different pictures of the product (a chair)
3. try to close the thumbnail picture by clicking x mark


Actual results:

a slow script warning pops up


Expected results:

It should not

#1 Regression window(m-c)
*Works fine(close the thumbnail immediately):
http://hg.mozilla.org/mozilla-central/rev/8a81c455ece0
Mozilla/5.0 (Windows NT 6.1; WOW64; rv:2.0b7pre) Gecko/20100924 Firefox/4.0b7pre ID:20100924103506
*Lag(3-4 sec) to close popped up image when click x mark at top-right of the image.
http://hg.mozilla.org/mozilla-central/rev/d70a9ed2b89e
Mozilla/5.0 (Windows NT 6.1; WOW64; rv:2.0b7pre) Gecko/20100924 Firefox/4.0b7pre ID:20100924104336
#1 Pushlog(m-c):
http://hg.mozilla.org/mozilla-central/pushloghtml?fromchange=8a81c455ece0&tochange=d70a9ed2b89e
Suspected:
bug 596460


#2 Regression window(m-c)
*Lag(3-4 sec) to close popped up image when click x mark at top-right of the image.
http://hg.mozilla.org/mozilla-central/rev/2cd50afa5a00
Mozilla/5.0 (Windows NT 6.1; WOW64; rv:2.0b8pre) Gecko/20101117 Firefox/4.0b8pre ID:20101117143731
*Unresponsive script dialog pops up when click x mark at top-right of popped up image.
http://hg.mozilla.org/mozilla-central/rev/35f8ec6fa9e6
Mozilla/5.0 (Windows NT 6.1; WOW64; rv:2.0b8pre) Gecko/20101117 Firefox/4.0b8pre ID:20101117151808
#2 Pushlog(m-c):
http://hg.mozilla.org/mozilla-central/pushloghtml?fromchange=2cd50afa5a00&tochange=35f8ec6fa9e6

#2 Regression window(TM)
*Lag(3-4 sec) to close popped up image when click x mark at top-right of the image.
http://hg.mozilla.org/tracemonkey/rev/71c0268fb372
Mozilla/5.0 (Windows NT 6.1; WOW64; rv:2.0b8pre) Gecko/20101104 Firefox/4.0b8pre ID:20101104045249
*Unresponsive script dialog pops up when click x mark at top-right of popped up image.
http://hg.mozilla.org/tracemonkey/rev/92af3359a18f
Mozilla/5.0 (Windows NT 6.1; WOW64; rv:2.0b8pre) Gecko/20101104 Firefox/4.0b8pre ID:20101104170738
#2 Pushlog(TM):
http://hg.mozilla.org/tracemonkey/pushloghtml?fromchange=71c0268fb372&tochange=92af3359a18f
Triggered by:
d1bf74046ba7	Luke Wagner — Bug 602129 - JM: make f.call(...) fast, part 2 (r=dvander)
Comment 1 Luke Wagner [:luke] 2012-06-19 19:13:45 PDT
I'm not able to load the page.  Any cached version or new URL available?
Comment 2 Alice0775 White 2012-06-19 20:01:29 PDT
Created attachment 634725 [details]
Zip file, Semi-reduced html

Open aaaa.html .
Comment 3 Luke Wagner [:luke] 2012-06-19 20:04:52 PDT
Thanks!
Comment 4 Luke Wagner [:luke] 2012-06-20 11:16:54 PDT
I think the underlying problem is a bug in the site: clicking the 'X' causes an infinite recursion that ultimately hits a stack limit in both FF (before and after bug 602129) and in Chrome.

The way bug 602129 changes the behavior is that, before, we'd consume C stack space for each f.call (as we called from jit code into C++ and then back to run f).  After bug 602129, we'd stay in jit code and consume no C stack space and comparatively little JS stack space.  This lets us get a lot deeper in the JS stack.  What we end up spending all our time doing is creating exceptions (for some failed quickstub) since there is some terrible quadratic (in stack depth) algorithm to find the line number in the XPConnect exception logic.  I'll file a bug, since this has come up a few times, but, since this is ultimately a bug in content and we are correctly producing the slow-script dialog, it doesn't seem like a high priority.

Alice: do you have contact information for the site developer?  I can post the JS callstack so they can fix their bug, if that would be helpful.
Comment 5 Luke Wagner [:luke] 2012-06-20 11:24:52 PDT
Actually, since this bug has a reproducible test-cast attached, I'll just re-purpose and re-prioritize.

One simple fix would be to just make a fallible version of JS_GetFramePC that takes an upper bound on how many stack frames to traverse before giving up and returning NULL.  That should keep the cost linear.
Comment 6 Alice0775 White 2012-06-20 11:31:28 PDT
(In reply to Luke Wagner [:luke] from comment #4)
> Alice: do you have contact information for the site developer?  I can post
> the JS callstack so they can fix their bug, if that would be helpful.

Sorry, I cannot....
Comment 7 Matthias Versen [:Matti] 2012-06-20 11:32:10 PDT
FYI: This bug is a spin off from bug 756288 and I don't think that Alice has a connection to that site.
Comment 8 Luke Wagner [:luke] 2012-06-20 12:41:20 PDT
Created attachment 635015 [details] [diff] [review]
cap quadratic behavior of JS_GetFramePC

Actually, this has come up a few times and it is annoying to diagnose each time so I might as well do it now.  This patch limits the search done by JS_GetFramePC; if the search hits the limit, we just return script->code which will just mean that the backtrace line is wrong.
Comment 9 Luke Wagner [:luke] 2012-06-20 13:05:15 PDT
Created attachment 635023 [details] [diff] [review]
cut the stack size in half

The previous patch takes us down from >1 minute to 10 seconds.  What still takes so much time (compared to Chrome, which takes maybe .4 seconds) is repeated calls to a quickstub that throws (querySelector), each of which does one of these (now O(n)) CreateStack calls.  CreateStack creates a COM object per stack frame (already capped to 3000 stack frames a while ago), so this page reduces it to 100.  Also, the number of CreateStack calls is proportional to the max recursion depth.  Our max recursion depth is already >2x bigger than some other engines so this patch cuts that in half.

The patch is trivial so we can easily back it out if anything breaks.
Comment 10 Luke Wagner [:luke] 2012-06-20 16:32:29 PDT
Created attachment 635116 [details] [diff] [review]
build less XPCOM stack objects

Actually, cutting the stack size in half broke some mochitests, so I'll back down on that.  (That brings the hang time from 1s to 2s.)
Comment 11 Luke Wagner [:luke] 2012-06-20 18:30:30 PDT
With that change, looking green on try.
Comment 12 Brian Hackett (:bhackett) 2012-06-23 07:17:30 PDT
Comment on attachment 635015 [details] [diff] [review]
cap quadratic behavior of JS_GetFramePC

Review of attachment 635015 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/vm/Stack.cpp
@@ +195,4 @@
>  {
> +    /*
> +     * This isn't just an optimization; seg->computeNextFrame(fp) is only
> +     * defined if fp != seg->regs->fp.

With this comment's phrasing, I think it reads better if it's immediately before the 'if' (so you know what "this" refers to).

::: js/src/vm/Stack.h
@@ +705,5 @@
>          return isScriptFrame() ? script() : NULL;
>      }
>  
>      /*
> +     * TODO

TODO.  Comment needs a little work it looks like.

Note You need to log in before you can comment on or make changes to this bug.