0.8.2.7:

[sbcl.git] / src / code / target-sxhash.lisp

diff --git a/src/code/target-sxhash.lisp b/src/code/target-sxhash.lisp
index 96d7b12..74e739b 100644 (file)
--- a/src/code/target-sxhash.lisp
+++ b/src/code/target-sxhash.lisp
@@ -11,18 +11,13 @@
 
 (in-package "SB!IMPL")
 
 
 (in-package "SB!IMPL")
 

-(file-comment
-  "$Header$")
-

 ;;; the depthoid explored when calculating hash values
 ;;;
 ;;; "Depthoid" here is a sort of mixture of what Common Lisp ordinarily calls
 ;;; depth and what Common Lisp ordinarily calls length; it's incremented either
 ;;; when we descend into a compound object or when we step through elements of
 ;;; a compound object.
 ;;; the depthoid explored when calculating hash values
 ;;;
 ;;; "Depthoid" here is a sort of mixture of what Common Lisp ordinarily calls
 ;;; depth and what Common Lisp ordinarily calls length; it's incremented either
 ;;; when we descend into a compound object or when we step through elements of
 ;;; a compound object.

-(eval-when (:compile-toplevel :load-toplevel :execute)

 (defconstant +max-hash-depthoid+ 4)
 (defconstant +max-hash-depthoid+ 4)

-) ; EVAL-WHEN

 \f
 ;;;; mixing hash values
 
 \f
 ;;;; mixing hash values
 

@@ -31,9 +26,9 @@
 ;;; 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
 ;;; 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 SXHASH 18b
+;;;     special cases like bit vectors the way that CMUCL 18b SXHASH 

 ;;;     does. (Under CMUCL 18b, SXHASH of any bit vector is 1..)
 ;;;     does. (Under CMUCL 18b, SXHASH of any bit vector is 1..)

-;;;   * We'd like to scatter our hash values the entire possible range
+;;;   * We'd like to scatter our hash values over the entire possible range

 ;;;     of values instead of hashing small or common key values (like
 ;;;     2 and NIL and #\a) to small FIXNUMs the way that the CMUCL 18b
 ;;;     SXHASH function does, again helping to avoid pathologies like
 ;;;     of values instead of hashing small or common key values (like
 ;;;     2 and NIL and #\a) to small FIXNUMs the way that the CMUCL 18b
 ;;;     SXHASH function does, again helping to avoid pathologies like

@@ -89,11 +84,12 @@
   (declare (type index count))
   (let ((result 408967240))
     (declare (type fixnum result))
   (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))))
+    (unless (typep string '(vector nil))
+      (dotimes (i count)
+       (declare (type index i))
+       (mixf result
+             (the fixnum
+               (ash (char-code (aref string i)) 5)))))

     result))
 ;;; test:
 ;;;   (let ((ht (make-hash-table :test 'equal)))
     result))
 ;;; test:
 ;;;   (let ((ht (make-hash-table :test 'equal)))

@@ -104,7 +100,7 @@
 ;;;         (unless (string= (gethash hash ht) string)
 ;;;           (format t "collision: ~S ~S~%" string (gethash hash ht)))
 ;;;         (setf (gethash hash ht) string))))
 ;;;         (unless (string= (gethash hash ht) string)
 ;;;           (format t "collision: ~S ~S~%" string (gethash hash ht)))
 ;;;         (setf (gethash hash ht) string))))

-;;;     (format t "final count=~D~%" (hash-table-count ht)))
+;;;     (format t "final count=~W~%" (hash-table-count ht)))

 
 (defun %sxhash-simple-string (x)
   (declare (optimize speed))
 
 (defun %sxhash-simple-string (x)
   (declare (optimize speed))

@@ -120,9 +116,12 @@
 ;;;; the SXHASH function
 
 (defun sxhash (x)
 ;;;; the SXHASH function
 
 (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
+  (declare (optimize speed))

   (labels ((sxhash-number (x)
             (etypecase x
   (labels ((sxhash-number (x)
             (etypecase x

-              (fixnum (sxhash x)) ; through DEFTRANSFORM
+              (fixnum (sxhash x))      ; through DEFTRANSFORM

               (integer (sb!bignum:sxhash-bignum x))
               (single-float (sxhash x)) ; through DEFTRANSFORM
               (double-float (sxhash x)) ; through DEFTRANSFORM
               (integer (sb!bignum:sxhash-bignum x))
               (single-float (sxhash x)) ; through DEFTRANSFORM
               (double-float (sxhash x)) ; through DEFTRANSFORM

@@ -140,32 +139,39 @@
           (sxhash-recurse (x &optional (depthoid +max-hash-depthoid+))
             (declare (type index depthoid))
             (typecase x
           (sxhash-recurse (x &optional (depthoid +max-hash-depthoid+))
             (declare (type index depthoid))
             (typecase x

-              (list
+              (cons

                (if (plusp depthoid)
                    (mix (sxhash-recurse (car x) (1- depthoid))
                         (sxhash-recurse (cdr x) (1- depthoid)))
                    261835505))
               (instance
                (if (plusp depthoid)
                    (mix (sxhash-recurse (car x) (1- depthoid))
                         (sxhash-recurse (cdr x) (1- depthoid)))
                    261835505))
               (instance

-               (if (typep x 'structure-object)
+               (if (or (typep x 'structure-object) (typep x 'condition))

                    (logxor 422371266
                            (sxhash ; through DEFTRANSFORM
                    (logxor 422371266
                            (sxhash ; through DEFTRANSFORM

-                            (class-name (layout-class (%instance-layout x)))))
-                   309518995))
+                            (classoid-name
+                             (layout-classoid (%instance-layout x)))))
+                   (sxhash-instance x)))

               (symbol (sxhash x)) ; through DEFTRANSFORM
               (symbol (sxhash x)) ; through DEFTRANSFORM

-              (number (sxhash-number x))

               (array
                (typecase x
                  (simple-string (sxhash x)) ; through DEFTRANSFORM
                  (string (%sxhash-substring x))
               (array
                (typecase x
                  (simple-string (sxhash x)) ; through DEFTRANSFORM
                  (string (%sxhash-substring x))

-                 (bit-vector (let ((result 410823708))
-                               (declare (type fixnum result))
-                               (dotimes (i (min depthoid (length x)))
-                                 (mixf result (aref x i)))
-                               result))
+                 (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
                  (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)))
 \f
               (t 42))))
     (sxhash-recurse x)))
 \f

@@ -190,7 +196,7 @@
     (array (array-psxhash key depthoid))
     (hash-table (hash-table-psxhash key))
     (structure-object (structure-object-psxhash key depthoid))
     (array (array-psxhash key depthoid))
     (hash-table (hash-table-psxhash key))
     (structure-object (structure-object-psxhash key depthoid))

-    (list (list-psxhash key depthoid))
+    (cons (list-psxhash key depthoid))

     (number (number-psxhash key))
     (character (sxhash (char-upcase key)))
     (t (sxhash key))))
     (number (number-psxhash key))
     (character (sxhash (char-upcase key)))
     (t (sxhash key))))

@@ -243,8 +249,8 @@
   (declare (type (integer 0 #.+max-hash-depthoid+) depthoid))
   (let* ((layout (%instance-layout key)) ; i.e. slot #0
         (length (layout-length layout))
   (declare (type (integer 0 #.+max-hash-depthoid+) depthoid))
   (let* ((layout (%instance-layout key)) ; i.e. slot #0
         (length (layout-length layout))

-        (class (layout-class layout))
-        (name (class-name class))
+        (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)))
         (result (mix (sxhash name) (the fixnum 79867))))
     (declare (type fixnum result))
     (dotimes (i (min depthoid (1- length)))

@@ -309,7 +315,7 @@
               (etypecase key
                 (single-float (frob single-float))
                 (double-float (frob double-float))
               (etypecase key
                 (single-float (frob single-float))
                 (double-float (frob double-float))

-                (short-float (frob short-float))
+                #!+long-float

                 (long-float (error "LONG-FLOAT not currently supported")))))
       (rational (if (and (<= most-negative-double-float
                             key
                 (long-float (error "LONG-FLOAT not currently supported")))))
       (rational (if (and (<= most-negative-double-float
                             key

@@ -324,88 +330,3 @@
                     (mixf result (number-psxhash (realpart key)))
                     (mixf result (number-psxhash (imagpart key)))
                     result))))))
                     (mixf result (number-psxhash (realpart key)))
                     (mixf result (number-psxhash (imagpart key)))
                     result))))))

-
-;;; SXHASH and PSXHASH should distribute hash values well over the
-;;; space of possible values, so that collisions between the hash values
-;;; of unequal objects should be very uncommon.
-;;;
-;;; FIXME: These tests should be enabled once the rest of the system is
-;;; stable. (For now, I don't want to mess with things like making sure
-;;; that bignums are hashed uniquely.)
-;;;#!+sb-test
-#+nil
-(let* ((test-cases `((0 . 1)
-                    (0 . 1)
-                    (1 . 0)
-                    ((1 . 0) (0 . 0))
-                    ((0 . 1) (0 . 0))
-                    ((0 . 0) (1 . 0))
-                    ((0 . 0) (0 . 1))
-                    #((1 . 0) (0 . 0))
-                    #((0 . 1) (0 . 0))
-                    #((0 . 0) (1 . 0))
-                    #((0 . 0) (0 . 1))
-                    #((1 . 0) (0 . 0))
-                    #((0 1) (0 0))
-                    #((0 0) (1 0))
-                    #((0 0) (0 1))
-                    #(#(1 0) (0 0))
-                    #(#(0 1) (0 0))
-                    #(#(0 0) (1 0))
-                    #(#(0 0) (0 1))
-                    #(#*00 #*10)
-                    #(#(0 0) (0 1.0d0))
-                    #(#(-0.0d0 0) (1.0 0))
-                    ;; KLUDGE: Some multi-dimensional array test cases would
-                    ;; be good here too, but currently SBCL isn't smart enough
-                    ;; to dump them as literals, and I'm too lazy to make
-                    ;; code to create them at run time. -- WHN 20000111
-                    44 44.0 44.0d0
-                    44 44.0 44.0d0
-                    -44 -44.0 -44.0d0
-                    0 0.0 0.0d0
-                    -0 -0.0 -0.0d0
-                    -121 -121.0 -121.0d0
-                    3/4 0.75 0.75d0
-                    -3/4 -0.75 -0.75d0
-                    44.1 44.1d0
-                    45 45.0 45.0d0
-                    ,(expt 2 33) ,(expt 2.0 33) ,(expt 2.0d0 33)
-                    ,(- (expt 1/2 50)) ,(- (expt 0.5 50)) ,(- (expt 0.5d0 50))
-                    ,(- (expt 1/2 50)) ,(- (expt 0.5 50)) ,(- (expt 0.5d0 50))
-                    #c(1.0 2.0) #c(1 2.0) #c(1.5 -3/2) #c(3/2 -3/2) #c(0 1)
-                    #c(1.0 2.0) #c(1 2.0) #c(1.5 -3/2) #c(3/2 -3/2) #c(0 1)
-                    ,(make-hash-table)
-                    ,(make-hash-table :test 'equal)
-                    "abc" "ABC" "aBc" 'abc #(#\a #\b #\c) #(a b c) #("A" b c)
-                    "abcc"
-                    "" #* #() () (()) #(()) (#())
-                    "" #* #() () (()) #(()) (#())
-                    #\x #\X #\*
-                    #\x #\X #\*)))
-  (dolist (i test-cases)
-    (unless (typep (sxhash i) '(and fixnum unsigned-byte))
-      (error "bad SXHASH behavior for ~S" i))
-    (unless (typep (psxhash i) '(and fixnum unsigned-byte))
-      (error "bad PSXHASH behavior for ~S" i))
-    (dolist (j test-cases)
-      (flet ((t->boolean (x) (if x t nil)))
-       ;; Note: It's possible that a change to the hashing algorithm could
-       ;; leave it correct but still cause this test to bomb by causing an
-       ;; unlucky random collision. That's not very likely (since there are
-       ;; (EXPT 2 29) possible hash values and only on the order of 100 test
-       ;; cases, but it's probably worth checking if you are getting a
-       ;; mystifying error from this test.
-       (unless (eq (t->boolean (equal i j))
-                   (t->boolean (= (sxhash i) (sxhash j))))
-         (error "bad SXHASH behavior for ~S ~S" i j))
-       (unless (eq (t->boolean (equalp i j))
-                   (t->boolean (= (psxhash i) (psxhash j))))
-         (error "bad PSXHASH behavior for ~S ~S" i j))))))
-
-;;; FIXME: Test that the the hash functions can deal with common cases without
-;;; consing.
-;(defun consless-test ()
-;  (dotimes (j 100000)
-;    (dolist (i '("yo" #(1 2 3) #2A((1 2) (1 2)) (1 2 (3)) 1 1.0 1.0d0))
-;      (psxhash i))))