[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: 	Wed, 26 Sep 1990 15:39:24 PDT
>Subject: Compilation of methods per class.
>re: What do you mean "go out of line"??  What went out line and what
>did it    do when it was "out if line"??
>    . . .    By the way, I still don't know what is meant by "cache
> assumption    breakdown".
>You should look at the Victoria Day and prior sources, for the uses of
>the function DCODE-CACHE-MISS.  Calling it is "out of line"; calling it
>when the entry is actually in the cache is the "assumption breakdown".
>I say "breakdown", because it is plausible to suffer the 

>order-of-magnitudeloss to go "out of line" if it rarely happens; this is 

>the classic analysis for caching.  But an application can randomly fall
>into a hole where asubstantial fraction of its lookups are in this case.
>Trent's symptoms arequite consistent with this, and less consistent with
>the other explanations.

  Are you saying that the Victoria Day cache lookup code can get repeated  
misses (calls to DCODE-CACHE-MISS) even though the entry is, or should  
be,  in the cache?  If so, this is exactly the bug that Gregor referred to.  A fix  
is appended to this message.  


>Furthermore, sequential assignment of the class hashing numbers 

>won'tguarantee repeatablility of the problem across ports -- it is
>sensitiveto the order in which the classes are assigned, and the order
>in whichmethod are called on generic funtions (i.e., the way in which
>the cache's are filled up with entries).  Just a tiny variation in any of
>these between two ports can make one avoid the problem where the
>other falls into it. 

  It seems to me that deterministic assignment of hashing numbers is all you  
need to guarantee repeatability in Victoria Day.  The benchmarks run in the  
same order in any port, which means that classes and methods will be  
created and called in the same order.  Also, Victoria Day is completely  
deterministic, in the sense that it never calls the function random.  Please  
elaborate on exactly where non-determinism is introduced.



  The patched version of DCODE-CACHE-MISS is included below.  There is  
only one change, and it can be located by searching for the string "++".  

  Basically, under certain circumstances the bug causes cache entries to be  
shifted around to locations where the lookup routine doesn't look or to  
locations where they qualify to be "dropped on the floor".  If this happens, the  
next time the generic function is called, the damaged entries will not be  
found, and thus the lookup code will get a cache miss.

  May Day PCL doesn't suffer from this, since the lookup code checks the  
whole cache for an entry.  It is the responsibility of the filler code to make  
sure that entries are placed close to their primary locations. 

;;;-*-Mode:LISP; Package:(PCL LISP 1000); Base:10; Syntax:Common-lisp -*-
;;; *************************************************************************
;;; Copyright (c) 1985, 1986, 1987, 1988, 1989, 1990 Xerox Corporation.
;;; All rights reserved.
;;; Use and copying of this software and preparation of derivative works
;;; based upon this software are permitted.  Any distribution of this
;;; software or derivative works must comply with all applicable United
;;; States export control laws.

;;; This software is made available AS IS, and Xerox Corporation makes no
;;; warranty about the software, its performance or its conformity to any
;;; specification.

;;; Any person obtaining a copy of this software is requested to send their
;;; name and post office or electronic mail address to:
;;;   CommonLoops Coordinator
;;;   Xerox PARC
;;;   3333 Coyote Hill Rd.
;;;   Palo Alto, CA 94304
;;; (or send Arpanet mail to CommonLoops-Coordinator.pa@Xerox.arpa)
;;; Suggestions, comments and requests for improvements are also welcome.
;;; *************************************************************************

(in-package 'pcl)


;;; This dcode-cache-miss is for Victoria Day PCL

(defun dcode-cache-miss
       (gf					;actual generic function
	tertiary-miss-fn			;function to call if the
						;scan of the next entries
						;also misses
	cache					;the cache
	size					;size of the cache in `words'
	mask					;the cache mask
	line-size				;line size in `words'
	nkeys					;number of keys per entry
	next-scan-limit				;The limit of next entries
						;to scan before declaring a
						;tertiary miss.  When filling
						;the cache, this controls how
						;many next slots to try before
						;declaring a cache miss.
	expandp					;If this is false, don't
						;expand the cache no matter
	dcode-constructor			;Passed to EXPAND-DCODE-CACHE
	&rest wrappers-and-args)		;A list whose first NKEYS
						;elements are wrappers.  The
						;remaining elements are the
						;required arguments to the

  (macrolet ((compute-mirror (loc)
	       `(- size line-size ,loc))
	     (compute-loc-from-line (line-loc)
		  cache ,line-loc mask line-size nkeys)))


	 (let* ((entries-have-value-p (%< nkeys line-size))
		;; Recompute the primary location for ourselves, since this
		;; version of the computation will do obsolete instance traps.
		;; It also side-effects the list of wrappers if there are any
		;; new wrappers as a result of obsolete traps.
		(primary (compute-wrapper-cache-location-1 mask
		(mirror (compute-mirror primary))
		(free-next 0)
		(value nil))

	   (labels ((fill-line (loc)
		      (let ((tail wrappers-and-args))
			(dotimes (i nkeys)
			  (setf (%svref cache (%+ i loc)) (pop tail)))
			(when entries-have-value-p
			  (setf (%svref cache (%+ nkeys loc)) value))))

		    (copy-line (from to)
		      (dotimes (i nkeys)
			(setf (%svref cache (%+ to i))
			      (%svref cache (%+ from i))))
		      (when entries-have-value-p
			(setf (%svref cache (%+ nkeys to))
			      (%svref cache (%+ nkeys from)))))

		    (fill-primary ()
		      (when (%svref cache primary) (displace-primary))
		      (fill-line primary))

		    (displace-primary ()		 

		      (cond ((zerop mirror)
			     (copy-to-next primary))
			    ((null (%svref cache mirror))
			     (copy-line primary mirror))
			      (let* ((mirror-contents-primary
				       ;; ++ Bug fix
				       ;; changed line below from
				       ;; (compute-loc-from-line primary) to:
				      (compute-loc-from-line mirror)))
			       (cond ((zerop mirror-contents-primary)
				      ;; The contents of the mirror location
				      ;; are obsolete.  Drop it on the floor.
				      (copy-line primary mirror))
				     ((= mirror-contents-primary mirror)
				      ;; The mirror is the primary location
				      ;; of its contents.  Leave it there.
				      (copy-to-next primary))
				      (copy-to-next mirror)
				      (copy-line primary mirror)))))))

		    (copy-to-next (loc)
		      (do ((scan-loc (%mod (%+ primary line-size) size)
				     (%mod (%+ scan-loc line-size) size))
			   (limit next-scan-limit limit))
			  ((zerop limit)
			   (when expandp (expand-cache)))
			(unless (zerop scan-loc)
			  (unless (= scan-loc mirror)
				(when (or (%= scan-loc free-next)
					  (null (%svref cache scan-loc))
					  (not (dotimes (i nkeys)
						 (unless (zerop
							     (%svref cache
								     (%+ i
						   (return t))))
					    (compute-loc-from-line scan-loc)))
				  (return (copy-line loc scan-loc))))
			  (decf limit))))

		    (expand-cache ()
		      (setq cache (expand-dcode-cache gf
			    size (generic-function-cache-size cache)
			    mask (make-wrapper-cache-mask (floor size
			    primary (compute-wrapper-cache-location-1
			    mirror (compute-mirror primary)
			    expandp nil)))


	     ;; First, get the actual value.  If this cache just has keys,
	     ;; and no values, we will use NIL as the value.
	     ;; First try to find it by scanning cache lines after primary.
	     ;; This scan stops when we reach next-scan-limit which is the
	     ;; maximimum number of next lines to try.
	     ;; If we find the element before the limit, great.  Otherwise,
	     ;; this is a tertiary cache miss.  Note that this doesn't cause
	     ;; a refill.   The refill will come later when we try to add
	     ;; this entry to the cache.  We use the variable FREE-NEXT to
	     ;; show that this next location is now up for grabs though.
	       (setq value 

		     (block scan-cache
		       (do ((try (%mod (%+ primary line-size) size)
				 (%mod (%+ try line-size) size))
			    (limit next-scan-limit limit))
			   ((zerop limit)
			    (return-from scan-cache
			      (prog2 (interrupts-on)
				     (apply tertiary-miss-fn
					    (nthcdr nkeys
			 (unless (zerop try)	;The zero entry of the
						;cache is never used!
			   (let ((tail wrappers-and-args))
			     (unless (dotimes (i nkeys)
				       (unless (eq (%svref cache (%+ i try))
						   (pop tail))
					 (return t)))
			       (setq free-next try)
			       (return-from scan-cache
				 (and entries-have-value-p
				      (%svref cache (%+ nkeys try))))))
			   (decf limit)))))
	       (unless (or (eq value '..no-applicable-method..)
			   (symbolp value))
		 (let ((old-count (cache-lock-count cache)))
		   (setf (cache-lock-count cache)
			 (if (= old-count most-positive-fixnum)
			     (1+ old-count)))
	       (return-from dcode-cache-miss value)))))))