Javascript stack model for generators

While I was using javascript generators to implement a debugger for a small scheme interpreter I starting wondering about the stack model in e.g. the chrome javascript engine. Normally It's enough to have one stack for function call frames. In case of generators I can leave a function call execute another path and then later jump back into the partially executed generator, i.e. put the part of the stack into life that was left.

How is this implemented e.g. in chrome or in the firefox javascript engine? Is the entire virtual stack composed of several virtual stacks or is the part of the stack that is left when yielding written into a generator object? Then it could put back on the stack when entering the generator again.

Answers:

Answer

Generators still run on the same single call stack that normal functions do. There are no multiple stacks that evaluation jumps around between.

When you instantiate a generator (by calling a generator function) and then call its .next() method, it just pushes that call on the top of the stack. It will then run the code inside the generator function.
When it encounters a yield statement, it just pops the call from the stack and returns from the .next() method, continuing as usual after any function call.

The difference between a generator call and a normal function call is what happens when entering and leaving the code.
A normal function leaves at the end of the function body or a return/throw statement, it's finished then. A generator also leaves on yield, but it has to remember the state (basically storing the instruction pointer in the generator instance) so that it can resume execution after the yield. Also it has to remember the state of all local variables, but engines already know how to do that from the implementation of closures.
A normal function enters a call by setting up a fresh environment, and starting execution at the top of the function body. A generator call will restore the state so that it can continue where it left off.

The normal behaviour of the stack is not affected by this.

OK, I lied. yield* makes it all a bit more complicated. A chain of recursively yield*ed generators will need to push and pop multiple stack frames when entering or leaving a .next() call. An engine might optimise this context switch by using multiple stacks. Still, one would see them as stacked atop each other, forming one large stack, and during execution only the top of that single stack is manipulated.

Answer

In Chrome/V8's current implementation, as part of yielding, all state that the generator needs for resuming execution later is written to an object. There is only one stack for function call frames.

The details are complicated; if you want to read the source, start at BytecodeGenerator::VisitYield in (v8)/src/interpreter/bytecode-generator.cc.

Tags

Recent Questions

Top Questions

Home Tags Terms of Service Privacy Policy DMCA Contact Us

©2020 All rights reserved.