Performance Improvement Project - Lexer caching
-----------------------------------------------

Measured and analysed the parsing times when parsing different
subsets of the Ruby 1.6.3 BNF grammar in examples/ruby/.

NoL = Number of lines in the input file as reported by 'wc -l file'
PT  = Parse time in seconds and the percentage of the time the process
      was in user or system (when not printing info below)
NIT  = Number of iterations of the parse algorithm
NAS = Number of active stacks in the last iteration
MNAS = Max number of active stacks over all iterations
NLP = Number of unique lexer positions among the active stacks
MNLP = Max NLP over all iterations

NoL   PT		NIT	NAS	MNAS	NLP	MNLP
50    1.36 s 99.34%     174	6	6   
100   2.20 s 99.09%     309	2	6       1       2
150   4.41 s 98.87%	562	4	6	1	2
200   10.96 s 99.19%	727     24      24	2	2
250   56.92 s 98.87%    855     128     196     1       2
300   NA

Unfortunately the behavior is clearly exponential growth! We see that the number of stacks grows very large but the number of unique lexer positions is still only two.

This implies that a straightforward performance enhancement will be beneficial:
Have a hash of the lexers so that when a new one is created we first check if there is one at that position available. If so we return the existing one. If not we create a new one and insert it into the hash. Since there is no need to save all old stacks we make the hash a LruHash with say 20 positions. This will trow out old lexers when new one are entered and thus save memory. Maybe this is the beginning of a object pool for the lexers so that we can reuse them?

Results after doing the above enhancement:
NoL   PT		
50    0.74 s 98.65%     
100   1.16 s 100.00%
150   2.29 s 99.56%
200   2.99 s 99.00%
250   3.99 s 98.24%
300   4.59 s 98.04%
350   4.94 s 99.59%
etc...

A very healthy improvement! Seems to be closer to linear now but the grammar
used here was very simple so this might not be representative in general.

-----------------------------------
Code used in measuring performance:
-----------------------------------

--- lib/glr_parser.rb   Thu May 24 16:39:23 2001
+++ /tmp/glr_parser_with_perf_mea.rb    Thu May 24 16:39:08 2001
@@ -95,8 +95,13 @@
     @lexer.init(aString)
     start_state = @parse_table.start_state
     @active_stacks = [ParseStack.new(start_state, @lexer)]
-    @cnt, @reducer_cnt = -1, 0
+    @cnt, @reducer_cnt, max_nas, max_nlp = -1, 0, -1, -1
     while @active_stacks.length > 0
+      nas = @active_stacks.length
+      max_nas = [nas, max_nas].max
+      nlp =@active_stacks.map {|s| s.lexer.position.char_position}.uniq.length
+      max_nlp = [nlp, max_nlp].max
+      puts "Parser it #{@cnt+=1}: nas = #{nas}, max nas = #{max_nas}" +
+        ", nlp = #{
nlp}, max nlp = #{max_nlp}"
       @stacks_to_shift.clear
       @stacks_to_act_on = @active_stacks.clone
