[antlr-interest] short circuiting further evaluation

Loring Craymer lgcraymer at yahoo.com
Sun May 30 19:04:49 PDT 2010 

Is your language embedded in an application under test, or just used for hardware testing?  Either way, it is easier to generate code for interpretation than it is to interpret via tree walk, and most of the effort is just to reorganize code that you have already written.

--Loring




----- Original Message ----
> From: Jane Eisenstein <janee at softweave.com>
> To: Loring Craymer <lgcraymer at yahoo.com>
> Cc: Jim Idle <jimi at temporal-wave.com>; "antlr-interest at antlr.org" <antlr-interest at antlr.org>
> Sent: Sun, May 30, 2010 5:08:12 PM
> Subject: Re: [antlr-interest] short circuiting further evaluation
> 
> Thank you all. This discussion is both interesting and getting beyond my depth. 
> 

The expressions are heavily re-used, but can be changed dynamically and 
> must run on multiple hardware platforms. 

In testing, interpreted 
> expressions are running 21-24x slower than equivalent existing code. However, 
> each test has other over head several times more costly than the time taken to 
> interpret its expression. Introducing an expression language will allow a 
> smaller number of tests to be written and should reduce the total time of each 
> run -- even without generating byte code. Even without implementing true short 
> circuiting. :-)

Jane


On May 30, 2010, at 7:20 PM, Loring 
> Craymer wrote:

> 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 <
> ymailto="mailto:jimi at temporal-wave.com" 
> href="mailto:jimi at temporal-wave.com">jimi at temporal-wave.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: 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:
> ymailto="mailto:janee at softweave.com" 
> href="mailto:janee at softweave.com">janee at softweave.com">
> ymailto="mailto:janee at softweave.com" 
> href="mailto:janee at softweave.com">janee at softweave.com]
>> Sent: 
> Sunday, 
>> May 30, 2010 1:46 AM
>> To: Jim Idle
>> 
> Cc: 
>> ymailto="mailto:
> href="mailto:antlr-interest at antlr.org">antlr-interest at antlr.org" 
> 
>> 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: 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:
> ymailto="mailto:antlr-interest-bounces at antlr.org" 
> href="mailto:antlr-interest-bounces at antlr.org">antlr-interest-bounces at antlr.org" 
> 
>> href="mailto:
> href="mailto:antlr-interest-bounces at antlr.org">antlr-interest-bounces at antlr.org">
> 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:
> href="mailto:bounces at antlr.org">bounces at antlr.org">
> ymailto="mailto:bounces at antlr.org" 
> 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:
> href="mailto:janee at softweave.com">janee at softweave.com">
> ymailto="mailto:janee at softweave.com" 
> href="mailto:janee at softweave.com">janee at softweave.com>
>> 
> 
>>>>> To: "Farr, John" <
>> href="mailto:
> ymailto="mailto:john.farr at medtronic.com" 
> href="mailto:john.farr at medtronic.com">john.farr at medtronic.com">
> ymailto="mailto:john.farr at medtronic.com" 
> href="mailto:john.farr at medtronic.com">john.farr at medtronic.com>
>> 
> 
>>>>> Cc: "
>> href="mailto:
> ymailto="mailto:antlr-interest at antlr.org" 
> 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" 
> <
>> ymailto="mailto:
> href="mailto:antlr-interest at antlr.org">antlr-interest at antlr.org" 
> 
>> 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>
>> 
> 
>>>>> 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:
> ymailto="mailto:antlr-interest-bounces at antlr.org" 
> href="mailto:antlr-interest-bounces at antlr.org">antlr-interest-bounces at antlr.org" 
> 
>> href="mailto:
> href="mailto:antlr-interest-bounces at antlr.org">antlr-interest-bounces at antlr.org">
> 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:
> ymailto="mailto:bounces at antlr.org" 
> href="mailto:bounces at antlr.org">bounces at antlr.org">
> ymailto="mailto:bounces at antlr.org" 
> href="mailto:bounces at antlr.org">bounces at antlr.org
>>>>> 
> 
>> [mailto:
>>>>> href="mailto:
>> 
> ymailto="mailto:
> href="mailto:antlr-interest-bounces at antlr.org">antlr-interest-bounces at antlr.org" 
> 
>> href="mailto:
> href="mailto:antlr-interest-bounces at antlr.org">antlr-interest-bounces at antlr.org">
> 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:
> ymailto="mailto:bounces at antlr.org" 
> href="mailto:bounces at antlr.org">bounces at antlr.org">
> ymailto="mailto:bounces at antlr.org" 
> 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:
> ymailto="mailto:antlr-interest at antlr.org" 
> 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">
>> 
> ymailto="mailto:
> href="mailto:antlr-interest at antlr.org">antlr-interest at antlr.org" 
> 
>> 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="
> href="http://www.antlr.org/mailman/listinfo/antlr-interest" target=_blank 
> >http://www.antlr.org/mailman/listinfo/antlr-interest" target=_blank 
> 
>>> 
> target=_blank 
> >http://www.antlr.org/mailman/listinfo/antlr-interest"
>>>> 
> 
>> target=_blank
>>>>>> 
>> href="
> href="http://www.antlr.org/mailman/listinfo/antlr-interest" target=_blank 
> >http://www.antlr.org/mailman/listinfo/antlr-interest" target=_blank 
> 
>>> 
> target=_blank 
> >http://www.antlr.org/mailman/listinfo/antlr-interest
>>>>> 
> 
>> Unsubscribe:
>>>>> 
>>>>> 
> target=_blank
>> 
>>>>>> 
>> href="
> href="http://www.antlr.org/mailman/options/antlr-interest/your-email-" 
> target=_blank 
> >http://www.antlr.org/mailman/options/antlr-interest/your-email-" 
> 
>> 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="
> href="http://emaildisclaimer.medtronic.com" target=_blank 
> >http://emaildisclaimer.medtronic.com" target=_blank 
>>> 
> href="http://emaildisclaimer.medtronic.com" target=_blank 
> >http://emaildisclaimer.medtronic.com
>>>>> 
>> 
> 
>>>>> 
>>>> 
>>>> 
> 
>>>> List:
>> 
>>>>> 
> target=_blank
>>>>>> 
>> href="
> href="http://www.antlr.org/mailman/listinfo/antlr-interest" target=_blank 
> >http://www.antlr.org/mailman/listinfo/antlr-interest" target=_blank 
> 
>>> 
> target=_blank 
> >http://www.antlr.org/mailman/listinfo/antlr-interest
>>>> 
> 
>> Unsubscribe:
>>>>> href="
>> href="
> href="http://www.antlr.org/mailman/options/antlr-interest/your-" target=_blank 
> >http://www.antlr.org/mailman/options/antlr-interest/your-" target=_blank 
> 
>>> 
> 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="
> href="http://www.antlr.org/mailman/options/antlr-interest/your-email-" 
> target=_blank 
> >http://www.antlr.org/mailman/options/antlr-interest/your-email-" 
> 
>> 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="
> href="http://www.antlr.org/mailman/listinfo/antlr-interest" target=_blank 
> >http://www.antlr.org/mailman/listinfo/antlr-interest" target=_blank 
> 
>>> 
> target=_blank 
> >http://www.antlr.org/mailman/listinfo/antlr-interest
>>>> 
> 
>> Unsubscribe: 
>>> 
> href="http://www.antlr.org/mailman/options/antlr-" target=_blank 
> >http://www.antlr.org/mailman/options/antlr-
>> 
> interest/your-
>> 
>>>> email-address
>>> 
> 
>>> 
>>> 
>> 
>>> 
>>> 
> List: 
>> href="
> href="http://www.antlr.org/mailman/listinfo/antlr-interest" target=_blank 
> >http://www.antlr.org/mailman/listinfo/antlr-interest" target=_blank 
> 
>>> 
> target=_blank 
> >http://www.antlr.org/mailman/listinfo/antlr-interest
>>> 
> 
>> Unsubscribe: 
>>> 
> href="http://www.antlr.org/mailman/options/antlr-" target=_blank 
> >http://www.antlr.org/mailman/options/antlr-
>> 
>> 
> interest/your-email-address
> 
> 
> 
> 
> 
> 
> List: 
>> href="
> href="http://www.antlr.org/mailman/listinfo/antlr-interest" target=_blank 
> >http://www.antlr.org/mailman/listinfo/antlr-interest" target=_blank 
> 
>>> 
> target=_blank >http://www.antlr.org/mailman/listinfo/antlr-interest
> 
> Unsubscribe: 
>> href="
> 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" 
> 
>> target=_blank 
>>> 
> 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: 
> 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

More information about the antlr-interest mailing list