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

[Peter Dimov]

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?