3 ;;;; This software is part of the SBCL system. See the README file for
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.
12 (in-package "SB!IMPL")
14 (defun pointer-hash (key)
17 ;;; the depthoid explored when calculating hash values
19 ;;; "Depthoid" here is a sort of mixture of what Common Lisp ordinarily calls
20 ;;; depth and what Common Lisp ordinarily calls length; it's incremented either
21 ;;; when we descend into a compound object or when we step through elements of
22 ;;; a compound object.
23 (defconstant +max-hash-depthoid
+ 4)
25 ;;;; mixing hash values
27 ;;; a function for mixing hash values
30 ;;; * Non-commutativity keeps us from hashing e.g. #(1 5) to the
31 ;;; same value as #(5 1), and ending up in real trouble in some
32 ;;; special cases like bit vectors the way that CMUCL 18b SXHASH
33 ;;; does. (Under CMUCL 18b, SXHASH of any bit vector is 1..)
34 ;;; * We'd like to scatter our hash values over the entire possible range
35 ;;; of values instead of hashing small or common key values (like
36 ;;; 2 and NIL and #\a) to small FIXNUMs the way that the CMUCL 18b
37 ;;; SXHASH function does, again helping to avoid pathologies like
38 ;;; hashing all bit vectors to 1.
39 ;;; * We'd like this to be simple and fast, too.
40 (declaim (ftype (sfunction ((and fixnum unsigned-byte
)
41 (and fixnum unsigned-byte
))
42 (and fixnum unsigned-byte
))
44 (declaim (inline mix
))
46 (declare (optimize (speed 3)))
47 (declare (type (and fixnum unsigned-byte
) x y
))
49 ;; * Bits diffuse in both directions (shifted arbitrarily left by
50 ;; the multiplication in the calculation of XY, and shifted
51 ;; right by up to 5 places by the ASH).
52 ;; * The #'+ and #'LOGXOR operations don't commute with each other,
53 ;; so different bit patterns are mixed together as they shift
55 ;; * The arbitrary constant XOR used in the LOGXOR expression is
56 ;; intended to help break up any weird anomalies we might
57 ;; otherwise get when hashing highly regular patterns.
58 ;; (These are vaguely like the ideas used in many cryptographic
59 ;; algorithms, but we're not pushing them hard enough here for them
60 ;; to be cryptographically strong.)
62 ;; note: 3622009729038463111 is a 62-bit prime such that its low 61
63 ;; bits, low 60 bits and low 29 bits are all also primes, thus
64 ;; giving decent distributions no matter which of the possible
65 ;; values of most-positive-fixnum we have. It is derived by simple
66 ;; search starting from 2^60*pi. The multiplication should be
67 ;; efficient no matter what the platform thanks to modular
69 (let* ((mul (logand 3622009729038463111 sb
!xc
:most-positive-fixnum
))
70 (xor (logand 608948948376289905 sb
!xc
:most-positive-fixnum
))
71 (xy (logand (+ (* x mul
) y
) sb
!xc
:most-positive-fixnum
)))
72 (logand (logxor xor xy
(ash xy -
5)) sb
!xc
:most-positive-fixnum
)))
74 ;; Return a number that increments by 1 for each word-pair allocation,
75 ;; barring complications such as exhaustion of the current page.
76 ;; The result is guaranteed to be a positive fixnum.
77 (declaim (inline address-based-counter-val
))
78 (defun address-based-counter-val ()
79 #!+(and (not sb-thread
) cheneygc
)
80 (ash (sap-int (dynamic-space-free-pointer)) (- (1+ sb
!vm
:word-shift
)))
81 ;; dynamic-space-free-pointer increments only when a page is full.
82 ;; Using boxed_region directly is finer-grained.
83 #!+(and (not sb-thread
) gencgc
)
84 (ash (extern-alien "boxed_region" unsigned-long
)
85 (- (1+ sb
!vm
:word-shift
)))
86 ;; threads imply gencgc. use the per-thread alloc region pointer
88 (ash (sap-int (sb!vm
::current-thread-offset-sap
89 sb
!vm
::thread-alloc-region-slot
))
90 (- (1+ sb
!vm
:word-shift
))))
92 ;; Return some bits that are dependent on the next address that will be
93 ;; allocated, mixed with the previous state (in case addresses get recycled).
94 ;; This algorithm, used for stuffing a hash-code into instances of CTYPE
95 ;; subtypes, is simpler than RANDOM, and a test of randomness won't
96 ;; measure up as well, but for the intended use, it doesn't matter.
97 ;; CLOS hashes could probably be made to use this.
98 (defun quasi-random-address-based-hash (state mask
)
99 (declare (type (simple-array (and fixnum unsigned-byte
) (1)) state
))
100 ;; Ok with multiple threads - No harm, no foul.
101 (logand (setf (aref state
0) (mix (address-based-counter-val) (aref state
0)))
107 ;;;; Note that this operation is used in compiler symbol table
108 ;;;; lookups, so we'd like it to be fast.
110 ;;;; As of 2004-03-10, we implement the one-at-a-time algorithm
111 ;;;; designed by Bob Jenkins (see
112 ;;;; <http://burtleburtle.net/bob/hash/doobs.html> for some more
115 (declaim (inline %sxhash-substring
))
116 (defun %sxhash-substring
(string &optional
(count (length string
)))
117 ;; FIXME: As in MIX above, we wouldn't need (SAFETY 0) here if the
118 ;; cross-compiler were smarter about ASH, but we need it for
119 ;; sbcl-0.5.0m. (probably no longer true? We might need SAFETY 0
120 ;; to elide some type checks, but then again if this is inlined in
121 ;; all the critical places, we might not -- CSR, 2004-03-10)
122 (declare (optimize (speed 3) (safety 0)))
123 (declare (type string string
))
124 (declare (type index count
))
125 (macrolet ((set-result (form)
126 `(setf result
(ldb (byte #.sb
!vm
:n-word-bits
0) ,form
))))
128 (declare (type (unsigned-byte #.sb
!vm
:n-word-bits
) result
))
129 (unless (typep string
'(vector nil
))
131 (declare (type index i
))
132 (set-result (+ result
(char-code (aref string i
))))
133 (set-result (+ result
(ash result
10)))
134 (set-result (logxor result
(ash result -
6)))))
135 (set-result (+ result
(ash result
3)))
136 (set-result (logxor result
(ash result -
11)))
137 (set-result (logxor result
(ash result
15)))
138 (logand result most-positive-fixnum
))))
140 ;;; (let ((ht (make-hash-table :test 'equal)))
141 ;;; (do-all-symbols (symbol)
142 ;;; (let* ((string (symbol-name symbol))
143 ;;; (hash (%sxhash-substring string)))
144 ;;; (if (gethash hash ht)
145 ;;; (unless (string= (gethash hash ht) string)
146 ;;; (format t "collision: ~S ~S~%" string (gethash hash ht)))
147 ;;; (setf (gethash hash ht) string))))
148 ;;; (format t "final count=~W~%" (hash-table-count ht)))
150 (defun %sxhash-simple-string
(x)
151 (declare (optimize speed
))
152 (declare (type simple-string x
))
153 ;; KLUDGE: this FLET is a workaround (suggested by APD) for presence
154 ;; of let conversion in the cross compiler, which otherwise causes
155 ;; strongly suboptimal register allocation.
157 (%sxhash-substring x
)))
158 (declare (notinline trick
))
161 (defun %sxhash-simple-substring
(x count
)
162 (declare (optimize speed
))
163 (declare (type simple-string x
))
164 (declare (type index count
))
165 ;; see comment in %SXHASH-SIMPLE-STRING
166 (flet ((trick (x count
)
167 (%sxhash-substring x count
)))
168 (declare (notinline trick
))
171 ;;;; the SXHASH function
174 (declaim (ftype (sfunction (integer) hash
) sxhash-bignum
))
176 (defun new-instance-hash-code ()
177 ;; ANSI SXHASH wants us to make a good-faith effort to produce
178 ;; hash-codes that are well distributed within the range of
179 ;; non-negative fixnums, and this address-based operation does that.
180 ;; This is faster than calling RANDOM, and is random enough.
184 (quasi-random-address-based-hash
185 (load-time-value (make-array 1 :element-type
'(and fixnum unsigned-byte
))
187 most-positive-fixnum
))))
189 ;; Make sure we never return 0 (almost no chance of that anyway).
192 (declaim (inline std-instance-hash
))
193 (defun std-instance-hash (instance)
194 (let ((hash (%instance-ref instance sb
!pcl
::std-instance-hash-slot-index
)))
195 (if (not (eql hash
0))
197 (let ((new (new-instance-hash-code)))
198 ;; At most one thread will compute a random hash.
199 ;; %INSTANCE-CAS is a full call if there is no vop for it.
200 (let ((old (%instance-cas instance sb
!pcl
::std-instance-hash-slot-index
202 (if (eql old
0) new old
))))))
204 ;; These are also random numbers, but not lazily computed.
205 (declaim (inline fsc-instance-hash
))
206 (defun fsc-instance-hash (fin)
207 (%funcallable-instance-info fin sb
!pcl
::fsc-instance-hash-slot-index
))
210 ;; profiling SXHASH is hard, but we might as well try to make it go
211 ;; fast, in case it is the bottleneck somewhere. -- CSR, 2003-03-14
212 (declare (optimize speed
))
213 (labels ((sxhash-number (x)
215 (fixnum (sxhash x
)) ; through DEFTRANSFORM
216 (integer (sb!bignum
:sxhash-bignum x
))
217 (single-float (sxhash x
)) ; through DEFTRANSFORM
218 (double-float (sxhash x
)) ; through DEFTRANSFORM
219 #!+long-float
(long-float (error "stub: no LONG-FLOAT"))
220 (ratio (let ((result 127810327))
221 (declare (type fixnum result
))
222 (mixf result
(sxhash-number (numerator x
)))
223 (mixf result
(sxhash-number (denominator x
)))
225 (complex (let ((result 535698211))
226 (declare (type fixnum result
))
227 (mixf result
(sxhash-number (realpart x
)))
228 (mixf result
(sxhash-number (imagpart x
)))
230 (sxhash-recurse (x depthoid
)
231 (declare (type index depthoid
))
233 ;; we test for LIST here, rather than CONS, because the
234 ;; type test for CONS is in fact the test for
235 ;; LIST-POINTER-LOWTAG followed by a negated test for
236 ;; NIL. If we're going to have to test for NIL anyway,
237 ;; we might as well do it explicitly and pick off the
238 ;; answer. -- CSR, 2004-07-14
241 (sxhash x
) ; through DEFTRANSFORM
243 (mix (sxhash-recurse (car x
) (1- depthoid
))
244 (sxhash-recurse (cdr x
) (1- depthoid
)))
249 ;; Pathnames are EQUAL if all the components are EQUAL, so
250 ;; we hash all of the components of a pathname together.
251 (let ((hash (sxhash-recurse (pathname-host x
) depthoid
)))
252 (mixf hash
(sxhash-recurse (pathname-device x
) depthoid
))
253 (mixf hash
(sxhash-recurse (pathname-directory x
) depthoid
))
254 (mixf hash
(sxhash-recurse (pathname-name x
) depthoid
))
255 (mixf hash
(sxhash-recurse (pathname-type x
) depthoid
))
256 ;; Hash :NEWEST the same as NIL because EQUAL for
257 ;; pathnames assumes that :newest and nil are equal.
258 (let ((version (%pathname-version x
)))
259 (mixf hash
(sxhash-recurse (if (eq version
:newest
)
264 ;; LAYOUTs have an easily-accesible hash value: we
265 ;; might as well use it. It's not actually uniform
266 ;; over the space of hash values (it excludes 0 and
267 ;; some of the larger numbers) but it's better than
268 ;; simply returning the same value for all LAYOUT
269 ;; objects, as the next branch would do.
270 (layout-clos-hash x
))
271 ((or structure-object condition
)
273 ;; FIXME: why not (LAYOUT-CLOS-HASH ...) ?
274 (sxhash ; through DEFTRANSFORM
276 (layout-classoid (%instance-layout x
))))))
277 (t (std-instance-hash x
))))
278 (symbol (sxhash x
)) ; through DEFTRANSFORM
281 (simple-string (sxhash x
)) ; through DEFTRANSFORM
282 (string (%sxhash-substring x
))
283 (simple-bit-vector (sxhash x
)) ; through DEFTRANSFORM
285 ;; FIXME: It must surely be possible to do better
286 ;; than this. The problem is that a non-SIMPLE
287 ;; BIT-VECTOR could be displaced to another, with a
288 ;; non-zero offset -- so that significantly more
289 ;; work needs to be done using the %VECTOR-RAW-BITS
290 ;; approach. This will probably do for now.
291 (sxhash-recurse (copy-seq x
) depthoid
))
292 (t (logxor 191020317 (sxhash (array-rank x
))))))
295 (sxhash (char-code x
)))) ; through DEFTRANSFORM
296 ;; general, inefficient case of NUMBER
297 (number (sxhash-number x
))
298 (generic-function (fsc-instance-hash x
))
300 (sxhash-recurse x
+max-hash-depthoid
+)))
302 ;;;; the PSXHASH function
304 ;;;; FIXME: This code does a lot of unnecessary full calls. It could be made
305 ;;;; more efficient (in both time and space) by rewriting it along the lines
306 ;;;; of the SXHASH code above.
308 ;;; like SXHASH, but for EQUALP hashing instead of EQUAL hashing
309 (defun psxhash (key &optional
(depthoid +max-hash-depthoid
+))
310 (declare (optimize speed
))
311 (declare (type (integer 0 #.
+max-hash-depthoid
+) depthoid
))
312 ;; Note: You might think it would be cleaner to use the ordering given in the
313 ;; table from Figure 5-13 in the EQUALP section of the ANSI specification
314 ;; here. So did I, but that is a snare for the unwary! Nothing in the ANSI
315 ;; spec says that HASH-TABLE can't be a STRUCTURE-OBJECT, and in fact our
316 ;; HASH-TABLEs *are* STRUCTURE-OBJECTs, so we need to pick off the special
317 ;; HASH-TABLE behavior before we fall through to the generic STRUCTURE-OBJECT
318 ;; comparison behavior.
320 (array (array-psxhash key depthoid
))
321 (hash-table (hash-table-psxhash key
))
322 (structure-object (structure-object-psxhash key depthoid
))
323 (cons (list-psxhash key depthoid
))
324 (number (number-psxhash key
))
325 (character (char-code (char-upcase key
)))
328 (defun array-psxhash (key depthoid
)
329 (declare (optimize speed
))
330 (declare (type array key
))
331 (declare (type (integer 0 #.
+max-hash-depthoid
+) depthoid
))
333 ;; VECTORs have to be treated specially because ANSI specifies
334 ;; that we must respect fill pointers.
337 '(let ((result 572539))
338 (declare (type fixnum result
))
339 (mixf result
(length key
))
340 (when (plusp depthoid
)
342 (dotimes (i (length key
))
343 (declare (type fixnum i
))
345 (psxhash (aref key i
) depthoid
))))
347 (make-dispatch (types)
349 ,@(loop for type in types
352 (make-dispatch (simple-base-string
353 (simple-array character
(*))
355 (simple-array (unsigned-byte 8) (*))
356 (simple-array fixnum
(*))
358 ;; Any other array can be hashed by working with its underlying
359 ;; one-dimensional physical representation.
361 (let ((result 60828))
362 (declare (type fixnum result
))
363 (dotimes (i (array-rank key
))
364 (mixf result
(array-dimension key i
)))
365 (when (plusp depthoid
)
367 (dotimes (i (array-total-size key
))
369 (psxhash (row-major-aref key i
) depthoid
))))
372 (defun structure-object-psxhash (key depthoid
)
373 (declare (optimize speed
))
374 (declare (type structure-object key
))
375 (declare (type (integer 0 #.
+max-hash-depthoid
+) depthoid
))
376 (let* ((layout (%instance-layout key
)) ; i.e. slot #0
377 ;; Is there some reason the name of the layout's classoid
378 ;; should be preferred as the seed, instead of using the CLOS-HASH
379 ;; just like SXHASH does?
380 (classoid (layout-classoid layout
))
381 (name (classoid-name classoid
))
382 (result (mix (sxhash name
) (the fixnum
79867))))
383 (declare (type fixnum result
))
384 (when (plusp depthoid
)
385 (let ((max-iterations depthoid
)
386 (depthoid (1- depthoid
)))
387 ;; We don't mix in LAYOUT here because it was already done above.
388 (do-instance-tagged-slot (i key
:layout layout
:exclude-padding t
)
389 (mixf result
(psxhash (%instance-ref key i
) depthoid
))
390 (if (zerop (decf max-iterations
)) (return)))))
391 ;; [The following comment blurs some issues: indeed it would take
392 ;; a second loop in the non-interleaved-slots code; that loop might
393 ;; never execute because depthoid "cuts off", although that's an arbitrary
394 ;; choice and could be decided otherwise; and efficiency would likely
395 ;; demand that we store some additional metadata in the LAYOUT indicating
396 ;; how to mix the bits in, because floating-point +/-zeros have to
397 ;; be considered EQUALP]
398 ;; KLUDGE: Should hash untagged slots, too. (Although +max-hash-depthoid+
399 ;; is pretty low currently, so they might not make it into the hash
403 (defun list-psxhash (key depthoid
)
404 (declare (optimize speed
))
405 (declare (type list key
))
406 (declare (type (integer 0 #.
+max-hash-depthoid
+) depthoid
))
412 (mix (psxhash (car key
) (1- depthoid
))
413 (psxhash (cdr key
) (1- depthoid
))))))
415 (defun hash-table-psxhash (key)
416 (declare (optimize speed
))
417 (declare (type hash-table key
))
418 (let ((result 103924836))
419 (declare (type fixnum result
))
420 (mixf result
(hash-table-count key
))
421 (mixf result
(sxhash (hash-table-test key
)))
424 (defun number-psxhash (key)
425 (declare (optimize speed
))
426 (declare (type number key
))
427 (flet ((sxhash-double-float (val)
428 (declare (type double-float val
))
429 ;; FIXME: Check to make sure that the DEFTRANSFORM kicks in and the
430 ;; resulting code works without consing. (In Debian cmucl 2.4.17,
434 (integer (sxhash key
))
435 (float (macrolet ((frob (type)
436 (let ((lo (coerce sb
!xc
:most-negative-fixnum type
))
437 (hi (coerce sb
!xc
:most-positive-fixnum type
)))
438 `(cond (;; This clause allows FIXNUM-sized integer
439 ;; values to be handled without consing.
441 (multiple-value-bind (q r
)
442 (floor (the (,type
,lo
,hi
) key
))
443 (if (zerop (the ,type r
))
446 (coerce key
'double-float
)))))
448 (multiple-value-bind (q r
) (floor key
)
449 (if (zerop (the ,type r
))
452 (coerce key
'double-float
)))))))))
454 (single-float (frob single-float
))
455 (double-float (frob double-float
))
457 (long-float (error "LONG-FLOAT not currently supported")))))
458 (rational (if (and (<= most-negative-double-float
460 most-positive-double-float
)
461 (= (coerce key
'double-float
) key
))
462 (sxhash-double-float (coerce key
'double-float
))
464 (complex (if (zerop (imagpart key
))
465 (number-psxhash (realpart key
))
466 (let ((result 330231))
467 (declare (type fixnum result
))
468 (mixf result
(number-psxhash (realpart key
)))
469 (mixf result
(number-psxhash (imagpart key
)))
472 ;;; Semantic equivalent of SXHASH, but better-behaved for function names.
473 ;;; It performs more work by not cutting off as soon in the CDR direction.
474 ;;; More work here equates to less work in the global hashtable.
475 ;;; To wit: (eq (sxhash '(foo a b c bar)) (sxhash '(foo a b c d))) => T
476 ;;; but the corresponding globaldb-sxhashoids differ.
477 (defun sb!c
::globaldb-sxhashoid
(name)
479 (declare (optimize (safety 0))) ; after the argc check
480 ;; TRAVERSE will walk across more cons cells than RECURSE will descend.
481 ;; That's why this isn't just one self-recursive function.
482 (labels ((traverse (accumulator x length-limit
)
483 (declare (fixnum length-limit
))
484 (cond ((atom x
) (mix (sxhash x
) accumulator
))
485 ((zerop length-limit
) accumulator
)
486 (t (traverse (mix (recurse (car x
) 4) accumulator
)
487 (cdr x
) (1- length-limit
)))))
488 (recurse (x depthoid
) ; depthoid = a blend of level and length
489 (declare (fixnum depthoid
))
490 (cond ((atom x
) (sxhash x
))
492 #.
(logand sb
!xc
:most-positive-fixnum
#36Rglobaldbsxhashoid
))
493 (t (mix (recurse (car x
) (1- depthoid
))
494 (recurse (cdr x
) (1- depthoid
)))))))
495 (traverse 0 name
10))))