From aa15be083d706358ce3611e750b95b7abcde6d61 Mon Sep 17 00:00:00 2001 From: Christophe Rhodes Date: Wed, 10 Mar 2004 16:10:17 +0000 Subject: [PATCH] 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!) --- NEWS | 3 +++ src/code/target-sxhash.lisp | 53 ++++++++++++++++++++++++++++++++++--------- version.lisp-expr | 2 +- 3 files changed, 46 insertions(+), 12 deletions(-) diff --git a/NEWS b/NEWS index 1d40778..0b1ee32 100644 --- a/NEWS +++ b/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: diff --git a/src/code/target-sxhash.lisp b/src/code/target-sxhash.lisp index 571b9c1..99e0830 100644 --- a/src/code/target-sxhash.lisp +++ b/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 +;;;; 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 diff --git a/version.lisp-expr b/version.lisp-expr index 7dc6b0c..85c5a2c 100644 --- a/version.lisp-expr +++ b/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" -- 1.7.10.4