Sep 14, 2008, 6:48:21 PM (12 years ago)

Implemented "nearly-lock-free" hash tables. They are created by
calling MAKE-HASH-TABLE with :LOCK-FREE t, or by setting
CCL::*LOCK-FREE-HASH-TABLE-DEFAULT* to T. There is some documentation
in a big comment in l0-hash.lisp, but basically the idea is to try to
avoid any locking in GETHASH, getting the performance equivalent to
readonly tables, at the cost of rehashing becoming more
expensive. PUTHASH should be roughly equivalent (it avoids getting a
lock, but does sync memory a few times).

So far, I've only tested them on linuxx8664, by building ccl multiple
times with *lock-free-hash-table-default* = T on, so no real
multi-threaded testing. I will now switch to the mac and try to
build and use the IDE that way.

Other changes: moved some slots from the hash table to the hash table
vector so they can all be swapped in/out all at once. Made nhash.find
return -1 when not found, also to avoid some synchronization issues.
%needs-rehashing-p now takes a hash table vector, not the hash table.
Got rid of a bunch of unused slots and constants in hash tables.

Incremented fasl version in case there are any fasdumped hash tables out there.

1 edited


  • trunk/source/lisp-kernel/ppc-constants64.h

    r10010 r10731  
    304304  LispObj link;                 /* If weak */
    305305  LispObj flags;                /* a fixnum; see below */
     306  LispObj gc_count;             /* gc-count kernel global */
    306307  LispObj free_alist;           /* preallocated conses for finalization_alist */
    307308  LispObj finalization_alist;   /* key/value alist for finalization */
    308309  LispObj weak_deletions_count; /* incremented when GC deletes weak pair */
    309310  LispObj hash;                 /* backpointer to hash-table */
    310   LispObj deleted_count;        /* number of deleted entries */
     311  LispObj deleted_count;        /* number of deleted entries [not maintained if lock-free] */
     312  LispObj count;                /* number of valid entries [not maintained if lock-free] */
    311313  LispObj cache_idx;            /* index of last cached pair */
    312314  LispObj cache_key;            /* value of last cached key */
    335337#define nhash_finalizable_mask fixnum_bitmask(10)
     339/* keys frozen, i.e. don't clobber keys, only values */
     340#define nhash_keys_frozen_mask fixnum_bitmask(9)
    338342/* Lfun bits */
    343347#define lfbits_optinit_mask fixnum_bitmask(14)
    344348#define lfbits_rest_mask fixnum_bitmask(15)
    345350#define lfbits_aok_mask fixnum_bitmask(16)
    346351#define lfbits_lap_mask fixnum_bitmask(23)
Note: See TracChangeset for help on using the changeset viewer.