Memory usage compared to gcc compiler

[mingodad]

Looking for a ready to use C peg grammar I found this one https://github.com/pointlander/peg/blob/master/grammars/c/c.peg and needed to make some changes (see attached) to build and parse the generated C file using packcc then I did a comparison of time and memory usage against gcc compiling it and got the result shown bellow, the generated parser compiled with -O2 uses 12x more memory than gcc compiling without optimization and 6.6x more when compiling with -O2.

packcc -l -o c99-mouse c99-mouse.peg

gcc -E c99-mouse.c > c99-mouse.pp.c

/usr/bin/time gcc -g -o c99-mouse c99-mouse.c
0.55user 0.02system 0:00.58elapsed 100%CPU (0avgtext+0avgdata 60484maxresident)k
0inputs+568outputs (0major+16781minor)pagefaults 0swaps

/usr/bin/time gcc -g -O2 -o c99-mouse c99-mouse.c
2.79user 0.07system 0:02.86elapsed 99%CPU (0avgtext+0avgdata 110656maxresident)k
0inputs+1304outputs (0major+36607minor)pagefaults 0swaps

/usr/bin/time ./c99-mouse c99-mouse.pp.c
1.16user 0.21system 0:01.38elapsed 99%CPU (0avgtext+0avgdata 740176maxresident)k
0inputs+0outputs (0major+184749minor)pagefaults 0swaps

c99-mouse.peg.zip

[mingodad]

And for comparison with https://github.com/edubart/lpegrex/blob/main/parsers/c11.lua that outputs an AST, the one generated with packcc only checks the syntax and uses 7.7x memory and 2x the time.

/usr/bin/time lua examples/c11-ast.lua c99-mouse.pp.c > /dev/null
0.46user 0.04system 0:00.50elapsed 99%CPU (0avgtext+0avgdata 96116maxresident)k
0inputs+0outputs (0major+25617minor)pagefaults 0swaps

[mingodad]

And here is the same using https://github.com/soasme/PeppaPEG with a slightly modified grammar (attached),
notice that PeppaPEG also is generating a parse tree, it uses as much memory as Lua but is slower.

/usr/bin/time ./cli parse -G c99-mouse.peg -e TranslationUnit c99-mouse.pp.c > /dev/null
4.69user 0.02system 0:04.71elapsed 100%CPU (0avgtext+0avgdata 97920maxresident)k
0inputs+0outputs (0major+24145minor)pagefaults 0swaps

c99-mouse.peg.zip

[mingodad]

I did some measurements on how/when the memory is allocated (see attached) and here a sample of the summaries:

Header (FULL)
line of call on c99-mouse.c | total malloced + total reallocated | total malloced | total reallocated

Allocation by calls
330	2096896	0	2096896
466	87390512	87390512	0
502	17548048	0	17548048
525	269296480	269296480	0
614	215437184	215437184	0
695	143300672	0	143300672
718	22290240	22290240	0
749	16776976	0	16776976
818	80788944	80788944	0
842	2032	0	2032
857	152	152	0

Header (FIRST 50 lines)
line on parsed file c99-mouse.pp.c | total malloced + total reallocated | total malloced | total reallocated

Allocation by line
0	0	0	0
1	1656	1112	544
2	1512	1112	400
3	1784	1112	672
4	1304	1112	192
5	2264	1112	1152
6	1368	1112	256
7	3288	1112	2176
8	672	608	64
9	336	304	32
10	336	304	32
11	592	304	288
12	336	304	32
13	336	304	32
14	904	808	96
15	1240	1112	128
16	1752	1112	640
17	5336	1112	4224
18	1240	1112	128
19	1240	1112	128
20	1240	1112	128
21	2776	1112	1664
22	9432	1112	8320
23	1240	1112	128
24	1240	1112	128
25	1240	1112	128
26	1240	1112	128
27	1240	1112	128
28	1240	1112	128
29	1240	1112	128
30	1240	1112	128
31	3288	1112	2176
32	17624	1112	16512
33	1240	1112	128
34	1240	1112	128
35	672	608	64
36	336	304	32
37	336	304	32
38	1360	304	1056
39	336	304	32
40	904	808	96
41	1240	1112	128
42	672	608	64
43	904	808	96
44	20456	16072	4384
45	31944	26424	5520
46	704	608	96
47	904	808	96
48	1304	1112	192
49	1240	1112	128
50	1368	1112	256
...

c99-mouse-mem.zip

[mingodad]

And peg from Piumatra (https://github.com/gpakosz/peg.git) is the winner (see attached):

./peg c99-mouse.peg > c99-mouse-peg.c
gcc -O2 -o c99-mouse c99-mouse.c
/usr/bin/time cat c99-mouse.pp.c | ./c99-mouse 
0.00user 0.00system 0:00.11elapsed 4%CPU (0avgtext+0avgdata 2196maxresident)k
0inputs+0outputs (0major+113minor)pagefaults 0swaps
yy 1

piumatra-peg-0.18.zip

[dolik-rce]

It is not very fair to compare the result of generic, multi-purpose packrat parser-generator to hand-written, single-purpose parser, that is optimized by some of the worlds best developers over last 35 years...

I don't see any issue here, packcc never claimed to be memory efficient. The main goal is to be easy to work with and generate easily understandable code.

[arithy]

Thanks for your interesting report.
PackCC requires more memory to support left-recursive grammars, which cannot be handled by most PEG parser generators.

By the way,

/usr/bin/time cat c99-mouse.pp.c | ./c99-mouse

should be

cat c99-mouse.pp.c | /usr/bin/time ./c99-mouse

[mingodad]

Thank you for pointing out my mistake, here is again the output for the peg from Piumarta:

/usr/bin/time ./c99-mouse c99-mouse.pp.c 
yy 1 : 15790
0.27user 0.00system 0:00.27elapsed 100%CPU (0avgtext+0avgdata 2228maxresident)k
0inputs+0outputs (0major+217minor)pagefaults 0swaps

[mingodad]

And here is the attached files used to produce the output shown above:
piumatra-peg-0.18.zip

I'm making some changes to peg/leg here https://github.com/mingodad/peg

[mingodad]

Also c99-mouse.peg doesn't use left recursion so probably some savings can be achieved for such cases because packcc already know that left recursion machinery is not necessary.

[arithy]

That makes sense. Left-recursive grammars can be detected before generating parsers.
To tell the truth, I'm not so interested in a parser generator without left-recursive grammar support, but I add it to my todo list because of repeated requests.
There was a similar comment: #46 (comment) .

[mingodad]

And here is the test with https://github.com/yhirose/cpp-peglib tool peglint () with and without producing an AST (parser tree):

/usr/bin/time peglint c99-mouse2.peg c99-mouse.peg.pp.c 
1.35user 0.00system 0:01.35elapsed 99%CPU (0avgtext+0avgdata 4588maxresident)k
0inputs+0outputs (0major+359minor)pagefaults 0swaps

mingo@mingo-X550VX:~/dev/c/A_grammars/cpp-peglib/example$ /usr/bin/time peglint --packrat c99-mouse2.peg c99-mouse.peg.pp.c 
0.35user 0.01system 0:00.37elapsed 99%CPU (0avgtext+0avgdata 40580maxresident)k
0inputs+0outputs (0major+9363minor)pagefaults 0swaps

mingo@mingo-X550VX:~/dev/c/A_grammars/cpp-peglib/example$ /usr/bin/time peglint --ast c99-mouse2.peg c99-mouse.peg.pp.c > /dev/null
2.33user 0.05system 0:02.39elapsed 99%CPU (0avgtext+0avgdata 133792maxresident)k
0inputs+0outputs (0major+36504minor)pagefaults 0swaps

mingo@mingo-X550VX:~/dev/c/A_grammars/cpp-peglib/example$ /usr/bin/time peglint --packrat --ast c99-mouse2.peg c99-mouse.peg.pp.c > /dev/null
0.74user 0.05system 0:00.80elapsed 100%CPU (0avgtext+0avgdata 182072maxresident)k
0inputs+0outputs (0major+48993minor)pagefaults 0swaps

[dolik-rce]

Hello @mingodad

I have stumbled into this issue after a long time and realized that you might be having same problem as I had some time ago. I was using packcc to generate Kotlin parser, but it was slow and took a lot of memory. This have led me to start working on pegof , which can optimize the grammar before it is compiled.

I have just tried with the grammar from your original post and here is the result:

	lines	bytes	rules	terms	duration	memory
original	10091	427671	195	865	9836	578432
optimized by pegof	8639	370298	35	909	3126	198656
difference in percent	85%	86%	17%	105%	31%	34%

You'll be probably most interested in the last two columns. Duration here is how long it took to process c99-mouse.pp.c 10 times, expressed in milliseconds. Memory is peak resident memory (as reported by GNU time) during those ten runs.

I'm not sure if you're still interested in this after two years (sorry for disturbing you if that is the case), but it might be useful to you in some future project or to anyone who finds this issue when looking for solution to some similar problem.

[mingodad]

Thank you !
Even after two years it's still good news !
I'm looking at it now.