[cpp-threads] Memory model question

[Boehm, Hans]

As far as compiler optimization is concerned, the example that bothers
me most is really my standard one:

for (p = q; p != 0; p = p -> next) ++global_counter;

We'd like to translate this to

r = global_counter;
for (p = q; p != 0; p = p -> next) ++r;
global_counter = r;

as most compilers seem to do now.

But that's unsafe, since global_counter may not be written in the
original, and thus this can introduce a race.  Thus we need to
strip off the first loop iteration:

p = q;
if (p != 0) {
	r = global_counter;
	++r;
	p = p -> next;
	for (; p != 0; p = p -> next) ++r;
      global_counter = r;
}

The result is already a bit messy, but I think the transformation
is still pretty straightforward.

With the alternate interpretation, the compiler now also has to
prove that the assignment to global_counter in the initial loop
iteration actually writes back a modified value.  And I don't think
that sort of analysis is something that
compilers already do.  And in general, it can be quite hard.
If I had global_counter += x + y instead of ++global_counter, I'd
have to prove that x + y is not zero (mod 2**32 or whatever),
which would rarely be feasible.

Unless we can think of a real benefit, this seems like too
serious a burden on compiler writers.  (Or worse, it would be an
invitation for compiler writers to ignore the specification.)

Hans
	

> -----Original Message-----
> From: 
> Cpp-threads_decadentplace.org.uk-bounces at decadentplace.org.uk 
> [mailto:Cpp-threads_decadentplace.org.uk-bounces at decadentplace
> .org.uk] On Behalf Of Peter Dimov
> Sent: Friday, August 26, 2005 1:01 PM
> To: cpp-threads at decadentplace.org.uk
> Subject: Re: [cpp-threads] Memory model question
> 
> 
> >> On 8/26/05, Peter Dimov <pdimov at mmltd.net> wrote:
> >>> In your opinion, does the following example contain a data race?
> >>>
> >>> // initially x == 0
> >>>
> >>> T1:
> >>>
> >>> x = 0;
> >>>
> >>> T2:
> >>>
> >>> r1 = x;
> >>
> >> Yes.
> >>
> >> regards,
> >> alexander.
> 
> Boehm, Hans wrote:
> > I agree with Alexander.
> >
> > Presumably you are asking the question, because the pthread 
> standard 
> > uses the word "modify", and it's not clear that x is being modified 
> > here?
> 
> There are two ways to specify the memory model. One approach 
> is to talk 
> about reads and writes, under which there is a race. The 
> other alternative 
> is to talk about values and their potential visibility, which is more 
> consistent with the current language of the standard, where 
> there is no 
> concept of (nonvolatile) variable read. Under the second 
> model, there is no 
> "race", because the only value that x ever has is 0.
> 
> The significance is, as you say, compiler optimizations.
> 
> x = 0;
> 
> ->
> 
> x = 1; x = 0; is allowed under (1) and disallowed under (2). 
> Similarly,
> 
> if( a ) x = 0; else x = 1;
> 
> ->
> 
> x = 1; if( a ) x = 0;
> 
> is disallowed under (2).
> 
> 
> -- 
> cpp-threads mailing list
> cpp-threads at decadentplace.org.uk 
> http://decadentplace.org.uk/mailman/listinfo/cpp-threads_decad
entplace.org.uk