[climacs-devel] cached grammar

[Christophe Rhodes]

Robert Strandh <strandh at labri.fr> writes:

> Christophe Rhodes writes:
>  > 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

Yeah.  Since for me ADD-RULE is a load-time operation, I thought I
wouldn't spend too much time making its effects incremental, and went
for the sledgehammer rather than the scalpel.

>  > 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.  

I think about 20% of the total time is spent in item-equal.  Another
20% is spent in handle-item but not item-equal.  I'm pretty sure that
the modification to item-equal is a net win, at least for sbcl,
because parse-tree-equal (which simply compares the results of two
class-ofs) is not a time consuming operation at all -- an
insignificant amount of time is spent in parse-tree-equal, according
to my traces.

Cheers,

Christophe