[antlr-interest] short circuiting further evaluation

[Jane Eisenstein]

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