- Glasgow-haskell-users

difficult profiling example
by Serge D. Mechveliani 14 Dec '06

14 Dec '06

This is again on the time profiling in ghc-6.6. Who could, please, guess what is happening? ------------------------------------------------------------------------ main = putStr (showsList newProveds "\n") where ... ((_, newProveds), _) = {-# SCC "main.searchLemmataInInitial" #-} searchLemmataInInitial opts rc rcPerLemma initState searchLemmataInInitial proverOpts rc rcPerLemma searchState = (let ((state', newProveds), rcRem) = ---------- {-# SCC "searchLemmata" #-} searchLemmata ((searchState, []), rc) cost = lsisCost searchState -- data field selection in ((state' {lsisCost = cost + rc - rcRem}, newProveds), rcRem) ---------- -- only newProveds is used in the test in `main' ) where ... searchLemmata extState@ ((searchState, newProveds), rc) = {-# SCC "searchLemmata 2" #-} (case splitCs of ... <complex definitions> ) where ... <complex definitions> -------------------------------------------------------------------- ghc-6.6 is built with -prof -auto-all, so that the ghc library functions are shown as the cost centers too (I doubt of whether this can help me). Making: ghc $compilationOptions -prof --make Main Running ./Main +RTS -p -M200m -RTS (this is for -Onot, because -O takes too long, and commonly produces a similar report for this kind of example). In this test, newProveds occurs [], and it is printed out as the only result. My user's SCC centers are set only at the three points shown above. The profiling shows ---------------------------------------------------------------- CAF Main 2\60 89 0.0 0.0 99.9 99.9 ... main.searchLemmataInInitial Main \ 347 1 24.1 26.8 99.8 99.8 ... searchLemmata 2 Main 3\49 114 1.3 1.3 4.2 3.6 ... searchLemmata Main 3\48 1 0.0 0.0 0.0 0.0 ... ------------------------------------------------------------ What I expected --------------- 1. "main.searchLemmataInInitial" inherits 99% of time. 2. searchLemmata is a loop inside searchLemmataInInitial which does everything, so it inherits 99% of time (it has SCC too). What is reported ---------------- 6 lines for the SCC "main.searchLemmataInInitial" -- while in reality it is called only once. I do not know why they are so many, but let it be. Exactly one of these lines is "non-zero": main.searchLemmataInInitial Main 347 1 24.1 26.8 99.8 99.8 Its individual time % is 24.1, inherited 99.8. A single line for "searchLemmata" (main loop). searchLemmata Main 348 1 0.0 0.0 0.0 0.0 -- entered 1 time from `main', (but the function searchLemmata calls itself many times -- see "searchLemmata 2"). A single line for "searchLemmata 2" (its SCC is in the beginning of the definition of searchLemmata): searchLemmata 2 Main 349 114 1.3 1.3 4.2 3.6 It is probable that it is entered 114 times. But its inherited time 4.2 % is un-probable, it must be near 100%. Because, who has taken a great cost of time(searchLemmataInInitial) - time(searchLemmata) ? This difference must be close to zero, because it is defined let ((..., newProveds), ...) = searchLemmata ((searchState, []), rc) ... in ((..., newProveds), ...), and only newProveds is used in the test in `main'. What computation remains after searchLemmata ? Only extracting snd . fst from a pair of pairs. The result is [], so `shows' and the output cost almost zero. So, the profiling says actually that this snd . fst costs 99%. I do not understand this profiling, so far. It also shows many GHC and Haskell library centers, like this: ---------------------------------------------------------- total time = 228.40 secs (4568 ticks @ 50 ms) total alloc = 4,272,700,464 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc main.searchLemmataInInitial Main 24.1 26.8 . GHC.Base 7.6 4.9 insert Data.Set 6.2 1.4 foldlStrict Data.Set 5.6 0.0 hedgeUnion Data.Set 5.4 6.3 map GHC.Base 5.2 6.5 trim Data.Set 4.6 0.0 ... and also about 6000 of expanded lines. ---------------------------------------------------------- And this all does not explain why the inherited time % for "searchLemmata 2" is 4.2 instead of 99. Probably, compiling GHC under -auto-all does not help my aim, but neither it seems creating extra difficulties. Another curious point is, for example, that Base.map is said to take a considerable time when entered from (.) (composition). In my user program, this is applied as compose $ map shows xs for the need of showing a list -- probably, the only usage. And it costs zero in this example, because nothing is shown except []. Maybe, the GHC library uses it. My program contains many places with foldl, which I am going, maybe, to replace with foldr. But I do not think that this will change essentially the profiling for this particular example. Who can, please, tell what I may be missing? Thank you in advance, ----------------- Serge Mechveliani mechvel(a)botik.ru

2 1

RE: [Haskell] ANNOUNCE: Visual Haskell 0.2 final
by Bayley, Alistair 12 Dec '06

12 Dec '06

> From: haskell-bounces(a)haskell.org > [mailto:haskell-bounces@haskell.org] On Behalf Of Krasimir Angelov > > The final version of Visual Haskell 0.2 is ready: > > http://www.haskell.org/visualhaskell > > This is the first version that is: > - available for both VStudio 2003 and VStudio 2005 > - distributed with a stable GHC version (6.6) > - the plugin itself is much more stable than its first 0.0 version I'm trying to use this, but it seems to hang whenever I try to do a build (or a clean). Is there some way I can debug it to see why/where it's stuck? There's no build output in the output window. Alistair ***************************************************************** Confidentiality Note: The information contained in this message, and any attachments, may contain confidential and/or privileged material. It is intended solely for the person(s) or entity to which it is addressed. Any review, retransmission, dissemination, or taking of any action in reliance upon this information by persons or entities other than the intended recipient(s) is prohibited. If you received this in error, please contact the sender and delete the material from any computer. *****************************************************************

3 6

generic ghc binary Linux (x86_64) misses libHSghc
by Christian Maeder 11 Dec '06

11 Dec '06

having just installed http://www.haskell.org/ghc/dist/6.6/ghc-6.6-x86_64-unknown-linux.tar.bz2 it occurs that libHSghc.a is missing, but ghc-pkg lists (ghc-6.6). Christian maeder@castor:~/haskell/linux64> ghci -package ghc ___ ___ _ / _ \ /\ /\/ __(_) / /_\// /_/ / / | | GHC Interactive, version 6.6, for Haskell 98. / /_\\/ __ / /___| | http://www.haskell.org/ghc/ \____/\/ /_/\____/|_| Type :? for help. Loading package base ... linking ... done. Loading package template-haskell ... linking ... done. Loading package readline-1.0 ... linking ... done. Loading package unix-1.0 ... linking ... done. Loading package Cabal-1.1.6 ... linking ... done. Loading package regex-base-0.71 ... linking ... done. Loading package regex-posix-0.71 ... linking ... done. Loading package regex-compat-0.71 ... linking ... done. Loading package haskell98 ... linking ... done. Loading package ghc-6.6 ... ghc-6.6: can't load .so/.DLL for: HSghc (libHSghc.so: cannot open shared object file: No such file or directory)

2 2

throwTo & block statements considered harmful
by Chris Kuklewicz 11 Dec '06

11 Dec '06

Title: "throwTo & block statements considered harmful" This is a short essay to prove that the current GHC concurrency implementation has a critical flaw. And this is on the wiki at: http://haskell.org/haskellwiki/GHC/Concurrency#throwTo_.26_block_statements… The key problem is, at least in the presence of block/unblock, that Exceptions are never reliably delivered. And this is not a theoretical case, but can cause a hang in something as innocuous as "program A" given below. Simon Marlow wrote: >> I think people are misunderstanding the nature of a safepoint. The >> safepoint is a point at which you are prepared to have exceptions >> delivered. This does not mean that they *will* be delivered, just that they >> can. If you need to *wait* for an asynchronous exception, then you >> shouldn't be using them at all. > > Right. If a thread mostly runs inside 'block' with the occasional safe > point, then your exceptions are not really asynchronous, they're synchronous. > > > In this case, I'd say a better solution is to have an explicit event queue, > and instead of the safe point take an event from the queue. The action on > receiving an event can be to raise an exception, if necessary. > > Cheers, Simon The implementation of asynchronous signals, as described by the paper "Asynchronous exceptions in Haskell Simon Marlow, Simon Peyton Jones, Andy Moran and John Reppy, PLDI'01." is fatally inconsistent with the implementation in GHC 6.4 and GHC 6.6 today. The implemented semantics have strictly weaker guarantees and render programs using asynchronous expressions impossible to write correctly. The semantics in the paper were carefully designed to solve the problem laid out in the first sentence of the abstract: "Asynchronous exceptions, such as timeouts, are important for robust, modular programs, but are extremely difficult to program with -- so much so that most programming languages either heavily restrict them or ban them altogether." And I believe the paper succeeded. The paper shows how to replace other languages pervasive and intrusive error catching and handling code with much cleaner, clearer, and often more correct code. The implementation in GHC has changed the behavior of throwTo from asynchronous (not-interruptible) to synchronous (interruptible?) as discussed in section 8 of the paper. This change, in and of itself, is not the fatal problem; as described in the paper a (forkIO (throwTo ...)) recovers the asynchronous behavior. The fatal change between the paper and GHC comes from not following section 7.2 as published. Section "7.2 Implementation of throwTo" has two bullet point, and the second bullet point is (retyped, so typos are my own fault): "As soon as a thread exits the scope of a 'block', and at regular intervals during execution inside 'unblock', it should check its queue of pending exceptions. If the queue is non-empty, the first exception from the queue should be raised." A test of GHC 6.6 shows that this is not the case. Test program A: > loop = block (print "alive") >> loop main = do tid <- forkIO loop threadDelay > 1 killThread tid Program A, compiled with (-threaded) on a single CPU machine never halts. It will print "alive" forever while the the main thread is blocked on "killThread". This is wh As an aside, removing the threadDelay causes killThread to destroy the child before it can enter the block, thus showing the need to add "forkBlockedIO" or "forkInheritIO" to the library. This can be worked around using an MVar. Changing the definition of loop produces Test program B: > loop = block (print "alive") >> yield >> loop main = do tid <- forkIO loop > threadDelay 1 killThread tid This prints "alive" twice before the killThread succeeds. The paper demands that when the loop in Program A exits the scope of "block (print a)" that it check a queue of pending exceptions, see that it is non-empty, and raise the exception thrown by killThread. This can also be seen in "Figure 5. Transition Rules for Asynchronous Exceptions", where killThread should use throwTo to create an in-flight exception and exiting the scope of block in the presence of this in-flight exception should raise the exception. The implementation in GHC sleeps the main thread at the killThread command, and it is awoken when the block is exited and to succeed in delivering the exception it must execute while the child is still in the unblocked state. But the child re-enters a blocked state too quickly in Program A, so killThread never succeeds. The change in Program B has the child "yield" when unblocked and this gives the main thread a change to succeed. This trick using yield to make a safepopint was suggested by Simon Marlow: > The window in 'unblock (return ())' is tiny, I'm not really surprised if > nothing ever gets through it. You might have more luck with 'unblock yield'. It has been said on this mailing list thread that needing "yield" to program concurrently is a bug in the user's code and should be replaced by other mechanisms. In a complex program with many threads even the yield trick may not be enough to program reliably. Using blockY io = do x <- block io yield return x unblockY io = unblock (yield >> io) instead of 'block' and 'unblock' is at least a simple but unreliable workaround. This would not be a fatal flaw if there were a simple reliable workaround. The best workaround is the following, which is anything but simple, and amount to re-implementing the mechanisms in the paper: * When forking a thread: ** Create an (Chan Exception) (or (TChan Exception)) and pass it to the child thread. Call this the queue. ** Create a ((T)MVar queue) to indicate whether the thread is still alive or not and wrap the whole child action in a 'finally' to ensure this is set to the dead state when the child exits. (Alive iff the queue is in the MVar) ** To be sure the child thread is in the handler, use another MVar or re-use the "alive/dead" MVar to ensure the child is running before returning the ThreadId from the fork operation. * Replace all uses throwTo/killThread by ** Test the alive/dead state of the thread, proceeding only on living threads ** Putting the Exception in the queue ** Call throwTo/killThread with the Exception * The child thread must: ** implement safepoints by checking the queue ** At each 'block' to 'unblock' transition the child ought to add a safepoint This machinery closely recovers the queue of exceptions and the semantics described in the paper. When a thread has died the queue is removed from the alive/dead MVar and can be garbage collected, along with any pending exceptions for the dead thread. To ensure the above semantics are not violated by the caller, the now fork operation should not return an exposed ThreadId, but should return some proxy type or operation to ensure only the proper throwto/killThread are peformed. Next I will demonstrate how the paper's achievement of simple and clear error handling code is lost. The child thread is where the workaround becomes a nightmare. It is impossible to test the current 'block' versus 'unblock' state. So the only time the child is certain that a 'block' to 'unblock' transition has occurred is when it is explicit: > unblock ( .... block ( ... ) <*> .... ) The <*> is obviously such a transition and ought to have a safepoint added. But is only because the block had the explicit unblock around it. If there were a function such as > atomicUpdateFoo = block (...) <?> then there is no way to know if the <?> should be a safepoint. Therefore atomicUpdateFoo needs documentation so that the caller knows to add a safepoint in the case it is called from the unblocked case. In a more complex example: > atomicUpdateFooBar = block (...) <1?> block (...) <2?> the caller cannot add <1?> itself, and must therefore pass in code 'safe :: IO ()' to all such functions: > atomicUpdateFooBar safe = block (...) >> trans >> block (...) >> trans where 'trans' is "return ()" or "checkChan queue" depending on whether the the caller knows it is in a 'block' or 'unblock' state. If the parent never needed to use 'throwTo'/'killThread' then the child never needs 'block'/'unblock' and the nightmare is avoided. But if the child uses any operation which can block such as 'accept' or 'getChar' or 'takeMVar' then the parent cannot deliver the signal without waking up the child with a 'throwTo' which quickly leads to either an overwhelming use of 'catch' in the child (like other languages) or use of 'block' and the fragile workaround I just described. As an aside, if there was a "isBlockedThreadState" operation, then it would be possible to create a better client workaround: checkChan queue x = do isBlocked <- isBlockedThreadState -- perhaps needing =<< myThreadId case isBlocked of True -> return x False -> raiseQueue queue x raiseQueue queue x = do hasException <- isEmptyChan queue case hasException of False -> return x True -> readChan >>= raise checkedBlock queue io = do x <- block io checkChan queue x checkedUnblock queue io = checkChan queue >> io If that existed then the client should use checkedBlock and checkedUnblock instead of block and unblock. The net effect of this workaround is to implement the queue described in the original paper and wrap the forkIO/throwTo/block/unblock operations with new ones that implement the semantics described in the section 7.2 of the paper. We can try to implement isBlockedThread state by maintaining a stack of block/unblock operations: checkedBlock stack queue io = do x <- bracket_ (modifyIORef stack (True:)) (modifyIORef stack tail) (io) checkChan queue x checkedUnblock stack queue io = do checkChan queue () x <- bracket_ (modifyIORef stack (False:)) (modifyIORef stack tail) (io) isBlockedThread stack = liftM head (readIORef stack) Where "stack :: IORef [Bool]" is created and passed to the child by the modified fork operation. The 'stack' above grows without bound during recursion and is not tail recursive, so the stack management should be changed to the algorithm in the paper... in which case one really has recreated the paper's implementation inside Haskell. The only alternatives are to * write code that may hang forever at a throwTo/killThread * never use throwTo or killThread making block/unblock irrelevant * never use 'block' (and 'unblock') * only write children with explicit "(unblock ... block (... block () ...) >>= raiseQueue queue >>= ...." where the different between checked and unchecked block is obvious and explicit. * Track and propagate the blocked state as in atomicUpdateFooBar. This problem with throwTo/block was not obvious until I stated writing small programs to test the implementation in GHC and thus discovered that the paper's description had mislead me. The key problem is, at least in the presence of block/unblock, that Exceptions are never reliably delivered. And this is not a theoretical case, but can cause a hang in something as innocuous as "program A" given above. -- Chris Kuklewicz

4 4

GHC 6.6 on Ubuntu
by Pupeno 10 Dec '06

10 Dec '06

> Is there a preferred way of getting this going? I tried the GHC To get GHC 6.6 on Ubuntu I recommend you my way, getting the sources for the packages for Ubuntu + 1 and building the packages. It is very easy, I've documented it on my blog: http://pupeno.com/blog-en/unstable-packages-on-ubuntu/ > instructions for Debian, but this seems to depend on 6.6 already being > in the repository, which it's not, in Ubuntu (why?). The lattest stable Ubuntu was released before GHC 6.6. Same for Debian. GHC 6.6 will be in the next release of both. > I like Debian/Ubuntu's install system, and I assume that 6.6 will > eventually make it into Ubuntu. I want to be sure whatever I do now > doesn't later confuse the system. What I recommended shouldn't cause any problem or confusion. -- Pupeno <pupeno(a)pupeno.com> (http://pupeno.com)

1 0

ghc-6.6-src-extralibs.tar.bz2
by Christian Maeder 09 Dec '06

09 Dec '06

The archive http://www.haskell.org/ghc/dist/6.6/ghc-6.6-src-extralibs.tar.bz2 does not contain the files ControlPoint.hs and Domain.hs from directory libraries/OpenGL/Graphics/Rendering/OpenGL/GL/ These files are listed by the binary distribution http://www.haskell.org/ghc/dist/6.6/ghc-6.6-i386-unknown-linux.tar.bz2 Personally I don't miss these files, but they are of course missing from distributions I (and possibly others) made. How imported are these files? They are also not listed in libraries/OpenGL/openGL.cabal. Cheers Christian

3 3

'accept' behavior with an asynchronous exception inside of a 'block'
by Cat Dancer 08 Dec '06

08 Dec '06

Chris Kuklewicz suggested I direct this question to the developers ^_^ If I use a network accept inside a block: block ( ... (clientSocket, sockAddr) <- accept serverSocket ... ) and the 'accept' unblocks a pending asynchronous exception and the exception gets thrown, does this mean that the 'accept' won't have accepted a network connection? Certainly this seems like desirable behavior, since if the 'accept' call might accept a network connection and *then* raise the asynchronous exception, the reference to the accepted connection would be lost. However I couldn't tell from the library documentation whether this was intended to be a guarantee of the 'accept' function or not.

1 1

Unlifted type variables in GHC
by Brian Alliet 08 Dec '06

08 Dec '06

What kind of problems could crop up if I try to create type variables with an unlifted kind inside GHC (not in user code, just inside the compiler)? I want to make ByteArray# and MutableByteArray# parameterized over their element types. ByteArray# would have kind # -> #, and MutableByteArray#, * -> # -> # . indexByteArray# would have the type (in pseudo haskell) forall (e::#). ByteArray# e -> Int# -> e. This would put all the ByteArray# operations (along with tagToEnum#) in that weird class of primops that have a polymorphic type but must be instantiated with a monomorphic type by the time it hits the code generator but that shouldn't be a big deal. Don't get too hung up on the ByteArray# example. I'm not actually proposing we change ByteArray# (I know it'll cause a few problems with the current UArray implementation). I'm just wondering if something like this is possible, and if so, what I should watch out for if I try to do it. Thanks, -Brian

2 2

bang patterns give fundamentally new capabilities?
by John Meacham 08 Dec '06

08 Dec '06

I was recently presented with the problem of writing a function like so seqInt__ :: forall a . a -> Int# -> Int# seqInt__ x y = x `seq` y which seems fine, except 'seq' of type forall a b . a -> b -> b cannot be applied to an unboxed value. I could not think of a way to actually get the behavior I wanted until I remembered bang patterns. seqInt__ :: forall a . a -> Int# -> Int# seqInt__ !x y = y which seems to work! my question is, is this actually something fundamentally new that bang patterns allow or was I just not able to figure out the "old" way to do it? Also, is there a way to do something similar but for 'lazy' rather than 'seq'? I want something of type type World__ = State# RealWorld {-# NOINLINE newWorld__ #-} newWorld__ :: a -> World__ newWorld__ x = realWord# -- ??? except that I need newWorld__ to be lazy in its first argument. I need to convince the opimizer that the World__ newWorld__ is returning depends on the argument passed to newWorld__. using any wacky ghc primitives in 6.6 is fine, I would just like something that stands up to ghc -O2. when compiling with -O, ghc is too clever and sees through tricks like this. (at least, that is what I think is happening) John -- John Meacham - ⑆repetae.net⑆john⑈

4 5

profiling experience
by Serge D. Mechveliani 08 Dec '06

08 Dec '06

People, I describe below my small experience with the time profiling in ghc-6.6. To make sure, consider first the following simple example: ------------------------------------------------------- import List (sort) main = {-# SCC "main" #-} let n = 5*10^4 :: Int in putStr (shows (f [1 .. n]) "\n") f :: [Int] -> Int f xs = {-# SCC "f" #-} case xs of [] -> 0 x: ys -> (g x) + (h x) + (f ys) where g x = {-# SCC "g" #-} last $ sort [0 .. (rem x 10)] h x = {-# SCC "h" #-} last $ sort [0 .. (rem x 20)] ------------------------------------------------------- Making: ghc -O -prof --make Main Running: ./Main +RTS -p -M100m -RTS This produces the report (its indentation shows which center is called from which): -------------------------------------------------------------------- total time = 3.00 secs (60 ticks @ 50 ms) total alloc = 130,608,300 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc h Main 65.0 67.3 g Main 33.3 30.9 main Main 1.7 1.5 individual inherited COST CENTRE MODULE no. entries %time %alloc %time %alloc MAIN MAIN 1 0 0.0 0.0 100.0 100.0 main Main 162 1 0.0 0.0 0.0 0.0 CAF Main 156 3 0.0 0.0 100.0 100.0 main Main 163 0 1.7 1.5 100.0 100.0 f Main 164 50001 0.0 0.3 98.3 98.5 h Main 166 50000 65.0 67.3 65.0 67.3 g Main 165 50000 33.3 30.9 33.3 30.9 CAF GHC.Handle 109 3 0.0 0.0 0.0 0.0 -------------------------------------------------------------------- To my mind, these numbers look all right: like I expected. Only I do not so firmly understand what is CAF, a "constant application form", a data which has cost, is assigned cost, but is out of the stack of calls. Is this profiling all right? Then, I need to find the main time eater in a certain concrete (and complex) example. Its profiling looks strange. I set SCC in all valuable inner loops in the modules Main.hs and LemmaSearch.hs. It shows --------------------------------------------- LemSearchList +RTS -p -M200m -RTS total time = 112.00 secs (2240 ticks @ 50 ms) total alloc = 3,813,365,740 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc CAF Main 95.5 96.1 splitDisjunctScheme LemmaSearch 2.5 2.2 addEquationsWithReduction LemmaSearch 1.3 1.4 --------------------------------------------- My idea was that some of the loops inside LemmaSearch must take almost all time. Instead, it shows that some CAF (anonymous, to me) in Main takes almost everything, and among places which I marked with SCC, the two are shown as 2.5% and 1.4%, and all the rest shown as zero: --------------------------------------------------- MAIN MAIN \ 1 0 0.0 0.0 100.0 100.0 CAF Main 2 80 57 96.0 96.1 99.9 99.9 ... --------------------------------------------------- The whole user project is build under -prof ("auto-all" skipped). The test Main.hs is built also under -prof. SCC are set only inside the functions Main.main and LemmaSearch.searchLemmataInInitial. What may consitute this strange CAF cost of 96% ? Kirsten Chevalier <catamorphism(a)gmail.com> wrote > I didn't look at your code all that carefully, but did you build the > GHC libraries with "-prof -auto-all"? (Not just "-prof".) If you don't > build the libraries with "-auto-all", then cost centres won't get > inserted for library functions, and if it's really a standard library > function that's taking all of that time, the profiling report won't > indicate that. I made ghc-6.6 from the official source in a standard way: ./configure ...; make; make install Does this presume that this also generates the .p.o GHC library versions for -prof -auto-all ? Generally, I do not guess, so far, what is happening. Regards, ----------------- Serge Mechveliani mechvel(a)botik.ru

2 2