Hi,

On Sat, Feb 21, 2015 at 8:07 PM, Thierry Goubier <thierry.goubier@gmail.com> wrote:

Le 21/02/2015 11:14, Jan Kurš a écrit :

Hey,

I was not aware about some exponential element in the overall
complexity, it is strange and I will investigate it. Thank you Usman,
for pointing this out.

In general, it is hard to add features into the PetitParser and preserve
performance. Therefore, we work on a tool, that will take PetitParser,
analyze it and generates faster parser. The idea is to use PetitParser
while developing the grammar and than generate a fast parser for "real"
use. We hope we will be present the tool during the next ESUG.

I certainly be interested with what you come up with. From profiling PetitParser, it seems there is at least one low-hanging fruit in term of performance.

What is that log hanging fruit?

Doru

And thanks too Usman, for pointing out long source code files may (or do) show diverging asymptotic behaviors. And real life use for most programming languages are very long files :(

Thierry

Cheers,
Jan

On 20 February 2015 at 17:47, Usman Bhatti <usman.bhatti@gmail.com
<mailto:usman.bhatti@gmail.com>> wrote:

I executed the script that I shared earlier in this thread and I see
a considerable performance improvement in the latest version of
PP. The attached chart shows the comparison chart between PP v 1.51
(green) with the newer version (red). For shorter strings (i.e. to
the left on x-axis), the execution time is almost comparable to the
previous version of PetitParser that dates before changes introduced
by Jan.

However, when I take the new version and parse the code source of
larger code bases, the execution time still get a hit. For example,
parsing 100K lines takes almost twice longer. The increase is
exponential with even larger ones. That is consistent with results
we see in the graph (the larger the chain to be parsed i.e. going
from left to right in the x-axis, the higher the performance
penalty). Meaning I still prefer the older version.

What will be good is to prepare some benches with Java Parser in PP,
as it is open source, and a set of programs (e.g. ArguUML) that can
serve as a standard to test execution time for PP that we can run as
a jenkins service.

Inline image 1

regards.

On Fri, Feb 20, 2015 at 9:09 AM, Tudor Girba <tudor@tudorgirba.com
<mailto:tudor@tudorgirba.com>> wrote:

Great news.

@Usman: could you check?

Doru

On Fri, Feb 20, 2015 at 9:04 AM, Jan Kurš <kurs.jan@gmail.com
<mailto:kurs.jan@gmail.com>> wrote:

Hey all, Please note that a new version in of PetitParser
(JanKurs-271) should improve performance roughly comparable
to the original performance. On my computer, I got
improvement from 3900ms to 1300ms.

Cheers,
Jan

On 1 February 2015 at 22:55, Jan Kurš <kurs.jan@gmail.com
<mailto:kurs.jan@gmail.com>> wrote:

Hey all, thanks for the report, I will have a look at it
asap.

Cheers Jan

On 1 Feb 2015 20:55, "Usman Bhatti"
<usman.bhatti@gmail.com <mailto:usman.bhatti@gmail.com>>
wrote:

On Fri, Jan 30, 2015 at 9:36 PM, Sven Van
Caekenberghe <sven@stfx.eu <mailto:sven@stfx.eu>> wrote:

Usman, this is a really cool bug report !

Thanks :)

> On 30 Jan 2015, at 16:36, Usman Bhatti <usman.bhatti@gmail.com
<mailto:usman.bhatti@gmail.com>> wrote:
>
> Here is a script that shows the factor of 2 in time taken for parsing. The idea of the script is to introduce several wrong branches before hitting the correct one (originally proposed by Guillaume).
>
> |rule wrongBranches|
> [wrongBranches := (25 to: 45) inject: 24 asCharacter asParser into: [:acc :each | acc / each asCharacter asParser].
> rule := PPDelegateParser new.
> rule setParser: $a asParser / ((wrongBranches / $. asParser), rule).
> rule parse: (String streamContents: [ :s |
> 30000 timesRepeat: [s nextPut: $.]. s nextPut: $a ])] timeToRun
>
>
> Below are the graphs that were generated when varying the string length provided to the above parser description. Green part shows the time taken by the older version and the red part with the latest PP.
>
> <graph.png>
>
> Data values and graph generated by the script
in the attached file.
>
> regards.
>
> usman
>
> On Fri, Jan 30, 2015 at 1:30 PM, Tudor Girba
<tudor@tudorgirba.com
<mailto:tudor@tudorgirba.com>> wrote:
> Hi,
>
> Hmm. I thought this was fixed and that you
said at the end that the performance penalty is
no longer a factor of 2.
>
> Do you have a simple example for checking the
simple case of 2x performance loss?
>
> Doru
>
>
> On Fri, Jan 30, 2015 at 12:28 PM, Usman
Bhatti <usman.bhatti@gmail.com
<mailto:usman.bhatti@gmail.com>> wrote:
> Hi,
>
> Since the work on the integration of
PPContext in PetitParser, there is significant
performance degradation. I have already
mentioned that on simple grammar the factor is
about 2. But on complex grammar (for example,
our proprietary parser for 4D language ), we
have seen that degradation is goes well beyond
this factor. So, for example, for 800K lines
that we parse in under 10 minutes without
PPContext work, with the latest version it goes
beyond 2h.
>
> I have not been able to reproduce my case on
simple grammars. May be we can have some
benchmarks using open source parsers and large
code bases (e.g. PP Java Parser on JHotDraw or
ArgoUML).
>
> Currently, I circumvent this issue by using
PP v1.51 but I can provide relevant feedback and
run benches on any improvements.
>
> regards.
>
> Usman
>
> _______________________________________________
> Moose-dev mailing list
> Moose-dev@iam.unibe.ch
<mailto:Moose-dev@iam.unibe.ch>
>
https://www.iam.unibe.ch/mailman/listinfo/moose-dev
>
>
>
>
> --
> www.tudorgirba.com <http://www.tudorgirba.com>
>
> "Every thing has its own flow"
>
> _______________________________________________
> Moose-dev mailing list
> Moose-dev@iam.unibe.ch
<mailto:Moose-dev@iam.unibe.ch>
>
https://www.iam.unibe.ch/mailman/listinfo/moose-dev
>
>
>
<script-graph.txt>_______________________________________________
> Moose-dev mailing list
> Moose-dev@iam.unibe.ch
<mailto:Moose-dev@iam.unibe.ch>
>
https://www.iam.unibe.ch/mailman/listinfo/moose-dev

_______________________________________________
Moose-dev mailing list
Moose-dev@iam.unibe.ch
<mailto:Moose-dev@iam.unibe.ch>
https://www.iam.unibe.ch/mailman/listinfo/moose-dev

_______________________________________________
Moose-dev mailing list
Moose-dev@iam.unibe.ch <mailto:Moose-dev@iam.unibe.ch>
https://www.iam.unibe.ch/mailman/listinfo/moose-dev

_______________________________________________
Moose-dev mailing list
Moose-dev@iam.unibe.ch <mailto:Moose-dev@iam.unibe.ch>
https://www.iam.unibe.ch/mailman/listinfo/moose-dev

--
www.tudorgirba.com <http://www.tudorgirba.com>

"Every thing has its own flow"

_______________________________________________
Moose-dev mailing list
Moose-dev@iam.unibe.ch <mailto:Moose-dev@iam.unibe.ch>
https://www.iam.unibe.ch/mailman/listinfo/moose-dev

_______________________________________________
Moose-dev mailing list
Moose-dev@iam.unibe.ch <mailto:Moose-dev@iam.unibe.ch>
https://www.iam.unibe.ch/mailman/listinfo/moose-dev

_______________________________________________
Moose-dev mailing list
Moose-dev@iam.unibe.ch
https://www.iam.unibe.ch/mailman/listinfo/moose-dev

_______________________________________________
Moose-dev mailing list
Moose-dev@iam.unibe.ch
https://www.iam.unibe.ch/mailman/listinfo/moose-dev

www.tudorgirba.com

"Every thing has its own flow"