- Glasgow-haskell-users

RE: ghc --make and make
by Simon Marlow 09 Dec '05

09 Dec '05

On 04 December 2005 00:51, John Meacham wrote: > I was thinking it would be nice if ghc --make could touch the output > file with the timestamp of the most recently modified source file. > > As it is, if you edit a file in between when ghc --make starts and it > finishes (a substantial amount of time in some cases) then 'make' will > not realize the dependencies have changed. Hmm, I'm not sure about this. I see the problem: you have a Makefile rule that looks like this: myprog : Main.hs Foo.hs Bar.hs ... $(GHC) -o $@ --make Main.hs and while building myprog, you edit Foo.hs after it has been compiled, with the result that myprog has a later modification date than Foo.hs so won't be recompiled. However, touching myprog to match the date of Foo.hs when it was compiled doesn't seem right - the date on the executable would be earlier than the object files, which might not cause problems with the Makefile rule above, but would likely lead to problems with different Makefile setups. Perhaps the date on an object file should be set to the same as the source file? And the date on the .hi file? The easiest thing to do is not to try to use make dependencies with --make, just run ghc --make every time. It doesn't link if linking isn't required any more. Cheers, Simon

2 1

RE: Optimizations for mutable structures?
by Simon Marlow 08 Dec '05

08 Dec '05

On 08 December 2005 11:52, Claus Reinke wrote: > is every MVar access is a synchronisation point (in terms of memory > update propagation between threads, not just in terms of thread > interaction)? Yes, it is. On a multiprocessor every MVar operation performs a full memory barrier internally. Incedentally, GHC hasn't actually supported multiprocessors until very recently, and it's still only in CVS and very experimental. Cheers, Simon

1 0

RE: Optimizations for mutable structures?
by Simon Marlow 08 Dec '05

08 Dec '05

On 07 December 2005 19:57, Claus Reinke wrote: > 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. > > see, eg, > http://research.microsoft.com/users/lamport/pubs/pubs.html#lamport-fairn ess Yes, good point. Regarding fairness, I've been working with the assumption that we don't need to preserve (certain kinds of) fairness properties when performing optimisations, whereas you and others want to preserve all fairness. Why don't I care about preserving fairness? Well you said it - it's not practical to implement. And since the implementation already doesn't guarantee strong fairness (or whatever it's called), it doesn't do any harm to weaken the fairness that we do provide, because programmers can't rely on strong fairness anyway. In practical terms, you won't notice the difference. Furthermore, I'd go so far as to say that a program that relies on the kind of fairness we've been talking about (arbitrary interleaving) for correctness or termination, is broken. We ceratinly *do* care about some kind of fairness. The property that we try to maintain is something like this: If a thread is unblocked according to the semantics, then the implementation ensures that it runs after a finite time. I'm not familiar with the fairness literature, perhaps this property is known? You may well call our implementation incomplete because it doesn't implement full fairness. I don't think that's useful though; I'd much rather characterise exactly what fairness property we can and do implement, and use that for reasoning with. [snip] > 2) compiler optimisation validity in sequential and non-sequential > environments > > 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. I don't think this applies in our setting. The reason we have IORef and {M,T}Vars, and not just a single mutable reference type, is that {M,T}Vars provide strong consistency guarantees when used to communicate between threads, whereas IORefs do not. Hence, IORefs can be implemented with much fewer restrictions. If you share IORefs between threads and run on a multiprocessor, you are at the mercy of both sequential optimisations and your architecture's memory consistency guarantees. In other words, don't do it. Use communication primitives that have strong properties in a multi-threaded 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 about programs. If you think any of this impacts your ability to reason about programs, please elaborate - I don't think it does. Cheers, Simon

4 3

RE: Optimizations for mutable structures?
by Simon Marlow 08 Dec '05

08 Dec '05

On 08 December 2005 09:40, Simon Marlow wrote: > If you share IORefs between threads and run on a multiprocessor, you > are at the mercy of both sequential optimisations and your > architecture's memory consistency guarantees. In other words, don't > do it. Use communication primitives that have strong properties in a > multi-threaded setting. I realised this paragraph is a bit stronger than I meant. Of course it's fine to share IORefs between threads as long as you use a proper communication primitive to synchronise access to the IORef. eg. using one MVar to lock on a bunch of IORefs is perfectly fine (this is how GHC's IO library is implemented). Cheers, Simon

2 1

RE: Optimizations for mutable structures?
by Simon Marlow 08 Dec '05

08 Dec '05

On 07 December 2005 15:21, Claus Reinke wrote: >> (assuming 'acts' doesn't modify 'r'). > > this remark is the problem. > >> No, Jan's transformation is correct even in a multithreaded setting. >> It might eliminate some possible outcomes from a non-deterministic >> program, but that's ok. There's no requirement that all >> interleavings according to the semantics have to be implemented. .. > > not implementing traces promised as possible by the semantics is not > a good idea, imho, as programmers have some control over the set of > traces themselves. It's unreasonable to expect an implementation to provide *all* transitions specified by the semantics. How could you tell, for one thing? For example, what if the compiler doesn't allow a context switch between two adjacent operations: writeIORef r e x <- readIORef r this is a good example, in fact, because GHC will quite possibly compile this code into a single basic block that doesn't allow a context switch between the two statements. However, the semantics certainly allows a context switch between these two operations. Is GHC wrong? No way! So how do you specify which transitions an implementation must provide? Perhaps there's a good formulation, but I don't know what it is. > in this case, acts could implement the synchronisation with another > thread working on r, ie., even if acts does not modify r itself, it > might reliably cause another thread to modify r before acts can end. > if such synchronisations depend on traces you have eliminated, the > code > would just block (without apparent reason), whereas in this case, r > will have a value after acts that shouldn't have been possible, due > to the explicit synchronisation code (again, happy debugging) .. I should have said that if 'acts' blocks, then the transformation is invalid. When I say "acts doesn't modify r", I mean to include all ways of modifying r, including synchronising with another thread, or calling an unknown function. > of course, you could try to infer non-sequential interference with r > resulting from act, but that is what Malcolm pointed out - you have > to take the full semantics into account when doing such > transformations (btw, java originally made a mess of this- hope that > has been fixed by now). I don't think so. Malcolm asserted that the transformation was invalid in a multi-threaded implementation; I disagree - it's just as valid in a multi-threaded implementation as a single-threaded one. You don't have to preserve non-deterministic interactions with other threads, because they're non-deterministic! Cheers, Simon

5 4

RE: Optimizations for mutable structures?
by Simon Marlow 08 Dec '05

08 Dec '05

On 07 December 2005 13:38, Malcolm Wallace wrote: > Jan-Willem Maessen <jmaessen(a)alum.mit.edu> writes: > >> - Fetch elimination for imperative reads: >> writeIORef r e >> acts >> readIORef r >> === writeIORef r e >> acts >> return e > > This transformation is valid only on single-threaded systems. > If there is any possibility of an IORef being shared across threads, > you are out of luck. (assuming 'acts' doesn't modify 'r'). No, Jan's transformation is correct even in a multithreaded setting. It might eliminate some possible outcomes from a non-deterministic program, but that's ok. There's no requirement that all interleavings according to the semantics have to be implemented. This is a hard property to state precisely, indeed we gave up trying to in the concurrency/FFI paper: http://www.haskell.org/~simonmar/papers/conc-ffi.pdf, see Section 6.1. Cheers, Simon

4 3

Re: Optimizations for mutable structures?
by Malcolm Wallace 07 Dec '05

07 Dec '05

[previously sent by mistake to Simon only - new para at end] "Simon Marlow" <simonmar(a)microsoft.com> writes: > Now, take the original program, but change the creation of m2 to > "newMVar ()", i.e. m2 starts off full. Is the transformation valid now? > Well maybe, because in some interleavings acts does not block, and we > can prove that at compilation time. I don't think it is valid for a compiler to say that "one possible execution path permits me to remove some code, therefore I will remove that code on all possible execution paths". The example I had in mind was a GUI where the action writeIORef r e >> acts >> readIORef r is intended to capture a situation where first we record some global configuration data for the application, then permit some arbitrary GUI actions to occur, and then we retrieve the configuration data again. My expectation is that the config data /will/ have been changed by some other GUI thread. Surely it cannot be OK for the compiler to silently deliver the original unchanged data here - it goes against the programmer's intention. Surely, if a Haskell programmer is going to write code that explicitly reads from a reference after writing to it, that sequence must 9/10 be intentional: otherwise wouldn't she have just used a let-binding? Regards, Malcolm

2 1

Optimizations for mutable structures?
by Jan-Willem Maessen 07 Dec '05

07 Dec '05

Talk of uniqueness and so forth on the various Haskell mailing lists causes me to wonder: with so much imperative code being written in Haskell these days, to what extent is / should GHC perform standard imperative optimizations? A few things come to mind: - Fetch elimination for imperative reads: writeIORef r e >> acts >> readIORef r === writeIORef r e >> acts >> return e readIORef r >>= \e -> acts >> readIORef r === readIORef r >>= \e -> acts >> return e And that sort of thing, generalized for other imperative monadic types... My feeling is this doesn't come up much in code as written on the page, but might well be relevant after inlining. - Some way to turn the following idiom into memcpy (for any array type): do a <- newArray writeArray a 0 e0 writeArray a 1 e1 writeArray a 2 e2 ...etc... What say others? Is there a need yet? (I don't honestly know the answer!) -Jan-Willem Maessen

3 2

RE: GCC in the Windows distribution of GHC
by Simon Marlow 07 Dec '05

07 Dec '05

On 07 December 2005 13:39, cschmidt(a)deds.nl wrote: > The Windows distribution of GHC includes GCC. Some header files > (such as iostream, algorithm, and so forth), however, are missing > (at least I was not able to find them). > > I could, of course, download the correct version of GCC (this must be > version 3.2.3 for GHC 6.4), and put the header files where GCC > can find them. I only wonder if this is the right thing to do. > > Were the header files omitted just to make the distribution smaller, > or for some other reason? The GCC bundled with GHC is intended mainly for compiling Haskell code via-C, and we didn't intend it to be invoked independently. Hence, it just contains the bits we need. If you want to compile C files using GHC (a reasonable thing to do), then the right thing to do is install a full GCC somewhere (eg. the mingw gcc), and tell GHC to use it, like this: $ ghc -pgmc c:/mingw/bin/gcc -c foo.c Cheers, Simon

2 1

RE: Strictness annotations on type parameters
by Simon Peyton-Jones 07 Dec '05

07 Dec '05

It's not at all easy in general. Suppose we have f :: [!a] -> [a] f xs = xs Does f run down the list, behind the scenes, evaluating each element? That could be expensive. Would it make any difference if we wrote f :: [!a] -> [a], or f :: [a] -> [!a]? Or does the type mean that f *requires* a list with *already-evaluated* elements? It's hard to avoid the feeling that one ought to be able to say something useful about strictness in the types but it's swampy territory, and hard to get right. Meanwhile, you can easily define your own writeIORef: strictWriteIORef r x = x `seq` writeIORef r x No need to sprinkle seq's everywhere! Simon | -----Original Message----- | From: glasgow-haskell-users-bounces(a)haskell.org [mailto:glasgow-haskell-users- | bounces(a)haskell.org] On Behalf Of Mario Blazevic | Sent: 06 December 2005 21:06 | To: glasgow-haskell-users(a)haskell.org | Subject: Strictness annotations on type parameters | | I spent several days last week trying to track a cause of a 100% | slowdown after some trivial changes I made. The profiler didn't show any | slowdown, presumably because it was dependent on optimizations, so I had | to revert to tweak-run-measure cycle. | | It turned out the slowdown was caused by some unevaluated thunks | that were kept around in long-lived IORefs. This is not the first time I | was bitten by too laziness, either. What made things worse this time is | that there is no way do declare the following: | | data Label = LabelRef {labelId:: !Unique, | reference:: (IORef !LabelState), -- illegal | origin:: Maybe !Label} -- illegal | | | No container data type can be annotated as strict. That means I have | to pepper my code with explicit evaluations to HNF before every | writeIORef (reference label): | | newState `seq` writeIORef (reference label) newState | | What is the reason for this restriction on where strictness | annotations can appear? Is it purely an implementation problem or is | there a reason emanating from Haskell design? If former, how hard would | it be to fix? | | _______________________________________________ | Glasgow-haskell-users mailing list | Glasgow-haskell-users(a)haskell.org | http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

4 3