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

[Herb Sutter]

Hans wrote:
> I certainly think that this sort of example must work for atomic/Java
> volatile operations.  Thus I think there has to be a cheap way to make
> it work, in general not necessarily with standard load and store
> instructions.

But note that Hans isn't saying that ordinary loads/stores are unaffected. They are affected: The system must still accurately transitively publish ordinary loads and stores. Pasting from my other email a minute ago just to put the example into this context also:

T1: lock();
    construct X;
    p = reference to X;
    unlock();

T2: lock();
    r2 = p;
    q = r2;
    unlock();

T3: lock();
    r3 = q;
    if( r3 != null ) {
      q.foo();
    }
    unlock();

Clearly the unlocks do something special (e.g., volatile stores). But they must accurately /and transitively/ publish the ordinary loads and stores to p and q.

> The other fundamental problem is that I haven't a clue as to what a
> programming language level memory model would look like that doesn't
> require this, or what semi-understandable rules one could give the
> programmer.

Right, because it would be demonstrably more difficult to reason about than relativity: Even in that difficult model, even with time dilation and other special effects, observers always agree on the order (though not time and speed) of causally related events. It is not possible for anyone to observe an effect E before observing some cause C that was visible to the entity that performed E at the time it did E (and thus could have affected E).

I think the reason we can't imagine a non-transitive programming model is that it literally wouldn't be sane -- it would not describe a universe that humans are capable of reasoning about. As Lamport noted:

  The concept of time is fundamental to our way of thinking.
  It is derived from the more basic concept of the order in
  which events occur. -- Lamport, 1978

If we don't support transitivity, we would be adopting something demonstrably harder than relativity, and we would be putting reliable programming well above the difficulty level that Einstein and Hawking labor(ed) at. I don't know of anyone claiming evidence that a human could understand such a world.

Herb





> -----Original Message-----
> From: cpp-threads-bounces at decadentplace.org.uk [mailto:cpp-threads-
> bounces at decadentplace.org.uk] On Behalf Of Boehm, Hans
> Sent: Friday, September 01, 2006 6:05 PM
> To: C++ threads standardisation
> Cc: c++std-ext at accu.org; Bronis R. deSupinski; 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
>
> I certainly think that this sort of example must work for atomic/Java
> volatile operations.  Thus I think there has to be a cheap way to make
> it work, in general not necessarily with standard load and store
> instructions.
>
> For X86, there's the added problem that I'm sure there's code out there
> that assumes that it works with ordinary loads and stores, since it
> generally does.  I would be amazed if there is no such code in the Linux
> kernel.  However I have no idea how to find it.
>
> The other fundamental problem is that I haven't a clue as to what a
> programming language level memory model would look like that doesn't
> require this, or what semi-understandable rules one could give the
> programmer.
>
> Hans
>
> > -----Original Message-----
> > From: cpp-threads-bounces at decadentplace.org.uk
> > [mailto:cpp-threads-bounces at decadentplace.org.uk] On Behalf
> > Of Peter Dimov
> > Sent: Friday, September 01, 2006 4:35 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. deSupinski;
> > Eric Niebler; Becker
> > Subject: Re: [cpp-threads] RE: "Agenda" for august 23-25
> > concurrency meeting
> >
> > Herb Sutter wrote:
> > > 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
> >
> > Slight variation:
> >
> > init: X *p1 = 0, *p2 = 0;
> >
> > P1: p1 = new X;
> >
> > P2: if( p1 ) p2 = p1;
> >
> > P3: if( p2 ) p2->f();
> >
> > Is it not a killer?
> >
> >
> > --
> > 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