Changes between Version 2 and Version 3 of Internals/LockFreeHashTables


Ignore:
Timestamp:
09/23/08 01:17:30 (6 years ago)
Author:
gz
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Internals/LockFreeHashTables

    v2 v3  
    33CCL implements a modification of the lock-free hash table algorithm described by Cliff Click Jr. in http://blogs.azulsystems.com/cliff/2007/03/a_nonblocking_h.html.  
    44 
    5 CCL uses this algorithm to implement thread-safe hash tables without the need for locking on every access.  The result is that CCL's fully thread-safe hash tables have typical performance as good or better than non-thread safe hash tables. 
     5CCL uses this algorithm to implement thread-safe hash tables without the need for locking on every access.  The result is that CCL's fully thread-safe hash tables have typical performance equivalent to non-thread safe hash tables. 
    66 
    77The modifications have to do with the fact that our goal is just to minimize the  
     
    5353 * gc: for weak tables, gc may convert IN-USE states to DELETED2 states.  For all lock-free hash tables (weak or not) gc converts DELETED1 states to DELETED2 - gc can do that because the entire gc takes place atomically wrt the lisp runtime.  REMHASH cannot do it without violating the invariants. 
    5454 
    55 It's left as an exercise to the reader to prove that this results in GETHASH always getting the correct value, no matter what other threads are doing. 
     55It's left as an exercise for the reader to prove that this results in GETHASH always getting the correct value, no matter what other threads are doing. 
    5656