Quantcast

Scala performance

classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Scala performance

jorge.ortiz@gmail.com
As mentioned in my previous email, I wrote a parser for Apache Thrift using
Parboiled Scala.

Benchmarking the parser, I noticed a lot of time spent calling
getStackTrace in getCurrentRuleMethod. Getting stack traces on the JVM is
fairly expensive (the JVM aggressively inlines method calls, so when you
ask for a stack trace it needs to materialize the stack it's gotten rid
of), so I set out to avoid getCurrentRuleMethod.

First I switched to labeled rules. That is, I refactored rules like:

  def Foo = rule { ... }

to:

  def Foo = rule("Foo") { ... }

This got about a ~2x speedup, but I hadn't realized that even labeled rules
call getCurrentRuleMethod, so I was still spending a lot of time creating
stack traces. Next I switched my rules from defs to lazy vals:

  lazy val Foo = rule("Foo") { ... }

(Normal vals were not an option because I have some circular references
between rules.)

This way stack traces were only getting created once per rule per parser,
rather than once per rule per invocation. The two changes combined were
about a ~4x speedup. However, I'm parsing a lot of files (~300 files),
which means creating a lot of parsers (one per file), which means a lot of
stack traces.

Finally I pulled in all the private rule-creating code from Parsers.scala
into my own source, and overrode it to use the label name as the key for
the cache, rather than the StackTraceElement. This gave me about ~18x
speedup over the original code. Parsing my ~300 files now takes ~700ms
instead of ~13,000ms.

I'm sure I can get further performance improvements from left-factoring my
grammar, etc. But just removing stack trace creation gave pretty
significant performance improvements.

Is there any chance of rewriting Parser.scala to not rely on stack traces?
At the very least, there should be an option to avoid them if the user
provides a unique string for every rule. (As it is, I had to duplicate a
lot of code that was marked private in Parsers.scala.)

Thanks,

--j

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Scala performance

mathias
Administrator
Jorge,

thanks for your feedback!
In all our own applications we were never re-creating parsers, so we never hit the performance problem you are experiencing.
In fact, is it really necessary to re-create your parser's rule tree over and over again?

If you write your parser in a way that avoids side-effecting beyond using the value stack you should be able to re-use your rule tree completely, thereby circumventing all performance issues of rule creation!

(This is what we do, for example, in spray.io, which also relies on parboiled for parsing HTTP headers into their high-level model classes.)

> Is there any chance of rewriting Parser.scala to not rely on stack traces?


There is currently a push for a V2.0 version of parboiled ongoing:
https://github.com/sirthias/parboiled2

This project has been accepted as a Google Summer of Code 2013 project, so we have some momentum behind it.
The idea is a complete and Scala-only rewrite of parboiled, which relies on Scala 2.10 compiler macros to directly transform your rule definitions into the respective bytecode *at compile-time*. So no more interpreting of a rule tree at run time against an input. The resulting parser should be just as fast as a hand-written one, just much easier to write/maintain and with better error messages.

We'll keep the DSL more or less identical to parboiled 1.x, so migration should be quite easy.

Since we'd like to use parboiled2 in several other projects ourselves (most importantly in spray) we are eager to get it done. The first version should be out before summer is over. If you want I can let you know when a first milestone is ready.

Cheers,
Mathias

PS: The only feature that we probably will not include in parboiled2 from the start is the (equivalent) of the RecoveringParseRunner.

---
[hidden email]
http://www.parboiled.org

On 21.06.2013, at 08:34, "[hidden email] [via parboiled users]" <[hidden email]> wrote:

>
>
> As mentioned in my previous email, I wrote a parser for Apache Thrift using
> Parboiled Scala.
>
> Benchmarking the parser, I noticed a lot of time spent calling
> getStackTrace in getCurrentRuleMethod. Getting stack traces on the JVM is
> fairly expensive (the JVM aggressively inlines method calls, so when you
> ask for a stack trace it needs to materialize the stack it's gotten rid
> of), so I set out to avoid getCurrentRuleMethod.
>
> First I switched to labeled rules. That is, I refactored rules like:
>
>  def Foo = rule { ... }
>
> to:
>
>  def Foo = rule("Foo") { ... }
>
> This got about a ~2x speedup, but I hadn't realized that even labeled rules
> call getCurrentRuleMethod, so I was still spending a lot of time creating
> stack traces. Next I switched my rules from defs to lazy vals:
>
>  lazy val Foo = rule("Foo") { ... }
>
> (Normal vals were not an option because I have some circular references
> between rules.)
>
> This way stack traces were only getting created once per rule per parser,
> rather than once per rule per invocation. The two changes combined were
> about a ~4x speedup. However, I'm parsing a lot of files (~300 files),
> which means creating a lot of parsers (one per file), which means a lot of
> stack traces.
>
> Finally I pulled in all the private rule-creating code from Parsers.scala
> into my own source, and overrode it to use the label name as the key for
> the cache, rather than the StackTraceElement. This gave me about ~18x
> speedup over the original code. Parsing my ~300 files now takes ~700ms
> instead of ~13,000ms.
>
> I'm sure I can get further performance improvements from left-factoring my
> grammar, etc. But just removing stack trace creation gave pretty
> significant performance improvements.
>
> Is there any chance of rewriting Parser.scala to not rely on stack traces?
> At the very least, there should be an option to avoid them if the user
> provides a unique string for every rule. (As it is, I had to duplicate a
> lot of code that was marked private in Parsers.scala.)
>
> Thanks,
>
> --j
>
>
>
>
> _______________________________________________
> If you reply to this email, your message will be added to the discussion below:
> http://users.parboiled.org/Scala-performance-tp4024217.html
> To start a new topic under parboiled users, email [hidden email]
> To unsubscribe from parboiled users, visit
fge
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Scala performance

fge
Hello,

On Fri, Jun 21, 2013 at 9:40 AM, mathias [via parboiled users]
<[hidden email]> wrote:
[...]
>
> There is currently a push for a V2.0 version of parboiled ongoing:
> https://github.com/sirthias/parboiled2
>

Uhm, does that mean that the Java version of parboiled will be
abandoned? I am not inclined to doing scala in any way, shape or form,
and Parboiled is the most convenient parser in existence for Java...

--
Francis Galiegue, [hidden email]
JSON Schema in Java: http://json-schema-validator.herokuapp.com
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Scala performance

tsuckow

You could fork it. Is there many show stoppers for you? I thought the java version was pretty stable.

On Jun 22, 2013 10:25 AM, "fge [via parboiled users]" <[hidden email]> wrote:
Hello,

On Fri, Jun 21, 2013 at 9:40 AM, mathias [via parboiled users]
<[hidden email]> wrote:
[...]
>
> There is currently a push for a V2.0 version of parboiled ongoing:
> https://github.com/sirthias/parboiled2
>

Uhm, does that mean that the Java version of parboiled will be
abandoned? I am not inclined to doing scala in any way, shape or form,
and Parboiled is the most convenient parser in existence for Java...

--
Francis Galiegue, [hidden email]
JSON Schema in Java: http://json-schema-validator.herokuapp.com



If you reply to this email, your message will be added to the discussion below:
http://users.parboiled.org/Scala-performance-tp4024217p4024220.html
To start a new topic under parboiled users, email [hidden email]
To unsubscribe from parboiled users, click here.
NAML
fge
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Scala performance

fge
Hello,


On Sat, Jun 22, 2013 at 7:35 PM, tsuckow [via parboiled users]
<[hidden email]> wrote:
> You could fork it.

Yes, of course ;) But I am no parser expert.

> Is there many show stoppers for you? I thought the java
> version was pretty stable.
>

No showstopper, no, but two things which could make it even more appealing:

* a split package with examples only, one per langugage (I have
proposed that a few months ago already);
* customizable error messages (this one is an absolute must).

But do you mean parboiled authors mean to stop the work on the Java
side entirely? That was my initial question.

--
Francis Galiegue, [hidden email]
JSON Schema in Java: http://json-schema-validator.herokuapp.com
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Scala performance

mathias
Administrator
Francis,

since we are doing all our development in Scala now we don't have much incentive to innovate on the Java side of parboiled, especially since Java is evolving so slowly that innovation is not that easy.
On the Scala side however there is plenty of space for innovation and the macro-based parser-generation approach combining the advantages of traditional parser generators with the convenience of parboiled 1.x is quite sexy. Unfortunately though, all this sexiness is unavailable to parboiled's Java users.

So, parboiled 2 will be a Scala-only solution.
We'll maintain the 1.x branch for some time longer but don't expect to put in new features…

Cheers,
Mathias

---
[hidden email]
http://www.parboiled.org

On 22.06.2013, at 19:53, fge [via parboiled users] <[hidden email]> wrote:

>
>
> Hello,
>
>
> On Sat, Jun 22, 2013 at 7:35 PM, tsuckow [via parboiled users]
> <[hidden email]> wrote:
>> You could fork it.
>
> Yes, of course ;) But I am no parser expert.
>
>> Is there many show stoppers for you? I thought the java
>> version was pretty stable.
>>
>
> No showstopper, no, but two things which could make it even more appealing:
>
> * a split package with examples only, one per langugage (I have
> proposed that a few months ago already);
> * customizable error messages (this one is an absolute must).
>
> But do you mean parboiled authors mean to stop the work on the Java
> side entirely? That was my initial question.
>
> --
> Francis Galiegue, [hidden email]
> JSON Schema in Java: http://json-schema-validator.herokuapp.com
>
>
>
>
> _______________________________________________
> If you reply to this email, your message will be added to the discussion below:
> http://users.parboiled.org/Scala-performance-tp4024217p4024222.html
> To start a new topic under parboiled users, email [hidden email]
> To unsubscribe from parboiled users, visit
fge
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Scala performance

fge
On Mon, Jun 24, 2013 at 1:28 PM, mathias [via parboiled users]
<[hidden email]> wrote:
> Francis,
>
> since we are doing all our development in Scala now we don't have much
> incentive to innovate on the Java side of parboiled, especially since Java
> is evolving so slowly that innovation is not that easy.
>

I can somewhat feel the pain, backwards compatibility is a hindrance
sometimes (generics discarded at runtime, property files still read in
ISO, etc)... But Java 8 will change this ;)

> On the Scala side however there is plenty of space for innovation and the
> macro-based parser-generation approach combining the advantages of
> traditional parser generators with the convenience of parboiled 1.x is quite
> sexy. Unfortunately though, all this sexiness is unavailable to parboiled's
> Java users.
>
> So, parboiled 2 will be a Scala-only solution.
> We'll maintain the 1.x branch for some time longer but don't expect to put
> in new features…
>

Well, I guess/hope someone will take over... I do wish it were someone
else than me, I have no theoretical knowledge of parsers, but I don't
want to see such a tool die, it is just too good to be thrown away!

Sorry for sounding somewhat harsh at first.

Have fun, and thanks for {the tool,all the fish}!
--
Francis Galiegue, [hidden email]
JSON Schema in Java: http://json-schema-validator.herokuapp.com
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Scala performance

jorge.ortiz@gmail.com
In reply to this post by mathias
Thanks for your reply Mathias!

Sadly, because of the AST I am targeting, the parser has to be a little bit stateful. I could add a "reset" method and call it between runs, but that makes me a little nervous.

In any case, the parser is running as part of a build step. If I don't want to keep parsers around between build invocations, it's best to keep startup costs as low as possible.

In any case, I'm looking forward to parboiled2!

Thanks,

--j


On Fri, Jun 21, 2013 at 3:40 AM, mathias [via parboiled users] <[hidden email]> wrote:
Jorge,

thanks for your feedback!
In all our own applications we were never re-creating parsers, so we never hit the performance problem you are experiencing.
In fact, is it really necessary to re-create your parser's rule tree over and over again?

If you write your parser in a way that avoids side-effecting beyond using the value stack you should be able to re-use your rule tree completely, thereby circumventing all performance issues of rule creation!

(This is what we do, for example, in spray.io, which also relies on parboiled for parsing HTTP headers into their high-level model classes.)

> Is there any chance of rewriting Parser.scala to not rely on stack traces?


There is currently a push for a V2.0 version of parboiled ongoing:
https://github.com/sirthias/parboiled2

This project has been accepted as a Google Summer of Code 2013 project, so we have some momentum behind it.
The idea is a complete and Scala-only rewrite of parboiled, which relies on Scala 2.10 compiler macros to directly transform your rule definitions into the respective bytecode *at compile-time*. So no more interpreting of a rule tree at run time against an input. The resulting parser should be just as fast as a hand-written one, just much easier to write/maintain and with better error messages.

We'll keep the DSL more or less identical to parboiled 1.x, so migration should be quite easy.

Since we'd like to use parboiled2 in several other projects ourselves (most importantly in spray) we are eager to get it done. The first version should be out before summer is over. If you want I can let you know when a first milestone is ready.

Cheers,
Mathias

PS: The only feature that we probably will not include in parboiled2 from the start is the (equivalent) of the RecoveringParseRunner.

---
[hidden email]
http://www.parboiled.org


On 21.06.2013, at 08:34, "[hidden email] [via parboiled users]" <[hidden email]> wrote:

>
>
> As mentioned in my previous email, I wrote a parser for Apache Thrift using
> Parboiled Scala.
>
> Benchmarking the parser, I noticed a lot of time spent calling
> getStackTrace in getCurrentRuleMethod. Getting stack traces on the JVM is
> fairly expensive (the JVM aggressively inlines method calls, so when you
> ask for a stack trace it needs to materialize the stack it's gotten rid
> of), so I set out to avoid getCurrentRuleMethod.
>
> First I switched to labeled rules. That is, I refactored rules like:
>
>  def Foo = rule { ... }
>
> to:
>
>  def Foo = rule("Foo") { ... }
>
> This got about a ~2x speedup, but I hadn't realized that even labeled rules
> call getCurrentRuleMethod, so I was still spending a lot of time creating
> stack traces. Next I switched my rules from defs to lazy vals:
>
>  lazy val Foo = rule("Foo") { ... }
>
> (Normal vals were not an option because I have some circular references
> between rules.)
>
> This way stack traces were only getting created once per rule per parser,
> rather than once per rule per invocation. The two changes combined were
> about a ~4x speedup. However, I'm parsing a lot of files (~300 files),
> which means creating a lot of parsers (one per file), which means a lot of
> stack traces.
>
> Finally I pulled in all the private rule-creating code from Parsers.scala
> into my own source, and overrode it to use the label name as the key for
> the cache, rather than the StackTraceElement. This gave me about ~18x
> speedup over the original code. Parsing my ~300 files now takes ~700ms
> instead of ~13,000ms.
>
> I'm sure I can get further performance improvements from left-factoring my
> grammar, etc. But just removing stack trace creation gave pretty
> significant performance improvements.
>
> Is there any chance of rewriting Parser.scala to not rely on stack traces?
> At the very least, there should be an option to avoid them if the user
> provides a unique string for every rule. (As it is, I had to duplicate a
> lot of code that was marked private in Parsers.scala.)
>
> Thanks,
>
> --j
>
>
>
>
> _______________________________________________
> If you reply to this email, your message will be added to the discussion below:
> http://users.parboiled.org/Scala-performance-tp4024217.html
> To start a new topic under parboiled users, email [hidden email]
> To unsubscribe from parboiled users, visit


To start a new topic under parboiled users, email [hidden email]
To unsubscribe from parboiled users, click here.
NAML

Loading...