Bug 16547 - Perform return/continue/break syntax checking at parse time
Summary: Perform return/continue/break syntax checking at parse time
Status: RESOLVED INVALID
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: 528+ (Nightly build)
Hardware: Macintosh OS X 10.4
: P2 Normal
Assignee: Nobody
URL:
Keywords:
Depends on: 16571
Blocks:
  Show dependency treegraph
 
Reported: 2007-12-20 19:04 PST by Eric Seidel (no email)
Modified: 2010-10-28 11:06 PDT (History)
2 users (show)

See Also:


Attachments
First pass, it compiles (117.17 KB, patch)
2007-12-22 02:39 PST, Eric Seidel (no email)
no flags Details | Formatted Diff | Diff
No longer crashes, but still fails 800+ tests (8.00 KB, patch)
2007-12-22 03:27 PST, Eric Seidel (no email)
no flags Details | Formatted Diff | Diff
Now only fails one test, due likely to a regression in var access (4.41 KB, patch)
2007-12-22 04:57 PST, Eric Seidel (no email)
no flags Details | Formatted Diff | Diff
Fix labeled continues and print() from within testkjs (7.05 KB, patch)
2007-12-22 23:59 PST, Eric Seidel (no email)
no flags Details | Formatted Diff | Diff
Simplify break/continue loop logic for a small speedup (3.20 KB, patch)
2007-12-22 23:59 PST, Eric Seidel (no email)
no flags Details | Formatted Diff | Diff
Final combined patch for review (no changelog yet) (119.92 KB, patch)
2007-12-23 00:01 PST, Eric Seidel (no email)
no flags Details | Formatted Diff | Diff
Now with more ChangeLog! (125.79 KB, patch)
2007-12-23 20:51 PST, Eric Seidel (no email)
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Eric Seidel (no email) 2007-12-20 19:04:48 PST
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()
Comment 1 Eric Seidel (no email) 2007-12-20 19:05:04 PST
This is tangentially related to bug 16472.
Comment 2 Eric Seidel (no email) 2007-12-20 23:39:57 PST
This will have to be done in a post-parse tree walk, since I believe parsing works innermost to outermost.
Comment 3 Eric Seidel (no email) 2007-12-21 13:02:07 PST
I'm on it.
Comment 4 Eric Seidel (no email) 2007-12-21 14:52:15 PST
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.
Comment 5 Eric Seidel (no email) 2007-12-22 02:39:29 PST
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(-)
Comment 6 Eric Seidel (no email) 2007-12-22 03:27:11 PST
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(-)
Comment 7 Eric Seidel (no email) 2007-12-22 04:57:53 PST
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(-)
Comment 8 Eric Seidel (no email) 2007-12-22 04:59:40 PST
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.
Comment 9 Eric Seidel (no email) 2007-12-22 21:41:08 PST
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.
Comment 10 Eric Seidel (no email) 2007-12-22 23:59:56 PST
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(-)
Comment 11 Eric Seidel (no email) 2007-12-22 23:59:58 PST
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(-)
Comment 12 Eric Seidel (no email) 2007-12-23 00:01:57 PST
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.
Comment 13 Eric Seidel (no email) 2007-12-23 00:09:01 PST
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% 

Comment 14 Eric Seidel (no email) 2007-12-23 20:51:03 PST
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(-)
Comment 15 Maciej Stachowiak 2007-12-24 02:25:11 PST
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.
Comment 16 Maciej Stachowiak 2007-12-24 02:32:57 PST
Comment on attachment 18083 [details]
Now with more ChangeLog!

r=me if you address these points.
Comment 17 Eric Seidel (no email) 2007-12-25 22:01:03 PST
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.
Comment 18 Darin Adler 2008-01-03 00:19:55 PST
Comment on attachment 18083 [details]
Now with more ChangeLog!

Clearing the review flag because Eric says he's going to rewrite this.
Comment 19 Eric Seidel (no email) 2008-01-06 18:51:28 PST
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.
Comment 20 Xan Lopez 2010-10-28 07:44:13 PDT
I guess this is not as relevant as it used to be. Should we close the bug Eric?
Comment 21 Eric Seidel (no email) 2010-10-28 11:06:25 PDT
Wow, yeah, this no longer matters.