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

[Gary Byers]

On Mon, 11 Jan 2010, Gail Zacharias wrote:

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

On Intel hardware, I think that (SETF SBIT) is "pretty atomic", in that
it affects at most a single bit in memory.

On the PPC, there's no "set bit in memory" operation, so (SETF SBIT) has
to load a word from memory into a register, change the bit in the register,
and store the whole word back to memory; if two or more threads try to set
"nearby" bits in the same vector at roughly the same time, some of these
assignments may get canceled by other assignments.

AFAIK, the CISCy operations are guaranteed not to change "nearby" bits;
the RISCy approach would have to do some sort of store-conditional loop
to guarantee this, and (SETF SBIT) certainly doesn't do that.  (A variant
of (SETF SBIT) that offered that guarantee might be useful.)


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

I'd implemented (SETF SBIT) that way on x86-64 originally, but Matt
noticed that the x86[32,64] offered CISCy "set Nth bit in memory"
instructions (that're shorter/use fewer temporary registers than
the RISCier approach that I'd used originally), and I think that
he/we changed both x86 ports to use them.

I don't think that we were thinking explicitly about atomicity in
this case, but I think that it's actually true that whether or not
(SETF SBIT) is as atomic as other flavors of (SETF AREF) is platform-
dependent.  (Which may still be equivalent to "not guaranteed to be
atomic".)