[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Compilation of methods per class.

>From: Jon L White <jonl@lucid.com>
>Date: 	Tue, 25 Sep 1990 23:05:08 PDT
>Subject: Compilation of methods per class.
>re: There was a horrible bug in Victoria Day PCL which had symptoms like
>    what you are mentioning --- an entry could be in the cache, but there
>    would still be a cache miss.  I recall that bug being fixed, but I don't
>    know if the patch was widely distributed.
>The behaviour I'm referring to was present in previous versions too(at least
>one -- maybe more).  It wasn't really a bug in that it wouldstill correctly find
>the cached entry; but it was a performance pitfall
>in that it had to go out of line at unpredictable times to do it.
>Lucid's CLOS uses a different approach to generic function "caching",
>which doesn't follow any of the PCL versions nor of that referred to inthe
>L&FP90 paper.  Rather, it is more akin to TICLOS's.  Method-functionsand
>other data are being "cached" (in a general sense) from the lookup
>phase; but the data-structure in which the cached entries are stored is
>ahash-table rather than a cache.
>-- JonL --

   What do you mean "go out of line"??  What went out line and what did it do  
when it was "out if line"??

  The "cache" implemented in the May Day version of PCL is a simple  
vector.  The algorithm used by May Day to fill the cache (described in  
LFP'90) is, in many aspects, similar to open hashing, where the hash table  
is flat.

>From: Jon L White <jonl@lucid.COM>
>Date: 	Wed, 26 Sep 1990 10:18:26 PDT
>Subject: Compilation of methods per class.
>re: I couldn't illustrate any significant differences in run times with
>    this test file in Franz, though I do get them (up to 10 times slowdown,
>    as I do in Lucid) with my large program that has some generic-functions
>    specialized on over 20 different classes with a number of variable mixins
>    on run-time classes.
>This is precisely the symptom of the "cache assumption breakdown."
>Namely, you probably can't get the identically same example to be the
>breakdown case in two different implementations of Lisp, because
>just the slightest change in "hashing numbers" used for the overall
>technique will skew the distribution of entries in the cache.  There
>is a verrrry non-linear change here for just a trivial skew.

  In Victoria Day PCL, the hashing numbers are assigned sequentially.  If  
you set the variable pcl::*last-wrapper-cache-no* to 0 (or any constant)  
before defining the classes to be used in the benchmarks, you will always  
get the same hash number assignment.  However, I seriously doubt that  
having different hash numbers would cause the "non-linear" changes Trent  
discovered.  Nevertheless, if Trent's version of Victoria Day has not been  
fixed for the bug that Gregor mentioned, it would exhibit some slowdown,  
especially for larger cache sizes, where the bug's effects can be more  
prominent.  By the way, I still don't know what is meant by "cache  
assumption breakdown".
   In May Day PCL, this has all changed, because during lookup, the entire  
hash table is scanned.  It is the responsibility of the filler to put entries close  
to their primary hash location.