Re: locking of hash tables

Unable to parse email body. Email id is 529

Re: locking of hash tables

Nick Levine <ndl@ravenbrook.com> writes:

>    I've noticed (on LW 4.2.6/Linux) that MAP-HASH-TABLE locks the hash
>    table (at least for writing, it seems) during its operation.
> 
> Did you mean MAPHASH?

eh, of course... :-)

>    Is there a way to do iteration over hash tables that will avoid
>    locking during the iteration?
> 
> I hope not. According to ANSI spec: 
> 
>   "The consequences are unspecified if any attempt is made to add or
>   remove an entry from the hash-table while a maphash is in progress,
>   with two exceptions: the function can use can use setf of gethash to
>   change the value part of the entry currently being processed, or it
>   can use remhash to remove that entry."
> 
> and quite rightly too, otherwise the iteration could run into serious
> problems.

A few comments:

 - I was looking for _any_ built-in way to do iteration over hash tables,
   not necessarily via hash-tables. What I want is a multi-processing-
   friendly way to iterate over a hash-table without having to resort
   to the (obvious!) solution of first collecting the keys and values and
   then process them.

 - I would guess that this part of the ANSI spec was written without
   multiprocessing in mind. 

 - ACL does in fact _not_ lock the hash table during a maphash, in
   ACL you can unproblematically implement slow mapping functions without
   blocking hashtable inserts. This is very useful in networking 
   applications where you want to spit out (parts of) the contents of
   a hash-table to a slow-receiveing client while some other thread is
   constantly adding elements or modifying existing ones. I haven't
   heard of any unexpected consequences of this, so I guess ACLs maphash
   is a clean extension of the standard.
-- 
  (espen)

Re: locking of hash tables

Espen Vestre <ev@netfonds.no> writes:

>  - I was looking for _any_ built-in way to do iteration over hash tables,
>    not necessarily via hash-tables. 

Ouch. Too early in the morning. Of course i meant 'via maphash'.
-- 
  (espen)

Re: locking of hash tables

* Espen Vestre wrote:

>  - I would guess that this part of the ANSI spec was written without
>    multiprocessing in mind. 

>  - ACL does in fact _not_ lock the hash table during a maphash, in
>    ACL you can unproblematically implement slow mapping functions without
>    blocking hashtable inserts. This is very useful in networking 
>    applications where you want to spit out (parts of) the contents of
>    a hash-table to a slow-receiveing client while some other thread is
>    constantly adding elements or modifying existing ones. I haven't
>    heard of any unexpected consequences of this, so I guess ACLs maphash
>    is a clean extension of the standard.

I think it would be interesting to know how they do that.  It's not
enough to not lock the table, you have to make sure, somehow, that
things don't fall apart if the table gets rehashed.  I have no idea
what the intended semantics should be even.  Possibly it's enough to
suppress rehashing of the table, and then have some table that can
degrade gracefully if it doesn't get rehashed.

--tim