Re: Thread-safe caches

"Alex Mizrahi" <udodenko@xxxxxxxxxxxxxxxxxxxxx> writes:

PC> It may also be acceptable that the caches are not always updated, so if
PC> new entries in the caches are actually not written every now and then,
PC> that's fine, as long as the caches remain consistent...

i think plists are thread-safe when setq, rplaca and rplacd are atomic,
which i believe is true.

I think not. The plist implementation would also need to use the
atomic primitives in a way that ensures that the whole update is
atomic. Consider an implementation where (setf (getf place :b) 1)
expands to something like (ignoring gensymmage noise):

(let ((head (loop for head on var by #'cddr
when (eql (car head) :b) return head)))
(if head
(setf (cdr head) 1)
(progn
(push 1 var)
(push :b var)))
1)

(Which isn't completely unreasonable).

Now, having two concurrent writers could produce a plist (:b :b 1
1). Or just with a reader + a writer the reader could read VAR between
1 being pushed and :B being pushed, and see a plist with an odd number
of elements.

You could do (setq var (list* :b 1 var)) instead of the pushes, and
not suffer from these problems. But in this implementation it's still
possible for another thread to do an insert between the evaluation of
the arguments of the LIST* call and the evaluation of the SETQ, which
would result in an insert being dropped. So instead the branch for
inserting a new value would need to be:

(loop for old-value = var
for new-value = (list* :b 1 old-value)
until (eql (compare-and-swap var old-value new-value) old-value))

But of course you can't write that yourself, because there's no
standard COMPARE-AND-SWAP, and thus it's probably something not
exported to the users in most implementations (that example uses the
SBCL C-A-S).

So you'd need to trust the implementors to have gone through extra
effort to make (SETF GETF) thread-safe, which would only happen if all
implementors considered thread-safety of non-primitive data structures
to be a feature. And that's not true.

--
Juho Snellman
.

Relevant Pages

  • Re: Thread-safe caches
    ... ??>> i think plists are thread-safe when setq, ... i meant plist as data structure, and that it is possible to implement plists ... JS> possible for another thread to do an insert between the evaluation of ...
    (comp.lang.lisp)
  • Re: The iTunes that wouldnt die
    ... And it doesn't happen to another user, so it's part of my profile. ... What other settings are there beyond the plists? ... Caches exist. ...
    (uk.comp.sys.mac)