X-Git-Url: http://repo.macrolet.net/gitweb/?a=blobdiff_plain;f=src%2Fcode%2Ftarget-hash-table.lisp;h=83fd171eb3e0d5d154dc904b406f2d68efe0607b;hb=8ef3aa533aba5ac5760e83b798cd6b2388a807a6;hp=e4d0a32c1c2c6745ab4856d74e82c097eb393b38;hpb=f98d63ddb86859259bf12f2e276fb577cbe168eb;p=sbcl.git

diff --git a/src/code/target-hash-table.lisp b/src/code/target-hash-table.lisp
index e4d0a32..83fd171 100644
--- a/src/code/target-hash-table.lisp
+++ b/src/code/target-hash-table.lisp
@@ -14,6 +14,27 @@
 
 ;;;; utilities
 
+;; This stuff is performance critical and unwind-protect is too
+;; slow. And without the locking the next vector can get cyclic
+;; causing looping in a WITHOUT-GCING form, SHRINK-VECTOR can corrupt
+;; memory and who knows what else.
+(defmacro with-spinlock-and-without-gcing ((spinlock) &body body)
+  #!-sb-thread
+  (declare (ignore spinlock))
+  (with-unique-names (old-gc-inhibit)
+    `(let ((,old-gc-inhibit *gc-inhibit*)
+           (*gc-inhibit* t))
+       (unwind-protect
+            (progn
+              #!+sb-thread
+              (sb!thread::get-spinlock ,spinlock)
+              ,@body)
+         #!+sb-thread
+         (sb!thread::release-spinlock ,spinlock)
+         (let ((*gc-inhibit* ,old-gc-inhibit))
+           ;; the test is racy, but it can err only on the overeager side
+           (sb!kernel::maybe-handle-pending-gc))))))
+
 (eval-when (:compile-toplevel :load-toplevel :execute)
   (defconstant max-hash sb!xc:most-positive-fixnum))
 
@@ -82,10 +103,6 @@
 
 (defconstant +min-hash-table-size+ 16)
 (defconstant +min-hash-table-rehash-threshold+ (float 1/16 1.0))
-;; as explained by pmai on openprojects #lisp IRC 2002-07-30: #x80000000
-;; is bigger than any possible nonEQ hash value, and thus indicates an
-;; empty slot; and EQ hash tables don't use HASH-TABLE-HASH-VECTOR
-(defconstant +magic-hash-vector-value+ #x80000000)
 
 (defun make-hash-table (&key (test 'eql)
                              (size +min-hash-table-size+)
@@ -185,7 +202,8 @@
                    :hash-vector (unless (eq test 'eq)
                                   (make-array size+1
                                               :element-type '(unsigned-byte #.sb!vm:n-word-bits)
-                                              :initial-element +magic-hash-vector-value+)))))
+                                              :initial-element +magic-hash-vector-value+))
+                   :spinlock (sb!thread::make-spinlock))))
       (declare (type index size+1 scaled-size length))
       ;; Set up the free list, all free. These lists are 0 terminated.
       (do ((i 1 (1+ i)))
@@ -325,11 +343,11 @@
     (setf (hash-table-next-vector table) new-next-vector)
     (setf (hash-table-hash-vector table) new-hash-vector)
     ;; Shrink the old vectors to 0 size to help the conservative GC.
-    (shrink-vector old-kv-vector 0)
-    (shrink-vector old-index-vector 0)
-    (shrink-vector old-next-vector 0)
+    (%shrink-vector old-kv-vector 0)
+    (%shrink-vector old-index-vector 0)
+    (%shrink-vector old-next-vector 0)
     (when old-hash-vector
-      (shrink-vector old-hash-vector 0))
+      (%shrink-vector old-hash-vector 0))
     (setf (hash-table-rehash-trigger table) new-size))
   (values))
 
@@ -426,39 +444,48 @@
   "Three argument version of GETHASH"
   (declare (type hash-table hash-table)
            (values t (member t nil)))
-  (without-gcing
+  (with-spinlock-and-without-gcing ((hash-table-spinlock hash-table))
    (cond ((= (get-header-data (hash-table-table hash-table))
              sb!vm:vector-must-rehash-subtype)
           (rehash-without-growing hash-table))
          ((not (zerop (hash-table-needing-rehash hash-table)))
           (flush-needing-rehash hash-table)))
-   ;; Search for key in the hash table.
-   (multiple-value-bind (hashing eq-based)
-       (funcall (hash-table-hash-fun hash-table) key)
-     (declare (type hash hashing))
-     (let* ((index-vector (hash-table-index-vector hash-table))
-            (length (length index-vector))
-            (index (rem hashing length))
-            (next (aref index-vector index))
-            (table (hash-table-table hash-table))
-            (next-vector (hash-table-next-vector hash-table))
-            (hash-vector (hash-table-hash-vector hash-table))
-            (test-fun (hash-table-test-fun hash-table)))
-       (declare (type index index))
-       ;; Search next-vector chain for a matching key.
-       (if (or eq-based (not hash-vector))
-           (do ((next next (aref next-vector next)))
-               ((zerop next) (values default nil))
-             (declare (type index next))
-             (when (eq key (aref table (* 2 next)))
-               (return (values (aref table (1+ (* 2 next))) t))))
-           (do ((next next (aref next-vector next)))
-               ((zerop next) (values default nil))
-             (declare (type index next))
-             (when (and (= hashing (aref hash-vector next))
-                        (funcall test-fun key (aref table (* 2 next))))
-               ;; Found.
-               (return (values (aref table (1+ (* 2 next))) t)))))))))
+
+   ;; First check the cache.  Use EQ here for speed.
+   (let ((cache (hash-table-cache hash-table))
+         (table (hash-table-table hash-table)))
+
+     (if (and cache (< cache (length table)) (eq (aref table cache) key))
+         (values (aref table (1+ cache)) t)
+
+       ;; Search for key in the hash table.
+       (multiple-value-bind (hashing eq-based)
+           (funcall (hash-table-hash-fun hash-table) key)
+         (declare (type hash hashing))
+         (let* ((index-vector (hash-table-index-vector hash-table))
+                (length (length index-vector))
+                (index (rem hashing length))
+                (next (aref index-vector index))
+                (next-vector (hash-table-next-vector hash-table))
+                (hash-vector (hash-table-hash-vector hash-table))
+                (test-fun (hash-table-test-fun hash-table)))
+           (declare (type index index))
+           ;; Search next-vector chain for a matching key.
+           (if (or eq-based (not hash-vector))
+               (do ((next next (aref next-vector next)))
+                   ((zerop next) (values default nil))
+                 (declare (type index next))
+                 (when (eq key (aref table (* 2 next)))
+                   (setf (hash-table-cache hash-table) (* 2 next))
+                   (return (values (aref table (1+ (* 2 next))) t))))
+             (do ((next next (aref next-vector next)))
+                 ((zerop next) (values default nil))
+               (declare (type index next))
+               (when (and (= hashing (aref hash-vector next))
+                          (funcall test-fun key (aref table (* 2 next))))
+                 ;; Found.
+                 (setf (hash-table-cache hash-table) (* 2 next))
+                 (return (values (aref table (1+ (* 2 next))) t)))))))))))
 
 ;;; so people can call #'(SETF GETHASH)
 (defun (setf gethash) (new-value key table &optional default)
@@ -468,7 +495,7 @@
 (defun %puthash (key hash-table value)
   (declare (type hash-table hash-table))
   (aver (hash-table-index-vector hash-table))
-  (without-gcing
+  (with-spinlock-and-without-gcing ((hash-table-spinlock hash-table))
    ;; We need to rehash here so that a current key can be found if it
    ;; exists. Check that there is room for one more entry. May not be
    ;; needed if the key is already present.
@@ -480,64 +507,76 @@
          ((not (zerop (hash-table-needing-rehash hash-table)))
           (flush-needing-rehash hash-table)))
 
-   ;; Search for key in the hash table.
-   (multiple-value-bind (hashing eq-based)
-       (funcall (hash-table-hash-fun hash-table) key)
-     (declare (type hash hashing))
-     (let* ((index-vector (hash-table-index-vector hash-table))
-            (length (length index-vector))
-            (index (rem hashing length))
-            (next (aref index-vector index))
-            (kv-vector (hash-table-table hash-table))
-            (next-vector (hash-table-next-vector hash-table))
-            (hash-vector (hash-table-hash-vector hash-table))
-            (test-fun (hash-table-test-fun hash-table)))
-       (declare (type index index))
-
-       (cond ((or eq-based (not hash-vector))
-              (when eq-based
-                (set-header-data kv-vector sb!vm:vector-valid-hashing-subtype))
-
-              ;; Search next-vector chain for a matching key.
-              (do ((next next (aref next-vector next)))
-                  ((zerop next))
-                (declare (type index next))
-                (when (eq key (aref kv-vector (* 2 next)))
-                  ;; Found, just replace the value.
-                  (setf (aref kv-vector (1+ (* 2 next))) value)
-                  (return-from %puthash value))))
-             (t
-              ;; Search next-vector chain for a matching key.
-              (do ((next next (aref next-vector next)))
-                  ((zerop next))
-                (declare (type index next))
-                (when (and (= hashing (aref hash-vector next))
-                           (funcall test-fun key
-                                    (aref kv-vector (* 2 next))))
-                  ;; Found, just replace the value.
-                  (setf (aref kv-vector (1+ (* 2 next))) value)
-                  (return-from %puthash value)))))
-
-       ;; Pop a KV slot off the free list
-       (let ((free-kv-slot (hash-table-next-free-kv hash-table)))
-         ;; Double-check for overflow.
-         (aver (not (zerop free-kv-slot)))
-         (setf (hash-table-next-free-kv hash-table)
-               (aref next-vector free-kv-slot))
-         (incf (hash-table-number-entries hash-table))
-
-         (setf (aref kv-vector (* 2 free-kv-slot)) key)
-         (setf (aref kv-vector (1+ (* 2 free-kv-slot))) value)
-
-         ;; Setup the hash-vector if necessary.
-         (when hash-vector
-           (if (not eq-based)
-               (setf (aref hash-vector free-kv-slot) hashing)
-               (aver (= (aref hash-vector free-kv-slot) +magic-hash-vector-value+))))
-
-         ;; Push this slot into the next chain.
-         (setf (aref next-vector free-kv-slot) next)
-         (setf (aref index-vector index) free-kv-slot)))))
+   (let ((cache (hash-table-cache hash-table))
+         (kv-vector (hash-table-table hash-table)))
+
+     ;; Check the cache
+     (if (and cache (< cache (length kv-vector)) (eq (aref kv-vector cache) key))
+         ;; If cached, just store here
+         (setf (aref kv-vector (1+ cache)) value)
+
+       ;; Search for key in the hash table.
+       (multiple-value-bind (hashing eq-based)
+           (funcall (hash-table-hash-fun hash-table) key)
+         (declare (type hash hashing))
+         (let* ((index-vector (hash-table-index-vector hash-table))
+                (length (length index-vector))
+                (index (rem hashing length))
+                (next (aref index-vector index))
+                (kv-vector (hash-table-table hash-table))
+                (next-vector (hash-table-next-vector hash-table))
+                (hash-vector (hash-table-hash-vector hash-table))
+                (test-fun (hash-table-test-fun hash-table)))
+           (declare (type index index))
+
+           (cond ((or eq-based (not hash-vector))
+                  (when eq-based
+                    (set-header-data kv-vector sb!vm:vector-valid-hashing-subtype))
+
+                  ;; Search next-vector chain for a matching key.
+                  (do ((next next (aref next-vector next)))
+                      ((zerop next))
+                    (declare (type index next))
+                    (when (eq key (aref kv-vector (* 2 next)))
+                      ;; Found, just replace the value.
+                      (setf (hash-table-cache hash-table) (* 2 next))
+                      (setf (aref kv-vector (1+ (* 2 next))) value)
+                      (return-from %puthash value))))
+                 (t
+                  ;; Search next-vector chain for a matching key.
+                  (do ((next next (aref next-vector next)))
+                      ((zerop next))
+                    (declare (type index next))
+                    (when (and (= hashing (aref hash-vector next))
+                               (funcall test-fun key
+                                        (aref kv-vector (* 2 next))))
+                      ;; Found, just replace the value.
+                      (setf (hash-table-cache hash-table) (* 2 next))
+                      (setf (aref kv-vector (1+ (* 2 next))) value)
+                      (return-from %puthash value)))))
+
+           ;; Pop a KV slot off the free list
+           (let ((free-kv-slot (hash-table-next-free-kv hash-table)))
+             ;; Double-check for overflow.
+             (aver (not (zerop free-kv-slot)))
+             (setf (hash-table-next-free-kv hash-table)
+                   (aref next-vector free-kv-slot))
+             (incf (hash-table-number-entries hash-table))
+
+             (setf (hash-table-cache hash-table) (* 2 free-kv-slot))
+             (setf (aref kv-vector (* 2 free-kv-slot)) key)
+             (setf (aref kv-vector (1+ (* 2 free-kv-slot))) value)
+
+             ;; Setup the hash-vector if necessary.
+             (when hash-vector
+               (if (not eq-based)
+                   (setf (aref hash-vector free-kv-slot) hashing)
+                   (aver (= (aref hash-vector free-kv-slot)
+                            +magic-hash-vector-value+))))
+
+             ;; Push this slot into the next chain.
+             (setf (aref next-vector free-kv-slot) next)
+             (setf (aref index-vector index) free-kv-slot)))))))
   value)
 
 (defun remhash (key hash-table)
@@ -546,7 +585,7 @@
    was such an entry, or NIL if not."
   (declare (type hash-table hash-table)
            (values (member t nil)))
-  (without-gcing
+  (with-spinlock-and-without-gcing ((hash-table-spinlock hash-table))
    ;; We need to rehash here so that a current key can be found if it
    ;; exists.
    (cond ((= (get-header-data (hash-table-table hash-table))
@@ -555,6 +594,9 @@
          ((not (zerop (hash-table-needing-rehash hash-table)))
           (flush-needing-rehash hash-table)))
 
+   ;; For now, just clear the cache
+   (setf (hash-table-cache hash-table) nil)
+
    ;; Search for key in the hash table.
    (multiple-value-bind (hashing eq-based)
        (funcall (hash-table-hash-fun hash-table) key)
@@ -580,7 +622,8 @@
                       (hash-table-next-free-kv hash-table))
                 (setf (hash-table-next-free-kv hash-table) slot-location)
                 (when hash-vector
-                  (setf (aref hash-vector slot-location) +magic-hash-vector-value+))
+                  (setf (aref hash-vector slot-location)
+                        +magic-hash-vector-value+))
                 (decf (hash-table-number-entries hash-table))
                 t))
          (cond ((zerop next)
@@ -614,30 +657,32 @@
   "This removes all the entries from HASH-TABLE and returns the hash table
    itself."
   (declare (optimize speed))
-  (let* ((kv-vector (hash-table-table hash-table))
-         (next-vector (hash-table-next-vector hash-table))
-         (hash-vector (hash-table-hash-vector hash-table))
-         (size (length next-vector))
-         (index-vector (hash-table-index-vector hash-table)))
-    ;; Disable GC tricks.
-    (set-header-data kv-vector sb!vm:vector-normal-subtype)
-    ;; Mark all slots as empty by setting all keys and values to magic
-    ;; tag.
-    (aver (eq (aref kv-vector 0) hash-table))
-    (fill kv-vector +empty-ht-slot+ :start 2)
-    ;; Set up the free list, all free.
-    (do ((i 1 (1+ i)))
-        ((>= i (1- size)))
-      (setf (aref next-vector i) (1+ i)))
-    (setf (aref next-vector (1- size)) 0)
-    (setf (hash-table-next-free-kv hash-table) 1)
-    (setf (hash-table-needing-rehash hash-table) 0)
-    ;; Clear the index-vector.
-    (fill index-vector 0)
-    ;; Clear the hash-vector.
-    (when hash-vector
-      (fill hash-vector +magic-hash-vector-value+)))
-  (setf (hash-table-number-entries hash-table) 0)
+  (with-spinlock-and-without-gcing ((hash-table-spinlock hash-table))
+    (let* ((kv-vector (hash-table-table hash-table))
+           (next-vector (hash-table-next-vector hash-table))
+           (hash-vector (hash-table-hash-vector hash-table))
+           (size (length next-vector))
+           (index-vector (hash-table-index-vector hash-table)))
+      ;; Disable GC tricks.
+      (set-header-data kv-vector sb!vm:vector-normal-subtype)
+      ;; Mark all slots as empty by setting all keys and values to magic
+      ;; tag.
+      (aver (eq (aref kv-vector 0) hash-table))
+      (fill kv-vector +empty-ht-slot+ :start 2)
+      ;; Set up the free list, all free.
+      (do ((i 1 (1+ i)))
+          ((>= i (1- size)))
+          (setf (aref next-vector i) (1+ i)))
+      (setf (aref next-vector (1- size)) 0)
+      (setf (hash-table-next-free-kv hash-table) 1)
+      (setf (hash-table-needing-rehash hash-table) 0)
+      ;; Clear the index-vector.
+      (fill index-vector 0)
+      ;; Clear the hash-vector.
+      (when hash-vector
+        (fill hash-vector +magic-hash-vector-value+)))
+    (setf (hash-table-cache hash-table) nil)
+    (setf (hash-table-number-entries hash-table) 0))
   hash-table)
 
 ;;;; MAPHASH
@@ -701,14 +746,12 @@
 
 (def!method print-object ((hash-table hash-table) stream)
   (declare (type stream stream))
-  (cond ((not *print-readably*)
+  (cond ((or (not *print-readably*) (not *read-eval*))
          (print-unreadable-object (hash-table stream :type t :identity t)
            (format stream
                    ":TEST ~S :COUNT ~S"
                    (hash-table-test hash-table)
                    (hash-table-count hash-table))))
-        ((not *read-eval*)
-         (error "can't print hash tables readably without *READ-EVAL*"))
         (t
          (with-standard-io-syntax
           (format stream