X-Git-Url: http://repo.macrolet.net/gitweb/?a=blobdiff_plain;f=src%2Fcode%2Ftarget-sxhash.lisp;h=5e7b3d9d68aea2c0b1009f7431c2d8ad374c45b1;hb=a74b0bdb483504f6faddf8089f848f61ed94b92a;hp=96d7b1260ef1f3c0238d211b7e01fb0d1ca63946;hpb=a530bbe337109d898d5b4a001fc8f1afa3b5dc39;p=sbcl.git diff --git a/src/code/target-sxhash.lisp b/src/code/target-sxhash.lisp index 96d7b12..5e7b3d9 100644 --- a/src/code/target-sxhash.lisp +++ b/src/code/target-sxhash.lisp @@ -11,18 +11,13 @@ (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. -(eval-when (:compile-toplevel :load-toplevel :execute) (defconstant +max-hash-depthoid+ 4) -) ; EVAL-WHEN ;;;; 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 -;;; 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..) -;;; * 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 @@ -104,7 +99,7 @@ ;;; (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)) @@ -122,7 +117,7 @@ (defun sxhash (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 @@ -150,9 +145,8 @@ (logxor 422371266 (sxhash ; through DEFTRANSFORM (class-name (layout-class (%instance-layout x))))) - 309518995)) + (sxhash-instance x))) (symbol (sxhash x)) ; through DEFTRANSFORM - (number (sxhash-number x)) (array (typecase x (simple-string (sxhash x)) ; through DEFTRANSFORM @@ -166,6 +160,9 @@ (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))) @@ -324,88 +321,3 @@ (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))))