Optimization: Move the main state machine code into a separate function. (issue 7759049)

[usrb...@yahoo.com]

Reviewers: arv-chromium, slightlylate, peterhal,

Message:
Note: this diff is against the patch series:

https://codereview.appspot.com/7761043

I get about a 36% speedup on my computer. The difference should be
greater for generators that do more work, or that are longer-lived
(minimizing the creation costs).

#--cut--
dl_check() {
local f=$(basename $1)
test -e $f || curl -sO $1
openssl sha1 < $f | grep -q "= $2" && return 0
echo sha1 mismatch!
return 1
}

git checkout -b issue7759049-yield-expr-8-opt-func-try-catch

cat > bench-gen.js <<"END"
require('./src/node/traceur.js');
function* G(n) {
for (var i = 0; i < n; i++) {
yield i;
}
}

// Don't include generator creation overhead.
var g = G(10000000);

var v = 0;
start = Date.now();
for (var x of g) {
v = (v + x) % 0x40000000;
}
console.log(Date.now() - start, v);
END

### before
./traceur --out bench-gen.out.js -- bench-gen.js && node
bench-gen.out.js

dl_check https://codereview.appspot.com/download/issue7759049_2002.diff
\
e36a4a8d96d6759c && git apply issue7759049_2002.diff && make test

### after
./traceur --out bench-gen.out.js -- bench-gen.js && node
bench-gen.out.js
#--cut--

----

Kind of an aside, but it might be nice to eventually have a series of
standard benchmarks to be able to measure performance regressions or
advancements.

Description:
Optimization: Move the main state machine code into a separate function.

This allows V8 to optimize better, since the separated function doesn't
contain a try-catch.

BUG=None
TEST=None


Please review this at https://codereview.appspot.com/7759049/

Affected files:
M src/codegeneration/generator/AsyncTransformer.js
M src/codegeneration/generator/CPSTransformer.js
M src/codegeneration/generator/GeneratorTransformer.js
M src/codegeneration/generator/State.js
M src/syntax/PredefinedName.js


Index: src/codegeneration/generator/AsyncTransformer.js
diff --git a/src/codegeneration/generator/AsyncTransformer.js
b/src/codegeneration/generator/AsyncTransformer.js
index
fee4687a8a2de1426e1d84ef2c4e1ef81006ac03..0c5fa09918ce79c093d0a71aa9fb088970709476
100644
--- a/src/codegeneration/generator/AsyncTransformer.js
+++ b/src/codegeneration/generator/AsyncTransformer.js
@@ -33,6 +33,7 @@ import {
WAIT_TASK
} from '../../syntax/PredefinedName.js';
import {STATE_MACHINE} from '../../syntax/trees/ParseTreeType.js';
+import {parseStatement} from '../PlaceholderParser.js';
import {StateMachine} from '../../syntax/trees/StateMachine.js';
import {VAR} from '../../syntax/TokenType.js';
import {
@@ -248,11 +249,25 @@ export class AsyncTransformer extends CPSTransformer {
VAR,
WAIT_TASK,
null));
- // var $continuation = machineMethod;
+ var id = createIdentifierExpression;
+ var G = '$G';
+ statements.push(
+ parseStatement `
+ var ${G} = {
+ GState: 0,
+ current: undefined,
+ yieldReturn: undefined,
+ innerFunction: ${this.generateMachineInnerFunction(machine)},
+ moveNext: ${this.generateMachineMethod(machine)}
+ };
+ `);
+ // var $continuation = $G.moveNext.bind($G);
statements.push(createVariableStatement(
VAR,
CONTINUATION,
- this.generateMachineMethod(machine)));
+ createCallExpression(
+ createMemberExpression(id(G), 'moveNext', 'bind'),
+ createArgumentList(id(G)))));
// var $createCallback = function(newState) { return function
(value) { $state = newState; $value = value; $continuation(); }}
statements.push(createVariableStatement(
VAR,
Index: src/codegeneration/generator/CPSTransformer.js
diff --git a/src/codegeneration/generator/CPSTransformer.js
b/src/codegeneration/generator/CPSTransformer.js
index
56d2e837188247794a6e2297219458c2364f7362..894ea2a2239cb8a8fea7fa99fd52908a8f7fd246
100644
--- a/src/codegeneration/generator/CPSTransformer.js
+++ b/src/codegeneration/generator/CPSTransformer.js
@@ -21,6 +21,7 @@ import {
} from '../../syntax/trees/ParseTreeType.js';
import {
CaseClause,
+ FunctionDeclaration,
IdentifierExpression,
SwitchStatement
} from '../../syntax/trees/ParseTrees.js';
@@ -37,6 +38,7 @@ import {
ARGUMENTS,
CAUGHT_EXCEPTION,
FINALLY_FALL_THROUGH,
+ INNER_FUNCTION,
STATE,
STORED_EXCEPTION,
YIELD_ACTION,
@@ -55,6 +57,7 @@ import {
} from '../../syntax/TokenType.js';
import {TryState} from './TryState.js';
import {
+ createArgumentList,
createAssignStateStatement,
createAssignmentExpression,
createAssignmentStatement,
@@ -64,15 +67,18 @@ import {
createBreakStatement,
createCaseClause,
createCatch,
+ createCallExpression,
createCommaExpression,
createDefaultClause,
createEmptyStatement,
createExpressionStatement,
createFunctionExpression,
createIdentifierExpression,
+ createMemberExpression,
createNumberLiteral,
createOperatorToken,
createParameterList,
+ createReturnStatement,
createStatementList,
createStringLiteral,
createSwitchStatement,
@@ -740,14 +746,10 @@ export class CPSTransformer extends
ParseTreeTransformer {
}

// With this to $that and arguments to $arguments alpha renaming
- // function($yieldSent) {
+ // function($yieldSent, $yieldAction) {
// while (true) {
// try {
- // switch ($state) {
- // ... converted states ...
- // case rethrow:
- // throw $storedException;
- // }
+ // return this.innerFunction($yieldSent, $yieldAction);
// } catch ($caughtException) {
// $storedException = $caughtException;
// switch ($state) {
@@ -798,6 +800,35 @@ export class CPSTransformer extends
ParseTreeTransformer {
createIdentifierExpression(ARGUMENTS));
}

+ generateMachineInnerFunction(machine) {
+ var enclosingFinallyState = machine.getEnclosingFinallyMap();
+ var enclosingCatchState = machine.getEnclosingCatchMap();
+ var rethrowState = this.allocateState();
+ var machineEndState = this.allocateState();
+
+ // while (true) {
+ // switch ($state) {
+ // ... converted states
+ // case rethrow:
+ // throw $storedException;
+ // }
+ // }
+ var body =
+ createWhileStatement(
+ createTrueLiteral(),
+ createSwitchStatement(
+ createIdentifierExpression(STATE),
+ this.transformMachineStates(
+ machine,
+ State.END_STATE,
+ State.RETHROW_STATE,
+ enclosingFinallyState)));
+
+ return createFunctionExpression(
+ createParameterList(YIELD_SENT, YIELD_ACTION),
+ createBlock(body));
+ }
+
/**
* @param {StateMachine} machine
* @return {ParseTree}
@@ -805,15 +836,16 @@ export class CPSTransformer extends
ParseTreeTransformer {
generateMachine(machine) {
var enclosingFinallyState = machine.getEnclosingFinallyMap();
var enclosingCatchState = machine.getEnclosingCatchMap();
- var rethrowState = this.allocateState();
- var machineEndState = this.allocateState();
- var body =
- // switch ($state) {
- createSwitchStatement(createIdentifierExpression(STATE),
- // ... converted states
- this.transformMachineStates(machine, machineEndState, rethrowState,
- enclosingFinallyState));

+ // 'this' refers to the '$G' object from
+ // GeneratorTransformer.transformGeneratorBody
+ //
+ // return this.innerFunction($yieldSent, $yieldAction);
+ var body = createReturnStatement(
+ createCallExpression(
+ createMemberExpression(createThisExpression(), INNER_FUNCTION),
+ createArgumentList(createIdentifierExpression(YIELD_SENT),
+ createIdentifierExpression(YIELD_ACTION))));
// try {
// ...
// } catch ($caughtException) {
@@ -835,15 +867,15 @@ export class CPSTransformer extends
ParseTreeTransformer {
// }
// }
var caseClauses = [];
- this.addExceptionCases_(rethrowState, enclosingFinallyState,
+ this.addExceptionCases_(State.RETHROW_STATE, enclosingFinallyState,
enclosingCatchState, machine.states,
caseClauses);
// default:
// throw $storedException;
caseClauses.push(
createDefaultClause(
- this.machineUncaughtExceptionStatements(rethrowState,
- machineEndState)));
+ this.machineUncaughtExceptionStatements(State.RETHROW_STATE,
+ State.END_STATE)));

// try {
// ...
Index: src/codegeneration/generator/GeneratorTransformer.js
diff --git a/src/codegeneration/generator/GeneratorTransformer.js
b/src/codegeneration/generator/GeneratorTransformer.js
index
dc8584e1d204d9956fd4f174dcd96facb255f123..2f7ef4fbef38f986059e417240e230e4e3e86788
100644
--- a/src/codegeneration/generator/GeneratorTransformer.js
+++ b/src/codegeneration/generator/GeneratorTransformer.js
@@ -227,6 +227,7 @@ export class GeneratorTransformer extends
CPSTransformer {
GState: ${ST_NEWBORN},
current: undefined,
yieldReturn: undefined,
+ innerFunction: ${this.generateMachineInnerFunction(machine)},
moveNext: ${this.generateMachineMethod(machine)}
};
`);
Index: src/codegeneration/generator/State.js
diff --git a/src/codegeneration/generator/State.js
b/src/codegeneration/generator/State.js
index
9470d7a1ec0b2fc7e811d2bca506cc9a9bcdafda..44e671a0ff823e35883c0e8394cc2419fc91930a
100644
--- a/src/codegeneration/generator/State.js
+++ b/src/codegeneration/generator/State.js
@@ -77,6 +77,8 @@ export class State {


State.INVALID_STATE = -1;
+State.END_STATE = -2;
+State.RETHROW_STATE = -3;

/**
* Returns a list of statements which jumps to a given destination state.
If transfering control
Index: src/syntax/PredefinedName.js
diff --git a/src/syntax/PredefinedName.js b/src/syntax/PredefinedName.js
index
d74adb4259e2f7bd6844a204ea834869144ea310..ef6cf9f14bc2dcfec5c81ed4a0f7add43d93418b
100644
--- a/src/syntax/PredefinedName.js
+++ b/src/syntax/PredefinedName.js
@@ -64,6 +64,7 @@ export var HAS = 'has';
export var INIT = '$init';
export var IS_DONE = 'isDone';
export var ITERATOR = 'iterator';
+export var INNER_FUNCTION = 'innerFunction';
export var LENGTH = 'length';
export var MODULE = 'module';
export var MODULES = 'modules';

[a...@chromium.org]

The generatorWrap function has $G in it. Now that it does not embed any
user code we should rename $G to generator.


https://codereview.appspot.com/7759049/diff/2002/src/codegeneration/generator/AsyncTransformer.js
File src/codegeneration/generator/AsyncTransformer.js (right):

https://codereview.appspot.com/7759049/diff/2002/src/codegeneration/generator/AsyncTransformer.js#newcode268
src/codegeneration/generator/AsyncTransformer.js:268:
createCallExpression(
or

parseStatement `var ${id(CONTINUATION)} =
${id(G)}.moveNext.bind(${id(G)});`

https://codereview.appspot.com/7759049/diff/2002/src/codegeneration/generator/CPSTransformer.js
File src/codegeneration/generator/CPSTransformer.js (right):

https://codereview.appspot.com/7759049/diff/2002/src/codegeneration/generator/CPSTransformer.js#newcode828
src/codegeneration/generator/CPSTransformer.js:828:
createParameterList(YIELD_SENT, YIELD_ACTION),
fix indentation... this should have been 4 spaces indented

https://codereview.appspot.com/7759049/diff/2002/src/codegeneration/generator/CPSTransformer.js#newcode844
src/codegeneration/generator/CPSTransformer.js:844: var body =
createReturnStatement(
parseStatement?

https://codereview.appspot.com/7759049/diff/2002/src/codegeneration/generator/GeneratorTransformer.js
File src/codegeneration/generator/GeneratorTransformer.js (right):

https://codereview.appspot.com/7759049/diff/2002/src/codegeneration/generator/GeneratorTransformer.js#newcode316
src/codegeneration/generator/GeneratorTransformer.js:316:
statements.push(createExpressionStatement(
This part can now be moved into generatorWrap

https://codereview.appspot.com/7759049/

[a...@chromium.org]

I really like this change. It is nice to extract part of the
complications to a shared function. It makes things easier to follow and
reduces the amount of code per generator.

https://codereview.appspot.com/7759049/

[usrb...@yahoo.com]

Experimenting with patch set series. Git and rietveld were made for each
other.

There doesn't seem to be an easy way to scroll through a series of patch
sets, though tabbed browsing can approximate the experience with a
little more clicking.

----

On 2013/03/18 21:34:36, arv-chromium wrote:
> I really like this change. It is nice to extract part of the
> complications to a shared function. It makes things easier to follow
> and reduces the amount of code per generator.

After having worked with this code awhile (especially on some upcoming
patches for optimizing the state machine output) I can't help thinking
that making some even larger architectural divisions would make this
code even more understandable.

One of the biggest things is that
- the transformer(s) for creating the state machine, and
- the code for generating the code from that state machine
are mixed together in GeneratorTransformer and CPSTransformer.

Another is that a lot of the utility functions for
- transforming state machines, or
- transforming or querying combinations of state machines and normal
ParseTree nodes
are private members of CPSTransformer, when they don't need to be.

I still have a few patches in flight, so it's not convenient to do any
of these at the moment, but just noting them for future reference.

The biggest win in clarity would come from more dramatic changes,
which would be even further in the future. The biggest driver for this
would be if it makes it easier to do state machine optimizations, or
to integrate full yield expressions.



https://codereview.appspot.com/7759049/diff/21001/src/runtime/runtime.js
File src/runtime/runtime.js (right):

https://codereview.appspot.com/7759049/diff/21001/src/runtime/runtime.js#newcode329
src/runtime/runtime.js:329: return object;
One of those cases where it's nice to be able to modify the runtime api.

https://codereview.appspot.com/7759049/diff/25001/src/codegeneration/generator/AsyncTransformer.js
File src/codegeneration/generator/AsyncTransformer.js (right):

https://codereview.appspot.com/7759049/diff/25001/src/codegeneration/generator/AsyncTransformer.js#newcode267
src/codegeneration/generator/AsyncTransformer.js:267: var
${id(CONTINUATION)} = ${id(G)}.moveNext.bind(${id(G)});`);
Obviously, there are a lot of complicated ParseTreeFactory calls here
that could be converted to use parseStatement. I'm reluctant to clean up
this file too much, since 'async' is probably not going to be in the
spec, which means that this file is likely going away sometime.

For the moment, I've just decided to do the minimum necessary to pass
the current set of async tests.

https://codereview.appspot.com/7759049/

[a...@chromium.org]

LGTM

Committed as 61695efebd562b7ceafc9a20c3f380c5666d4fc8

https://codereview.appspot.com/7759049/