On 2/19/08, Victor Kryukov <victor.kryukov@...> wrote:
CL-USER> (documentation 'make-hash-table 'function)
"Create and return a new hash table. The keywords are as follows:
:TEST -- Indicates what kind of test to use.
:SIZE -- A hint as to how many elements will be put in this hash
:REHASH-SIZE -- Indicates how to expand the table when it fills up.
If an integer, add space for that many elements. If a floating
point number (which must be greater than 1.0), multiply the size
by that amount.
:REHASH-THRESHOLD -- Indicates how dense the table can become before
forcing a rehash. Can be any positive number <=1, with density
approaching zero as the threshold approaches 0. Density 1 means an
average of one entry per bucket.
:WEAKNESS -- If NIL (the default) it is a normal non-weak hash table.
If one of :KEY, :VALUE, :KEY-AND-VALUE, :KEY-OR-VALUE it is a weak
Depending on the type of weakness the lack of references to the
key and the value may allow for removal of the entry. If WEAKNESS
is :KEY and the key would otherwise be garbage the entry is eligible
for removal from the hash table. Similarly, if WEAKNESS is :VALUE
the life of an entry depends on its value's references. If WEAKNESS
is :KEY-AND-VALUE and either the key or the value would otherwise be
garbage the entry can be removed. If WEAKNESS is :KEY-OR-VALUE and
both the key and the value would otherwise be garbage the entry can
:SYNCHRONIZED -- If NIL (the default), the hash-table may have
multiple concurrent readers, but results are undefined if a
thread writes to the hash-table concurrently with another
reader or writer. If T, all concurrent accesses are safe, but
note that CLHS 3.6 (Traversal Rules and Side Effects) remains
in force. See also: SB-EXT:WITH-LOCKED-HASH-TABLE. This keyword
argument is experimental, and may change incompatibly or be
removed in the future."
CL-USER> (documentation 'sb-ext:with-locked-hash-table 'function)
"Limits concurrent accesses to HASH-TABLE for the duration of BODY.
If HASH-TABLE is synchronized, BODY will execute with exclusive
ownership of the table. If HASH-TABLE is not synchronized, BODY will
execute with other WITH-LOCKED-HASH-TABLE bodies excluded -- exclusion
of hash-table accesses not surrounded by WITH-LOCKED-HASH-TABLE is
> 1/ Multiple threads can safely read from the same hash table.
Yes, assuming there are no writers.
> 2/ Multiple threads can write to the same hash table. If two different
> threads attempt to overwrite the same key simultaneously, the
> resulting value (first or second one) is not specified, but it will be
> one of the values provided, and no other problems would occur.
No. Multiple unlocked writers are unsafe -- at the very least you can
expect type-errors. We try fairly hard not to corrupt your whole lisp
image, but the hash-table as a whole may be trashed.
> 3/ Multiple threads can read and write to the same hash table. If one
> thread attempts to read a value while another thread attempts to write
> a new value, the value that reader gets (old or new) is not specified,
> but the new value would be written, and no other problems would occur.
> 4/ Same as 2,3 above if one thread removes a key and another tries to
> write/read it.
> 5/ Last, but not the least - I'd like to understand the behaviour of
> maphash when other threads write to the hash-table. Is it true that
> maphash is guaranteed about looping over all the _initial_ hash
> elements, while behaviour for new added values is not specified?
CL-USER> (documentation 'maphash 'function)
"For each entry in HASH-TABLE, call the designated two-argument function on
the key and value of the entry. Return NIL.
Consequences are undefined if HASH-TABLE is mutated during the call to
MAPHASH, except for changing or removing elements corresponding to the
current key. The applies to all threads, not just the current one --
even for synchronized hash-tables. If the table may be mutated by
another thread during iteration, use eg. SB-EXT:WITH-LOCKED-HASH-TABLE
to protect the MAPHASH call."
> 6/ Same as above if maphash removes or updates some values while
> walking along the hash table.
Same as above.
If you have tricky parallelism requirements, I recommend you look into
various lockless algorithms and SB-EXT:COMPARE-AND-SWAP.