X3 Parsing Performances

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

X3 Parsing Performances

Baptiste Wicht
Hi,

I finally had time to complete the X3 grammar. Now the grammar is
complete and can parse all my samples :)

Here are the first results when benchmarking the parsing time:

qi: 32.72s
x3: 23.37

Note1: the qi version was highly optimized

Note2: From profiling, I get that about 20% of the time is spent skipping,
almost 10% in the symbols parser and about 5% in annotating the AST
(x3::position_tagged and annotation_base from calc9).

I think it is not a bad result to start with, almost 30% improvement. I
was afraid that the lack of a lexer would cause the performance to be
slower.

However, I'm pretty sure my grammar can still be optimized.

Do you have any tricks on X3 performance tuning ?

Thanks

Baptiste Wicht

P.S. For those interested in taking a look, the grammar (warning: large
block of monolithic code ahead) is here:
https://github.com/wichtounet/eddic/blob/feature/spirit_x3/src/parser_x3/SpiritParser.cpp 

------------------------------------------------------------------------------
Want excitement?
Manually upgrade your production database.
When you want reliability, choose Perforce
Perforce version control. Predictably reliable.
http://pubads.g.doubleclick.net/gampad/clk?id=157508191&iu=/4140/ostg.clktrk
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|

Re: X3 Parsing Performances

Joel de Guzman
On 9/13/14, 9:27 PM, Baptiste Wicht wrote:

> Hi,
>
> I finally had time to complete the X3 grammar. Now the grammar is
> complete and can parse all my samples :)
>
> Here are the first results when benchmarking the parsing time:
>
> qi: 32.72s
> x3: 23.37
>
> Note1: the qi version was highly optimized
>
> Note2: From profiling, I get that about 20% of the time is spent skipping,
> almost 10% in the symbols parser and about 5% in annotating the AST
> (x3::position_tagged and annotation_base from calc9).
>
> I think it is not a bad result to start with, almost 30% improvement. I
> was afraid that the lack of a lexer would cause the performance to be
> slower.

Interesting results! Do I understand correctly that the previous Qi
parser uses the lexer and the X3 one does not?

BTW, how about compile time?

> However, I'm pretty sure my grammar can still be optimized.
>
> Do you have any tricks on X3 performance tuning ?

I'm on the road right now, I won't be able to look at the code
until next week. Perhaps some other folks here can chime in.

Anyway, it might be a good idea to start thinking about memoization,
techniques, perhaps starting with the skipper.


Regards,
--
Joel de Guzman
http://www.ciere.com
http://boost-spirit.com
http://www.cycfi.com/


------------------------------------------------------------------------------
Want excitement?
Manually upgrade your production database.
When you want reliability, choose Perforce
Perforce version control. Predictably reliable.
http://pubads.g.doubleclick.net/gampad/clk?id=157508191&iu=/4140/ostg.clktrk
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|

Re: X3 Parsing Performances

Baptiste Wicht
On Sun, Sep 14, 2014 at 07:22:26PM +0800, Joel de Guzman wrote:
> On 9/13/14, 9:27 PM, Baptiste Wicht wrote:
> > Here are the first results when benchmarking the parsing time:
> >
> > qi: 32.72s
> > x3: 23.37
>
> Interesting results! Do I understand correctly that the previous Qi
> parser uses the lexer and the X3 one does not?

Yes, the qi version used a generated static lexer.
 
> BTW, how about compile time?

The new grammar takes about 15-16 seconds to compile. The previous
grammar was split in several files and probably took something like 3 to
4 minutes to compile with one thread.

> > However, I'm pretty sure my grammar can still be optimized.
> >
> > Do you have any tricks on X3 performance tuning ?

> I'm on the road right now, I won't be able to look at the code
> until next week. Perhaps some other folks here can chime in.
>
> Anyway, it might be a good idea to start thinking about memoization,
> techniques, perhaps starting with the skipper.

Memoization would probably be an interesting improvement.

I'd be glad to help with the testing ;)

Baptiste

------------------------------------------------------------------------------
Want excitement?
Manually upgrade your production database.
When you want reliability, choose Perforce
Perforce version control. Predictably reliable.
http://pubads.g.doubleclick.net/gampad/clk?id=157508191&iu=/4140/ostg.clktrk
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general

attachment0 (817 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: X3 Parsing Performances

Joel de Guzman
On 9/14/14, 8:48 PM, Baptiste Wicht wrote:

> On Sun, Sep 14, 2014 at 07:22:26PM +0800, Joel de Guzman wrote:
>> On 9/13/14, 9:27 PM, Baptiste Wicht wrote:
>>> Here are the first results when benchmarking the parsing time:
>>>
>>> qi: 32.72s
>>> x3: 23.37
>>
>> Interesting results! Do I understand correctly that the previous Qi
>> parser uses the lexer and the X3 one does not?
>
> Yes, the qi version used a generated static lexer.
>
>> BTW, how about compile time?
>
> The new grammar takes about 15-16 seconds to compile. The previous
> grammar was split in several files and probably took something like 3 to
> 4 minutes to compile with one thread.
>
>>> However, I'm pretty sure my grammar can still be optimized.
>>>
>>> Do you have any tricks on X3 performance tuning ?
>
>> I'm on the road right now, I won't be able to look at the code
>> until next week. Perhaps some other folks here can chime in.
>>
>> Anyway, it might be a good idea to start thinking about memoization,
>> techniques, perhaps starting with the skipper.
>
> Memoization would probably be an interesting improvement.
>
> I'd be glad to help with the testing ;)

Wonderful! But before we proceed, let's work out these issues:

  * 1. Some structures have a fake_ field. This field is only here to make single-element
structures works :(
  * 2. start_instruction rule is only here to make type deduction works :(
  * 3. The ugly end of primary_value rule (the 3 parts with ()) is only here to overcome
limitations in type deduction


Regards,
--
Joel de Guzman
http://www.ciere.com
http://boost-spirit.com
http://www.cycfi.com/


------------------------------------------------------------------------------
Want excitement?
Manually upgrade your production database.
When you want reliability, choose Perforce
Perforce version control. Predictably reliable.
http://pubads.g.doubleclick.net/gampad/clk?id=157508191&iu=/4140/ostg.clktrk
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|

Re: X3 Parsing Performances

Baptiste Wicht
On Sun, Sep 14, 2014 at 11:09:44PM +0800, Joel de Guzman wrote:
> Wonderful! But before we proceed, let's work out these issues:
>
>   * 1. Some structures have a fake_ field. This field is only here to make single-element
> structures works :(
>   * 2. start_instruction rule is only here to make type deduction works :(
>   * 3. The ugly end of primary_value rule (the 3 parts with ()) is only here to overcome
> limitations in type deduction

I'd be glad to get rid of these "problems" :)

But, I'm not sure that all of them can be worked out since you explained
that type deduction works a bit differently in X3.

------------------------------------------------------------------------------
Want excitement?
Manually upgrade your production database.
When you want reliability, choose Perforce
Perforce version control. Predictably reliable.
http://pubads.g.doubleclick.net/gampad/clk?id=157508191&iu=/4140/ostg.clktrk
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general

attachment0 (817 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: X3 Parsing Performances

Baptiste Wicht
In reply to this post by Joel de Guzman
On Sun, Sep 14, 2014 at 11:09:44PM +0800, Joel de Guzman wrote:

> On 9/14/14, 8:48 PM, Baptiste Wicht wrote:
> > On Sun, Sep 14, 2014 at 07:22:26PM +0800, Joel de Guzman wrote:
> >> On 9/13/14, 9:27 PM, Baptiste Wicht wrote:
> >>> Here are the first results when benchmarking the parsing time:
> >>>
> >>> qi: 32.72s
> >>> x3: 23.37
> >>
> >> Interesting results! Do I understand correctly that the previous Qi
> >> parser uses the lexer and the X3 one does not?
> >
> > Yes, the qi version used a generated static lexer.
> >
> >> BTW, how about compile time?
> >
> > The new grammar takes about 15-16 seconds to compile. The previous
> > grammar was split in several files and probably took something like 3 to
> > 4 minutes to compile with one thread.
> >
> >>> However, I'm pretty sure my grammar can still be optimized.
> >>>
> >>> Do you have any tricks on X3 performance tuning ?
> >
> >> I'm on the road right now, I won't be able to look at the code
> >> until next week. Perhaps some other folks here can chime in.
> >>
> >> Anyway, it might be a good idea to start thinking about memoization,
> >> techniques, perhaps starting with the skipper.
> >
> > Memoization would probably be an interesting improvement.
> >
> > I'd be glad to help with the testing ;)
>
> Wonderful! But before we proceed, let's work out these issues:
>
>   * 1. Some structures have a fake_ field. This field is only here to make single-element
> structures works :(
>   * 2. start_instruction rule is only here to make type deduction works :(
>   * 3. The ugly end of primary_value rule (the 3 parts with ()) is only here to overcome
> limitations in type deduction
Hi Joel,

Do you have any idea on how to work out theses issues, if they can be ?

------------------------------------------------------------------------------
Meet PCI DSS 3.0 Compliance Requirements with EventLog Analyzer
Achieve PCI DSS 3.0 Compliant Status with Out-of-the-box PCI DSS Reports
Are you Audit-Ready for PCI DSS 3.0 Compliance? Download White paper
Comply to PCI DSS 3.0 Requirement 10 and 11.5 with EventLog Analyzer
http://pubads.g.doubleclick.net/gampad/clk?id=154622311&iu=/4140/ostg.clktrk
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general

attachment0 (817 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: X3 Parsing Performances

Joel de Guzman
On 9/25/14, 5:05 PM, Baptiste Wicht wrote:

>>    * 1. Some structures have a fake_ field. This field is only here to make single-element
>> structures works :(
>>    * 2. start_instruction rule is only here to make type deduction works :(
>>    * 3. The ugly end of primary_value rule (the 3 parts with ()) is only here to overcome
>> limitations in type deduction
>
> Hi Joel,
>
> Do you have any idea on how to work out theses issues, if they can be ?

I hope so. This is high in my todo list. It would help a lot (read: make
my life easier) if you can provide some minimal cpp code for each of these
for my testing :=-)

Regards,
--
Joel de Guzman
http://www.ciere.com
http://boost-spirit.com
http://www.cycfi.com/


------------------------------------------------------------------------------
Meet PCI DSS 3.0 Compliance Requirements with EventLog Analyzer
Achieve PCI DSS 3.0 Compliant Status with Out-of-the-box PCI DSS Reports
Are you Audit-Ready for PCI DSS 3.0 Compliance? Download White paper
Comply to PCI DSS 3.0 Requirement 10 and 11.5 with EventLog Analyzer
http://pubads.g.doubleclick.net/gampad/clk?id=154622311&iu=/4140/ostg.clktrk
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|

Re: X3 Parsing Performances

Baptiste Wicht
On Thu, Sep 25, 2014 at 06:03:14PM +0800, Joel de Guzman wrote:

> On 9/25/14, 5:05 PM, Baptiste Wicht wrote:
>
> >>    * 1. Some structures have a fake_ field. This field is only here to make single-element
> >> structures works :(
> >>    * 2. start_instruction rule is only here to make type deduction works :(
> >>    * 3. The ugly end of primary_value rule (the 3 parts with ()) is only here to overcome
> >> limitations in type deduction
> >
> > Hi Joel,
> >
> > Do you have any idea on how to work out theses issues, if they can be ?
>
> I hope so. This is high in my todo list. It would help a lot (read: make
> my life easier) if you can provide some minimal cpp code for each of these
> for my testing :=-)
I will try my best to make you some nice test cases ;) Probably around
this week-end.

------------------------------------------------------------------------------
Meet PCI DSS 3.0 Compliance Requirements with EventLog Analyzer
Achieve PCI DSS 3.0 Compliant Status with Out-of-the-box PCI DSS Reports
Are you Audit-Ready for PCI DSS 3.0 Compliance? Download White paper
Comply to PCI DSS 3.0 Requirement 10 and 11.5 with EventLog Analyzer
http://pubads.g.doubleclick.net/gampad/clk?id=154622311&iu=/4140/ostg.clktrk
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general

attachment0 (817 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: X3 Parsing Performances

Baptiste Wicht
In reply to this post by Joel de Guzman
On Thu, Sep 25, 2014 at 06:03:14PM +0800, Joel de Guzman wrote:

> On 9/25/14, 5:05 PM, Baptiste Wicht wrote:
>
> >>    * 1. Some structures have a fake_ field. This field is only here to make single-element
> >> structures works :(
> >>    * 2. start_instruction rule is only here to make type deduction works :(
> >>    * 3. The ugly end of primary_value rule (the 3 parts with ()) is only here to overcome
> >> limitations in type deduction
> >
> > Hi Joel,
> >
> > Do you have any idea on how to work out theses issues, if they can be ?
>
> I hope so. This is high in my todo list. It would help a lot (read: make
> my life easier) if you can provide some minimal cpp code for each of these
> for my testing :=-)
Here we go :)

All the test cases are in this repository:
https://github.com/wichtounet/spirit_x3_tests 

The lines starting with //SOLUTION indicate a temporary solution that I
do not find elegant and it is perhaps sometimes not efficient as well..

not_nice_1.cpp
--------------

The struct else_ has only a std::vector as members. To make it work, I
have to add a x3::unused_type fake_ member.

not_nice_2.cpp
--------------

null is an empty struct. To make it work, I have to use x3::eps.

P.S. This is by far the least important of the four test cases. It was
already the case in qi ;)

not_nice_3.cpp
--------------

We cannot assign itself to a variant rule, we have to assign a member of
the variant (sorry, wasn't able to phrase that better...)

not_nice_4.cpp
--------------

A member of the variant cannot be used to an attribute of the variant
type with boost optional. If I use an intermediate rule it works and
with std::vector it works too.



I hope that helps a bit. Don't hesitate if you need more information or
other test cases.

------------------------------------------------------------------------------
Meet PCI DSS 3.0 Compliance Requirements with EventLog Analyzer
Achieve PCI DSS 3.0 Compliant Status with Out-of-the-box PCI DSS Reports
Are you Audit-Ready for PCI DSS 3.0 Compliance? Download White paper
Comply to PCI DSS 3.0 Requirement 10 and 11.5 with EventLog Analyzer
http://pubads.g.doubleclick.net/gampad/clk?id=154622311&iu=/4140/ostg.clktrk
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general

attachment0 (817 bytes) Download Attachment