[cpp-threads] infinite loops

[Boehm, Hans]

I agree with Bill's concerns.  And I would really like to see the
guarantee about sequential consistency for data-race-free programs
stand.

On the other hand, I've been convinced that giving undefined semantics
to some infinite loops is probably tolerable.

Our conclusion the last time we thought about this was that the
offending class of nonterminating loops is essentially nonexistent in
real code.  Even Bill's example of a loop searching forever for a
counterexample is realistically going to write out check-points now and
then.  And some compilers have already concluded that such code is
usually erroneous, and thus flag blatantly infinite loops with a
warning.

If there are interesting examples of useful infinite loops that would
violate this rule, we should probably reconsider.  The only such example
I've knowingly written is an intentional infinite loop in a signal
handler to facilitate debugging.

I think the reasons for considering it include:

1) I expect there are many more optimizing C++ back-ends than there are
optimizing Java compilers.  Many of them would get this wrong anyway.
And currently we don't seem to have good test cases, probably not even
for Java.  The problem is that this is a restriction on the analysis
that rarely shows symptoms in the generated code, and then probably not
in very predictable ways.  How confident are we that optimizing Java
implementations actually get this right?  (I'd be surprised if gcj did.
But it's a bit behind on some of these things anyway.)  Imposing an
essentially untestable requirement that gets mostly ignored is almost
certainly not useful.  At that point it probably makes more sense to
give programmers rules to avoid the questionable behavior, which seems
relatively easy here.

2) My intuition is that this gets in the way of some transformations
that are likely to be profitable for static compilers, though I don't
know to what extent they are currently being performed.  It seems to be
fairly standard for C++ compiler back-ends to perform things like
"unroll and jam" transformations that would become invalid if you cannot
prove that the inner loop terminates.  I have no idea whether these are
currently likely to be performed for a loop with unknown iteration
count, but there are certainly cases for which the inner loop always
traverses the same linked list, and thus the transformation could be
valid in the sequential case.  I'm concerned that more of these cases
show up with automatic parallelization.

I agree that empirical results here would help a lot.  I think it's easy
to contrive code for which it threoretically would make a large
difference.  Whether such code is important in practice,  I do not know.

Hans

> -----Original Message-----
> From: cpp-threads-bounces at decadentplace.org.uk 
> [mailto:cpp-threads-bounces at decadentplace.org.uk] On Behalf 
> Of Bill Pugh
> Sent: Saturday, August 05, 2006 10:53 PM
> To: C++ threads standardisation
> Subject: Re: [cpp-threads] infinite loops
> 
> Sorry to have sat this out for a while.
> 
> I must say I find it profoundly disturbing that we are 
> considering defining the C++ spec so that programs that 
> exhibit no data races in any sequentially consistent 
> execution are allowed to exhibit behaviors that are not 
> sequentially consistent.
> 
> I'd also hate to think that a program that uses BigIntegers 
> to search for a counter example to Fermat's last theorem 
> would be defined as having semantics only if Fermat's last 
> theorem is false.
> 
> I think the current efforts are bending too far backwards to 
> accommodate the errors in existing compilers. it has been 
> known for years, before the JMM, that there was a problem 
> with the standard definition of control dependence (although 
> this problem wasn't widely understood).
> 
> Now, we are trying to define a semantics for C and C++ so it 
> will be possible to write reliable multithreaded software in 
> C++ for the 64 core desktop machine I'll have in 8 years. I 
> fear greatly the result if we bend too far backwards to 
> accommodate errors in existing compilers, with no empirical 
> data to show that using the broken definition for control 
> dependence gives substantial performance advantages.
> 
> No objections to using the correct definition in Java were 
> raised. If someone could provide data showing that by using 
> the broken definition we could get a 25% performance 
> improvement on a major benchmark, we might want to consider 
> using the broken definition in C/C++. But otherwise, we 
> shouldn't continue to make it harder to write correct 
> multithreaded C/C++ codes.
> 
> All the C/C++ compiler writers are going to have to expend 
> serious effort to make their compilers ready for 
> multithreaded code. Han's work has shown this.
> This is just one more thing that will need to be fixed. If we 
> don't fix the widely used definition of control  dependence 
> now, it will still be broken 100 years. Now is the time to fix it.
> 
> Bill
> 
> --
> cpp-threads mailing list
> cpp-threads at decadentplace.org.uk
> http://www.decadentplace.org.uk/cgi-bin/mailman/listinfo/cpp-threads
>