Performance Improvement Project - LaLr1Generation
-------------------------------------------------

Problem
*******
Generation of parse tables for Ruby grammars takes an awful long time and shows signs of exponential growth. I need to find out why and find a way to take it to ponymial (qubic or quadratic?) growth in the number of nonterminals or productions.

Measurements
************
I made some changes to the parse_y_to_rockit translator so that one can tune the size of the resulting ruby grammar. The simplest was to choose the number of nonterminals. Here's the procedure used:

After the grammar has been extracted and parsed (in full) from parse.y I decide how many nonterminals N to include (in total there are 78 nonterminals and Y productions). The N nonterminals to retain are chosen from the "logical" top of the grammar to increase the likelihood that the resulting grammar would be a valiad grammar. The "logical" top is found by ordering the nonterminals by the order in which they are mentioned when we start by looking from the start production. After choosing the N out of 78 nonterminals, I delete all productions for the rest 78-N nonterminals. I also delete all occurences of the deleted nonterminals in the right hand sides of the remaining productions. The code added can be seen in the diffs below.

I then insert timers in the LaLR1Gen code and measure:

NoN = Number of Nonterminals left in grammar
NoL = Number of lines in the grammar file
NoP = Number of productions left in grammar
TtN = Time to normalize the grammar
NoPN = Number of productions in the normalized grammar
TtL0 = Time to calc the LR0 collection
TtLA = Time to calc the lookahead
TtPT = Time to create the parse table

Measurements 1
--------------

NoN  NoL    NoP    TtN	      NoPN	TtL0	TtLA	TtPT
5    46	    26	   0.10	      36	0.01	0.02	1.06
6    47	    27	   0.07	      42	1.92	30.63	2.22
7    53	    33	   0.09	      48	2.16	36.09	2.72
10   60	    41	   0.16	      56	2.88	48.90	3.35
11   65	    46	   0.12	      61	3.04	52.41	3.73
12   66	    47	   0.12	      62	3.17	53.22	3.87
13   68	    49	   0.12	      64	3.21	53.39	3.97
14   69	    50	   0.11	      65	3.25	53.49	4.08
15   108    88	   0.29	      104	??	??	??

Analysis 1
----------
What happens between 5 and 6? Well

    CompoundStatement -> Statements? ';'*

is added which makes it the first time that Statement is in there so before 6 the grammar is simply

    StartSymbol -> 'String'

which is of course not very complex. There seems to be a similar problem when going from 14-15. These "jumps" might also be attributed to the way we generate the subgrammars.

However, it seems clear that the behavior does not scale.

If we take a closer look at the productions that are added when going from 14-15 it is the largest one ie. Arg which also has got lots of left recursion ie. where the first right hand element is Arg.

So, we have our first theory to explain the behavior:

Theory 1 (T1)
-------------
Current LaLr1Generation implementation does not fare well when there are lots of left recursion in the productions.

but it could also be that there are simply lots of productions having the same first element on the rhs since there are many alternatives for Arg and they all have Arg in the first pos. 

Theory 2 (T2)
-------------
Current LaLr1Generation implementation does not fare well when there are many alternatives for a nonterminal and they all have the same first element(s).

Refutation attempt 1: T1 vs. T2
-------------------------------
I substituted the Args being the first elements on the left hand side in Arg with string "'Dummy'". If still takes a long time then T2 is favored to T1. If faster then T1 is favored to T2.

Result:
NoN  NoL    NoP    TtN	      NoPN	TtL0	TtLA	TtPT
!14   69    50	   0.11	      65	3.25	53.49	4.08 (OLD res for comp)
15   108    88	   0.29	      104	45.99	??	??

So this favours none since it still seems to take a hell of a time but its shorter. So this seems to indicate that

Both the generation of the lr0_collection but especially the lookahead calc is sensitive to productions that have the same element in the first position. The effect is even worse when they are left recursive.

The next question is if this depends on the number of productions having the same prefix for the same nonterminal or if it is dependant on the total number of such productions in the grammar.

I tried this by taking away some alternatives for the Arg nonterm so that I only had 6 left. I then changed the last 3 to be alternatives for the top-level nonterminal instead. This is not foolproof but lets try!

All 6 as Arg alternatives:
TtL0	TtLA	TtPT
4.86	72.11	6.88

3 as Arg alts and 3 as Program alts
TtL0	TtLA	TtPT
4.41	64.18	5.98

So the effect is larger when there are multiple alternatives for the same noterminal that have the same prefix. Its even worse when there are many left-recursive alternatives.

Now lets take a look at what is taking the time when calculating the lookaheads. Lets start by timing the calc of the sponatneous lookaheads.

NoN TtLA      TtSLA  %SLA
6   30.96     27.52  88%
11  53.50     47.32  88%
14  53.43     47.97  90%

Ok, so the majority of the time is spent in calc the spontaneous lookaheads.
Now lets do a real profile

Measurements 2 - Profile
------------------------
I profiled the lalr1Gen methods when run on the 5, 10 and 14 nonterminal grammars:

NoN	   % time     # calls  ms/call  method	 
5	   
	   62.5%	156	0.96	lr0_goto
	   20.8%	3	16.67	lr1_closure
           12.5%	1	30.00	lr0_collection
	   4.17%	3	3.33    lookaheads

10	   
	   40.9%	10877	3.37    lr0_closure
	   29.8%	10876   2.46    lr0_goto
	   10.5%	172     54.87   lr1_closure
           7.39%	94      70.63   lookaheads
	   6.57%	1      5898.00  lalr1_lookaheads
	   2.71%	1      2432.00  lr0_collection
	   1.30%	1344   0.87     first

14
	   40.6%	12630   3.22    lr0_closure
	   30.7%	12629   2.43	lr0_goto
	   9.6%		186    51.85    lr1_closure
	   7.5%		104    72.50    lookaheads
	   6.5%		1    6519.00    lalr1_lookaheads
	   3.1%		1    3134.00    lr0_collection
	   1.1%		1360    0.79    first

for NoN = 14 here are the argument info (only for the ones with multiple calls with the same arguments):

lr0_closure
   0.04% (5) of calls with unique args, and
   99.96% (12625) of calls with args that were used several times
lr0_goto
   41.74% (5271) of calls with unique args, and
   58.26% (7358) of calls with args that were used several times
lr1_closure
   63.44% (118) of calls with unique args, and
   36.56% (68) of calls with args that were used several times
first
   0.96% (13) of calls with unique args, and
   99.04% (1347) of calls with args that were used several times

Measurements after implementing better lalr1 generation alg
-----------------------------------------------------------

Before
NoN  NoL    NoP    TtN	      NoPN	TtL0	TtLA	TtPT
5    46	    26	   0.10	      36	0.01	0.02	1.06
6    47	    27	   0.07	      42	1.92	30.63	2.22
7    53	    33	   0.09	      48	2.16	36.09	2.72
10   60	    41	   0.16	      56	2.88	48.90	3.35
11   65	    46	   0.12	      61	3.04	52.41	3.73
12   66	    47	   0.12	      62	3.17	53.22	3.87
13   68	    49	   0.12	      64	3.21	53.39	3.97
14   69	    50	   0.11	      65	3.25	53.49	4.08
15   108    88	   0.29	      104	??	??	??

After
NoN  NoL    NoP    TtN	      NoPN	TtL0	TtLA	TtPT
5    46	    26	   0.07	      36	0.01	0.08	0
6    47	    27	   0.13	      42	0.15	3.67	0
10   60	    41	   0.14	      56	0.31	5.62	0
14   69	    50	   0.21	      65	0.29	7.26	0
15   108    88	   0.43	      104	1.91	318.x	0

Better but still not good enough!

For 20 NoN's there are 913 nodes in the relation graph and 8503 links between them. We traverse the graph once from each first set for a terminal => takes a long time!

We need a better way to calc reachability in the graph. Either we can try to decrease the propagation time by doing a simultaneous propagation the way I've previously sketched. Or we can find an algorithm that updates reachability as we go along. Better yet would be to find a way so that we don't have to calc

Timing relationbased lookahead
------------------------------
NoN	i2i	i2o	o2o	# Nodes	# Links	prop	reducs
10	0.02	0.07	0.25	119	330	0.65	4.70
15	0.10	1.71	5.12	285	4306	98.07	211.34

I instrumented StateGraph#traverse to see the percentage of calls that have
previously been seen. It was around 38-40%.

Timing with a simple transitive closure algorithm
-------------------------------------------------
TransClosure based on Floyd-Warshal compared to existing propagation:

NoN	     Prop  FW
5	     0.01  0.52
10	     0.94  93.58

Not good...

profile.rb of atest_bootstrap.rb
--------------------------------
  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 15.99   199.65    199.65    90656     2.20     4.90  Production#==
 11.24   340.04    140.39    30490     4.60   167.63  Array#each
 11.15   479.25    139.22   108239     1.29     1.83  GrammarSymbol#==
  4.63   537.07     57.82   220926     0.26     0.26  Kernel.type
  3.25   577.64     40.56     5164     7.85    93.05  Array#index
  2.83   612.93     35.30    18513     1.91     2.88  Token#==
  2.71   646.83     33.90   122792     0.28     0.28  String#==
  2.54   678.60     31.77   118914     0.27     0.27  Kernel.kind_of?
  2.48   709.60     31.00   123544     0.25     0.25  Kernel.==
  2.18   736.81     27.21    51375     0.53     0.92  Hash#[]
  1.90   760.57     23.76    14627     1.62     3.28  TerminalSet#index_included
?
  1.66   781.25     20.68     2988     6.92   167.78  ParseTable#add_action
  1.55   800.63     19.38    48927     0.40     0.40  ReferencingRegexpLexer#sca
nner
  1.16   815.16     14.53     1942     7.48    12.00  Array#delete
  1.13   829.31     14.14    56997     0.25     0.25  Fixnum#==
  1.09   842.91     13.61    10916     1.25     2.95  DefaultInitHash#[]
  1.09   856.50     13.59    14708     0.92     1.16  TerminalSet#mask
  1.02   869.23     12.73    46987     0.27     0.27  C_StringScanner#check

Profiling the main funcs
------------------------
I instrumented relationbased_lookahead.rb to profile the methods:
  simultaneous_terminalset_propagation
	propagate_terminals
	add_reductions
  precalc_first_to_first
  precalc_first_to_follow
  precalc_follow_to_follow

NoN
5
	50% propagate_terminals
	50% precalc_first_to_first
10
	75.76% add_reductions
	16.17% propagate_terminals
	4.03% precalc_follow_to_follow
14
	72.70% add_reductions
	19.75% propagate_terminals
	4.67% precalc_follow_to_follow
15
	50.62% add_reductions
	47.77% propagate_terminals

Ok lets add some profiling of methods in add_reductions:
   StateGraph#traverse
   ParseTable#add_action

NoN
10	Total: 12.538 seconds
	42.79% add_action
	31.06% add_reductions
	12.95% traverse
	7.95% propagate_terminals
15	Total: 674.67 seconds
	40.48% add_action
			126714 calls of which the majority is from 
			       add_reductions
			98.32% of calls with previously seen args
	26.80% propagate_terminals
	22.05% add_reductions
	9.85%  traverse

So when the number of nonterminals increase and the complexity of the productions increase the number of links in the follow-to-follow relation graph explodes. This leads to long computational times both when propagating terminal sets and when adding reductions. A majority of the reductions to be added are duplicates that we already know is in there.

Actions:
1. Find ways to not add follow-to-follow relations that do not add to the information already there.
2. Speed up add_action
3. Catch duplicate calls in add_reductions and skip them...

1 is a bit tricky so lets see how far we get with 2 and 3:

NoN
15	Total: 268 seconds
	67.14% propagate_terminals
	24.77% traverse
	3.12% add_reductions
	2.55& add_action

A healthy 60% speed up. Still things are out of hand though:

NoN     i2i_nodes   i2i_links i2o_nodes	 i2o_links o2o_nodes o2o_links
20
30	92	    135	      1134	 4778      207	     7006
	Total: 1487 seconds
	61.51% propagate_terminals
	26.70% traverse
	4.86%  add_reductions
	3.46%  add_action

40	129	    179	      1322	 5303      615	     8367
	Total: 2693 seconds
	65.85% propagate_terminals
	23.63% traverse
	4.42%  add_reductions
	3.55%  add_action

50	144         200	      1673	 6327      725       10235
	Total: 3908 seconds
	69.21% propagate_terminals
	21.14% traverse
	3.93%  add_reductions
	3.19%  add_action

Check if we can gain something be splitting the propagation in different phases
-------------------------------------------------------------------------------
Time for propagation of terminal sets in full state graph (78 nonterms):
     1.28 seconds
Num states:			886
Num inconsistent states:	427 (48%)
Num end item states:		561 (63%)
Num inconsistent end item st.:	256

Seems like a good idea. Here's the new alg:

1. Build first-to-first relations graph
2. Propagate terminal sets in that graph
3. Build first-to-follow-nodes by updating the follow sets for all its first 
   sets
4. Build the follow-to-follow relation in the standard manner
5. Propagate the follow sets from the first-to-follow-nodes

and then add reductions as usual.

NoN	 Total Time	Before		Improvement
30	 637 seconds	1487		-57%
40	 1087		2693		-59%

