src/code/target-sxhash.lisp

   1 ;;;; hashing functions
   2
   3 ;;;; This software is part of the SBCL system. See the README file for
   4 ;;;; more information.
   5 ;;;;
   6 ;;;; This software is derived from the CMU CL system, which was
   7 ;;;; written at Carnegie Mellon University and released into the
   8 ;;;; public domain. The software is in the public domain and is
   9 ;;;; provided with absolutely no warranty. See the COPYING and CREDITS
  10 ;;;; files for more information.
  11
  12 (in-package "SB!IMPL")
  13
  14 ;;; the depthoid explored when calculating hash values
  15 ;;;
  16 ;;; "Depthoid" here is a sort of mixture of what Common Lisp ordinarily calls
  17 ;;; depth and what Common Lisp ordinarily calls length; it's incremented either
  18 ;;; when we descend into a compound object or when we step through elements of
  19 ;;; a compound object.
  20 (defconstant +max-hash-depthoid+ 4)
  21 \f
  22 ;;;; mixing hash values
  23
  24 ;;; a function for mixing hash values
  25 ;;;
  26 ;;; desiderata:
  27 ;;;   * Non-commutativity keeps us from hashing e.g. #(1 5) to the
  28 ;;;     same value as #(5 1), and ending up in real trouble in some
  29 ;;;     special cases like bit vectors the way that CMUCL 18b SXHASH
  30 ;;;     does. (Under CMUCL 18b, SXHASH of any bit vector is 1..)
  31 ;;;   * We'd like to scatter our hash values over the entire possible range
  32 ;;;     of values instead of hashing small or common key values (like
  33 ;;;     2 and NIL and #\a) to small FIXNUMs the way that the CMUCL 18b
  34 ;;;     SXHASH function does, again helping to avoid pathologies like
  35 ;;;     hashing all bit vectors to 1.
  36 ;;;   * We'd like this to be simple and fast, too.
  37 ;;;
  38 ;;; FIXME: Should this be INLINE?
  39 (declaim (ftype (function ((and fixnum unsigned-byte)
  40                            (and fixnum unsigned-byte))
  41                           (and fixnum unsigned-byte)) mix))
  42 (defun mix (x y)
  43   ;; FIXME: We wouldn't need the nasty (SAFETY 0) here if the compiler
  44   ;; were smarter about optimizing ASH. (Without the THE FIXNUM below,
  45   ;; and the (SAFETY 0) declaration here to get the compiler to trust
  46   ;; it, the sbcl-0.5.0m cross-compiler running under Debian
  47   ;; cmucl-2.4.17 turns the ASH into a full call, requiring the
  48   ;; UNSIGNED-BYTE 32 argument to be coerced to a bignum, requiring
  49   ;; consing, and thus generally obliterating performance.)
  50   (declare (optimize (speed 3) (safety 0)))
  51   (declare (type (and fixnum unsigned-byte) x y))
  52   ;; the ideas here:
  53   ;;   * Bits diffuse in both directions (shifted left by up to 2 places
  54   ;;     in the calculation of XY, and shifted right by up to 5 places
  55   ;;     by the ASH).
  56   ;;   * The #'+ and #'LOGXOR operations don't commute with each other,
  57   ;;     so different bit patterns are mixed together as they shift
  58   ;;     past each other.
  59   ;;   * The arbitrary constant in the #'LOGXOR expression is intended
  60   ;;     to help break up any weird anomalies we might otherwise get
  61   ;;     when hashing highly regular patterns.
  62   ;; (These are vaguely like the ideas used in many cryptographic
  63   ;; algorithms, but we're not pushing them hard enough here for them
  64   ;; to be cryptographically strong.)
  65   (let* ((xy (+ (* x 3) y)))
  66     (declare (type (unsigned-byte 32) xy))
  67     (the (and fixnum unsigned-byte)
  68          (logand most-positive-fixnum
  69                  (logxor 441516657
  70                          xy
  71                          (the fixnum (ash xy -5)))))))
  72 \f
  73 ;;;; hashing strings
  74 ;;;;
  75 ;;;; Note that this operation is used in compiler symbol table lookups, so we'd
  76 ;;;; like it to be fast.
  77
  78 #!-sb-fluid (declaim (inline %sxhash-substring))
  79 (defun %sxhash-substring (string &optional (count (length string)))
  80   ;; FIXME: As in MIX above, we wouldn't need (SAFETY 0) here if the
  81   ;; cross-compiler were smarter about ASH, but we need it for sbcl-0.5.0m.
  82   (declare (optimize (speed 3) (safety 0)))
  83   (declare (type string string))
  84   (declare (type index count))
  85   (let ((result 408967240))
  86     (declare (type fixnum result))
  87     (when (typep string 'base-string)
  88       (dotimes (i count)
  89         (declare (type index i))
  90         (mixf result
  91               (the fixnum
  92                 (ash (char-code (aref string i)) 5)))))
  93     result))
  94 ;;; test:
  95 ;;;   (let ((ht (make-hash-table :test 'equal)))
  96 ;;;     (do-all-symbols (symbol)
  97 ;;;       (let* ((string (symbol-name symbol))
  98 ;;;           (hash (%sxhash-substring string)))
  99 ;;;      (if (gethash hash ht)
 100 ;;;          (unless (string= (gethash hash ht) string)
 101 ;;;            (format t "collision: ~S ~S~%" string (gethash hash ht)))
 102 ;;;          (setf (gethash hash ht) string))))
 103 ;;;     (format t "final count=~W~%" (hash-table-count ht)))
 104
 105 (defun %sxhash-simple-string (x)
 106   (declare (optimize speed))
 107   (declare (type simple-string x))
 108   (%sxhash-substring x))
 109
 110 (defun %sxhash-simple-substring (x count)
 111   (declare (optimize speed))
 112   (declare (type simple-string x))
 113   (declare (type index count))
 114   (%sxhash-substring x count))
 115 \f
 116 ;;;; the SXHASH function
 117
 118 (defun sxhash (x)
 119   ;; profiling SXHASH is hard, but we might as well try to make it go
 120   ;; fast, in case it is the bottleneck somwhere.  -- CSR, 2003-03-14
 121   (declare (optimize speed))
 122   (labels ((sxhash-number (x)
 123              (etypecase x
 124                (fixnum (sxhash x))      ; through DEFTRANSFORM
 125                (integer (sb!bignum:sxhash-bignum x))
 126                (single-float (sxhash x)) ; through DEFTRANSFORM
 127                (double-float (sxhash x)) ; through DEFTRANSFORM
 128                #!+long-float (long-float (error "stub: no LONG-FLOAT"))
 129                (ratio (let ((result 127810327))
 130                         (declare (type fixnum result))
 131                         (mixf result (sxhash-number (numerator x)))
 132                         (mixf result (sxhash-number (denominator x)))
 133                         result))
 134                (complex (let ((result 535698211))
 135                           (declare (type fixnum result))
 136                           (mixf result (sxhash-number (realpart x)))
 137                           (mixf result (sxhash-number (imagpart x)))
 138                           result))))
 139            (sxhash-recurse (x &optional (depthoid +max-hash-depthoid+))
 140              (declare (type index depthoid))
 141              (typecase x
 142                (cons
 143                 (if (plusp depthoid)
 144                     (mix (sxhash-recurse (car x) (1- depthoid))
 145                          (sxhash-recurse (cdr x) (1- depthoid)))
 146                     261835505))
 147                (instance
 148                 (if (or (typep x 'structure-object) (typep x 'condition))
 149                     (logxor 422371266
 150                             (sxhash ; through DEFTRANSFORM
 151                              (classoid-name
 152                               (layout-classoid (%instance-layout x)))))
 153                     (sxhash-instance x)))
 154                (symbol (sxhash x)) ; through DEFTRANSFORM
 155                (array
 156                 (typecase x
 157                   (simple-string (sxhash x)) ; through DEFTRANSFORM
 158                   (string (%sxhash-substring x))
 159                   (simple-bit-vector (sxhash x)) ; through DEFTRANSFORM
 160                   (bit-vector
 161                    ;; FIXME: It must surely be possible to do better
 162                    ;; than this.  The problem is that a non-SIMPLE
 163                    ;; BIT-VECTOR could be displaced to another, with a
 164                    ;; non-zero offset -- so that significantly more
 165                    ;; work needs to be done using the %RAW-BITS
 166                    ;; approach.  This will probably do for now.
 167                    (sxhash-recurse (copy-seq x) depthoid))
 168                   (t (logxor 191020317 (sxhash (array-rank x))))))
 169                (character
 170                 (logxor 72185131
 171                         (sxhash (char-code x)))) ; through DEFTRANSFORM
 172                ;; general, inefficient case of NUMBER
 173                (number (sxhash-number x))
 174                (generic-function (sxhash-instance x))
 175                (t 42))))
 176     (sxhash-recurse x)))
 177 \f
 178 ;;;; the PSXHASH function
 179
 180 ;;;; FIXME: This code does a lot of unnecessary full calls. It could be made
 181 ;;;; more efficient (in both time and space) by rewriting it along the lines
 182 ;;;; of the SXHASH code above.
 183
 184 ;;; like SXHASH, but for EQUALP hashing instead of EQUAL hashing
 185 (defun psxhash (key &optional (depthoid +max-hash-depthoid+))
 186   (declare (optimize speed))
 187   (declare (type (integer 0 #.+max-hash-depthoid+) depthoid))
 188   ;; Note: You might think it would be cleaner to use the ordering given in the
 189   ;; table from Figure 5-13 in the EQUALP section of the ANSI specification
 190   ;; here. So did I, but that is a snare for the unwary! Nothing in the ANSI
 191   ;; spec says that HASH-TABLE can't be a STRUCTURE-OBJECT, and in fact our
 192   ;; HASH-TABLEs *are* STRUCTURE-OBJECTs, so we need to pick off the special
 193   ;; HASH-TABLE behavior before we fall through to the generic STRUCTURE-OBJECT
 194   ;; comparison behavior.
 195   (typecase key
 196     (array (array-psxhash key depthoid))
 197     (hash-table (hash-table-psxhash key))
 198     (structure-object (structure-object-psxhash key depthoid))
 199     (cons (list-psxhash key depthoid))
 200     (number (number-psxhash key))
 201     (character (sxhash (char-upcase key)))
 202     (t (sxhash key))))
 203
 204 (defun array-psxhash (key depthoid)
 205   (declare (optimize speed))
 206   (declare (type array key))
 207   (declare (type (integer 0 #.+max-hash-depthoid+) depthoid))
 208   (typecase key
 209     ;; VECTORs have to be treated specially because ANSI specifies
 210     ;; that we must respect fill pointers.
 211     (vector
 212      (macrolet ((frob ()
 213                   '(let ((result 572539))
 214                      (declare (type fixnum result))
 215                      (mixf result (length key))
 216                      (dotimes (i (min depthoid (length key)))
 217                        (declare (type fixnum i))
 218                        (mixf result
 219                              (psxhash (aref key i)
 220                                       (- depthoid 1 i))))
 221                      result)))
 222        ;; CMU can compile SIMPLE-ARRAY operations so much more efficiently
 223        ;; than the general case that it's probably worth picking off the
 224        ;; common special cases.
 225        (typecase key
 226          (simple-string
 227           ;;(format t "~&SIMPLE-STRING special case~%")
 228           (frob))
 229          (simple-vector
 230           ;;(format t "~&SIMPLE-VECTOR special case~%")
 231           (frob))
 232          (t (frob)))))
 233     ;; Any other array can be hashed by working with its underlying
 234     ;; one-dimensional physical representation.
 235     (t
 236      (let ((result 60828))
 237        (declare (type fixnum result))
 238        (dotimes (i (min depthoid (array-rank key)))
 239          (mixf result (array-dimension key i)))
 240        (dotimes (i (min depthoid (array-total-size key)))
 241          (mixf result
 242                (psxhash (row-major-aref key i)
 243                         (- depthoid 1 i))))
 244        result))))
 245
 246 (defun structure-object-psxhash (key depthoid)
 247   (declare (optimize speed))
 248   (declare (type structure-object key))
 249   (declare (type (integer 0 #.+max-hash-depthoid+) depthoid))
 250   (let* ((layout (%instance-layout key)) ; i.e. slot #0
 251          (length (layout-length layout))
 252          (classoid (layout-classoid layout))
 253          (name (classoid-name classoid))
 254          (result (mix (sxhash name) (the fixnum 79867))))
 255     (declare (type fixnum result))
 256     (dotimes (i (min depthoid (1- length)))
 257       (declare (type fixnum i))
 258       (let ((j (1+ i))) ; skipping slot #0, which is for LAYOUT
 259         (declare (type fixnum j))
 260         (mixf result
 261               (psxhash (%instance-ref key j)
 262                        (1- depthoid)))))
 263     result))
 264
 265 (defun list-psxhash (key depthoid)
 266   (declare (optimize speed))
 267   (declare (type list key))
 268   (declare (type (integer 0 #.+max-hash-depthoid+) depthoid))
 269   (cond ((null key)
 270          (the fixnum 480929))
 271         ((zerop depthoid)
 272          (the fixnum 779578))
 273         (t
 274          (mix (psxhash (car key) (1- depthoid))
 275               (psxhash (cdr key) (1- depthoid))))))
 276
 277 (defun hash-table-psxhash (key)
 278   (declare (optimize speed))
 279   (declare (type hash-table key))
 280   (let ((result 103924836))
 281     (declare (type fixnum result))
 282     (mixf result (hash-table-count key))
 283     (mixf result (sxhash (hash-table-test key)))
 284     result))
 285
 286 (defun number-psxhash (key)
 287   (declare (optimize speed))
 288   (declare (type number key))
 289   (flet ((sxhash-double-float (val)
 290            (declare (type double-float val))
 291            ;; FIXME: Check to make sure that the DEFTRANSFORM kicks in and the
 292            ;; resulting code works without consing. (In Debian cmucl 2.4.17,
 293            ;; it didn't.)
 294            (sxhash val)))
 295     (etypecase key
 296       (integer (sxhash key))
 297       (float (macrolet ((frob (type)
 298                           (let ((lo (coerce most-negative-fixnum type))
 299                                 (hi (coerce most-positive-fixnum type)))
 300                             `(cond (;; This clause allows FIXNUM-sized integer
 301                                     ;; values to be handled without consing.
 302                                     (<= ,lo key ,hi)
 303                                     (multiple-value-bind (q r)
 304                                         (floor (the (,type ,lo ,hi) key))
 305                                       (if (zerop (the ,type r))
 306                                           (sxhash q)
 307                                           (sxhash-double-float
 308                                            (coerce key 'double-float)))))
 309                                    (t
 310                                     (multiple-value-bind (q r) (floor key)
 311                                       (if (zerop (the ,type r))
 312                                           (sxhash q)
 313                                           (sxhash-double-float
 314                                            (coerce key 'double-float)))))))))
 315                (etypecase key
 316                  (single-float (frob single-float))
 317                  (double-float (frob double-float))
 318                  #!+long-float
 319                  (long-float (error "LONG-FLOAT not currently supported")))))
 320       (rational (if (and (<= most-negative-double-float
 321                              key
 322                              most-positive-double-float)
 323                          (= (coerce key 'double-float) key))
 324                     (sxhash-double-float (coerce key 'double-float))
 325                     (sxhash key)))
 326       (complex (if (zerop (imagpart key))
 327                    (number-psxhash (realpart key))
 328                    (let ((result 330231))
 329                      (declare (type fixnum result))
 330                      (mixf result (number-psxhash (realpart key)))
 331                      (mixf result (number-psxhash (imagpart key)))
 332                      result))))))