[cpp-threads] Causality on more than two processors, write atomicity

[Herb Sutter]

Doug:
> >>And historically, almost no algorithms/programs have ever been
> >>found to require such strong guarantees. We once challenged
> >>people to come up with non-toy examples, and never got any.

Herb:
> > Really? Off the top of my head (imagine these represent a bounded
queue,
> > or a series of state changes in a FSM, or a series of barrier/gate
> > flags, or...):

Doug:
> You've just listed a bunch of things for which (to the best of
> my knowledge) no lock free algorithms exist. (We are still in
> the dark ages here.)

Hmm. Again off the top of my head (and I admit ignorance about lock-free
research), I know there are various lock-free hash table
implementations. Can't all of the above be implemented on top of a
shared hash table (albeit inefficiently, this is just to try to show
existence)?

> I guess what I am saying is that lock-free algorithms have to deal
> with so much other chaos that the lack of transitivity of visibility
> across observers doesn't seem to make anything any harder. They are
> already plenty hard enough though.

It seemed to me that "multi-variable invariants whose parts could be
updated by >1 threads and observed by another thread" sounded like a
case that could be common unless deliberately avoided. Are you saying
that if I read through the published lock-free algorithms, each one
would know and state whether it relies on this (or should do so)?

Now what about a general transformation that would make these examples
correct by introducing another write, by changing "var == value" into
"cas( &var, value, value )"?

  int x, y;

  start: x == y == 0;
  invariant: x <= y <= x+1

  P0: if( cas( &x, 0, 0 ) ) x = 1;
  P1: if( cas( &x, 1, 1 ) ) y = 2;
  P2: assert( invariant );

Now certainly the invariant never breaks for P2 (under a sane memory
model, including the JMM), right? Similarly, it seems to me that

  if( var < value ) // or any other nonequal comparison
    ...

could be transformed to

  lvar = var;
  if( lvar < value )
   if( cas( &var, lvar, lvar ) )
    ...

Presumably this is known, and just too expensive?

Herb