Sep 14, 2008, 6:48:21 PM (13 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/gc-common.c

    r10173 r10731  
    218218  Boolean
    219219    weak_on_value = ((hashp->flags & nhash_weak_value_mask) != 0);
     220  Boolean
     221    keys_frozen = ((hashp->flags & nhash_keys_frozen_mask) != 0);
    220222  bitvector markbits = GCmarkbits;
    221223  int tag;
    232234      if ((dnode < GCndnodes_in_area) &&
    233235          ! ref_bit(markbits, dnode)) {
    234         pairp[0] = slot_unbound;
    235         pairp[1] = lisp_nil;
     236        if (keys_frozen) {
     237          if (pairp[1] != slot_unbound) {
     238            pairp[1] = unbound;
     239          }
     240        }
     241        else {
     242          pairp[0] = slot_unbound;
     243          pairp[1] = lisp_nil;
     244        }
    236245        hashp->weak_deletions_count += (1<<fixnumshift);
    237246      }
Note: See TracChangeset for help on using the changeset viewer.