[climacs-devel] cached grammar

[Christophe Rhodes]

Robert Strandh <strandh at labri.fr> writes:

> Christophe Rhodes writes:
>  > -(defmethod item-equal ((item1 incomplete-item) (item2 incomplete-item))
>  > +(defun item-equal (item1 item2)
>  > +  (declare (optimize speed))
>  >    (and (eq (rule item1) (rule item2))
>  > -       (eq (length (parse-trees item1)) (length (parse-trees item2)))
>  > -       (every #'parse-tree-equal (parse-trees item1) (parse-trees item2))))
>  > +       (do ((trees1 (parse-trees item1) (cdr trees1))
>  > +	    (trees2 (parse-trees item2) (cdr trees2)))
>  > +	   ((and (null trees1) (null trees2)) t)
>  > +	 (when (or (null trees1) (null trees2))
>  > +	   (return nil))
>  > +	 (when (not (parse-tree-equal (car trees1) (car trees2)))
>  > +	   (return nil)))))
>
> Are you sure this is an improvement? If parse-tree-equal is relatively
> slow and there is a prefix of the parse trees that are equal but the
> length of the two lists is not equal, then many unnecessary tests for
> parse-tree-equal are made. 

Here is some relevant profiling data, from a run where I've typed in
the top comment of foo.pl, in climacs with my patch applied.

           Self        Cumul        Total
  Nr  Count     %  Count     %  Count     % Function
------------------------------------------------------------------------
   1    110  17.9    111  18.0    110  17.9 (SB-C::XEP (LAMBDA (SB-PCL::.ARG0.)))
   2     34   5.5    227  36.9    144  23.4 (SB-PCL::FAST-METHOD CLIMACS-SYNTAX::HANDLE-ITEM (CLIMACS-SYNTAX::INCOMPLETE-ITEM T T))
   3     34   5.5     74  12.0    178  28.9 CLIMACS-SYNTAX::ITEM-EQUAL
   4     33   5.4     33   5.4    211  34.3 "no debug information for frame"
   5     29   4.7     31   5.0    240  39.0 (SB-C::HAIRY-ARG-PROCESSOR GETHASH)
   6     19   3.1     19   3.1    259  42.0 "foreign function closure_tramp"
   7     18   2.9     31   5.0    277  45.0 (SB-C::XEP (LAMBDA (SB-PCL::.ARG0. SB-PCL::.ARG1. "#<...>" . "#<...>")))
   8     17   2.8     17   2.8    294  47.7 "foreign function sigprocmask"
   9     16   2.6     17   2.8    310  50.3 (SB-C::TL-XEP SB-KERNEL:SUB-GC)
  10     15   2.4     15   2.4    325  52.8 (SB-C::TL-XEP SB-KERNEL::%%TYPEP)
  11     13   2.1     20   3.2    338  54.9 (SB-C::TL-XEP SB-KERNEL:VALUES-SPECIFIER-TYPE)
[...]
  85      1   0.2      2   0.3    558  90.6 CLIMACS-SYNTAX::PARSE-TREE-EQUAL

So PARSE-TREE-EQUAL takes up an apparently insignificant amount of
time compared with ITEM-EQUAL and HANDLE-ITEM (INCOMPLETE-ITEM T T).

One might wonder what %%TYPEP and VALUES-SPECIFIER-TYPE are doing
there.  They come in because the class definitions and prolog grammar
rules are in the same file: defclass at compile-time does not provide
the type system with complete information about the forthcoming class,
so typep on those class names cannot be compiled efficiently.  If the
file is recompiled, these calls will go away, but since they
collectively account for only 5% of the total time, it's not the
bottleneck in any case.

Cheers,

Christophe