[Sbcl-commits] CVS: sbcl/src/compiler srctran.lisp,1.150,1.151

[Juho S. <js...@us...>]

Update of /cvsroot/sbcl/sbcl/src/compiler
In directory sc8-pr-cvs8.sourceforge.net:/tmp/cvs-serv12016/src/compiler

Modified Files:
	srctran.lisp 
Log Message:
1.0.10.14: remove locking and gc inhibition from hash-tables, power of 2 sizes

        This commit removes a bunch of bottlenecks from the hash-table
        implementation. It speeds up GETHASH, (SETF GETHASH) and
        REMHASH by a factor of 2-4x (on platforms with a real
        WITH-PINNED-OBJECTS) depending on the operation. On the flip
        side, no automatic locking is done on tables any more, so
        multi-threaded applications must do their own locking. (The
        locking done by SBCL was always just an implementation detail,
        not a part of the external interface). By popular demand it's
        also still safe to have multiple readers on the same table
        without locking.

	Originally GCs were inhibited during most hash-table
        operations for two reasons. To prevent the GC from rehashing a
        table while a Lisp-side operation is going on, and to prevent
        the GC from moving the key after the hash-value has been
        calculated.

        More recently, most hash-tables operations have acquired a
        lock on the table in order to prevent two concurrent writers
        from corrupting the chains. While it's never been the intent
        for the standard data structures to be automatically
        thread-safe in SBCL, this locking had to be done since corrupt
        tables could lead to infinite GC loops.

        Both the locking and the without-gcing are expensive
        operations relative to the total cost of a hash-table lookup.
        This commit removes both the gc inhibition and the locks.
        Additionally we switch to power of two table size, which
        allows calculating a cheaper hash -> bucket with cheaper
        operations than MOD.

        * The GC no longer does the rehashing itself, but just marks
          the hash-table as needing a rehash, which will then be done
          Lisp-side when the table is next accessed. While it's
          possible to find cases where the former behaviour has better
          performance, they're very contrived.
        * The hash-table operations that work on the chains now check
          for loops in the chains, and signal an error if one is found.
        * The hash-table operations now pin the key before calculating
          the hash value (needed for EQ-based hash functions).
        * Add a GC epoch value that GETHASH can use to check whether
          a GC happened during the lookup. This is needed since another
          thread calling GETHASH on the same table might have caused it
          to be rehashed.
        * Kill the old MUST-REHASH vector header, and replace it with a
          slot in the HASH-TABLE structure. The overloading of the header
          caused missed rehashings when both the GC and %%PUTHASH modified
          it at the same time.
        * Switch to power of two table sizes, with a slightly more complex
          hash value -> bucket calculation than just taking the low bits,
          which in many cases have a very skewed distribution for the existing
          SBCL hash functions. Still a lot faster than using MOD.
        * Leave in locking and GC inhibition during rehashing (needed to
          allow multiple readers to coexist) and for weak hash-tables
          (they need some GC support, and the code is much simpler when
          all of the logic is in the GC instead of interleaved in the GC and 
          Lisp-side). Neither of these cases is performance critical.



Index: srctran.lisp
===================================================================
RCS file: /cvsroot/sbcl/sbcl/src/compiler/srctran.lisp,v
retrieving revision 1.150
retrieving revision 1.151
diff -u -d -r1.150 -r1.151
--- srctran.lisp	30 Jun 2007 09:21:26 -0000	1.150
+++ srctran.lisp	30 Sep 2007 23:18:51 -0000	1.151
@@ -145,7 +145,7 @@
 (define-source-transform last (x) `(sb!impl::last1 ,x))
 (define-source-transform gethash (&rest args)
   (case (length args)
-   (2 `(sb!impl::gethash2 ,@args))
+   (2 `(sb!impl::gethash3 ,@args nil))
    (3 `(sb!impl::gethash3 ,@args))
    (t (values nil t))))
 (define-source-transform get (&rest args)