Closed Bug 550350 Opened 14 years ago Closed 14 years ago

lightweight JSParseNode subclasses

Categories

(Core :: JavaScript Engine, defect)

Product:
Core
Component:
JavaScript Engine
Platform:
x86
macOS
Type:
defect
Priority:
Not set
Severity:
normal

Tracking

()

Status:
RESOLVED FIXED

People

(Reporter: dherman, Assigned: dherman)

References

Details

(Whiteboard: fixed-in-tracemonkey)

Attachments

(1 file, 4 obsolete files)

JSParseNode subclasses and static factories
70.18 KB, patch
Details | Diff | Splinter Review 
Create subclasses of JSParseNode corresponding to the different node types, each with a static factory function.
This is a subpatch of the mega-patch I submitted to bug #548461. It seems to be a teeny performance win *most* of the time but not always (just barely loses -- by about 0.1ms -- on ga.js and yui-min.js from bug #548621).
Attachment #430461 - Flags: review?(gal)
Comment on attachment 430461 [details] [diff] [review]
JSParseNode subclasses and static factories

I suggest moving the implementation of the constructors into the .cpp file, they are only used from there.
Attachment #430461 - Flags: review?(gal) → review+
Moved inline JSParseNode::init out of header file and into jsparse.cpp.
Attachment #430461 - Attachment is obsolete: true
Attachment #430472 - Flags: review?(gal)
Comment on attachment 430472 [details] [diff] [review]
JSParseNode subclasses and static factories

>+void inline
>+JSParseNode::init(JSTokenType type, JSOp op, JSParseNodeArity arity) {
>+    pn_type = type;
>+    pn_op = op;
>+    pn_arity = arity;
>+    pn_parens = false;
>+    JS_ASSERT(!pn_used);
>+    JS_ASSERT(!pn_defn);
>+    pn_next = pn_link = NULL;
>+}

This seems better and (you just said) goes faster if in the .h file, inline in the class or struct.

Style nit: left brace goes on own line for top-level function-like definitions (methods if at top level), but in classes and structs, at end of "method head" line is fine (method is indented one c-basic-offset of course).

>+namespace js {
>+
>+JSParseNode *
>+BinaryNode::createFlat(JSTokenType tt, JSOp op, JSParseNode *left, JSParseNode *right,
>+                       JSTreeContext *tc)

Is Flat important to include in the name? Probably create is enough, flattening left-heavy binary trees into lists is just a detail. Unless there's a createTree alternative?

>+NameNode *
>+NameNode::create(JSAtom *atom, JSTreeContext *tc)
>+{
>+    JSParseNode *pn;
>+
>+    pn = JSParseNode::create(PN_NAME, tc);

Is placement new better than create methods: new (tc) JSParseNode(PN_NAME, tc), with the appropriate operator new definition and <new> included.

Awkward to pass tc to new and the ctor, but both want it. I'm not sure placement new is better than static create methods, just throwing this out.

>@@ -4380,17 +4387,17 @@ ReturnOrYield(JSContext *cx, JSTokenStre
> static JSParseNode *
> PushLexicalScope(JSContext *cx, JSTokenStream *ts, JSTreeContext *tc,
>                  JSStmtInfo *stmt)
> {
>     JSParseNode *pn;
>     JSObject *obj;
>     JSObjectBox *blockbox;
> 
>-    pn = NewParseNode(PN_NAME, tc);
>+    pn = LexicalNode::create(tc);

LexicalScopeNode -- may as well spell it out.

>-            pn4 = NewParseNode(PN_TERNARY, tc);
>+            pn4 = TernaryNode::create(tc);
>             if (!pn4)
>                 return NULL;
>             pn4->pn_type = TOK_FORHEAD;
>             pn4->pn_op = JSOP_NOP;
>             pn4->pn_kid1 = pn1;
>             pn4->pn_kid2 = pn2;
>             pn4->pn_kid3 = pn3;

Another design question: why not pass the kids as arguments? type and op too if that wins in most or all call sites.

>+namespace js {
>+
>+struct NullaryNode : public JSParseNode {
>+    static inline NullaryNode *create(JSTreeContext *tc) {
>+        return (NullaryNode *)JSParseNode::create(PN_NULLARY, tc);
>+    }
>+};
>+
>+struct UnaryNode : public JSParseNode {
>+    static inline UnaryNode *create(JSTreeContext *tc) {
>+        return (UnaryNode *)JSParseNode::create(PN_UNARY, tc);
>+    }
>+};
>+
>+struct BinaryNode : public JSParseNode {
>+    static inline BinaryNode *create(JSTreeContext *tc) {
>+        return (BinaryNode *)JSParseNode::create(PN_BINARY, tc);
>+    }
>+    static JSParseNode *createFlat(JSTokenType tt, JSOp op, JSParseNode *left, JSParseNode *right,
>+                                   JSTreeContext *tc);
>+};
>+
>+struct TernaryNode : public JSParseNode {
>+    static inline TernaryNode *create(JSTreeContext *tc) {
>+        return (TernaryNode *)JSParseNode::create(PN_TERNARY, tc);
>+    }
>+};
>+
>+struct ListNode : public JSParseNode {
>+    static inline ListNode *create(JSTreeContext *tc) {
>+        return (ListNode *)JSParseNode::create(PN_LIST, tc);
>+    }
>+};
>+
>+struct FunctionNode : public JSParseNode {
>+    static inline FunctionNode *create(JSTreeContext *tc) {
>+        return (FunctionNode *)JSParseNode::create(PN_FUNC, tc);
>+    }
>+};
>+
>+struct NameNode : public JSParseNode {
>+    static NameNode *create(JSAtom *atom, JSTreeContext *tc);
>+
>+    void inline initCommon(JSTreeContext *tc);
>+};
>+
>+struct NameSetNode : public JSParseNode {
>+    static inline NameSetNode *create(JSTreeContext *tc) {
>+        return (NameSetNode *)JSParseNode::create(PN_NAMESET, tc);
>+    }
>+};
>+
>+struct LexicalNode : public JSParseNode {
>+    static inline LexicalNode *create(JSTreeContext *tc) {
>+        return (LexicalNode *)JSParseNode::create(PN_NAME, tc);
>+    }
>+};
>+
>+} /* namespace js */

Beautiful (except for the Flat, no need for that and it makes lines overlong and looks like an odd duck without motivation).

So I suspect if you put init back in the .h file as an inline method in the struct, any perf changes you seem to see are noise. Looking at generated code, if not shark profile diff'ing, would help confirm.

I'll r+ a patch with the nits and any C++ interface design issues you think are worth resolving differently addressed.

/be
Attachment #430472 - Flags: review?(gal) → review?(brendan)
Want to coordinate with cleary's work on bug 518055 to minimize conflicts and settle any common interface design issues.

/be
(In reply to comment #4)
> This seems better and (you just said) goes faster if in the .h file, inline in
> the class or struct.

Agreed, although I wish I understood why it affects perf.

> Style nit: left brace goes on own line for top-level function-like definitions
> (methods if at top level), but in classes and structs, at end of "method head"
> line is fine (method is indented one c-basic-offset of course).

Duly noted, thanks.

> >+JSParseNode *
> >+BinaryNode::createFlat(JSTokenType tt, JSOp op, JSParseNode *left, JSParseNode *right,
> >+                       JSTreeContext *tc)
> 
> Is Flat important to include in the name? Probably create is enough, flattening
> left-heavy binary trees into lists is just a detail. Unless there's a
> createTree alternative?

I don't feel too strongly about the name, but this is going to become an issue eventually. For example, tools like Bespin that will want to do syntax highlighting will need very precise parses with no transformations. I don't see any obvious way to make such optimizations optional without an additional branch or at least a computed jump, so it would probably affect perf. For now I'm not touching it.

> Is placement new better than create methods: new (tc) JSParseNode(PN_NAME, tc),
> with the appropriate operator new definition and <new> included.
> 
> Awkward to pass tc to new and the ctor, but both want it. I'm not sure
> placement new is better than static create methods, just throwing this out.

No idea; perhaps someone else can comment? I will leave it as statics for now. Easy enough to change later.

> LexicalScopeNode -- may as well spell it out.

Will do.

> >-            pn4 = NewParseNode(PN_TERNARY, tc);
> >+            pn4 = TernaryNode::create(tc);
> >             if (!pn4)
> >                 return NULL;
> >             pn4->pn_type = TOK_FORHEAD;
> >             pn4->pn_op = JSOP_NOP;
> >             pn4->pn_kid1 = pn1;
> >             pn4->pn_kid2 = pn2;
> >             pn4->pn_kid3 = pn3;
> 
> Another design question: why not pass the kids as arguments? type and op too if
> that wins in most or all call sites.

Maybe; it'd be a bit more invasive logical change. If it's okay, I'd rather split that out into another bug.

> So I suspect if you put init back in the .h file as an inline method in the
> struct, any perf changes you seem to see are noise. Looking at generated code,
> if not shark profile diff'ing, would help confirm.

I'll attack Shark tomorrow.

Thanks,
Dave
Implemented most of Brendan's suggestions. Will profile tomorrow.
Attachment #430472 - Attachment is obsolete: true
Attachment #430526 - Flags: review?(brendan)
Attachment #430472 - Flags: review?(brendan)
Moved inline NameNode::initCommon above NameNode::create which uses it.
Attachment #430526 - Attachment is obsolete: true
Attachment #430750 - Flags: review?(brendan)
Attachment #430526 - Flags: review?(brendan)
I can't see any perf differences > 1ms. On my machine, with a 32-bit build I found this patch 1ms *faster*, and with a 64-bit build it's 1ms *slower*. I suspect it's statistical noise.

I used

    gobjump -t jsparse.o

and found no mention of any of the inlines, so I suspect they are being correctly inlined, at least on MacOS.

Dave
Oh, I just re-discovered that eliminating the "Flat" suffix from the function name ends up with two overloaded BinaryNode::create static functions. That seems unfortunate. The two correspond to

    NewParseNode(PN_BINARY, ...)
    NewBinary(...)

in the previous version. I'm open to other names if createFlat is aesthetically unpleasing, but the overloading seems unnatural.

Dave
Blocks: 548461
I'm not going to stop the patch over createFlat (the name is not obvious but not terrible either :-/), but overloading is possible too. C++ connoisseurs should weigh in.

The optionality of flattening left-heavy binary trees into lists had not occurred to me, since anyone processing a left-heavy AST recursively might run too deep on the stack, which is why the parser listifies. Is it simpler to have two modes of parsing binary expressions, or one that makes two kinds of trees depending on whether operators are chained?

/be
Brendan's convinced me the overloading is fine. Ready for final review.

Dave
Comment on attachment 430750 [details] [diff] [review]
JSParseNode subclasses and static factories

> MakePlaceholder(JSParseNode *pn, JSTreeContext *tc)
> {
>     JSAtomListElement *ale = tc->lexdeps.add(tc->compiler, pn->pn_atom);
>     if (!ale)
>         return NULL;
> 
>     JSDefinition *dn = (JSDefinition *)
>-        NewNameNode(tc->compiler->context, pn->pn_atom, tc);
>+        NameNode::create(pn->pn_atom, tc);

This will fit on one line now, so pull the overflow line up. Ditto any similar later in the patch, I thought I spotted one such.

> ...
> #endif /* JS_HAS_DEBUGGER_KEYWORD */
> 
> #if JS_HAS_XML_SUPPORT
>       case TOK_DEFAULT:
>-        pn = NewParseNode(PN_UNARY, tc);
>+          pn = UnaryNode::create(tc);

Overindented by two spaces.

>+    void inline init(JSTokenType type, JSOp op, JSParseNodeArity arity) {
>+        pn_type = type;
>+        pn_op = op;
>+        pn_arity = arity;
>+        pn_parens = false;
>+        JS_ASSERT(!pn_used);
>+        JS_ASSERT(!pn_defn);
>+        pn_next = pn_link = NULL;
>+    }
>+
>+    /* used only by static create methods of subclasses */
>+    static JSParseNode *create(JSParseNodeArity arity, JSTreeContext *tc);
>+

Use private: before these two, and public: here to switch back to struct's default visibility? You should be able to make create private, at least.

r=me with these fixed.

/be
Attachment #430750 - Flags: review?(brendan) → review+
Addressed Brendan's remaining concerns. Also moved the controversial multi-arg BinaryNode::create to JSParseNode::newBinaryOrAppend since it's a) more descriptive of its behavior and b) clearer about the fact that it returns JSParseNode*, not js::BinaryNode*.

Should be ready to land.

Dave
Attachment #430750 - Attachment is obsolete: true
http://hg.mozilla.org/tracemonkey/rev/471665e9c47f

Sorry -- I tried hg qrefresh -m"..." -U "Dave Herman <dherman@mozilla.com>" but it didn't work. Hg gurus, what is the drill?

/be
Status: NEW → ASSIGNED
Whiteboard: fixed-in-tracemonkey
I always just tweak author once I have it committed locally "for real" (popped from the mq, and then "hg commit -U", then push) -- does hg qrefresh say that it takes -U?  hg qpush does, I think.
hg qrefresh --help says it takes --user (-U). I feel so misled!

Oh, time to manually update hg again. Grr, no selfupdate.

/be
Oh, it might.  Did the qtop entry not change author after you qrefreshed that way?  What version of hg?  What do the people in #hg say? :-)
(In reply to comment #4)
> >+namespace js {
> >+
> >+struct NullaryNode : public JSParseNode {
> >+    static inline NullaryNode *create(JSTreeContext *tc) {
> >+        return (NullaryNode *)JSParseNode::create(PN_NULLARY, tc);
> >+    }
> >+};
> >+
> >+struct UnaryNode : public JSParseNode {
> >+    static inline UnaryNode *create(JSTreeContext *tc) {
> >+        return (UnaryNode *)JSParseNode::create(PN_UNARY, tc);
> >+    }
> >+};
> >+
> >+struct BinaryNode : public JSParseNode {
> >+    static inline BinaryNode *create(JSTreeContext *tc) {
> >+        return (BinaryNode *)JSParseNode::create(PN_BINARY, tc);
> >+    }
> >+    static JSParseNode *createFlat(JSTokenType tt, JSOp op, JSParseNode *left, JSParseNode *right,
> >+                                   JSTreeContext *tc);
> >+};
> >+
> >+struct TernaryNode : public JSParseNode {
> >+    static inline TernaryNode *create(JSTreeContext *tc) {
> >+        return (TernaryNode *)JSParseNode::create(PN_TERNARY, tc);
> >+    }
> >+};
> >+
> >+struct ListNode : public JSParseNode {
> >+    static inline ListNode *create(JSTreeContext *tc) {
> >+        return (ListNode *)JSParseNode::create(PN_LIST, tc);
> >+    }
> >+};
> >+
> >+struct FunctionNode : public JSParseNode {
> >+    static inline FunctionNode *create(JSTreeContext *tc) {
> >+        return (FunctionNode *)JSParseNode::create(PN_FUNC, tc);
> >+    }
> >+};
> >+
> >+struct NameNode : public JSParseNode {
> >+    static NameNode *create(JSAtom *atom, JSTreeContext *tc);
> >+
> >+    void inline initCommon(JSTreeContext *tc);
> >+};
> >+
> >+struct NameSetNode : public JSParseNode {
> >+    static inline NameSetNode *create(JSTreeContext *tc) {
> >+        return (NameSetNode *)JSParseNode::create(PN_NAMESET, tc);
> >+    }
> >+};
> >+
> >+struct LexicalNode : public JSParseNode {
> >+    static inline LexicalNode *create(JSTreeContext *tc) {
> >+        return (LexicalNode *)JSParseNode::create(PN_NAME, tc);
> >+    }
> >+};
> >+
> >+} /* namespace js */
> 
> Beautiful (except for the Flat, no need for that and it makes lines overlong
> and looks like an odd duck without motivation).

There seems to be a considerable amount of duplication here.  Might it be useful to split out the basic create methods into a single template, to cut down on repetitive implementation slightly?

template<class T, JSParseNodeArity Arity>
struct SimpleParseNode : public JSParseNode {
  T* create(JSTreeContext *tc) {
    return (T*) JSParseNode::create(Arity, tc);
  }
};

struct FunctionNode : public SimpleParseNode<FunctionNode, PN_FUN> { };
struct LexicalNode : public SimpleParseNode<LexicalNode, PN_NAME> { };
...
> There seems to be a considerable amount of duplication here.  Might it be
> useful to split out the basic create methods into a single template, to cut
> down on repetitive implementation slightly?

Good call. Until my last change, BinaryNode was slightly different from the others, so the pattern was less obvious. I don't know if the different classes will start developing separate members later, but at least for now this seems like a clear win and easy to do.

Opened bug 551772.

Dave
For future reference, -u is what sets the given user.  -U sets the person running the command as the user.

dherman, I recommend putting "qnew = -U" in your .hgrc [defaults] section so all your mq patches would automatically have the right From: set.
http://hg.mozilla.org/mozilla-central/rev/471665e9c47f
Status: ASSIGNED → RESOLVED
Closed: 14 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: