search

p4lang / p4c-bm

Generates the JSON configuration for the behavioral-model (bmv2), as well as the C/C++ PD code
Apache License 2.0
24 stars 29 forks source link

Reduce topo sorting run time #80

Closed antoninbas closed 7 years ago

antoninbas commented 7 years ago

For more complex parser definitions with multiple tag stacks, the run time of the algorithm which builds the header graph (in order to run the topological sorting needed to program the deparser) was "exploding". To fix this, I implemented a caching approach to avoid further processing when the recursion visits the same parser state with the same processing state (previous node + tag stacks indices) again. This reduced the run time dramatically.

codecov-io commented 7 years ago

Codecov Report

Merging #80 into master will increase coverage by 0.02%.

@@            Coverage Diff             @@
##           master      #80      +/-   ##
==========================================
+ Coverage      97%   97.03%   +0.02%     
==========================================
  Files          10       10              
  Lines        1605     1620      +15     
==========================================
+ Hits         1557     1572      +15     
  Misses         48       48
Impacted Files Coverage Δ
p4c_bm/gen_json.py 98.02% <100%> (+0.03%) :white_check_mark:

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 91c7add...83623cf. Read the comment docs.