Permalink
Browse files

0.8.8.23:

	Better %SXHASH-SUBSTRING (patch Juho Snellman sbcl-devel 2004-03-09)
	... frob comments a little
	... make the same FLET workaround in %SXHASH-SIMPLE-SUBSTRING
	... probably fasl-incompatible with 0.8.8.22, but I've already
		changed the fasl version number once this cycle.  Let's
		see if anyone complains :)
	... 20% faster at compiling mk-defsystem on DB's iMac
		(MORE SPEED!)
  • Loading branch information...
1 parent 398c7bf commit aa15be083d706358ce3611e750b95b7abcde6d61 @csrhodes csrhodes committed Mar 10, 2004
Showing with 46 additions and 12 deletions.
  1. +3 −0 NEWS
  2. +42 −11 src/code/target-sxhash.lisp
  3. +1 −1 version.lisp-expr
View
3 NEWS
@@ -2327,6 +2327,9 @@ changes in sbcl-0.8.9 relative to sbcl-0.8.8:
WARNINGs, not just STYLE-WARNINGs, on the assumption that this is
more often programmer error than deliberate exploitation of undefined
behaviour.
+ * optimization: the hash algorithm for strings has changed to one
+ that is less vulnerable to spurious collisions. (thanks to Juho
+ Snellman)
* optimization: implemented multiplication as a modular
(UNSIGNED-BYTE 32) operation on the PPC backend.
* fixed some bugs revealed by Paul Dietz' test suite:
View
53 src/code/target-sxhash.lisp
@@ -70,25 +70,46 @@
;;;; 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))
+ (let ((result 0))
+ (declare (type (unsigned-byte 32) result))
(unless (typep string '(vector nil))
(dotimes (i count)
(declare (type index i))
- (mixf result
- (the fixnum
- (ash (char-code (aref string i)) 5)))))
- result))
+ (setf result
+ (ldb (byte 32 0)
+ (+ result (char-code (aref string i)))))
+ (setf result
+ (ldb (byte 32 0)
+ (+ result (ash result 10))))
+ (setf result
+ (logxor result (ash result -6)))))
+ (setf result
+ (ldb (byte 32 0)
+ (+ result (ash result 3))))
+ (setf result
+ (logxor result (ash result -11)))
+ (setf result
+ (ldb (byte 32 0)
+ (logxor result (ash result 15))))
+ (logand result most-positive-fixnum)))
;;; test:
;;; (let ((ht (make-hash-table :test 'equal)))
;;; (do-all-symbols (symbol)
@@ -103,13 +124,23 @@
(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
View
2 version.lisp-expr
@@ -17,4 +17,4 @@
;;; checkins which aren't released. (And occasionally for internal
;;; versions, especially for internal versions off the main CVS
;;; branch, it gets hairier, e.g. "0.pre7.14.flaky4.13".)
-"0.8.8.22"
+"0.8.8.23"

0 comments on commit aa15be0

Please sign in to comment.