Re: [Valgrind-developers] mtV : xor tt_fast

[Eliot M. <mo...@cs...>]

On 6/20/2012 8:03 AM, Eliot Moss wrote:

> No. I later pondered this and I think the only assumption I am making
> is that if thread i writes a pair (using tag 2 * i, for example), and
> later writes that same pair again (using tag 2 * i + 1, to be different),
> then both writes of the first pair of writes precede both writes of the
> second pair of writes. For absolute safety you would need a fence
> either before or after a pair of writes, and it would be a fence
> that prevents observations of writes from opposite sides of the fence
> from being perceived in the opposite order, i.e., a write fence. You
> could choose a place that minimizes the average cost -- perhaps
> immediately after the second write, to give maximum time until the next
> write, or immediately before the first write, to give maximum time
> for preceding writes to progress.  While a fence undoubtedly has
> *some* cost, I would expect it to have lower cost then a locked
> atomic operation.

A further refinement: The extra tag bit can viewed as a counter. You
can use more bits. This might be advantageous since you really need
the memory fence only between full cyclings of the counter. (This is
true also in the case at hand -- you need the fence only every other
time, and only if you are overwriting your own entry, e.g., you could
do it only if you are forced to use 2*i+1 because you observed 2*i
as the current tag before writing.) Notice that reading threads can
always observe an *old* valid pair -- the fence does not guarantee
that you see the latest values written, only that you won't see values
from opposite sides of a fence.

To use this algorithm you have to be happy with the occurrence of
invalid entries and with seeing stale entries ...

-- Eliot