[Openmcl-devel] Non Blocking Nearly Wait Free Hash Table questions...

[Jon S. Anthony]

On Mon, 2010-01-11 at 11:49 -0500, Gail Zacharias wrote:

> Puthash doesn't ordinarily use locks, though it uses a couple of
> conditional stores, which sync memory.  That's if you're just setting
> the values of existing keys.  If you use puthash to add keys, then it
> might need to grow the table, in which case it will grab a lock.

Nice.  Generally, these things are great.


> >Let's set that aside for a moment.  I would have thought that just
> >accessing the array elements, even if they are the entire "object" of
> >interest - say just fixnums, could be a locking issue if more than one
> >thread has access to the array.  Are you saying array element update,
> >(setf (aref A i) x), is an atomic operation in CCL?  That would lend
> >itself (in my case) to an even better solution!
> 
> 
> For simple vectors it is atomic (there might be some issues for
> adjustable arrays).

That's cool and very good to know.  So, let's say we have a simple
vector (an ivector) of fixnums.  Suppose further that we interpret this
so that the high byte is interpreted as bits and that these are flags.
One of the flags is "in-transition" or some such.  This could then be
set atomically.  So is something like this actually reasonable:

(while (in-transition A i) ; A is vector, i is index
  (sleep))
(set-in-transition A i) ; Sets the flag atomically
... do whatever on thing indicated by A(i) ...
(unset-in-transition A i)

That would be great, but it still looks like there would be contention
issues with this.  What is really needed is an atomic check-and-set.  I
would think there are machine instructions which do (effectively) just
that, but are they used in these atomic ops on simple vectors???


Thanks again!

/Jon