[Webkit-unassigned] [Bug 139847] New: JavaScriptCore deeply composed call performance issue

[bugzilla-daemon at webkit.org]

https://bugs.webkit.org/show_bug.cgi?id=139847

            Bug ID: 139847
           Summary: JavaScriptCore deeply composed call performance issue
    Classification: Unclassified
           Product: WebKit
           Version: 528+ (Nightly build)
          Hardware: Macintosh Intel
                OS: Mac OS X 10.10
            Status: NEW
          Severity: Normal
          Priority: P2
         Component: JavaScriptCore
          Assignee: webkit-unassigned at lists.webkit.org
          Reporter: mike at fikesfarm.com

If I define a function

inc=function( x ) { return x + 1; }

and make a deeply composed invocation of it

inc(inc(inc(inc(inc(inc(inc(inc(inc(inc(inc(inc
  (inc(inc(inc(inc(inc(inc(inc(inc(inc(1)))))))))))))))))))))

this will result in the value 22. If I revise the deeply composed expression to instead make use of call, passing in null for this, as

inc.call(null, inc.call(null, inc.call(null, inc.call(null,
  inc.call(null, inc.call(null, inc.call(null, inc.call(null,
    inc.call(null, inc.call(null, inc.call(null, inc.call(null,
      inc.call(null, inc.call(null, inc.call(null, inc.call(null,
        inc.call(null, inc.call(null, inc.call(null, inc.call(null,
          inc.call(null, 1)))))))))))))))))))))

this will also produce the value 22, but on JavaScriptCore this appears to consume O(2^n) memory, where n is the number of nested calls. This can easily exhaust memory; in the case above, evaluating this expression can consume several GB. (This is not the case if I try this JavaScript in Firefox or Chrome.)

What have I done so far includes producing a stack trace for when it fails on iOS, and in that trace, I see a deep call stack (80 to 100 frames) in the JavaScriptCore engine with frames like the following 4 repeated down the stack:

frame #77: 0x00f324dc JavaScriptCore`JSC::CallFunctionCallDotNode::emitBytecode(JSC::BytecodeGenerator&, JSC::RegisterID*) + 1852
frame #78: 0x00f30661 JavaScriptCore`JSC::ArgumentListNode::emitBytecode(JSC::BytecodeGenerator&, JSC::RegisterID*) + 65
frame #79: 0x00bef410 JavaScriptCore`JSC::BytecodeGenerator::emitCall(JSC::OpcodeID, JSC::RegisterID*, JSC::RegisterID*, JSC::ExpectedFunction, JSC::CallArguments&, JSC::JSTextPosition const&, JSC::JSTextPosition const&, JSC::JSTextPosition const&) + 368
frame #80: 0x00bef28d JavaScriptCore`JSC::BytecodeGenerator::emitCall(JSC::RegisterID*, JSC::RegisterID*, JSC::ExpectedFunction, JSC::CallArguments&, JSC::JSTextPosition const&, JSC::JSTextPosition const&, JSC::JSTextPosition const&) + 77

I've also done some experimentation where refactoring a few of the inner calls to temporaries will "truncate" the memory doubling behavior and allow things to succeed

var temp1 = inc.call(null, inc.call(null, inc.call(null, inc.call(null,
              inc.call(null, inc.call(null, inc.call(null, 1)))))));

var temp2 = inc.call(null, inc.call(null, inc.call(null, inc.call(null,
              inc.call(null, inc.call(null, inc.call(null, temp1)))))));

inc.call(null, inc.call(null, inc.call(null, inc.call(null,
  inc.call(null, inc.call(null, inc.call(null, temp2)))))));

This makes me thinks that perhaps this is simply a bug with the way JavaScriptCore evaluates deeply nested call invocations.

Steps to Reproduce:
1. Get set up to execute JavaScript in JavaScriptCore. (Go to jsfiddle.net with Safari, for example).
2. Evaluate the "inc" function definition in the Description
3. Evaluate the deeply composed "inc.call" expression in the Description
4. You could wrap the result of the "inc.call" in an alert call. The entire JavaScript is:

inc=function( x ) { return x + 1; }

alert(inc.call(null, inc.call(null, inc.call(null, inc.call(null,
  inc.call(null, inc.call(null, inc.call(null, inc.call(null,
    inc.call(null, inc.call(null, inc.call(null, inc.call(null,
      inc.call(null, inc.call(null, inc.call(null, inc.call(null,
        inc.call(null, inc.call(null, inc.call(null, inc.call(null,
          inc.call(null, 1))))))))))))))))))))))

Expected Results:
This should result in the number 22 being evaluated quickly.

Actual Results:
The number 22 is produced, but only after several seconds transpire. Additionally, if you watch in Activity Monitor, you will see several GB being consumed.

Version:
iOS 7 & 8, Yosemite. On Yosemite: 8.0.2 (10600.2.5)

Notes:


Configuration:
This occurs on Safari on iOS 7, and 8, and on Safari on Yosemite. Haven't tested on Mavericks.

-- 
You are receiving this mail because:
You are the assignee for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.webkit.org/pipermail/webkit-unassigned/attachments/20141220/db2ff509/attachment-0002.html>