Re: Hash table thread safety
"Tim Bradshaw (as tfb at tfeb dot org)" <[email protected]>
| Newsgroups | gmane.lisp.lispworks.general |
|---|---|
| Message-ID | <[email protected]> |
On 31 Mar 2026, at 10:12, Martin Simmons <[email protected]> wrote: > > Yes, that is correct (as long as you don't pass :single-thread t). > > I don't know what your definition of 'you can't destroy the table' is, but > thread-safety also covers transient problems like ensuring that gethash will > find an existing value even if the table is rehashed simultanously by another > thread. Thank you. Yes, I think that's what I'm after. In fact it's difficult to see that there really can be a difference between thread-safe and atomic-with-respect-to-other-hashtable-operations here. What I'm trying to do is implement an ordered hash table (by which I mean a hash table that remembers insertion order) which is (on at least some implementations) thread-safe. My original implementation just kept a doubly-linked list (doubly-linked helps with deletion) beside the underlying hash table, but that was never going to be thread-safe without a lock. The new one keeps a natural number which is the next index, and then two hash tables: k->o, and o->v (actually to a cons of key and value), where o is an index. If you can increment the next index slot atomically (which you can in LW and SBCL) then you can know you have a unique (up to machine integers wrapping on SBCL) index for insertion. The problems are (a) slower, and (b) if you delete lots of entries you end up with holes in the index space, so iteration can be slow. You can get orphan o->kv entries but it can GC those if asked. There will be a well-known and much cleverer approach I am sure. --tim _______________________________________________ Lisp Hug - the mailing list for LispWorks users [email protected] http://www.lispworks.com/support/lisp-hug.html