Re: Multi-threaded hash table access
On 25 Apr 2014, at 20:00, Martin Simmons <martin@lispworks.com> wrote:
>
>>>>>> On Fri, 25 Apr 2014 11:47:20 +0000, Costanza, Pascal said:
>>
>> On 25 Apr 2014, at 13:23, Martin Simmons <martin@lispworks.com> wrote:
>>
>>>>>>>> On Fri, 25 Apr 2014 09:06:18 +0000, Costanza, Pascal said:
>>>>
>>>> We are accessing hash tables from several threads, and see that locking the
>>>> hash tables using the LispWorks locks for hash tables is too
>>>> coarse-grained. We have some ideas how to fix this, but are wondering if
>>>> anybody else has encountered this, and whether there already exist
>>>> solutions, maybe in the form of third-party libraries (lock-free hash
>>>> tables, anyone?).
>>>
>>> Which "locks for hash tables" APIs are you using?
>>>
>>> LispWorks hash tables provide atomic (thread-safe) access by default, without
>>> any need for explicit locking.
>>
>> I’m thinking about
>> http://www.lispworks.com/documentation/lw61/LW/html/lw-868.htm and
>> http://www.lispworks.com/documentation/lw61/LW/html/lw-810.htm
>>
>> An important idiom for us is this:
>>
>> (hcl:with-hash-table-locked (table)
>> (let ((value (gethash key table)))
>> (cond (value (remhash key table) value)
>> (t (setf (gethash key table) value))))
>>
>> This should be atomic, ideally without preventing other threads from
>> accessing other entries in the hash table. Since both clauses of the cond
>> access the table again, we need to protect the whole operation with a lock,
>> though.
>>
>> Also this:
>>
>> (or (gethash key table)
>> (hcl:with-hash-table-locked (table)
>> (or (gethash key table)
>> (setf (gethash key table) value))))
>>
>> is already problematic for us because we do not encounter the keys often
>> enough to avoid the locking often enough. The documentation for modify-hash
>> sounds like it also locks the complete table, or is it more fine-grained?
>
> Thanks, I see.
>
> Unfortunately, modify-hash uses with-hash-table-locked. Also, it can't do
> remhash (as in your first example). I'm not sure if a fine-grained lock could
> be used without impacting setf gethash and remhash.
Maybe modify-hash could do a remhash when the called function returns no values (instead of nil for example)?
> I think making modify-hash completely lock-free would be impossible in the
> general case, unless its specification was changed to allow the modification
> function to be called more than once (which is an interesting idea).
Maybe make-hash-table could accept a keyword parameter that allows it to be used with a lock-free version of modify-hash (which could then have slightly different semantics, with regard to number of times being called, supporting remhash functionality, and disallowing setf gethash, etc.)
I think performance-conscientious would be fine with such restrictions…
Pascal
--
Pascal Costanza, ExaScience Life Lab, Intel, Belgium
pascal.costanza@intel.com
Intel Corporation NV/SA
Kings Square, Veldkant 31
2550 Kontich
RPM (Bruxelles) 0415.497.718.
Citibank, Brussels, account 570/1031255/09
This e-mail and any attachments may contain confidential material for the sole use of the intended recipient(s). Any review or distribution by others is strictly prohibited. If you are not the intended recipient, please contact the sender and delete all copies.
_______________________________________________
Lisp Hug - the mailing list for LispWorks users
lisp-hug@lispworks.com
http://www.lispworks.com/support/lisp-hug.html