X-Git-Url: http://repo.macrolet.net/gitweb/?a=blobdiff_plain;f=src%2Fcode%2Ftarget-sxhash.lisp;h=dbe9d23de5549e818ba013102813c697b8479be3;hb=5a9b7fcee7cd5374010d7a5b05463b84abc35079;hp=0c4f16ff2bda1b855e40c2a98ecd7e231aa76390;hpb=2d3cb6dba6461e98744eca2a1df4f770cea468ca;p=sbcl.git

diff --git a/src/code/target-sxhash.lisp b/src/code/target-sxhash.lisp
index 0c4f16f..dbe9d23 100644
--- a/src/code/target-sxhash.lisp
+++ b/src/code/target-sxhash.lisp
@@ -26,7 +26,7 @@
 ;;; desiderata:
 ;;;   * Non-commutativity keeps us from hashing e.g. #(1 5) to the
 ;;;     same value as #(5 1), and ending up in real trouble in some
-;;;     special cases like bit vectors the way that CMUCL 18b SXHASH 
+;;;     special cases like bit vectors the way that CMUCL 18b SXHASH
 ;;;     does. (Under CMUCL 18b, SXHASH of any bit vector is 1..)
 ;;;   * We'd like to scatter our hash values over the entire possible range
 ;;;     of values instead of hashing small or common key values (like
@@ -36,9 +36,10 @@
 ;;;   * We'd like this to be simple and fast, too.
 ;;;
 ;;; FIXME: Should this be INLINE?
-(declaim (ftype (function ((and fixnum unsigned-byte)
-			   (and fixnum unsigned-byte))
-			  (and fixnum unsigned-byte)) mix))
+(declaim (ftype (sfunction ((and fixnum unsigned-byte)
+                            (and fixnum unsigned-byte))
+                           (and fixnum unsigned-byte))
+                mix))
 (defun mix (x y)
   ;; FIXME: We wouldn't need the nasty (SAFETY 0) here if the compiler
   ;; were smarter about optimizing ASH. (Without the THE FIXNUM below,
@@ -63,116 +64,167 @@
   ;; algorithms, but we're not pushing them hard enough here for them
   ;; to be cryptographically strong.)
   (let* ((xy (+ (* x 3) y)))
-    (declare (type (unsigned-byte 32) xy))
-    (the (and fixnum unsigned-byte)
-	 (logand most-positive-fixnum
-		 (logxor 441516657
-			 xy
-			 (the fixnum (ash xy -5)))))))
+    (logand most-positive-fixnum
+            (logxor 441516657
+                    xy
+                    (ash xy -5)))))
 
 ;;;; hashing strings
 ;;;;
-;;;; Note that this operation is used in compiler symbol table lookups, so we'd
-;;;; like it to be fast.
+;;;; Note that this operation is used in compiler symbol table
+;;;; lookups, so we'd like it to be fast.
+;;;;
+;;;; As of 2004-03-10, we implement the one-at-a-time algorithm
+;;;; designed by Bob Jenkins (see
+;;;; <http://burtleburtle.net/bob/hash/doobs.html> for some more
+;;;; information).
 
 #!-sb-fluid (declaim (inline %sxhash-substring))
 (defun %sxhash-substring (string &optional (count (length string)))
   ;; FIXME: As in MIX above, we wouldn't need (SAFETY 0) here if the
-  ;; cross-compiler were smarter about ASH, but we need it for sbcl-0.5.0m.
+  ;; cross-compiler were smarter about ASH, but we need it for
+  ;; sbcl-0.5.0m.  (probably no longer true?  We might need SAFETY 0
+  ;; to elide some type checks, but then again if this is inlined in
+  ;; all the critical places, we might not -- CSR, 2004-03-10)
   (declare (optimize (speed 3) (safety 0)))
   (declare (type string string))
   (declare (type index count))
-  (let ((result 408967240))
-    (declare (type fixnum result))
-    (dotimes (i count)
-      (declare (type index i))
-      (mixf result
-	    (the fixnum
-		 (ash (char-code (aref string i)) 5))))
-    result))
+  (macrolet ((set-result (form)
+               `(setf result (ldb (byte #.sb!vm:n-word-bits 0) ,form))))
+    (let ((result 0))
+      (declare (type (unsigned-byte #.sb!vm:n-word-bits) result))
+      (unless (typep string '(vector nil))
+        (dotimes (i count)
+          (declare (type index i))
+          (set-result (+ result (char-code (aref string i))))
+          (set-result (+ result (ash result 10)))
+          (set-result (logxor result (ash result -6)))))
+      (set-result (+ result (ash result 3)))
+      (set-result (logxor result (ash result -11)))
+      (set-result (logxor result (ash result 15)))
+      (logand result most-positive-fixnum))))
 ;;; test:
 ;;;   (let ((ht (make-hash-table :test 'equal)))
 ;;;     (do-all-symbols (symbol)
 ;;;       (let* ((string (symbol-name symbol))
-;;;	      (hash (%sxhash-substring string)))
-;;;	 (if (gethash hash ht)
-;;;	     (unless (string= (gethash hash ht) string)
-;;;	       (format t "collision: ~S ~S~%" string (gethash hash ht)))
-;;;	     (setf (gethash hash ht) string))))
+;;;           (hash (%sxhash-substring string)))
+;;;      (if (gethash hash ht)
+;;;          (unless (string= (gethash hash ht) string)
+;;;            (format t "collision: ~S ~S~%" string (gethash hash ht)))
+;;;          (setf (gethash hash ht) string))))
 ;;;     (format t "final count=~W~%" (hash-table-count ht)))
 
 (defun %sxhash-simple-string (x)
   (declare (optimize speed))
   (declare (type simple-string x))
-  (%sxhash-substring x))
+  ;; KLUDGE: this FLET is a workaround (suggested by APD) for presence
+  ;; of let conversion in the cross compiler, which otherwise causes
+  ;; strongly suboptimal register allocation.
+  (flet ((trick (x)
+           (%sxhash-substring x)))
+    (declare (notinline trick))
+    (trick x)))
 
 (defun %sxhash-simple-substring (x count)
   (declare (optimize speed))
   (declare (type simple-string x))
   (declare (type index count))
-  (%sxhash-substring x count))
+  ;; see comment in %SXHASH-SIMPLE-STRING
+  (flet ((trick (x count)
+           (%sxhash-substring x count)))
+    (declare (notinline trick))
+    (trick x count)))
 
 ;;;; the SXHASH function
 
+;; simple cases
+(declaim (ftype (sfunction (integer) (integer 0 #.sb!xc:most-positive-fixnum))
+                sxhash-bignum))
+(declaim (ftype (sfunction (t) (integer 0 #.sb!xc:most-positive-fixnum))
+                sxhash-instance))
+
+(defmacro hash-array-using (recurse array depthoid)
+  ;; Any other array can be hashed by working with its underlying
+  ;; one-dimensional physical representation. Used by both SXHASH and
+  ;; PSXHASH.
+  (once-only ((array array) (depthoid depthoid))
+    `(let ((result 60828123))
+       (declare (type fixnum result))
+       (dotimes (i (min ,depthoid (array-rank ,array)))
+         (mixf result (array-dimension ,array i)))
+       (dotimes (i (min ,depthoid (array-total-size ,array)))
+         (mixf result
+               (,recurse (row-major-aref ,array i) (- ,depthoid 1 i))))
+       result)))
+
 (defun sxhash (x)
   ;; profiling SXHASH is hard, but we might as well try to make it go
-  ;; fast, in case it is the bottleneck somwhere.  -- CSR, 2003-03-14
+  ;; fast, in case it is the bottleneck somewhere.  -- CSR, 2003-03-14
   (declare (optimize speed))
   (labels ((sxhash-number (x)
-	     (etypecase x
-	       (fixnum (sxhash x))	; through DEFTRANSFORM
-	       (integer (sb!bignum:sxhash-bignum x))
-	       (single-float (sxhash x)) ; through DEFTRANSFORM
-	       (double-float (sxhash x)) ; through DEFTRANSFORM
-	       #!+long-float (long-float (error "stub: no LONG-FLOAT"))
-	       (ratio (let ((result 127810327))
-			(declare (type fixnum result))
-			(mixf result (sxhash-number (numerator x)))
-			(mixf result (sxhash-number (denominator x)))
-			result))
-	       (complex (let ((result 535698211))
-			  (declare (type fixnum result))
-			  (mixf result (sxhash-number (realpart x)))
-			  (mixf result (sxhash-number (imagpart x)))
-			  result))))
-	   (sxhash-recurse (x &optional (depthoid +max-hash-depthoid+))
-	     (declare (type index depthoid))
-	     (typecase x
-	       (cons
-		(if (plusp depthoid)
-		    (mix (sxhash-recurse (car x) (1- depthoid))
-			 (sxhash-recurse (cdr x) (1- depthoid)))
-		    261835505))
-	       (instance
-		(if (typep x 'structure-object)
-		    (logxor 422371266
-			    (sxhash ; through DEFTRANSFORM
-			     (classoid-name
-			      (layout-classoid (%instance-layout x)))))
-		    (sxhash-instance x)))
-	       (symbol (sxhash x)) ; through DEFTRANSFORM
-	       (array
-		(typecase x
-		  (simple-string (sxhash x)) ; through DEFTRANSFORM
-		  (string (%sxhash-substring x))
-		  (simple-bit-vector (sxhash x)) ; through DEFTRANSFORM
-		  (bit-vector
-		   ;; FIXME: It must surely be possible to do better
-		   ;; than this.  The problem is that a non-SIMPLE
-		   ;; BIT-VECTOR could be displaced to another, with a
-		   ;; non-zero offset -- so that significantly more
-		   ;; work needs to be done using the %RAW-BITS
-		   ;; approach.  This will probably do for now.
-		   (sxhash-recurse (copy-seq x) depthoid))
-		  (t (logxor 191020317 (sxhash (array-rank x))))))
-	       (character
-		(logxor 72185131
-			(sxhash (char-code x)))) ; through DEFTRANSFORM
-	       ;; general, inefficient case of NUMBER
-	       (number (sxhash-number x))
-	       (generic-function (sxhash-instance x))
-	       (t 42))))
-    (sxhash-recurse x)))
+             (etypecase x
+               (fixnum (sxhash x))      ; through DEFTRANSFORM
+               (integer (sb!bignum:sxhash-bignum x))
+               (single-float (sxhash x)) ; through DEFTRANSFORM
+               (double-float (sxhash x)) ; through DEFTRANSFORM
+               #!+long-float (long-float (error "stub: no LONG-FLOAT"))
+               (ratio (let ((result 127810327))
+                        (declare (type fixnum result))
+                        (mixf result (sxhash-number (numerator x)))
+                        (mixf result (sxhash-number (denominator x)))
+                        result))
+               (complex (let ((result 535698211))
+                          (declare (type fixnum result))
+                          (mixf result (sxhash-number (realpart x)))
+                          (mixf result (sxhash-number (imagpart x)))
+                          result))))
+           (sxhash-recurse (x depthoid)
+             (declare (type index depthoid))
+             (typecase x
+               ;; we test for LIST here, rather than CONS, because the
+               ;; type test for CONS is in fact the test for
+               ;; LIST-POINTER-LOWTAG followed by a negated test for
+               ;; NIL.  If we're going to have to test for NIL anyway,
+               ;; we might as well do it explicitly and pick off the
+               ;; answer.  -- CSR, 2004-07-14
+               (list
+                (if (null x)
+                    (sxhash x) ; through DEFTRANSFORM
+                    (if (plusp depthoid)
+                        (mix (sxhash-recurse (car x) (1- depthoid))
+                             (sxhash-recurse (cdr x) (1- depthoid)))
+                        261835505)))
+               (instance
+                (if (or (typep x 'structure-object) (typep x 'condition))
+                    (logxor 422371266
+                            (sxhash ; through DEFTRANSFORM
+                             (classoid-name
+                              (layout-classoid (%instance-layout x)))))
+                    (sxhash-instance x)))
+               (symbol (sxhash x)) ; through DEFTRANSFORM
+               (array
+                (typecase x
+                  (simple-string (sxhash x)) ; through DEFTRANSFORM
+                  (string (%sxhash-substring x))
+                  (simple-bit-vector (sxhash x)) ; through DEFTRANSFORM
+                  (bit-vector
+                   ;; FIXME: It must surely be possible to do better
+                   ;; than this.  The problem is that a non-SIMPLE
+                   ;; BIT-VECTOR could be displaced to another, with a
+                   ;; non-zero offset -- so that significantly more
+                   ;; work needs to be done using the %RAW-BITS
+                   ;; approach.  This will probably do for now.
+                   (sxhash-recurse (copy-seq x) depthoid))
+                  (t
+                   (hash-array-using sxhash-recurse x depthoid))))
+               (character
+                (logxor 72185131
+                        (sxhash (char-code x)))) ; through DEFTRANSFORM
+               ;; general, inefficient case of NUMBER
+               (number (sxhash-number x))
+               (generic-function (sxhash-instance x))
+               (t 42))))
+    (sxhash-recurse x +max-hash-depthoid+)))
 
 ;;;; the PSXHASH function
 
@@ -209,56 +261,49 @@
     ;; that we must respect fill pointers.
     (vector
      (macrolet ((frob ()
-		  '(let ((result 572539))
-		     (declare (type fixnum result))
-		     (mixf result (length key))
-		     (dotimes (i (min depthoid (length key)))
-		       (declare (type fixnum i))
-		       (mixf result
-			     (psxhash (aref key i)
-				      (- depthoid 1 i))))
-		     result)))
+                  '(let ((result 572539))
+                     (declare (type fixnum result))
+                     (mixf result (length key))
+                     (dotimes (i (min depthoid (length key)))
+                       (declare (type fixnum i))
+                       (mixf result
+                             (psxhash (aref key i)
+                                      (- depthoid 1 i))))
+                     result)))
        ;; CMU can compile SIMPLE-ARRAY operations so much more efficiently
        ;; than the general case that it's probably worth picking off the
        ;; common special cases.
        (typecase key
-	 (simple-string
-	  ;;(format t "~&SIMPLE-STRING special case~%")
-	  (frob))
-	 (simple-vector
-	  ;;(format t "~&SIMPLE-VECTOR special case~%")
-	  (frob))
-	 (t (frob)))))
-    ;; Any other array can be hashed by working with its underlying
-    ;; one-dimensional physical representation.
+         (simple-string
+          ;;(format t "~&SIMPLE-STRING special case~%")
+          (frob))
+         (simple-vector
+          ;;(format t "~&SIMPLE-VECTOR special case~%")
+          (frob))
+         (t (frob)))))
     (t
-     (let ((result 60828))
-       (declare (type fixnum result))
-       (dotimes (i (min depthoid (array-rank key)))
-	 (mixf result (array-dimension key i)))
-       (dotimes (i (min depthoid (array-total-size key)))
-	 (mixf result
-	       (psxhash (row-major-aref key i)
-			(- depthoid 1 i))))
-       result))))
+     (hash-array-using psxhash key depthoid))))
 
 (defun structure-object-psxhash (key depthoid)
   (declare (optimize speed))
   (declare (type structure-object key))
   (declare (type (integer 0 #.+max-hash-depthoid+) depthoid))
   (let* ((layout (%instance-layout key)) ; i.e. slot #0
-	 (length (layout-length layout))
-	 (classoid (layout-classoid layout))
-	 (name (classoid-name classoid))
-	 (result (mix (sxhash name) (the fixnum 79867))))
+         (length (layout-length layout))
+         (classoid (layout-classoid layout))
+         (name (classoid-name classoid))
+         (result (mix (sxhash name) (the fixnum 79867))))
     (declare (type fixnum result))
-    (dotimes (i (min depthoid (1- length)))
+    (dotimes (i (min depthoid (- length 1 (layout-n-untagged-slots layout))))
       (declare (type fixnum i))
       (let ((j (1+ i))) ; skipping slot #0, which is for LAYOUT
-	(declare (type fixnum j))
-	(mixf result
-	      (psxhash (%instance-ref key j)
-		       (1- depthoid)))))
+        (declare (type fixnum j))
+        (mixf result
+              (psxhash (%instance-ref key j)
+                       (1- depthoid)))))
+    ;; KLUDGE: Should hash untagged slots, too.  (Although +max-hash-depthoid+
+    ;; is pretty low currently, so they might not make it into the hash
+    ;; value anyway.)
     result))
 
 (defun list-psxhash (key depthoid)
@@ -266,12 +311,12 @@
   (declare (type list key))
   (declare (type (integer 0 #.+max-hash-depthoid+) depthoid))
   (cond ((null key)
-	 (the fixnum 480929))
-	((zerop depthoid)
-	 (the fixnum 779578))
-	(t
-	 (mix (psxhash (car key) (1- depthoid))
-	      (psxhash (cdr key) (1- depthoid))))))
+         (the fixnum 480929))
+        ((zerop depthoid)
+         (the fixnum 779578))
+        (t
+         (mix (psxhash (car key) (1- depthoid))
+              (psxhash (cdr key) (1- depthoid))))))
 
 (defun hash-table-psxhash (key)
   (declare (optimize speed))
@@ -286,46 +331,46 @@
   (declare (optimize speed))
   (declare (type number key))
   (flet ((sxhash-double-float (val)
-	   (declare (type double-float val))
-	   ;; FIXME: Check to make sure that the DEFTRANSFORM kicks in and the
-	   ;; resulting code works without consing. (In Debian cmucl 2.4.17,
-	   ;; it didn't.)
-	   (sxhash val)))
+           (declare (type double-float val))
+           ;; FIXME: Check to make sure that the DEFTRANSFORM kicks in and the
+           ;; resulting code works without consing. (In Debian cmucl 2.4.17,
+           ;; it didn't.)
+           (sxhash val)))
     (etypecase key
       (integer (sxhash key))
       (float (macrolet ((frob (type)
-			  (let ((lo (coerce most-negative-fixnum type))
-				(hi (coerce most-positive-fixnum type)))
-			    `(cond (;; This clause allows FIXNUM-sized integer
-				    ;; values to be handled without consing.
-				    (<= ,lo key ,hi)
-				    (multiple-value-bind (q r)
-					(floor (the (,type ,lo ,hi) key))
-				      (if (zerop (the ,type r))
-					  (sxhash q)
-					  (sxhash-double-float
-					   (coerce key 'double-float)))))
-				   (t
-				    (multiple-value-bind (q r) (floor key)
-				      (if (zerop (the ,type r))
-					  (sxhash q)
-					  (sxhash-double-float
-					   (coerce key 'double-float)))))))))
-	       (etypecase key
-		 (single-float (frob single-float))
-		 (double-float (frob double-float))
-		 (short-float (frob short-float))
-		 (long-float (error "LONG-FLOAT not currently supported")))))
+                          (let ((lo (coerce most-negative-fixnum type))
+                                (hi (coerce most-positive-fixnum type)))
+                            `(cond (;; This clause allows FIXNUM-sized integer
+                                    ;; values to be handled without consing.
+                                    (<= ,lo key ,hi)
+                                    (multiple-value-bind (q r)
+                                        (floor (the (,type ,lo ,hi) key))
+                                      (if (zerop (the ,type r))
+                                          (sxhash q)
+                                          (sxhash-double-float
+                                           (coerce key 'double-float)))))
+                                   (t
+                                    (multiple-value-bind (q r) (floor key)
+                                      (if (zerop (the ,type r))
+                                          (sxhash q)
+                                          (sxhash-double-float
+                                           (coerce key 'double-float)))))))))
+               (etypecase key
+                 (single-float (frob single-float))
+                 (double-float (frob double-float))
+                 #!+long-float
+                 (long-float (error "LONG-FLOAT not currently supported")))))
       (rational (if (and (<= most-negative-double-float
-			     key
-			     most-positive-double-float)
-			 (= (coerce key 'double-float) key))
-		    (sxhash-double-float (coerce key 'double-float))
-		    (sxhash key)))
+                             key
+                             most-positive-double-float)
+                         (= (coerce key 'double-float) key))
+                    (sxhash-double-float (coerce key 'double-float))
+                    (sxhash key)))
       (complex (if (zerop (imagpart key))
-		   (number-psxhash (realpart key))
-		   (let ((result 330231))
-		     (declare (type fixnum result))
-		     (mixf result (number-psxhash (realpart key)))
-		     (mixf result (number-psxhash (imagpart key)))
-		     result))))))
+                   (number-psxhash (realpart key))
+                   (let ((result 330231))
+                     (declare (type fixnum result))
+                     (mixf result (number-psxhash (realpart key)))
+                     (mixf result (number-psxhash (imagpart key)))
+                     result))))))