[cpp-threads] RE: "Agenda" for august 23-25 concurrency meeting

[Herb Sutter]

P.S.: For the examples I just gave below, assume transitivity doesn't hold, and then the question: What if I used locks to protect x and y? It's not obvious that the answer is yes, because the usual definition of release semantics would only guarantee that each lock release would publish only the earlier writes /by that thread/ -- which would still leave unanswered the question of whether P2's lock release would publish the update to x that P2 observed before the release but which was actually performed by P1. So even with locks and acq/rel semantics around, I think transitivity probably still needs to get explicit recognition as it doesn't seem to fall out of the basic definition of locks.



> -----Original Message-----
> From: cpp-threads-bounces at decadentplace.org.uk [mailto:cpp-threads-
> bounces at decadentplace.org.uk] On Behalf Of Herb Sutter
> Sent: Friday, September 01, 2006 4:21 PM
> To: C++ threads standardisation
> Cc: Pete; c++std-ext at accu.org; Bronis R. de Supinski; David Miller;
> Lawrence Crowl; omp-lang at openmp.org; Terrence.Miller at sun.com; David
> Miller; Howard Hinnant; Bill Seymour; P.J. Plauger (Dinkumware Ltd);
> Bjarne Stroustrup; Meredith, Alisdair; Eric Niebler; Becker
> Subject: RE: [cpp-threads] RE: "Agenda" for august 23-25 concurrency
> meeting
>
> Doug Lea wrote:
> > Robison, Arch wrote:
> > >
> > > > 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.
> > >
> > > If you have a non-toy example algorithm that shows a need for
> causality
> > > or total store order, I would very much like to see it and show it to
> > > our hardware architects.
> >
> > Despite lack of a killer example,
>
> Hmm. I keep seeing this assertion, and it surprises me. :-)
>
> I am under the impression that not having transitivity would break
> essentially every algorithm falling into the following general case: a
> lock-free multi-variable invariant maintained by more than one thread,
> where the two threads update disjoint parts of the invariant.
>
> For example, the canonical "toy" example was:
>
>   init: x = y = 0;
>
>   P1:   x = 1;               // a
>
>   P2:   if( x==1 )           // b
>           y = 1;             // c
>
>   P3:   if( y==1 )           // d
>           assert( x == 1 );  // e
>
> where x is only written by P1 and y is only written by P2. (This assumes x
> and y can be assigned atomically, where by "atomically" I only mean
> "without tearing" and I don't mean that they are necessarily globally
> visible all at once which would make the transitivity question moot.)
>
> One way to look at this is to say that the question comes down to: "If
> line d reads y == 1, does a given model guarantee that therefore line a
> causally-precedes (or happens-before, etc.) line e?"
>
> But the above isn't really a toy example, because it's only a slight
> transformation away from a bounded-queue producer-consumer, where P1
> consumes queue items (reads x and y, but updates x only), P2 produces them
> (reads x and y, but updates y only), and P3 observes the number of items
> in the queue (reads x and y, doesn't update either). Let x and y be of
> atomic type representing the lowest and highest indices in use (at least y
> must have acquire/release semantics), let bound == 50, and for coding
> simplicity ignore integer overflow:
>
>   init: x = y = 0;           // x==y => empty queue
>
>   invariant:
>         0 <= y-x <= 50       // never more than 50 items in queue
>
>   P1:   while( ... not done consuming ... ) {
>           if( x < y ) {      // if something in queue
>             Process( a[x] ); //   handle it, and
>             ++x;             //   record that it was done
>           }
>         }
>
>   P2:   while( ... not done producing ... ) {
>           while( y-x >= 50 ) // bounded at 50 items...
>             ;                //   so spin while it's full
>           a[y+1] = NewItem();// add new item, and
>           ++y;               // record its existence
>         }
>
>   P3:   if( y > 200 )
>           assert( x > 150 ); // assert (part of) the invariant
>
> Does that match the requirement in the transitivity question? P2 can only
> increment y past 200 if it sees x > 150, and clearly if P3 can observe y >
> 200 /before/ it observes the increment of x > 150, then P3 can observe a
> broken invariant -- and more generally we have observed an effect before
> its cause. (FWIW, Prism categorically prohibits this; allowing this would
> fundamentally violate Prism's causality principle.)
>
> Again, I thought this was only one example of the general case of "a lock-
> free multi-variable invariant maintained by more than one thread, where
> the two threads update disjoint parts of the invariant."
>
>
> > and my belief that macho
> > lock-free programmers could cope with lack of guaranteed
> > transitivity,
>
> I'm not sure about that. I wonder how many who would think they are coping
> with it would actually be shipping bugs. :-)
>
>
> > I am still uncomfortable about
> > relaxing requirements for TSO-ness as a both a human-factors
> > and language semantics concern. People seem to naturally
> > think causally, and will be unable to even see bugs due to
> > bad assumptions.
>
> I agree that better debuggability is a strong secondary argument for
> causal transitivity too, but to me the primary argument is that it's
> fundamentally necessary for maintaining ).
>
> Herb
>
>
> --
> cpp-threads mailing list
> cpp-threads at decadentplace.org.uk
> http://www.decadentplace.org.uk/cgi-bin/mailman/listinfo/cpp-threads