Changes between Version 2 and Version 3 of Internals/LockFreeHashTables
 Timestamp:
 09/23/08 01:17:30 (8 years ago)
Legend:
 Unmodified
 Added
 Removed
 Modified

Internals/LockFreeHashTables
v2 v3 3 3 CCL implements a modification of the lockfree hash table algorithm described by Cliff Click Jr. in http://blogs.azulsystems.com/cliff/2007/03/a_nonblocking_h.html. 4 4 5 CCL uses this algorithm to implement threadsafe hash tables without the need for locking on every access. The result is that CCL's fully threadsafe hash tables have typical performance as good or better thannonthread safe hash tables.5 CCL uses this algorithm to implement threadsafe hash tables without the need for locking on every access. The result is that CCL's fully threadsafe hash tables have typical performance equivalent to nonthread safe hash tables. 6 6 7 7 The modifications have to do with the fact that our goal is just to minimize the … … 53 53 * gc: for weak tables, gc may convert INUSE states to DELETED2 states. For all lockfree 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. 54 54 55 It's left as an exercise tothe reader to prove that this results in GETHASH always getting the correct value, no matter what other threads are doing.55 It'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. 56 56