Optimizations for mutable structures?

[Simon Marlow]

On 07 December 2005 16:38, Malcolm Wallace wrote:

> "Simon Marlow" <simonmar at microsoft.com> writes:
> 
>> I should have said that if 'acts' blocks, then the transformation is
>> invalid.
> 
> Well that is exactly what I was assuming when I said that the
> transformation is invalid. In the general case, for some arbitrary
> actions between the write and the read (excluding another write of
> course), there is no guarantee that the IORef remains unmodified.

This is an analysis that's performed all the time in C compilers, it's
quite straightforward to do a good approximation.  One simple algorithm
is: a store can be forwarded to a matching read as long as there are no
intervening writes that may alias, or function calls.

C does this and C has threads, so what's the difference?

> If you want to restrict the intermediate actions to be non-blocking,
> such that another thread cannot run, then that is an extra (and
> significant) proof obligation.
> 
> And AFAICS your non-blocking argument only applies to co-operative
> scheduling.  If pre-emption is permitted (e.g. interrupt-handling),
> then all bets are off, because an arbitrary thread could write to
> the IORef at any moment.

No, that is exactly what I disagree with.  Faced with non-derministic
semantics, the compiler does *not* have to preserve all possible
outcomes.  In other words, it does not have to assume that an IORef can
be modified between any two arbitrary instructions.  If we had to assume
this, then indeed all bets would be off, and C compilers would be very
much more restricted in what optimisations they could perform.  

I don't know how I can explain this a different way - it seems pretty
obvious to me, but I'm probably not explaining it well :-/

You cut the example from my message - did you agree with the conclusion?
Or the conclusion I made from Ian's example?

Cheers,
	Simon