Improve performance of LR item set construction

« glr project page

On my machine, the LR item set construction takes around 0.5 seconds. This is too long. A complete menhir run on the same grammar, including table construction, takes 0.7 seconds (bison runs in 0.3 seconds). I believe that our algorithm performs redundant computations, but my understanding is currently too limited to recognise opportunities for optimisation.

Details

Id: 864b0c70a8b67f88826d502e9cbe9d3d8168232c
Type: task
Creation time: 2012-10-19 15:42 GMT
Creator: Pippijn van Steenhoven <pippijn@...>
Release: unassigned
Component: glr
Status: unstarted

Issue log

2012-10-19 15:44 GMT Pippijn van Steenhoven <pippijn@...> created
Profiling suggests that move_dot_no_closure takes most time and that comparing symbols (GrammarUtil.equal_symbol) is the most called function.