[antlr-interest] short circuiting further evaluation

Sun May 30 16:20:11 PDT 2010

The correct answer is more along the lines of "it depends".  Typically, string-based interpreters run about 50 times slower than compiled code; compiled machine code is about 2x slower than hand-coded assembler.  Threaded code (not to be confused with multi-threading) is somewhere in the middle.  Address-threaded code comes in two flavors:  direct threaded, which runs about 6x slower than native machine code (ignoring cache issues), and indirect threaded, which runs about 11x slower than native.  Byte code interpreters run about 20x slower than native code.  Cacheing affects performance, and threaded code gains considerably relative to compiled code because it requires fewer memory references to fetch the instruction stream and because the underlying virtual machine fits neatly in the instruction cache.

If the "thousands of expressions" need to be interpreted from strings on the fly, then writing a custom byte code interpreter (basically, a loop surrounding a case statement in which each case is an operation corresponding to a byte code) probably makes sense--it will cost some performance (in comparison to a string interpreter) for expressions that avoid branches, but wins when there are loops.  On the other hand, if the expressions are heavily re-used and typically packaged in standalone scripts, then it makes sense to translate to C and then compile.  If scripts are heavily reused either in dynamic fashion (lots of mixing and matching of scripts) or on multiple different hardware platforms, then Jim's suggestions apply.

--Loring

----- Original Message ----
> From: Jim Idle <jimi at temporal-wave.com>
> Cc: "antlr-interest at antlr.org" <antlr-interest at antlr.org>
> Sent: Sun, May 30, 2010 3:05:24 PM
> Subject: Re: [antlr-interest] short circuiting further evaluation
> 
> 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:
> href="mailto:janee at softweave.com">janee at softweave.com]
> Sent: Sunday, 
> May 30, 2010 1:46 AM
> To: Jim Idle
> Cc: 
> ymailto="mailto:antlr-interest at antlr.org" 
> href="mailto:antlr-interest at antlr.org">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: 
> ymailto="mailto:antlr-interest-bounces at antlr.org" 
> href="mailto:antlr-interest-bounces at antlr.org">antlr-interest-bounces at antlr.org 
> [mailto:antlr-interest-
> >> 
> href="mailto:bounces at antlr.org">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 <
> href="mailto:janee at softweave.com">janee at softweave.com>
> 
> >>> To: "Farr, John" <
> href="mailto:john.farr at medtronic.com">john.farr at medtronic.com>
> 
> >>> Cc: "
> href="mailto:antlr-interest at antlr.org">antlr-interest at antlr.org" <
> ymailto="mailto:antlr-interest at antlr.org" 
> href="mailto: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:
> ymailto="mailto:antlr-interest-bounces at antlr.org" 
> href="mailto:antlr-interest-bounces at antlr.org">antlr-interest-bounces at antlr.org">antlr-interest-
> 
> >> 
> href="mailto:bounces at antlr.org">bounces at antlr.org
> >>> 
> [mailto:
> >>> href="mailto:
> ymailto="mailto:antlr-interest-bounces at antlr.org" 
> href="mailto:antlr-interest-bounces at antlr.org">antlr-interest-bounces at antlr.org">antlr-interest-
> 
> >> 
> href="mailto:bounces at antlr.org">bounces at antlr.org]
> >>> On 
> Behalf Of Jane Eisenstein
> >>> Sent: Friday, May 28, 2010 7:47 
> AM
> >>>
> >>> To:
> >>> 
> href="mailto:
> href="mailto:antlr-interest at antlr.org">antlr-interest at antlr.org">
> ymailto="mailto:antlr-interest at antlr.org" 
> 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="
> href="http://www.antlr.org/mailman/listinfo/antlr-interest" target=_blank 
> >http://www.antlr.org/mailman/listinfo/antlr-interest"
> >> 
> target=_blank
> >>>> 
> href="http://www.antlr.org/mailman/listinfo/antlr-interest" target=_blank 
> >http://www.antlr.org/mailman/listinfo/antlr-interest
> >>> 
> Unsubscribe:
> >>>
> >>> target=_blank
> 
> >>>> 
> href="http://www.antlr.org/mailman/options/antlr-interest/your-email-" 
> 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 >
> href="http://emaildisclaimer.medtronic.com" target=_blank 
> >http://emaildisclaimer.medtronic.com
> >>>
> 
> >>>
> >>
> >>
> >> List:
> 
> >>> target=_blank
> >>>> 
> href="http://www.antlr.org/mailman/listinfo/antlr-interest" target=_blank 
> >http://www.antlr.org/mailman/listinfo/antlr-interest
> >> 
> Unsubscribe:
> >>> href="
> href="http://www.antlr.org/mailman/options/antlr-interest/your-" target=_blank 
> >http://www.antlr.org/mailman/options/antlr-interest/your-
> 
> email-
> >> address"
> >>> target=_blank
> 
> >>>> 
> href="http://www.antlr.org/mailman/options/antlr-interest/your-email-" 
> target=_blank 
> >http://www.antlr.org/mailman/options/antlr-interest/your-email-
> 
> >> address
> >>
> >>
> >>
> 
> >>
> >>
> >> List: 
> href="http://www.antlr.org/mailman/listinfo/antlr-interest" target=_blank 
> >http://www.antlr.org/mailman/listinfo/antlr-interest
> >> 
> Unsubscribe: 
> >http://www.antlr.org/mailman/options/antlr-
> interest/your-
> 
> >> email-address
> >
> >
> >
> 
> >
> > List: 
> href="http://www.antlr.org/mailman/listinfo/antlr-interest" target=_blank 
> >http://www.antlr.org/mailman/listinfo/antlr-interest
> > 
> Unsubscribe: 
> >http://www.antlr.org/mailman/options/antlr-
> 
> interest/your-email-address

List: 
> href="http://www.antlr.org/mailman/listinfo/antlr-interest" 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