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.

1.0.10.13: trivial change: Print more explicit message upon entering LDB.

1.0.10.12: logged bug 417

1.0.10.11: Make FEATUREP accept only symbols or conses.

One more restriction on feature expressions: They can contain only conses
or symbols. The previous implementation allowed conses and atoms.

1.0.10.10: theoretical #!+long-float fix to MAKE-MEMBER-TYPE

* 0.0l0, not 0.0lo. Thanks to Peter Graves.

1.0.10.9: symbol-macro expansion uses *MACROEXPAND-HOOK*

Thanks to Tobias Rittweiler.

1.0.10.8: correct nested DX implementation

* Instead of just checking for BASIC-COMBINATION-P,
  HANDLE-NESTED-DYNAMIC-EXTENT needs to do the same check for each USE
  as RECHECK-DYNAMIC-EXTENT-LVARS does.

* Tests.

1.0.10.7: multiply-used DX LVARS

* HANDLE-NESTED-DYNAMIC-EXTENT maps over all the uses of the LVAR,
  collecting their argument lvars as well.

* RECHECK-DYNAMIC-EXTENT-LVARS accepts multiply-used DX LVARs,
  checking that all uses support stack allocation.

* UPDATE-UVL-LIVE-SETS accepts multiply-used DX LVARs, doing that
  lifetime merging with all uses.

* ...and OOPS, move the NEWS entries of .5 and .6 to a new section for
  1.0.11...

1.0.10.6: nested DX allocation

* RECOGNIZE-DYNAMIC-EXTENT-LVARS needs to propagate DX information to
  combination arguments, so that

  (LET ((X (LIST (LIST 1 2) (LIST 3 4))))
    (DECLARE (DYNAMIC-EXTENT X))
    (FOO X))

  does the right thing.

1.0.10.5: dynamic-extent CONS

* Extend EMIT-FIXED-ALLOC to support stack-allocation.

* Appropriate DEFOPTIMIZER for CONS.

Note: it seems like it should be a simple matter to support stack
allocation of all primitive objects allocated using the :ALLOC-TRANS
framework.

1.0.10.4: Use variable for SIG_MEMORY_FAULT on FreeBSD

When SIGBUS is signalled on FreeBSD 7, or SIGSEGV is signalled on
FreeBSD 6 or earlier, it's very hard to debug if both of the signals
are hooked for GC.

Instead to hook both signals, define SIG_MEMORY_FAULT as variable
and set it at startup.

1.0.10.3: Grovel suseconds_t

Instead to detect if suseconds_t exists by OS and architecture,
check it in grovel-features.sh.

1.0.10.2: Don't link unnecessary undefines.c on FreeBSD/i386

undefines.c is not required anymore on FreeBSD/i386.  Since I'm not
sure it's required or not on other *BSD, add it to OS_SRC in
Config.x86-*bsd.

1.0.10.1: Cleanup code

Shut GCC warnings up.

1.0.10: release, will be tagged as sbcl_1_0_10

1.0.9.64: Use umtx system call on FreeBSD to emulate futex.

1.0.9.63: Disallow (:not) in #+/#- expressions.

NOT in feature expressions is specified to accept exactly one argument.
The previous implementation of FEATUREP allowed zero or one argument,
so tighten that check.

Might need to fix CLRFI-1, as well (-:

1.0.9.62: Performance and stability improvement of threading on FreeBSD

* Use GCC's Thread-Local Storage to store current thread.
  (Tested on Linux x86 and x86-64, too)

* Restore lisp level TLS segment register at interrupt handler.

1.0.9.61: Fix %report-reader-error
It was missing an apply (or, equivalently, a ~?) for printing
the simple-condition part of the error.

1.0.9.60: partial fix for bug in STREAM-ERROR :REPORT
* added a new (partially #+NILed out) test case for a bug in
  STREAM-ERROR :REPORT, where it expects STREAM-ERROR to have
  SIMPLE-CONDITION-like properties
* partial fix for bug in test case:
  ** Define SB-INT:SIMPLE-READER-ERROR which portably behaves
     the way that pre-ANSI code expected READER-ERROR to behave.
  ** Redo most internal references to READER-ERROR as references
     to SB-INT:SIMPLE-READER-ERROR.
* (This is only a partial fix because PARSE-ERROR and
  STREAM-ERROR still have similar issues.)

1.0.9.59: Fix ash/smod61 on x86-64 for constant large shifts.
Thanks to Paul Khuong for the translation.

1.0.9.58: Fix x86 smod30 ash with a constant large argument.
The usual thing: the VOP was written in the belief that the
compiler had already proved that the shift couldn't be
too large.

(Include test cases which should catch the analogous problem on
x86-64 as well as the problem just fixed.)

1.0.9.57: allow pv-optimizations for typechecking (SETF SLOT-VALUE)

* For each optimized access, store both the slot location and the
  typecheck function in the permutation vector. If the write is in
  safe code, use the typecheck function to validate the new value
  before using it.

* Approximately ~5x as fast as SAFE-SET-SLOT-VALUE -- which is still
  needed in a few places as ACCESSOR-SET-SLOT-VALUE doesn't do type
  checking.

1.0.9.56: faster typechecking/optimized std-writer-method-functions

* Fetch the type-check-fun from wrapper-slot-table, not
  from the slot-definition.

1.0.9.55: trivial src/pcl/vector.lisp cleanup

* There hasn't been a :DEFAULT kind in permutation vector code
  for ages -- delete the code that handled it.

1.0.9.54: clean up old pv updating code

* Since the vectors that are updated are referred to by stale
  wrappers, this seems to be quite useless: if an instance has an
  invalid wrapper it will still have the old layout as well.

1.0.9.53: trivial typo fixes
(I had batched these up as a "git baby steps" commit, but now
that's been delayed...)

1.0.9.52: copy propagation interfering with local calls

* Don't allow copy propagation to a local call argument, thus
  preserving parallel assignment semantics -- to judge by the comment
  above OK-COPY-REF, this is what it was ment to do in the first
  place. Reported by Paul Khuong on sbcl-devel.

1.0.9.51: SB-CLTL2: implement FUNCTION-INFORMATION, touch VARIABLE-INFORMATION

* Based on work done by Larry D'Anna.

* Rewire VARIABLE-INFORMATION in a similar manner. Add a FIXME
  note about lexically apparent special bindings, and document
  the current state of affairs. Improve the documentation string.

* Tests, and more tests for VARIABLE-INFORMATION as well.

1.0.9.50: O(1) weak pointer scavenging

* Use self-pointer instead of NULL to mark the end of scavenged weak
  pointer list in GC, which allows identifying unscavenged pointers
  by the NULL next pointers.

* Scavenging a single weak pointer in gencgc is now an O(1) operation
  instead of O(#scanned pointers so far).

Thanks to Paul Khuong.

1.0.9.49: NetBSD 2.0 build fix (Aymeric Vincent sbcl-devel 2007-09-05)
No ptsname() and friends on NetBSD.

1.0.9.48: texi2pdf rework (Aymeric Vincent sbcl-devel 2007-09-05)
It looks likely that texi2dvi is more ubiquitous than texi2pdf,
so just apply the patch.
... (plus whitespace and .cvsignore collateral changes).

1.0.9.47: VALID-WRAPPER-OF

* Renamed CHECK-OBSOLETE-INSTANCE/WRAPPER-OF, and fixed the semantics
  so that it always returns the fresh wrapper.

* Add FIXME re CHECK-WRAPPER-VALIDITY name.

1.0.9.46: take pv-slot value from wrapper-slot-table

* Use NIL instead of T in the CAR of the SLOT-TABLE cells to indicate
  "slot location not saved for some reason".

* Better slot location computation for SLOT-TABLES: remaining wrapper
  copies now also copy the slot-table, and bootstrapping computes the
  slot locations for rest of the interesting cases.

* Use SLOT-TABLE to obtain the slot location for permutation vectors
  instead of WRAPPER-CLASS-SLOTS and WRAPPER-INSTANCE-SLOTS-LAYOUT.
  Faster, and slowly point the way to getting rid of WRAPPER/LAYOUT
  distinction.

* We deal with slot names in permutation vectors: remove the unused
  code that computed things for non-slot-name places in them.

1.0.9.45: cleaner & thread-safe pv-table interning

* Rename the global interning tables and comment on
  their purpose for easier understanding.

* Simplify by-slot indexing: PV-OFFSETS are not needed in the global
  table.

* Lock around hash-table accesses.

1.0.9.44: clean up PV-TABLE constructor

1.0.9.43: .PV-CELL., use .PV. directly

* Now that .CALLS. are gone we can get rid of the extra indirection.
  (Maybe we have to add it back later, but worry about that then.)

* Since .PV. is magical, also localize its bindings to vector.lisp,
  instead of exposing the variable in PV-BINDING1's interface (which
  is used elsewhere as well.)

1.0.9.42: remove stale CALLS support

* Permutation vector code contained infrastructure for optimizing
  GF calls inside method bodies in a similar manner as slot accesses
  are optimized, but this support was never finished.

  While it would be nice to have it, right now clarity of the code
  seems like a higher priority -- it seems to be simple enough to
  reinstate when we want, and the end result is liable to be easier to
  understand.

* Add a big FIXME with a short explanation of the optimization and
  a pointer to this commit.

1.0.9.41: Fix test on unthreaded config.

1.0.9.40: fix 64 bit build

* Need to cast (BACKEND_PAGE_SIZE-1) to an unsigned long before bit
  flipping, otherwise we're potentially cutting the high bits off the
  allocation address.

1.0.9.39: thread stack memory leaks

* Since 1.0.9.30 we pad & align the per-thread areas after
  allocation -- but we need to still pass the original address
  and size to os_invalidate(), or else we leak.

* Also refactor the freeable_thread_stack stuff slightly for
  less OAOOM.

* Whitespace in tests.

1.0.9.38: fix COMPARE-AND-SWAP

* :COMPARE-AND-SWAP-VOPS, not :COMPARE-AND-SWAP-VOP in *FEATURES*.

* Threaded cas tests. (threads.impure.lisp currently broken for
  unrelated reasons since .30 or so.)

1.0.9.37: MIPS shared libraries will need an explicit -fPIC soon-ish.

1.0.9.36: Match the correct atomicity bit.
The wonders of copy & paste ...

1.0.9.35: Delete wrong comment.
At that place, the header tag is written, and we have nothing
like closure-header-slot.

1.0.9.34: Encapulate the whole closure generation in pseudo-atomic.

1.0.9.33: Change SIGINFO to the more common SIGPWR, and fix its documentation.

1.0.9.32: Remove accidentially committed debug code.

1.0.9.31: Fix broken syntax.

1.0.9.30: Make SBCL work on MIPS/Linux with larger page sizes.
- Supports now up to 64k pages, aas defined by the o32 ABI.
- Tested on a bcm1480 with a kernel for 16k pages.
- The pagesize handling in SBCL is very broken for most other
  architectures / OSes.

1.0.9.29: Fix document string formatting.

1.0.9.28: Enable alien callbacks for MIPS.

1.0.9.27: Fix large file support for MIPS.

1.0.9.26: Update comment about little-endian MIPS.

1.0.9.25: Revert the /xhow -> /show change.
... as the original version was correct.

1.0.9.24: Adjust assembly callers of WITH-FIXED-ALLOCATION.

1.0.9.23: Delete conditional INST NOP optimization.
Using it is apparently too complicated for cold init.

1.0.9.22: Dynamic-extent value-cells for MIPS.

1.0.9.21: Make less eager use of eval-when unless cross-compiling.

1.0.9.20: Add #+sb-doc conditionals.

1.0.9.19: Less magic constants in the mips backend.

1.0.9.18: Instrument COMPUTE-CALLING-FRAME for non-x86 with /noshow0.

1.0.9.17: Delete deprecated DEF-ALIENs.

1.0.9.16: Remove :mips from Bug #372.
This was a Linux/MIPS kernel bug, fixed in the latest version.

1.0.9.15: Fix typo.

1.0.9.14: Marginally improved VOPs, and a bit of code cleanup.

1.0.9.13: copy the WRAPPER-SLOT-TABLE in FORCE-CACHE-FLUSHES

* Otherwise the new wrapper will be missing the slot table,
  potentially leading to bogus SLOT-MISSING calls.

  No test case, as I was unable to cause bad behaviour with current
  HEAD in the absence of this patch, but future changes depend on
  this.

1.0.9.12: inform genesis about FOR-STD-CLASS-P slot in LAYOUT

* It was left uninitialized by genesis, resulting in bogus results
  from LAYOUT-FOR-STD-CLASS-P.

* Poke at it in tests.

1.0.9.11: even faster SLOT-VALUE &co

* Move the SLOT-TABLE data to layout, so that it can be accessed
  faster, giving ~40% more speed to SLOT-VALUE &co using variable slot
  names. Speedup is due to one less level of indirection, and avoiding
  a GF call when fetching the table.

* FIND-SLOT-DEFINITION goes back to using the linear search, as in
  some cases where we use it the class wrapper may already be invalid.
  This will be re-addressed later.

1.0.9.10: make tests clean up after themselves a bit better

* Delete various temporary files (still some left).

* Also add test/test-status.lisp-expr to .gitignore.

1.0.9.9: rename CLASS-SLOT-VECTOR to CLASS-SLOT-TABLE

* And the corresponding slot from SLOT-VECTOR
  to SLOT-TABLE.

* Avoids confusion with instance slot vectors.

1.0.9.8: prettier DEFINE-MODIFY-MACRO arglist

* Use MAKE-SYMBOL instead of GENSYM for symbols that appear in the
  final lambda-list.

Thanks to Tobias C. Rittweiler.

1.0.9.7: the MSI should not add .lisp and .fasl associations

* It could, but not without asking permission.

1.0.9.6: remove :UNIX from *FEATURES* on Windows

Thanks to Luis Oliveira.

keep docstrings from PCL bootstrap around

* Keep documentation strings from early generics and methods.

added .gdb_history to .gitignore

micro-optimize SKIP-FAST-SLOT-ACCESS-P

* It's the only caller of SKIP-OPTIMIZE-SLOT-SLOT-VALUE-BY-CLASS-P, so
  inline the latter's body and remove the duplicate *BOOT-STATE* check
  and FIND-SLOT-DEFINITION call. Add FIXME due to apparent strangeness
  re existense of the slot definition.

faster SLOT-VALUE &co with variable slot names

* Cache the slot-location and typecheckfun in the class-slots-vector
  in addition to the slot-definition for STANDARD-CLASS and
  FUNCALLABLE-STANDARD-CLASS.

* New function CHECK-OBSOLETE-INSTANCE/CLASS-OF, which combines the
  two. Faster then calling both separately, since both need to grab
  the wrapper -- used by SLOT-VALUE &co.

* Unoptimized SLOT-VALUE, (SETF SLOT-VALUE), SLOT-BOUNDP, and
  SLOT-MAKUNBOUND can now directly access instance and class slots the
  typecheckfun in normal cases, giving upto 20-25% performance boost
  for these functions.

* Obsolete-instance protocol tests using variable slot-names.

1.0.9.1: faster MAKE-MEMBER-TYPE, UNION, and NUNION

* MAKE-MEMBER-TYPE was doing several SUBSETP calls,
  instead just walk once over the list of members.

* UNION and NUNION were using an O(N^2) implementation
  for all input sizes. Use a hashtable (giving O(N))
  for large inputs when :TEST is something we can
  use with a hash-table.

Thanks to Damien Diederen for catching a typo in the new UNION /
NUNION code.

1.0.9: release, will be tagged as sbcl_1_0_9

1.0.8.48: Update comment.

1.0.8.47: Declare alien input parameters as such.

1.0.8.46: attempt to answer the "executables" FAQ in the manual

* The information was there, but hidden in the second part of a
  somewhat-related paragraph in a generic section.

* Including "Executables" in the first page of the table of contents
  should make the function easier to find, one hopes...

1.0.8.45: Fix sb-sprof on non-x86oids

         * Patch by Pierre Mai

1.0.8.44: Fix EQUALP on structures with raw slots

         * Old version was basically accessing raw slots with %INSTANCE-REF,
           and doing EQUALP on the results. This was most obviously wrong
           for raw slots that were larger than a word (double-floats on 32-bit
           platforms). Less obviously this is also wrong for some float
           corner-cases, like negative zeroes.
         * Add RAW-INSTANCE-SLOTS-EQUALP which instead grovels the layout for
           the slot definitions and determines the proper accessor functions
           for each slot from that.
         * Reported by Vjacheslav Fyodorov.

1.0.8.43: Fix GCD on most-negative-fixnum on x86-64

         * Bogus type declarations.
         * Reported by Gregory Vanuxem on sbcl-devel.

1.0.8.42: Fix some source-location bugs, alternate sb-cover annotation mode

         * Bug introduced in the code coverage commit caused sldb-show-source
           to highlight the wrong forms in many cases.
         * Changes in 1.0.6.23 caused branch forms to be not annotated as
           such in sb-cover.
         * Add a new annotation mode to sb-cover, which basically uses
           the source location information of the car of the form instead
           of using the information for the form itself. This mode shows
           explicitly which forms have been instrumented. According to
           a #lisp poll, the old version looks nicer, so it's been retained
           as the default.

1.0.8.41: doc spelling fixes.

1.0.8.40: Acrually use reset-signal-mask only for Linux/MIPS.

1.0.8.39: Mark remaining MIPS test failures as known.

1.0.8.38: Add missing quote sign.

1.0.8.37: Workaround (or bugfix?) for blocked SIGTRAP on SBCL/MIPS.

1.0.8.36: Improve MIPS (and HPPA) floating pooint support.
  - For MIPS/HPPA, the NaN signalling bit's meaning is inverted.
  - Implement FLOATING-POINT-MODES and SET-FLOATING-POINT-MODES in C.
  - Delete the corresponding VOPs.
  - Document the MIPS special "unimplemented" floating point trap.
  - Add handling of the floating point control word in C signal handlers.
  - Mark NAN-COMPARISIONS as expected failure on MIPS. (It still doesn't
    work due to a kernel bug, siginfo_t's si_code field doesn't get
    updated properly.)

1.0.8.35: Fix MIPS foreign_function_call_active handling.

1.0.8.34: Fix MIPS spinlock implementation.

1.0.8.33: sample sbcl-export alias in Git for SBCL Hackers

* Forgot to save the file, so missed from the last commit...

1.0.8.32: improved Git for SBCL Hackers in a few places

* Grammar and typos.

* Remove references to version.lisp-expr now that we have
  branch-version.lisp-expr.

* Better explanation of history cleaning (mostly for the benefit of
  non-committer hackers, shades of "How to Contribute".

* Alias for easy git-cvsexportcommit usage.

* Mention git-format-patch.

* Add link to Git User Manual.

1.0.8.31: add missing Git for SBCL Hackers guide

* Accidentally left out from 1.0.8.15.

1.0.8.30: better standard-instance accessors

* Add SETF functions for STANDARD-INSTANCE-ACCESS and
  FUNCALLABLE-STANDARD-INSTANCE-ACCESS.

* Declare them and the readers inline.

  Thanks to Attila Lendvai.

1.0.8.29: better printing of anonymous objects

* In PCL, the NAMED-OBJECT-PRINT-FUNCTION prints the identity of the
  object when it has no name. Among other things, it affects the
  printing of anonymous classes.

  Thanks to Attila Lendvai.