Tokenize and Parse PHP source code

[abertschi]

Tokenize and Parse PHP source code

[abertschi]

JPHP SyntaxAnalyser:

• https://github.com/jphp-group/jphp/blob/master/jphp-core/src/org/develnext/jphp/core/syntax/SyntaxAnalyzer.java

ANTRL PHP Grammar:

• https://github.com/antlr/grammars-v4/tree/master/php

[abertschi]

Benchmarking showed that the ANTRL parser is slow compared to the original PHP parser and JPHP (up to 100x slower).

~/.../main/resources >>> find . | xargs wc                        
wc: .: Is a directory
      0       0       0 .
      3       5      73 ./test2.php
     61     269    1973 ./test.php
wc: ./phpoffice: Is a directory
      0       0       0 ./phpoffice
   7948   26260  285899 ./phpoffice/Xls.php
     21     169    1079 ./phpoffice/LICENSE
wc: ./benchmarkgame: Is a directory
      0       0       0 ./benchmarkgame
    143     387    3136 ./benchmarkgame/fasta.php-3.php
     16      64     470 ./benchmarkgame/binarytrees.php-2.php
     99     216    2871 ./benchmarkgame/nbody.php-3.php
     64     171    1095 ./benchmarkgame/spectralnorm.php-2.php
    123     319    2874 ./benchmarkgame/fasta.php-2.php
     51     259    1783 ./benchmarkgame/fannkuchredux.php-1.php
     61     164    1361 ./benchmarkgame/binarytrees.php-1.php

# average parsing speed in ms after warm up
BenchmarkParser.antrlParser                                          phpoffice/Xls.php    avgt       5  1590.528 ± 122.401   ms/op
BenchmarkParser.antrlParser                        benchmarkgame/binarytrees.php-1.php    avgt       5    13.981 ±   0.204   ms/op
BenchmarkParser.antrlParser                      benchmarkgame/fannkuchredux.php-1.php    avgt       5    54.455 ±   0.376   ms/op
BenchmarkParser.antrlParser                                                   test.php    avgt       5    36.484 ±   0.614   ms/op
BenchmarkParser.jphpParser                                           phpoffice/Xls.php    avgt       5    15.030 ±   0.270   ms/op
BenchmarkParser.jphpParser                         benchmarkgame/binarytrees.php-1.php    avgt       5     0.388 ±   0.017   ms/op
BenchmarkParser.jphpParser                       benchmarkgame/fannkuchredux.php-1.php    avgt       5     0.464 ±   0.011   ms/op
BenchmarkParser.jphpParse                                                     test.php    avgt       5     0.452 ±   0.011   ms/op

# cold start speed
BenchmarkParser.antrlParser                                          phpoffice/Xls.php      ss          3627.084             ms/op
BenchmarkParser.antrlParser                        benchmarkgame/binarytrees.php-1.php      ss           263.001             ms/op
BenchmarkParser.antrlParser                      benchmarkgame/fannkuchredux.php-1.php      ss           289.005             ms/op
BenchmarkParser.antrlParser                                                   test.php      ss           451.512             ms/op
BenchmarkParser.jphpParser                                           phpoffice/Xls.php      ss           331.019             ms/op
BenchmarkParser.jphpParser                         benchmarkgame/binarytrees.php-1.php      ss           145.861             ms/op
BenchmarkParser.jphpParser                       benchmarkgame/fannkuchredux.php-1.php      ss           156.936             ms/op
BenchmarkParser.jphpParser                                                    test.php      ss           141.496             ms/op

Above listing shows JMH benchmarks on selected sample files:

• avgt is average parsing execution after JVM warmup
• ss is cold start execution
• we see that antrl parser is 100x slower than JPHP;
• Xls.php is 8000 lines long, execution takes 1590 ms with ANTRL, 15 ms with JPHP (after warm up)
• binarytree.php-1.php is 61 lines, execution takes 13 ms with ANTRL, 0.4ms with JPHP

Native PHP parsing speed of Xls.php is in the range of 10ms

~/.../resources/phpoffice >>> perf stat -r 10 -B php -l Xls.php
No syntax errors detected in Xls.php
No syntax errors detected in Xls.php
No syntax errors detected in Xls.php
No syntax errors detected in Xls.php
No syntax errors detected in Xls.php
No syntax errors detected in Xls.php
No syntax errors detected in Xls.php
No syntax errors detected in Xls.php
No syntax errors detected in Xls.php
No syntax errors detected in Xls.php

 Performance counter stats for 'php -l Xls.php' (10 runs):

             10.50 msec task-clock:u              #    0.965 CPUs utilized            ( +-  0.51% )
                 0      context-switches:u        #    0.000 K/sec                  
                 0      cpu-migrations:u          #    0.000 K/sec                  
             1,613      page-faults:u             #    0.154 M/sec                    ( +-  0.04% )
        28,924,264      cycles:u                  #    2.755 GHz                      ( +-  0.25% )
        47,378,960      instructions:u            #    1.64  insn per cycle           ( +-  0.00% )
         9,736,313      branches:u                #  927.426 M/sec                    ( +-  0.00% )
           234,643      branch-misses:u           #    2.41% of all branches          ( +-  0.13% )

         0.0108791 +- 0.0000619 seconds time elapsed  ( +-  0.57% )

ANTRL parser is too slow and thus not an option to adopt for graalphp.

• options:
  • test ANTRL with native image and see if performance much better (it is not)
  • stick to ANTRL, try to optimize grammar for speedup
    • unclear if optimization gives much speedup
    • there are many nestings in antrl grammar
    • html and js rules implemented as well, removal may give speedup
  • switch to JPHP, find a way to convert tree
    • implies that we need to main sourcecode (10k loc)
    • code is ugly, hard(er) to maintain
    • code uses reflection (causes troubles with graal native-installer, I did not manage to compile it)
  • write better ANTRL grammar from scratch
    • may take several weeks

[abertschi]

I stumbled upon the Eclipse PHP Development Tools. Eclipse provides a PHP flavor of its IDE. It comes with a Java parser for PHP. https://www.eclipse.org/pdt/

Benchmarking of their parser showed promising results. Similar speeds to JPHP and native PHP.
Challenges:

• Parser is tightly integrated in the eclipse tool suite
• Dependencies to dltk, UI code and eclipse runtime

I extracted their parser into a standalone project. It will be used for graalphp.