X3 Parsing performances (updated)

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

X3 Parsing performances (updated)

Baptiste Wicht
Hi guys,

I have updated my compiler parser with the latest changes of X3 and here
are the last performance results I got:

Qi: 33.69s
X3: 20.22

This makes around 40% improvements compared to Qi (the Qi version uses a
generated static lexer and is quite optimized). In my last tests, months
ago, the improvements was almost 30%.

This is really great!

Do you have any more plans/ideas on how to improve performance further ?
Or any grammar implementation tips for more performance ?

Regards

Baptiste Wicht

P.S. The grammar can be seen here
https://github.com/wichtounet/eddic/blob/develop/src/parser_x3/SpiritParser.cpp

------------------------------------------------------------------------------
One dashboard for servers and applications across Physical-Virtual-Cloud
Widest out-of-the-box monitoring support with 50+ applications
Performance metrics, stats and reports that give you Actionable Insights
Deep dive visibility with transaction tracing using APM Insight.
http://ad.doubleclick.net/ddm/clk/290420510;117567292;y
_______________________________________________
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 (updated)

sehe
On 05/24/2015 12:06 AM, Baptiste Wicht wrote:
> Qi: 33.69s
> X3: 20.22
Are you comparing runtimes or compilation times?...

------------------------------------------------------------------------------
One dashboard for servers and applications across Physical-Virtual-Cloud
Widest out-of-the-box monitoring support with 50+ applications
Performance metrics, stats and reports that give you Actionable Insights
Deep dive visibility with transaction tracing using APM Insight.
http://ad.doubleclick.net/ddm/clk/290420510;117567292;y
_______________________________________________
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 (updated)

Joel de Guzman
In reply to this post by Baptiste Wicht
On 5/24/15 6:06 AM, Baptiste Wicht wrote:

> Hi guys,
>
> I have updated my compiler parser with the latest changes of X3 and here
> are the last performance results I got:
>
> Qi: 33.69s
> X3: 20.22
>
> This makes around 40% improvements compared to Qi (the Qi version uses a
> generated static lexer and is quite optimized). In my last tests, months
> ago, the improvements was almost 30%.
>
> This is really great!
>
> Do you have any more plans/ideas on how to improve performance further ?
> Or any grammar implementation tips for more performance ?

That is exciting news! I am guessing this is runtime performance? I'd
assume compile time speed would be even greater given that you are also
using the lexer. My CT tests give me 100% speedup for pure Qi vs X3.

My guess is that most of the time spent in parsing is in attributes
handling attributes. My plan is to look at complex hierarchical
data structures (maybe json) and see how they can be optimized
further. X3 does a lot of moves already (as compared to copies in
Qi), but the speedup that results from that until now has been
largely unproven.

Tip? use more moveable structures. Vectors and strings are actually
good since they have movable resources. But better yet, have them
use optimized allocators to mitigate heap usage. Use x3::variant.
They are move optimized, especially x3::forward_ast where a move
is just a pointer swap. x3::forward_ast might have its allocator
one day, for even tighter perf.

So there, performance, rather than more features, is the name of
the game for X3. It is hackable, so I welcome the community to
look at the code and see if there's something more that can be
optimized. This is *your* parser!

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


------------------------------------------------------------------------------
One dashboard for servers and applications across Physical-Virtual-Cloud
Widest out-of-the-box monitoring support with 50+ applications
Performance metrics, stats and reports that give you Actionable Insights
Deep dive visibility with transaction tracing using APM Insight.
http://ad.doubleclick.net/ddm/clk/290420510;117567292;y
_______________________________________________
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 (updated)

Baptiste Wicht
On Sun, May 24, 2015 at 12:17:43AM +0200, Seth wrote:
> On 05/24/2015 12:06 AM, Baptiste Wicht wrote:
> > Qi: 33.69s
> > X3: 20.22
> Are you comparing runtimes or compilation times?...

Sorry, I'm comparing runtime, this is the primary concern in my project.

On Sun, May 24, 2015 at 08:57:20AM +0800, Joel de Guzman wrote:

> On 5/24/15 6:06 AM, Baptiste Wicht wrote:
> > Hi guys,
> >
> > I have updated my compiler parser with the latest changes of X3 and here
> > are the last performance results I got:
> >
> > Qi: 33.69s
> > X3: 20.22
> >
> > This makes around 40% improvements compared to Qi (the Qi version uses a
> > generated static lexer and is quite optimized). In my last tests, months
> > ago, the improvements was almost 30%.
> >
> > This is really great!
> >
> > Do you have any more plans/ideas on how to improve performance further ?
> > Or any grammar implementation tips for more performance ?
>
> That is exciting news! I am guessing this is runtime performance? I'd
> assume compile time speed would be even greater given that you are also
> using the lexer. My CT tests give me 100% speedup for pure Qi vs X3.
Yes, runtime only. It takes 18s to compile the new grammar while it
takes 56s to compile the old grammar (without recompiling the lexer), it
is a huge improvement on that side as well.

> My guess is that most of the time spent in parsing is in attributes
> handling attributes. My plan is to look at complex hierarchical
> data structures (maybe json) and see how they can be optimized
> further. X3 does a lot of moves already (as compared to copies in
> Qi), but the speedup that results from that until now has been
> largely unproven.

I'll try to run some profiling to see if I can spot some bottlenecks.

> Tip? use more moveable structures. Vectors and strings are actually
> good since they have movable resources. But better yet, have them
> use optimized allocators to mitigate heap usage. Use x3::variant.
> They are move optimized, especially x3::forward_ast where a move
> is just a pointer swap. x3::forward_ast might have its allocator
> one day, for even tighter perf.

I'm already using x3::variant and x3::forward_ast, but I'll give a try
to optimized allocators.

> So there, performance, rather than more features, is the name of
> the game for X3. It is hackable, so I welcome the community to
> look at the code and see if there's something more that can be
> optimized. This is *your* parser!

After I have done some profiling, I'll try to take a look at the code.

Thanks for all the good job :)

Baptiste

------------------------------------------------------------------------------
One dashboard for servers and applications across Physical-Virtual-Cloud
Widest out-of-the-box monitoring support with 50+ applications
Performance metrics, stats and reports that give you Actionable Insights
Deep dive visibility with transaction tracing using APM Insight.
http://ad.doubleclick.net/ddm/clk/290420510;117567292;y
_______________________________________________
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 (updated)

sehe
On Sun, May 24, 2015, at 11:25 AM, Baptiste Wicht wrote:
> On Sun, May 24, 2015 at 12:17:43AM +0200, Seth wrote:
> > On 05/24/2015 12:06 AM, Baptiste Wicht wrote:
> > > Qi: 33.69s
> > > X3: 20.22
> > Are you comparing runtimes or compilation times?...
>
> Sorry, I'm comparing runtime, this is the primary concern in my project.
>

Wow. That's motivating to play with it

>
> Thanks for all the good job :)
>

Fully agree here!


------------------------------------------------------------------------------
One dashboard for servers and applications across Physical-Virtual-Cloud
Widest out-of-the-box monitoring support with 50+ applications
Performance metrics, stats and reports that give you Actionable Insights
Deep dive visibility with transaction tracing using APM Insight.
http://ad.doubleclick.net/ddm/clk/290420510;117567292;y
_______________________________________________
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 (updated)

Joel de Guzman
In reply to this post by Baptiste Wicht
On 5/24/15 5:25 PM, Baptiste Wicht wrote:

>> That is exciting news! I am guessing this is runtime performance? I'd
>> assume compile time speed would be even greater given that you are also
>> using the lexer. My CT tests give me 100% speedup for pure Qi vs X3.
>
> Yes, runtime only. It takes 18s to compile the new grammar while it
> takes 56s to compile the old grammar (without recompiling the lexer), it
> is a huge improvement on that side as well.

Wow! 3x compile time speedup! That's cool!

Now, 40% X3 speedup against a lexer-based Qi parser confirms what I've
been saying all along: that you really do not need a lexer ;-)

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


------------------------------------------------------------------------------
One dashboard for servers and applications across Physical-Virtual-Cloud
Widest out-of-the-box monitoring support with 50+ applications
Performance metrics, stats and reports that give you Actionable Insights
Deep dive visibility with transaction tracing using APM Insight.
http://ad.doubleclick.net/ddm/clk/290420510;117567292;y
_______________________________________________
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 (updated)

Orient
In reply to this post by Joel de Guzman
Joel de Guzman wrote
On 5/24/15 6:06 AM, Baptiste Wicht wrote:
> Hi guys,
>
> I have updated my compiler parser with the latest changes of X3 and here
> are the last performance results I got:
>
> Qi: 33.69s
> X3: 20.22
>
> This makes around 40% improvements compared to Qi (the Qi version uses a
> generated static lexer and is quite optimized). In my last tests, months
> ago, the improvements was almost 30%.
>
> This is really great!
>
> Do you have any more plans/ideas on how to improve performance further ?
> Or any grammar implementation tips for more performance ?

That is exciting news! I am guessing this is runtime performance? I'd
assume compile time speed would be even greater given that you are also
using the lexer. My CT tests give me 100% speedup for pure Qi vs X3.

My guess is that most of the time spent in parsing is in attributes
handling attributes. My plan is to look at complex hierarchical
data structures (maybe json) and see how they can be optimized
further. X3 does a lot of moves already (as compared to copies in
Qi), but the speedup that results from that until now has been
largely unproven.

Tip? use more moveable structures. Vectors and strings are actually
good since they have movable resources. But better yet, have them
use optimized allocators to mitigate heap usage. Use x3::variant.
They are move optimized, especially x3::forward_ast where a move
is just a pointer swap. x3::forward_ast might have its allocator
one day, for even tighter perf.

So there, performance, rather than more features, is the name of
the game for X3. It is hackable, so I welcome the community to
look at the code and see if there's something more that can be
optimized. This is *your* parser!

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


------------------------------------------------------------------------------
One dashboard for servers and applications across Physical-Virtual-Cloud
Widest out-of-the-box monitoring support with 50+ applications
Performance metrics, stats and reports that give you Actionable Insights
Deep dive visibility with transaction tracing using APM Insight.
http://ad.doubleclick.net/ddm/clk/290420510;117567292;y
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
I propose my version of C++14 variant class, which is move-awared. Library contain multivisitor apply_visitor() (also move-awared (moreover, it distinct referenceness not only visitable parametres, but visitor's `operator ()` cv-qualifier too)), reference_wrapper (like x3::forward_ast), delayed apply_visitor(), compose_visitors() (like x3::lambda_visitor). Internally variant uses std::unique_ptr, along with reference_wrapper class (but in latter - double inderection (it is suboptimal, but unavoidable for incomplete types anyways)).
Reply | Threaded
Open this post in threaded view
|

Re: X3 Parsing performances (updated)

Mario Lang
In reply to this post by Baptiste Wicht
Baptiste Wicht <[hidden email]> writes:

> Do you have any more plans/ideas on how to improve performance further ?
> Or any grammar implementation tips for more performance ?

While skimming your code, I noticed that you are still using
line_pos_iterator.  This is no longer necessary, as x3::error_handler
can do the line/column calculation on its own now.  So you can use
straight std::string::const_iterator, no need for a wrapper iterator.

--
CYa,
  ⡍⠁⠗⠊⠕

------------------------------------------------------------------------------
One dashboard for servers and applications across Physical-Virtual-Cloud
Widest out-of-the-box monitoring support with 50+ applications
Performance metrics, stats and reports that give you Actionable Insights
Deep dive visibility with transaction tracing using APM Insight.
http://ad.doubleclick.net/ddm/clk/290420510;117567292;y
_______________________________________________
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 (updated)

Baptiste Wicht
On Mon, May 25, 2015 at 03:09:05PM +0200, Mario Lang wrote:
> Baptiste Wicht <[hidden email]> writes:
>
> > Do you have any more plans/ideas on how to improve performance further ?
> > Or any grammar implementation tips for more performance ?
>
> While skimming your code, I noticed that you are still using
> line_pos_iterator.  This is no longer necessary, as x3::error_handler
> can do the line/column calculation on its own now.  So you can use
> straight std::string::const_iterator, no need for a wrapper iterator.

Awesome! I didn't know the support was integrated into X3.

That's a very nice catch. The overhead was huge.

The time is now down to 15.83s (from 20.22s). Compared to Qi (33.69s) it
is now a 53% improvement :)

I hope I have made other mistakes like that :P

Thanks a lot Mario.

------------------------------------------------------------------------------
One dashboard for servers and applications across Physical-Virtual-Cloud
Widest out-of-the-box monitoring support with 50+ applications
Performance metrics, stats and reports that give you Actionable Insights
Deep dive visibility with transaction tracing using APM Insight.
http://ad.doubleclick.net/ddm/clk/290420510;117567292;y
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general

attachment0 (817 bytes) Download Attachment