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

[Gail Zacharias]

At 1/11/2010 04:12 PM, Jon S. Anthony wrote:
>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).

Ah, your reply reminds me that I forgot a case: setting the element 
of a bit vector is not atomic.


>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:

(setf (aref A i) x) is atomic.  But the sequence:

      (setf x (aref A i))
      (setf (aref A i) x)

is not atomic.  I.e. setting a value is atomic, but to modify it 
(e.g. set a bit) you need to first read the value and then set it, in 
two separate operations.


>(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???

At some point, aren't you just reimplementing locks?  I'm getting out 
of my depth here, Gary will have to say whether doing this sort of 
thing by hand is actually any better than using system locks (or 
semaphores or whatever).

Anyway, if you want to experiment, the functions that do this sort of 
thing are ccl::%store-node-conditional and 
ccl::%store-immediate-conditional.  Use at your own risk.




>Thanks again!
>
>/Jon