[climacs-devel] cached grammar

[Robert Strandh]

Christophe Rhodes writes:
 > Hi,
 > 
 > Is the attached what you (Robert) were thinking of for cacheing some
 > portions of HANDLE-ITEM?

Yes, except that I was not going to be as brutal about recomputing the
cache at each time.  I was thinking add-rule should do:

  1. For each symbol of the right hand side of the new rule
       If the symbol is not a key in the hash table
         then add it by setting the entry to '()
              loop for each existing rule
                if lhs of existing rule is compatible with symbol
                  then push rule onto the list 
  2. Loop for all entries in the hash table
       If the lhs of the new rule is compatible with the key in the entry 
         then push the new rule on that entry

 > If so, well, here it is, along with an optimization to ITEM-EQUAL.
 > Unfortunately, it's still too slow -- 

Ouch.  

 > in the attached prolog file in
 > Prolog Syntax, typing in the comment at the top of the buffer has
 > noticeable lag on my 2.8GHz x86.  About 50% of the time is spent in
 > HANDLE-ITEM and callees, according to sb-sprof, of which about half is
 > in ITEM-EQUAL.

This is very strange.  Normally, the previous algorithm was
quadratic and this one no longer is. 

Of course, if the problem is item-equal, that's a different story.  I
am guessing that the speedup is significant, though perhaps not
enough, and that the bottleneck is now in item-equal.  

 > Any ideas?  (Can other people reproduce this kind of performance
 > characteristic, for one?)  

HTML syntax is too slow as well (before the patch).  But I am having
trouble with incremental redisplay, so it is hard to tell what is
slower, redisplay or parsing.  

 > Is it possible that the grammar is in some
 > way badly formed, and is there a way of checking this automatically?

If that were the case, you would get some kind of quadratic or cubic
behavior (in the size of the input).  This can happen for certain
grammars.  In that case, you would get terrible performance on a long
input buffer even when using a relatively small window at the end of
it.  That is a fairly easy test to make.  You could also count the
number of items in various parser states to see whether it grows
linearly with the position in the buffer. 

-- 
Robert Strandh

---------------------------------------------------------------------
Greenspun's Tenth Rule of Programming: any sufficiently complicated C
or Fortran program contains an ad hoc informally-specified bug-ridden
slow implementation of half of Common Lisp.
---------------------------------------------------------------------