December 2005 - Glasgow-haskell-users

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

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

07 Dec '05

On 07 December 2005 15:14, Ian Lynagh wrote: > On Wed, Dec 07, 2005 at 02:15:24PM -0000, Simon Marlow wrote: >> 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. > > I don't think it's true for this program: > > import Data.IORef > import Control.Concurrent > > main = do m1 <- newEmptyMVar > m2 <- newEmptyMVar > let e = 6 > not_e = 7 > acts = putMVar m1 () >> takeMVar m2 > r <- newIORef 5 > forkIO $ do takeMVar m1 > writeIORef r not_e > putMVar m2 () > writeIORef r e > acts > readIORef r >>= print Sorry for not being clear enough, see my other message. I agree the transformation is not valid in this case. putMVar and takeMVar count as modifying the IORef. However... remove all the putMVars and takeMVars. Do you think it's valid now? Even though after the transformation the program might deliver a different answer? (I claim yes). 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. Interesting - I think you could justify doing the transformation in this case too, but I doubt any compiler would go that far. Cheers, Simon

1 0

RE: calling system gives exception, waitForProcess
by Simon Marlow 07 Dec '05

07 Dec '05

On 28 November 2005 23:16, Neil Mitchell wrote: > On Windows XP, with GHC 6.4.1, I get the following error consistently > when calling "system", from the module System. I get this error on two > entirely different computers, one slow (750Mhz) system, and one fast > (3Ghz) system. > > Its easiest to demonstrate when using GHCi, but the problem also > occurs when running Haskell programs compiled with GHC. > > Prelude System> system "yhi Main" > PreludeList.!!: on empty list > *** Exception: waitForProcess: does not exist (No such file or > directory) > >> From a windows standard console, in the same current directory, I >> get: > Windows> yhi Main > PreludeList.!!: on empty list > > When calling yhi using system in other circumstances (on other > programs), it works fine. The "PreludeList.!! ..." text is being > generated by the yhi program. > > The yhi program is written in C, and is available from > http://www.cs.york.ac.uk/~ndm/yhc/. Unfortunately this is probably a > bit too large to use as a minimal test case, and takes quite a while > to install/configure at the moment. > > Any idea why the waitForProcess error is being raised? I don't know why this is happening, sorry. waitForProcess does this: if (WaitForSingleObject((HANDLE) handle, INFINITE) == WAIT_OBJECT_0) { if (GetExitCodeProcess((HANDLE) handle, &retCode) == 0) { maperrno(); return -1; } return retCode; } So it seems that GetExitCodeProcess is returning ENOENT (or the Windows equivalent) for some reason. Could something else be calling GetExitCodeProcess() first? If you can find a smaller test case, I can probably look into it. Cheers, Simon

2 1

RE: New bug tracker: Trac
by Simon Marlow 07 Dec '05

07 Dec '05

On 07 December 2005 13:17, Gour wrote: > Simon Marlow (simonmar(a)microsoft.com) wrote: > > Hi Simon! > >> Unfortunately there isn't a way for users to register themselves, we >> have to create them manually using htpasswd. I'm sure someone must >> have implemented an online user-registration system for Trac though? > > This is what I got on #trac channel from one of the devs: > > "they created a 'guest/guest' login/password, and apparently that's > enough for discouraging spam attempts" and it refers to: > > http://initd.org/tracker/pysqlite/wiki Ah yes, good idea, I'll do that. Cheers, Simon

1 0