Bug 16547 – Perform return/continue/break syntax checking at parse time

• Component: JavaScriptCore
• Status: RESOLVED INVALID

[Eric Seidel (no email)]

Perform return/continue/break syntax checking at parse time

There is no need for ReturnNode or ContinueNode or BreakNode to syntax check at runtime (and needlessly branch in the common case), instead they could do all their syntax checking with a similar "codeType()" variable, during parse time.

These branches are somewhat hot in function-heavy code.  One example I saw tonight was the binary-trees test, where > 1% of total time is spent in ReturnNode::execute()

[Eric Seidel (no email)]

This is tangentially related to bug 16472.

[Eric Seidel (no email)]

This will have to be done in a post-parse tree walk, since I believe parsing works innermost to outermost.

[Eric Seidel (no email)]

I'm on it.

[Eric Seidel (no email)]

Well, first thing needed is a way to traverse the node tree.  So I'm re-writing ggaren's optimizeVarLookup optimization to use a new NodeWalker class.  I should chat w/ him about it on IRC next time he appears.

[Eric Seidel (no email)]

Created attachment 18058 [details]
First pass, it compiles

 .../JavaScriptCore.xcodeproj/project.pbxproj       |   10 +-
 JavaScriptCore/kjs/ExecState.cpp                   |    2 -
 JavaScriptCore/kjs/ExecState.h                     |   14 +-
 JavaScriptCore/kjs/LabelStack.h                    |   10 +-
 JavaScriptCore/kjs/NodeWalker.cpp                  |   74 ++++
 JavaScriptCore/kjs/NodeWalker.h                    |   54 +++
 JavaScriptCore/kjs/grammar.y                       |    7 +-
 JavaScriptCore/kjs/internal.cpp                    |    1 +
 JavaScriptCore/kjs/nodes.cpp                       |  402 +++++++++++---------
 JavaScriptCore/kjs/nodes.h                         |  333 +++++++++++------
 JavaScriptCore/kjs/nodes2string.cpp                |   19 +-
 11 files changed, 606 insertions(+), 320 deletions(-)

[Eric Seidel (no email)]

Created attachment 18059 [details]
No longer crashes, but still fails 800+ tests

 JavaScriptCore/kjs/NodeWalker.cpp |    5 ++---
 JavaScriptCore/kjs/NodeWalker.h   |    2 +-
 JavaScriptCore/kjs/nodes.cpp      |   33 +++++++++++++++++++++++++--------
 JavaScriptCore/kjs/nodes.h        |   20 ++++++++++++++++----
 4 files changed, 44 insertions(+), 16 deletions(-)

[Eric Seidel (no email)]

Created attachment 18060 [details]
Now only fails one test, due likely to a regression in var access

 JavaScriptCore/kjs/NodeWalker.cpp |    1 -
 JavaScriptCore/kjs/nodes.cpp      |   27 +++++++++++++++------------
 JavaScriptCore/kjs/nodes.h        |    2 +-
 3 files changed, 16 insertions(+), 14 deletions(-)

[Eric Seidel (no email)]

So the one regression still left is an undefined value on line 105 of String/split-002.js.  I expect that I somehow broke the var lookup optimization, probably by not coding the NodeWalker quite correctly.  I'll investigate tomorrow after some sleep.

[Eric Seidel (no email)]

The failing test is this javascript:

function CompareSplit( string, separator ) {
    split_1 = string.split( separator );
    split_2 = string_split( string, separator );

    AddTestCase(
        "( " + string +".split(" + separator + ") ).length" ,
        split_2.length,
        split_1.length );

the lookup which fails is split_2.length.  split_2 comes back as undefined.  I'm not yet sure if the split_2 lookup is failing, or if split_2 is somehow set to undefined.

[Eric Seidel (no email)]

Created attachment 18066 [details]
Fix labeled continues and print() from within testkjs

 .../JavaScriptCore.xcodeproj/project.pbxproj       |    4 ++--
 JavaScriptCore/kjs/grammar.y                       |    3 ++-
 JavaScriptCore/kjs/nodes.cpp                       |    8 ++++----
 JavaScriptCore/kjs/nodes.h                         |    5 ++++-
 JavaScriptCore/kjs/testkjs.cpp                     |    7 +++++--
 5 files changed, 17 insertions(+), 10 deletions(-)

[Eric Seidel (no email)]

Created attachment 18067 [details]
Simplify break/continue loop logic for a small speedup

 JavaScriptCore/kjs/nodes.cpp |   44 ++++++++++++++++++++++++++---------------
 1 files changed, 28 insertions(+), 16 deletions(-)

[Eric Seidel (no email)]

Created attachment 18068 [details]
Final combined patch for review (no changelog yet)

SunSpider claims this is a wash.  Regardless, I think this is a good direction to take the tree in.  Adding NodeWalker is useful and paves the way for further optimizations down the road.

[Eric Seidel (no email)]

FYI the current perf results for this patch:

TEST                   COMPARISON            FROM                 TO             DETAILS

=============================================================================

** TOTAL **:           -                 4041.7ms +/- 0.1%   4037.7ms +/- 0.1% 

=============================================================================

  3d:                  *1.006x as slow*   470.1ms +/- 0.2%    472.9ms +/- 0.3%     significant
    cube:              *1.015x as slow*   159.1ms +/- 0.4%    161.5ms +/- 0.4%     significant
    morph:             1.003x as fast     147.0ms +/- 0.0%    146.5ms +/- 0.3%     significant
    raytrace:          *1.005x as slow*   164.0ms +/- 0.2%    164.9ms +/- 0.7%     significant

  access:              *1.003x as slow*   668.4ms +/- 0.1%    670.3ms +/- 0.2%     significant
    binary-trees:      -                   97.6ms +/- 0.5%     97.5ms +/- 0.4% 
    fannkuch:          *1.014x as slow*   319.2ms +/- 0.1%    323.6ms +/- 0.1%     significant
    nbody:             1.012x as fast     180.2ms +/- 0.2%    178.1ms +/- 0.4%     significant
    nsieve:            -                   71.4ms +/- 0.5%     71.1ms +/- 0.3% 

  bitops:              1.016x as fast     516.3ms +/- 0.2%    508.1ms +/- 0.1%     significant
    3bit-bits-in-byte: *1.006x as slow*   105.9ms +/- 0.2%    106.5ms +/- 0.4%     significant
    bits-in-byte:      1.023x as fast     136.7ms +/- 0.3%    133.6ms +/- 0.3%     significant
    bitwise-and:       1.031x as fast     144.1ms +/- 0.3%    139.8ms +/- 0.2%     significant
    nsieve-bits:       1.011x as fast     129.6ms +/- 0.3%    128.2ms +/- 0.2%     significant

  controlflow:         1.027x as fast     146.1ms +/- 1.5%    142.2ms +/- 0.3%     significant
    recursive:         1.027x as fast     146.1ms +/- 1.5%    142.2ms +/- 0.3%     significant

  crypto:              1.011x as fast     329.0ms +/- 0.4%    325.3ms +/- 0.2%     significant
    aes:               ??                  94.1ms +/- 1.1%     94.2ms +/- 0.3%     not conclusive: might be *1.001x as slow*
    md5:               1.019x as fast     118.9ms +/- 0.4%    116.7ms +/- 0.3%     significant
    sha1:              1.014x as fast     116.0ms +/- 0.4%    114.4ms +/- 0.5%     significant

  date:                -                  349.5ms +/- 0.2%    349.7ms +/- 0.3% 
    format-tofte:      *1.009x as slow*   159.2ms +/- 0.2%    160.7ms +/- 0.2%     significant
    format-xparb:      1.007x as fast     190.3ms +/- 0.3%    189.0ms +/- 0.4%     significant

  math:                *1.004x as slow*   496.5ms +/- 0.1%    498.3ms +/- 0.3%     significant
    cordic:            *1.008x as slow*   196.4ms +/- 0.3%    198.0ms +/- 0.4%     significant
    partial-sums:      -                  183.0ms +/- 0.3%    182.8ms +/- 0.4% 
    spectral-norm:     ??                 117.1ms +/- 0.5%    117.5ms +/- 0.6%     not conclusive: might be *1.003x as slow*

  regexp:              *1.006x as slow*   240.3ms +/- 0.1%    241.7ms +/- 0.2%     significant
    dna:               *1.006x as slow*   240.3ms +/- 0.1%    241.7ms +/- 0.2%     significant

  string:              *1.004x as slow*   825.5ms +/- 0.2%    829.2ms +/- 0.3%     significant
    base64:            *1.019x as slow*   113.1ms +/- 0.4%    115.2ms +/- 0.4%     significant
    fasta:             1.013x as fast     192.5ms +/- 0.3%    190.1ms +/- 0.8%     significant
    tagcloud:          *1.012x as slow*   191.1ms +/- 0.4%    193.4ms +/- 0.5%     significant
    unpack-code:       *1.012x as slow*   192.6ms +/- 0.4%    195.0ms +/- 0.3%     significant
    validate-input:    -                  136.2ms +/- 0.5%    135.5ms +/- 0.6% 

[Eric Seidel (no email)]

Created attachment 18083 [details]
Now with more ChangeLog!

 JavaScriptCore/ChangeLog                           |  113 +++++
 .../JavaScriptCore.xcodeproj/project.pbxproj       |   10 +-
 JavaScriptCore/kjs/ExecState.cpp                   |    2 -
 JavaScriptCore/kjs/ExecState.h                     |   14 +-
 JavaScriptCore/kjs/LabelStack.h                    |   10 +-
 JavaScriptCore/kjs/NodeWalker.cpp                  |   82 ++++
 JavaScriptCore/kjs/NodeWalker.h                    |   55 +++
 JavaScriptCore/kjs/grammar.y                       |    6 +-
 JavaScriptCore/kjs/internal.cpp                    |    1 +
 JavaScriptCore/kjs/nodes.cpp                       |  447 ++++++++++++--------
 JavaScriptCore/kjs/nodes.h                         |  345 ++++++++++-----
 JavaScriptCore/kjs/nodes2string.cpp                |   19 +-
 JavaScriptCore/kjs/testkjs.cpp                     |    7 +-
 13 files changed, 782 insertions(+), 329 deletions(-)

[Maciej Stachowiak]

Looks reasonably good to me. Some comments (also mentioned on IRC):

1) addCallbackForAfterTraversingCurrentNodesChildren is a little verbose, and why not just have a uniformly named method as the exit callback? Then you'd just need to ask the NodeWalker to call your callback but would not need to register what it is.

2) I think a more conventional name for NodeWalker would be NodeVisitor, as in the "Visitor" design pattern from the gang of four book.

[Maciej Stachowiak]

Comment on attachment 18083 [details]
Now with more ChangeLog!

r=me if you address these points.

[Eric Seidel (no email)]

I talked mjs's ear off about this tonight.

I'm going to change the design around a bit more and post a new patch.

[Darin Adler]

Comment on attachment 18083 [details]
Now with more ChangeLog!

Clearing the review flag because Eric says he's going to rewrite this.

[Eric Seidel (no email)]

ggaren took issue with the inefficiency of my NodeWalker.  I've been distracted by other things.  Perhaps I'll come back to this some day.

[Xan Lopez]

I guess this is not as relevant as it used to be. Should we close the bug Eric?

[Eric Seidel (no email)]

Wow, yeah, this no longer matters.