Closed Bug 987560 Opened 10 years ago Closed 10 years ago

Generators should run on the interpreter stack

Categories

(Core :: JavaScript Engine, defect)

x86
macOS
defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla36

People

(Reporter: wingo, Assigned: wingo)

References

(Blocks 1 open bug)

Details

Attachments

(11 files, 1 obsolete file)

6.96 KB, patch
luke
: review+
Details | Diff | Splinter Review
14.03 KB, patch
luke
: review+
Details | Diff | Splinter Review
19.30 KB, patch
luke
: review+
Details | Diff | Splinter Review
17.40 KB, patch
luke
: review+
Details | Diff | Splinter Review
7.34 KB, patch
luke
: review+
Details | Diff | Splinter Review
45.37 KB, patch
luke
: review+
Details | Diff | Splinter Review
9.73 KB, patch
luke
: review+
Details | Diff | Splinter Review
71.53 KB, patch
luke
: review+
Details | Diff | Splinter Review
34.68 KB, patch
Details | Diff | Splinter Review
136.59 KB, patch
wingo
: review+
Details | Diff | Splinter Review
22.81 KB, patch
wingo
: review+
Details | Diff | Splinter Review
The attached patchset will refactor the implementation of generators to operate on the interpreter stack instead of on a separate single-frame generator stack.  

Instead of the generator state being implicitly stored as the contents of a stack frame on the heap, instead we separate out the components of the generator state:

  1. The callee.

  2. The receiver (this value).

  3. The scope chain.

  4. The args obj, if present.

  5. The expression stack.

  6. The PC offset.

(1), (2), and (4) will not change over the extent of the activation.  (3), (5), and (6) do change.  In most cases the expression stack will be empty, so suspending will not cause any allocation.  The size of a suspended generator will also be less than it is currently.

See bug 903457 for more discussion.

Instead of going through C++ to resume a generator, there will be new self-hosted builtins that can resume a generator, with a special JSOP_RESUME opcode to reconstruct the stack frame.  JSOP_RESUME is similar to JSOP_CALL in many ways.

Likewise JSOP_YIELD is much like JSOP_RETURN, except that it receives an additional argument, the generator.  Instead of setting the "current generator" in the JSContext, this patchset stores the generator object for an activation within the activation itself, in a temporary variable.  Currently the temporary variable is named ".generator", and is as if the generator function had an internal "var .generator = %NewGenerator()" call in it.  Seems to work?

Besides having internal advantages (i.e. getting rid of the horrible marker and finalizer on generator frames), this refactoring makes JSOP_YIELD and JSOP_RESUME amenable to baseline compilation.
Depends on: 985894
Assignee: nobody → wingo
Attachment #8396340 - Flags: review?(luke)
Attachment #8396341 - Flags: review?(luke)
Gaah.  Unhappily this makes things quite a bit slower -- on this test:

function *g(n) { for (var i = 0; i < n; i++) yield i }
var now = new Date(); for (var x of g(1000000)); var time = new Date() - now;

it goes from 430ms to 1310ms.  It shouldn't be due to allocation, as the yield points in g have an empty operand stack.  It's probably interpreter overhead then for the extra fetching of ".generator", but I haven't tried to profile yet.
LOL.  V8 runs that test in 48 ms.
Obviously the difference is that V8 does their equivalent of baseline compilation.  This patchset is necessary to do baseline compilation of generators, and uses the same approach V8 uses (as I implemented that one too).  I suggest we go ahead with this.  I would actually appreciate some help on the JIT side as my time is running really short; Jan would you be interested?  The tricky part is figuring out when to jit the resume stubs (should be as soon as any generator is jittable) and switching from a jitted resume stub to an interpreter generator (if the generator hasn't been compiled yet).
Attachment #8396340 - Flags: review?(luke) → review+
seems I forgot Generator.js in patch 6; will upload tomorrow.
(In reply to Andy Wingo [:wingo] from comment #12)
> I would actually appreciate some
> help on the JIT side as my time is running really short; Jan would you be
> interested?  The tricky part is figuring out when to jit the resume stubs
> (should be as soon as any generator is jittable) and switching from a jitted
> resume stub to an interpreter generator (if the generator hasn't been
> compiled yet).

Sure, I'd be happy to help. Just ping me on IRC or send me an email (I'm not online as much during the work week though).
Blocks: 987244
Comment on attachment 8396341 [details] [diff] [review]
Part 2: Synthesize ".generator" operands to yield expressions

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

::: js/src/frontend/Parser.cpp
@@ +4779,5 @@
>  typename ParseHandler::Node
> +Parser<ParseHandler>::newYieldExpression(uint32_t begin, typename ParseHandler::Node expr,
> +                                         bool isYieldStar)
> +{
> +    //JS_ASSERT(pc->isGenerator());

Comment back in?
Attachment #8396341 - Flags: review?(luke) → review+
Attachment #8396344 - Flags: review?(luke) → review+
Attachment #8396345 - Flags: review?(luke) → review+
Comment on attachment 8396346 [details] [diff] [review]
Part 5: Remove enterGenerator/leaveGenerator context methods

\o/
Attachment #8396346 - Flags: review?(luke) → review+
Comment on attachment 8396347 [details] [diff] [review]
Part 6: Self-host "next", "throw", "close" generator methods

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

Looks good, but I think Generator.js is missing from the patch.

::: js/src/frontend/BytecodeEmitter.cpp
@@ +5595,5 @@
> +    if (kindNode->pn_atom == cx->names().next)
> +        op = JSOP_GENERATORNEXT;
> +    else if (kindNode->pn_atom == cx->names().throw_)
> +        op = JSOP_GENERATORTHROW;
> +    else {

Curlies around then and else-if branches.

::: js/src/jsiter.h
@@ +261,5 @@
>                   JSGenerator::SuspendKind suspendKind);
>  
> +bool
> +ResumeGenerator(JSContext *cx, HandleObject genObj, HandleValue val, MutableHandleValue rval,
> +                JSGenerator::ResumeKind resumeKind);

Often we put the outparam as the last parameter in the list; could you put 'rval' last?

::: js/src/vm/Interpreter.cpp
@@ +3473,5 @@
> +        resumeKind = JSGenerator::NEXT;
> +    else if (*REGS.pc == JSOP_GENERATORTHROW)
> +        resumeKind = JSGenerator::THROW;
> +    else {
> +        JS_ASSERT(*REGS.pc == JSOP_GENERATORCLOSE);

Need curlies for the then and else-if branches.
Attachment #8396348 - Flags: review?(luke) → review+
Attachment #8396349 - Flags: review?(luke) → review+
Comment on attachment 8396350 [details] [diff] [review]
Part 9: Suspend and resume generators on the interpreter stack

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

::: js/src/vm/GeneratorObject.cpp
@@ +55,5 @@
> +    genObj->setThisValue(fp->thisValue());
> +    genObj->setScopeChain(*fp->scopeChain());
> +    if (fp->script()->needsArgsObj())
> +        genObj->setArgsObj(fp->argsObj());
> +    genObj->clearExpressionStack();

After NewObjectWithGivenProto, the reserved slots have been initialized to UndefinedValue(), so it seems like you could skip the clearExpressionStack().

@@ +87,5 @@
>  
>      return true;
>  }
>  
> +bool GeneratorObject::finalSuspend(JSContext *cx, HandleObject obj) {

{ on new line

::: js/src/vm/ScopeObject.cpp
@@ +1865,5 @@
>          if (!frame.hasCallObj())
>              return;
>  
> +        if (frame.fun()->isGenerator())
> +            return;

IIUC, this change is necessary because this patch removes the isYielding() exception for epilogue() calls so frame.scopeChain() might not be a CallObject() (b/c we're in the middle of the function).  Also, IIUC, it's fine to return early b/c this whole function is just recording unaliased variables for posterity and everything in generators is aliased.  In that case, could you hoist this early return to the beginning of the function (since it's not contingent on isHeavyweight()) and add a comment explaining why generators needn't be considered?
Attachment #8396350 - Flags: review?(luke) → review+
Overall, great patchset, thanks for breaking it up!  Just waiting on Generator.js (comment 18) before final r+.
Attachment #8396347 - Flags: review?(luke)
Attachment #8396347 - Attachment is obsolete: true
This update was to add Generators.js that was missing previously.
Right, so the state of these patches in summary:

 * Need a correctness fix: I believe this patchset keeps the generator in the "executing" state when a throw happens.  The fix is probably to add a try/catch or something around the resume, and manually patch the state on exceptional exit. 

 * The patch slows things down, as noted in comment 10 :(  The speed will be recuperated when generators are baseline jitted, but that makes this patchset unattractive to apply as-is.
Attached patch Rebased patchSplinter Review
Andy, this is the result of rebasing your patches on m-i tip. Does not pass tests, I will post a followup patch with changes on top of this that fixes the remaining issues.

Most of the rebasing was straight-forward. A lot of minor changes like JS_ASSERT => MOZ_ASSERT, but nothing huge.
Attachment #8504968 - Flags: review?(wingo)
Attached patch Various changesSplinter Review
This patch fixes a few problems:

* Close the generator when an exception is thrown + tests for this.
* Make the self-hosted functions work with CrossCompartmentWrappers, necessary to make testCrossCompartmentTransparency.js pass. I also added a bunch of extra tests for this.
* Fixes various debugger tests, as discussed on IRC today.

With this we pass all jit-tests and jstests locally. Will see how it does on Try...
Attachment #8505001 - Flags: review?(wingo)
Linux64 Try push looks pretty good, considering the size of those patches:

https://treeherder.mozilla.org/ui/#/jobs?repo=try&revision=149fc8dcd11a

Debug build is green but there's some Opt orange; we're crashing while marking interpreter frames. I think the problem is that we didn't push |undefined| for formal arguments when resuming generators so the GC marked bogus values. Let's see if this fixes it:

https://treeherder.mozilla.org/ui/#/jobs?repo=try&revision=aa0c2b8021c6
(In reply to Jan de Mooij [:jandem] from comment #26)
> Debug build is green but there's some Opt orange; we're crashing while
> marking interpreter frames. I think the problem is that we didn't push
> |undefined| for formal arguments when resuming generators so the GC marked
> bogus values. Let's see if this fixes it:
> 
> https://treeherder.mozilla.org/ui/#/jobs?repo=try&revision=aa0c2b8021c6

It's green. Will do an all-platforms Try push later.
Comment on attachment 8504968 [details] [diff] [review]
Rebased patch

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

lgtm
Attachment #8504968 - Flags: review?(wingo) → review+
Comment on attachment 8505001 [details] [diff] [review]
Various changes

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

LGTM; Some small nits but all looking nice.  Thank you!!

::: js/src/jit-test/tests/generators/throw-closes.js
@@ +9,5 @@
> +}
> +var i = g();
> +assertEq(i.next().value, 1);
> +assertEq(i.next().value, 2);
> +try {

This might be clearer here and below:

  load(libdir + "asserts.js")
  assertThrowsValue(() => i.next(), 3)

@@ +15,5 @@
> +    assertEq(0, 1);
> +} catch(e) {
> +    assertEq(e, 3);
> +}
> +assertEq(i.next().done, true);

load(libdir + "../../tests/ecma_6/Generator/shell.js");

assertIteratorDone(i, undefined)

@@ +24,5 @@
> +    yield 1;
> +    yield 2;
> +}
> +var i = h();
> +assertEq(i.next().value, 1);

assertIteratorNext(i, 1);

@@ +39,5 @@
> +    yield 1;
> +    yield 2;
> +}
> +var i = l1();
> +assertEq(i.next(), 1);

probably useful to implement a assertLegacyIteratorNext(i, 1)

@@ +47,5 @@
> +} catch(e) {
> +    assertEq(e, 5);
> +}
> +try {
> +    i.next();

assertThrowsInstanceOf(()=>i.throw(5), StopIteration)

::: js/src/jit-test/tests/generators/wrappers.js
@@ +9,5 @@
> +// LegacyGenerator.next
> +assertEq(it.next.call(g.it2), 3);
> +
> +// LegacyGenerator.throw
> +try {

asserThrowsValue combined with load(libdir + "asserts.js");

@@ +21,5 @@
> +it = gen3();
> +g.eval("function *gen4() { yield 5; yield 6; }; var it4 = gen4();");
> +
> +// StarGenerator.next
> +assertEq(it.next.call(g.it4).value, 5);

assertIteratorResult(it.next.call(g.it4), 5, false)

::: js/src/jit-test/tests/saved-stacks/generators.js
@@ +9,5 @@
>  }());
>  
>  assertEq(frame.functionDisplayName, "iife2");
>  assertEq(frame.parent.functionDisplayName, "generator");
> +assertEq(frame.parent.parent.functionDisplayName, "next");

nice!

::: js/src/vm/GeneratorObject.cpp
@@ +110,5 @@
>  {
>      Rooted<GeneratorObject*> genObj(cx, &obj->as<GeneratorObject>());
>      MOZ_ASSERT(!genObj->isClosed());
> +    MOZ_ASSERT(!genObj->isRunning());
> +    MOZ_ASSERT(!genObj->isClosing());

These three can be replaced with MOZ_ASSERT(genObj->isSuspended()) I think, which also catches the newborn case

@@ +150,5 @@
>  
>        case THROW:
>          cx->setPendingException(arg);
>          if (genObj->isNewborn())
> +            genObj->setClosed();

nice; untangling the jscontext and generators is a happy thing
Attachment #8505001 - Flags: review?(wingo) → review+
Thanks for the fast reviews. Pushed with nits addressed:

https://hg.mozilla.org/integration/mozilla-inbound/rev/b56d94c7261a
https://hg.mozilla.org/mozilla-central/rev/b56d94c7261a
Status: NEW → RESOLVED
Closed: 10 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla36
Blocks: 1093573
You need to log in before you can comment on or make changes to this bug.