Optimizations for mutable structures?
claus.reinke at talk21.com
Wed Dec 7 14:56:52 EST 2005
there seem to be two issues here - can we agree on that at least?
1) scheduling non-sequential programs on sequential processors
i wasn't arguing that the scheduler should realise all possible
interleavings at once. the issue i was referring to is known as
"fairness" in concurrent systems literature. as with referential
transparency, various non-equivalent definitions are in use,
but one informal description might be something like:
if, for a given experiment, some event is possible according to
the semantics, it should happen eventually if the experiment is
repeated often enough.
otherwise -if the event cannot happen no matter how often the
experiment is repeated, one could hardly call it "possible"?
scheduling is usually more difficult to implement with fairness
guarantees than without, but reasoning about programs is more
difficult without such guarantees. i wouldn't expect every
concurrent haskell implementation to suceed in guaranteeing
fairness, but i would expect the semantics to do so, and would
consider any implementation failing in this to be incomplete
(perhaps neccessarily so, for well-documented pragmatic reasons).
2) compiler optimisation validity in sequential and non-sequential
the original motivation of this thread - are sequential transformations
still valid in a non-sequential setting?
in general, the answer is no, to the surprise/annoyance of many many
compiler implementors who want their valuable optimisations to work
even when their sequential language acquires threads. this is in fact
so annoying that some languages, notably Java, have tried to specify
the language semantics in such a way that some level of sequential
optimisations would still be valid in spite of the language having
threads - the search keyword here is "memory model".
as I mentioned, they messed up the first time round, and have been
through a lengthy re-design phase that involved *changes to the
semantics*. I haven't followed that process - the original Java language
spec of concurrency and memory model was sufficient to drive me
away from the language for good (fingers crossed..).
[concurrent haskell doesn't seem to have this kind of memory hierarchy,
but when you're suggesting to transform single threads based on local
knowledge of shared variables, you implicitly assume a hierarchy, and
a weak memory model rather than a strong one - a memory model is
one way of specifying the conditions under which reordering and other
transformations remain valid in a non-sequential setting]
i'd really, really prefer concurrent haskell not to go down a route in which
demands of simpler implementation leads to subtle problems in reasoning
More information about the Glasgow-haskell-users