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

[Herb Sutter]

One more P.S.: I am realizing that this applies equally to lock-based code, so I shouldn't have restricted it to lock-free code only. Also, I didn't need to say "disjoint" when "different" was enough.

So please change my description of the general case that is problematic from:

  a lock-free multi-variable invariant maintained by more than
  one thread, where the two threads update disjoint parts of
  the invariant.

to:

  any multi-variable invariant maintained by more than one thread,
  where two threads update different parts of the invariant.

That describes a pretty broad set of cases that directly exploit/explode the hole in the PC "writes by the same processor occur in order" world by having the writes occur on different processors.

Then there are many other cases beyond even this broad set; one is the pass-the-pointer-around example Peter showed.

Herb


> -----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:34 PM
> To: C++ threads standardisation
> Cc: Meredith, Alisdair; c++std-ext at accu.org; 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;
> Bronis R. de Supinski; Eric Niebler; Becker
> Subject: RE: [cpp-threads] RE: "Agenda" for august 23-25 concurrency
> meeting
>
> 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
>
> --
> cpp-threads mailing list
> cpp-threads at decadentplace.org.uk
> http://www.decadentplace.org.uk/cgi-bin/mailman/listinfo/cpp-threads