[antlr-interest] short circuiting further evaluation

Sun May 30 15:05:24 PDT 2010

You will reap orders of magnitude improvement with a certainty of 100% :-) Interpreters can be perfectly fine when performance is not a watchword, as soon as it is, then generate some code and execute it. If your target is fxied and only one platform, then LLVM may well be a better bet, but ASM is trivial to learn 9basically, write the Java class you want to generate (include all the things you will need to generate) and compile it, then ask ASM to build the Java that would generate that class - then you have all the code snippets you need to call from the AST walker and generate a Java class- you can get that going a lot quicker than your tree based interpreter, then you get the JIT advantage from the JVM for free. 

Of course, if you generated assembler directly, or generated C and compiled it, you would usually get an even better performing result.

Jim

> -----Original Message-----
> From: Jane Eisenstein [mailto:janee at softweave.com]
> Sent: Sunday, May 30, 2010 1:46 AM
> To: Jim Idle
> Cc: antlr-interest at antlr.org
> Subject: Re: [antlr-interest] short circuiting further evaluation
> 
> I have implemented evaluators for this little language that parse a
> token stream and others that parse an AST. The tree based evaluators
> are noticeably slower on a quad core Windows XP machine (though faster
> on dual core Intel-based Mac OS 10!). Versions using gated semantic
> predicates are marginally slower than those that don't use gated
> semantic predicates.
> 
> My goal is to evaluate thousands of these expressions as quickly as
> possible in a multi-threaded environment. How likely is it that
> generating Java byte code to be interpreted at run time would
> significantly increase the performance of those evaluations?
> 
> 
> Jane
> 
> On May 29, 2010, at 7:28 PM, Jim Idle wrote:
> 
> >> -----Original Message-----
> >> From: antlr-interest-bounces at antlr.org [mailto:antlr-interest-
> >> bounces at antlr.org] On Behalf Of Loring Craymer
> >> Sent: Saturday, May 29, 2010 3:26 PM
> >>
> >> Don't walk the tree to evaluate the expression; walk the tree to
> >> generate byte code and then interpret the byte code.  The overall
> >> problem then gets simpler and the resulting code runs faster.
> >>
> >
> > Especially as code generation is almost trivial these days with ASM
> or LLVM (depending on your needs). If you can live with the JVM, then
> just use ASM and let the VM deal with it.
> >
> > While writing a tree based interpreter is a useful experiment and
> learning aid, I think that overall, interpreting via the tree is
> somewhat awkward. Just my opinion of course.
> >
> > Jim
> >
> >
> >> --Loring
> >>
> >>
> >>
> >> ----- Original Message ----
> >>> From: Jane Eisenstein <janee at softweave.com>
> >>> To: "Farr, John" <john.farr at medtronic.com>
> >>> Cc: "antlr-interest at antlr.org" <antlr-interest at antlr.org>
> >>> Sent: Sat, May 29, 2010 2:15:56 PM
> >>> Subject: Re: [antlr-interest] short circuiting further evaluation
> >>>
> >>> Thanks. Using gated semantic predicates nicely simplifies the logic
> >> in each rule
> >>> (while doubling the number of rules).
> >>
> >> It doesn't stop the parse though
> >>> -- just the evaluation.
> >>
> >> Is there a clean way to determine the
> >>> condition's final result and return it without having to complete
> the
> >> parse of
> >>> the entire expression?
> >>
> >> Jane
> >>
> >>
> >> On May 28, 2010, at 10:22 AM,
> >>> Farr, John wrote:
> >>
> >>> The message I posted on April 8 with the subject
> >>> "Processing/traversing a rule -- dealing with conditionals" may
> help
> >>> you.
> >>>
> >>> --John
> >>>
> >>>
> >>> -----Original
> >>> Message-----
> >>> From:
> >>> href="mailto:antlr-interest-bounces at antlr.org">antlr-interest-
> >> bounces at antlr.org
> >>> [mailto:
> >>> href="mailto:antlr-interest-bounces at antlr.org">antlr-interest-
> >> bounces at antlr.org]
> >>> On Behalf Of Jane Eisenstein
> >>> Sent: Friday, May 28, 2010 7:47 AM
> >>>
> >>> To:
> >>> href="mailto:antlr-interest at antlr.org">antlr-interest at antlr.org
> >>>
> >>> Subject: [antlr-interest] short circuiting further evaluation
> >>>
> >>>
> >>> I'm working with a simple expression grammar:
> >>>
> >>>
> >>> condition:    conditional_expression  EOF
> >>>
> >>>    ;
> >>>
> >>> conditional_expression
> >>>
> >>>    :    conditional_term
> >>>
> >>>        (  OR conditional_expression
> >>> )?
> >>>    ;
> >>>
> >>> conditional_term
> >>>
> >>>    :    conditional_factor
> >>>
> >>>        ( AND conditional_term  )?
> >>>
> >>>    ;
> >>>
> >>> conditional_factor
> >>>
> >>>    :    conditional_primary
> >>>
> >>>    |    NOT conditional_primary
> >>>
> >>>    ;
> >>>
> >>> conditional_primary
> >>>
> >>>    : ID
> >>>    | LEFT_PAREN
> >>> conditional_expression RIGHT_PAREN
> >>>    ;
> >>>
> >>>
> >>> At runtime, ID tokens evaluate to either true or false. Once it is
> >> clear the
> >>> condition as a whole will evaluate to either true or false, I'd
> like
> >> to stop the
> >>> evaluation and return the value of the condition. So far, all I've
> >> managed to do
> >>> is short-circuit further ID evaluations once an upper level outcome
> >> is
> >>> know.
> >>>
> >>> Is there a way to short circuit the entire parse? I'm not
> >>> sure how to even tell it would be time to do so.
> >>>
> >>> Jane
> >>>
> >>>
> >>>
> >>>
> >>>
> >>>
> >>> List:
> >>> href="http://www.antlr.org/mailman/listinfo/antlr-interest"
> >> target=_blank
> >>>> http://www.antlr.org/mailman/listinfo/antlr-interest
> >>> Unsubscribe:
> >>>
> >>> target=_blank
> >>>> http://www.antlr.org/mailman/options/antlr-interest/your-email-
> >> address
> >>>
> >>>
> >>>
> >>> [CONFIDENTIALITY AND PRIVACY NOTICE]
> >>>
> >>>
> >>> Information transmitted by this email is proprietary to Medtronic
> and
> >> is
> >>> intended for use only by the individual or entity to which it is
> >> addressed, and
> >>> may contain information that is private, privileged, confidential
> or
> >> exempt from
> >>> disclosure under applicable law. If you are not the intended
> >> recipient or it
> >>> appears that this mail has been forwarded to you without proper
> >> authority, you
> >>> are notified that any use or dissemination of this information in
> any
> >> manner is
> >>> strictly prohibited. In such cases, please delete this mail from
> your
> >>> records.
> >>>
> >>> To view this notice in other languages you can either
> >>> select the following link or manually copy and paste the link into
> >> the address
> >>> bar of a web browser:
> >>> target=_blank >http://emaildisclaimer.medtronic.com
> >>>
> >>>
> >>
> >>
> >> List:
> >>> target=_blank
> >>>> http://www.antlr.org/mailman/listinfo/antlr-interest
> >> Unsubscribe:
> >>> href="http://www.antlr.org/mailman/options/antlr-interest/your-
> email-
> >> address"
> >>> target=_blank
> >>>> http://www.antlr.org/mailman/options/antlr-interest/your-email-
> >> address
> >>
> >>
> >>
> >>
> >>
> >> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> >> Unsubscribe: http://www.antlr.org/mailman/options/antlr-
> interest/your-
> >> email-address
> >
> >
> >
> >
> > List: http://www.antlr.org/mailman/listinfo/antlr-interest
> > Unsubscribe: http://www.antlr.org/mailman/options/antlr-
> interest/your-email-address