- Glasgow-haskell-users

ghc's trac is wedged
by Gregory Wright 13 Mar '08

13 Mar '08

Hi, This morning (13 March 2008) the ghc trac wedged reporting Trac detected an internal error: with the python traceback Traceback (most recent call last): File "/var/lib/python-support/python2.4/trac/web/main.py", line 387, in dispatch_request dispatcher.dispatch(req) File "/var/lib/python-support/python2.4/trac/web/main.py", line 237, in dispatch resp = chosen_handler.process_request(req) File "/var/lib/python-support/python2.4/trac/web/auth.py", line 100, in process_request self._do_login(req) File "/var/lib/python-support/python2.4/trac/web/auth.py", line 139, in _do_login "VALUES (%s, %s, %s, %s)", (cookie, remote_user, File "/var/lib/python-support/python2.4/trac/db/util.py", line 50, in execute return self.cursor.execute(sql_escape_percent(sql), args) File "/usr/lib/python2.4/site-packages/sqlite/main.py", line 237, in execute self.con._begin() File "/usr/lib/python2.4/site-packages/sqlite/main.py", line 503, in _begin self.db.execute("BEGIN") OperationalError: database is locked Please let me know if there is a more direct way to report failures such as this one, instead of posting to the list. Best Wishes, Greg

3 2

Understanding the undefine flags passed to gcc when linking
by Bruce, Joseph R (Joe) 13 Mar '08

13 Mar '08

Hi, When I run 'ghc -v ...', the linking is done via gcc->ld with a large list of -u flags passed in. I'm hoping to find a way to link my object files without those flags, but first I need to understand what they are doing. Can someone explain it to me? Or point me to documentation that explains it? My ultimate goal is to build a static Haskell library and make it available to c programmers ignorant of Haskell. The undefines described above are a major obstacle. Does anyone know a way around them? Thanks, Joe Bruce Phone: 509.372.6198 Pacific Northwest National Laboratory 902 Battelle Blvd. Richland, WA

2 3

swap (x, y)
by Serge D. Mechveliani 11 Mar '08

11 Mar '08

I define and use swap (x, y) = (y, x) because do not find such in the standard library. Please, can people point at it, in the standard library, or at least in GHC? Thank you in advance for your help. ----------------- Serge Mechveliani mechvel(a)botik.ru

3 2

Release plans
by Ian Lynagh 10 Mar '08

10 Mar '08

Hi all, Here are our plans for the next couple of GHC releases. First, we intend to release the next version of GHC from the current stable branch, 6.8.3, around the end of May 2008. This will probably be the last release from this branch. We currently have 90 bugs in either the "6.8.3" or "6.8 branch" milestone, but we do not expect that we will have time to fix them all! So please take a few minutes to take a look through the list, and if there are any that are particularly important to you please: * add a comment to the bug report saying why it is important to you. It is not necessary to also send us a mail, as we get the comments e-mailed to us automatically. * add yourself to the CC list for the bug (we use this to get a count of the number of people interested in a bug). This will help us to make a release that fixes as many problems, for as many people, as possible. The list is here: http://hackage.haskell.org/trac/ghc/query?status=new&status=assigned&status… After that, around ICFP (late September 2008) we plan to make the first release, 6.10.1, from the next stable branch, 6.10. There will be more information on what exciting changes this will bring closer to the time. Thanks Ian, on behalf of the GHC team

3 4

monomorphic or not?
by John Meacham 06 Mar '08

06 Mar '08

http://www.cse.unsw.edu.au/~dons/code/nobench/real/compress/compress.hs if you notice this program has the line > compress = map toEnum . codes_to_ascii . encode It seems to me this should run afoul of the monomorphism restriction due to the unknown ambiguous type in Enum, but ghc 6.8.2 happily accepts it. Jhc thinks it is illegal according to my reading of the specification. Any ideas about what is going on here? John -- John Meacham - ⑆repetae.net⑆john⑈

2 4

Re: STM and fairness
by Josef Svenningsson 05 Mar '08

05 Mar '08

Tim, Simon, Thanks for your detailed descriptions. Much of my understanding was confirmed. I'll see if I can send you a patch with my suggested fix as soon as my teaching is over. Thanks, Josef On Mon, Mar 3, 2008 at 2:03 PM, Tim Harris (RESEARCH) <tharris(a)microsoft.com> wrote: > Hi, > > At the moment we don't make any particular effort to make threads runnable in some specific order when they are unblocked. The current implementation is simply what was easiest to write. > > If I remember rightly threads blocked on TVars will initially be "half-woken", putting them on the same run-queue as their waker and leaving the STM data structures intact. When scheduled they will check whether or not the TVars' contents differ from the values that caused them to block: if the values are unchanged then a thread can block again without needing to build up wait queue structures. In Simon's example of 100 threads blocked on a single-cell TVar buffer, this would mean 99 of them are validated and block again without needing to re-execute the rest of the transaction containing the TVar access. This will probably happen within a single OS thread so these are lightweight thread switches within the GHC run time rather than 99 OS thread switches. > > At some point it might be nice to look at using run-time feedback about how individual TVars are used. I suspect that, looking at it dynamically, there are a few simple policies that would apply to most TVars (wake-all / wake-one) with the caveat that anything other than "wake-all" must eventually fall back to "wake-all" to preserve the intended semantics for "retry". > > NB -- when thinking about a shared buffer built over TVars there's also the possibility that a non-blocked thread will consume the resource ahead of a blocked thread that has been woken. As with programming with locks/condition-variables, avoiding this case would need an explicit queue of consumers to be maintained by the application (and symmetrically for producers). > > In any case, running threads in something approximating the same order they blocked sounds sensible to me. The lists of threads blocked on a TVar are doubly-linked (right?) so wouldn't need to be explicitly reversed. > > Tim > > > > > > > > > -----Original Message----- > From: Simon Peyton-Jones > Sent: 29 February 2008 20:06 > To: Josef Svenningsson; glasgow-haskell-users(a)haskell.org > Cc: Tim Harris (RESEARCH) > Subject: RE: STM and fairness > > | I'd like to know a bit about the STM implementation in GHC, > | specifically about how it tries to achieve fairness. I've been reading > | "Composable Memory Transactions" but it does not contain that much > | details on this specific matter. What I want to know boils down to > | this: what order are processes run which have been woken up from a > | call to retry? > > Tim is the one who implemented this stuff, so I'm ccing him. > > If threads queue up on a single MVar, it's obvious how to achieve fairness of a sort. Furthremore, if 100 threads are blocked on one MVar, the scheduler can wake up exactly one when the MVar is filled. With STM it's much less obvious. > > First, a thread may block on a whole bunch of TVars; if any of them are changed, the thread should re-run. So there is no single list of threads to reverse or not reverse. > > Second, if 100 threads are blocked on a TVar, t, waking up just one of them may not suffice -- it may read some more TVars and then retry again, re-blocking itself on t (plus some more). The only simple thing to do is to wake all of them up. In common situations (e.g. a buffer), we may wake up all 100 threads, only for 99 of them to lose the race and block again. > > This arises from the fact that transactions do a wonderful thing, by letting you perform multiple operations atomically -- but that makes it harder to optimize. > > > All that said, you may well be right that one could do a better job of scheduling. For example, even though there may be lots of threads blocked on a TVar, and all must be made runnable, they could perhaps be run in the same order that they blocked, so the longest-blocked got to run first. I don't think we try to do that, but Tim would know. > > By all means suggest a patch! > > Simon >

1 0

Assembly decoding help?
by Justin Bailey 05 Mar '08

05 Mar '08

I'm trying to get a feel for the assembly output by GHC on my platform. Below is a module containing one function and the associated assembly. I've put in comments what I think is going on, but I'd appreciate it if anyone could give me some pointers. I'd really like to know three things: * Why does _Add_unsafeShiftR_info check if (%esi) is 3? * What's going on in _s86_info? * At the end of _s87_info, 8 is added to %ebp and then jumped to. Is that a jump to the I# constructor and, if so, how did it's address get to that offset from %ebp? Thanks in advance for any assistance! Justin --- cut here ---- # Compiled with # # ghc -c Add.hs -fext-core -keep-s-files -fasm -O2 -ddump-to-file -ddump-stg -ddump-cmm # # Platform: Windows XP. # Processor Pentium 4. # GHC Version: 6.8.2. # # > {-# OPTIONS_GHC -fglasgow-exts -fbang-patterns #-} # > module Add (unsafeShiftR) # # > where # # > import Data.Bits # > import GHC.Base (uncheckedShiftRL#, Int(..), word2Int#, int2Word#) # # > I# a `unsafeShiftR` I# b = I# (word2Int# (int2Word# a `uncheckedShiftRL#` b)) # .data .align 4 .globl _Add_unsafeShiftR_closure _Add_unsafeShiftR_closure: .long _Add_unsafeShiftR_info # Specifies entry point for unsafeShiftR? .text .align 4,0x90 .long 33 .long 34 _s87_info: addl $8,%edi cmpl 92(%ebx),%edi # Stack check? ja .Lc8n movl 4(%ebp),%eax # Get value to be shifted movl 3(%esi),%ecx # Get shift amount shrl %cl,%eax # Shift value movl $_base_GHCziBase_Izh_con_info,-4(%edi) # Get ready to call I#? movl %eax,(%edi) # Constructor value leal -3(%edi),%esi # Address to what in I#? addl $8,%ebp # Make room on stack for next caller? jmp *(%ebp) # Go to constructor? Tail call? .Lc8n: movl $8,112(%ebx) jmp *-8(%ebx) # Error routine if stack overflows? .text .align 4,0x90 .long 1 .long 34 _s86_info: movl 4(%ebp),%eax # Testing what here? movl 3(%esi),%ecx movl %ecx,4(%ebp) movl %eax,%esi movl $_s87_info,(%ebp) testl $3,%esi jne _s87_info jmp *(%esi) .text .align 4,0x90 .long 131084 .long 0 .long 15 .globl _Add_unsafeShiftR_info _Add_unsafeShiftR_info: movl (%ebp),%esi movl $_s86_info,(%ebp) testl $3,%esi # Looking at StgRetInfoTable here? jne _s86_info # Enter body of unsafeShiftR? jmp *(%esi) .data .align 4 __module_registered: .long 0 .text .align 4,0x90 .globl ___stginit_Add_ ___stginit_Add_: cmpl $0,__module_registered jne .Lc8E .Lc8F: movl $1,__module_registered addl $-4,%ebp movl $___stginit_base_GHCziBase_,(%ebp) addl $-4,%ebp movl $___stginit_base_Prelude_,(%ebp) addl $-4,%ebp movl $___stginit_base_DataziBits_,(%ebp) .Lc8E: addl $4,%ebp jmp *-4(%ebp) .text .align 4,0x90 .globl ___stginit_Add ___stginit_Add: jmp ___stginit_Add_ .ident "GHC 6.8.2"

4 3

static constants -- ideas?
by Jason Dusek 03 Mar '08

03 Mar '08

I have an awkward programming problem -- I need to take a dictionary, parse it, build a bunch of intermediate lists and then make maps and tries out of the list. A "programming problem" because it's taken me a fair amount of effort to pull together the parser and list generator -- and "awkward" because a 69000 item list, [(String, [(String, String)])], does not compile under GHC (stack overflow). (It's not likely to compile under anything else, either!) Members of #haskell have urged me to load the offending material from a file; indeed, it only takes ten seconds to parse the dictionary and build the lists, sort them and dump them back out again -- but it offends my sensibilities. I don't want to wait ten seconds to load my dictionary every time. I could use the FFI, then I can make the trie and lists all in C. That'd work great. My list likely uses too much RAM now, anyways. I'm considering one other option though -- I wonder if I can build large constants in GHC Core? If anybody has tried it -- or found some other way to make big huge constants in Haskell -- I would sure like to know about it. On another note, I am extremely curious about the difference between statically compiling a list and building it at runtime. I find it hard to wrap my head around the fact that I can build the list at runtime in a short time, but can not compile it without eating all of my machine's RAM. Is it due to laziness, maybe? Well, no -- because I subject the whole list to a sort. It's not just streaming records in from one IO handle and out another. -- _jsn

6 20

GHC code generation micro-optimisation patch
by Remi Turk 03 Mar '08

03 Mar '08

Hi, during the past semester I followed a seminar on the "Efficient implementation of functional languages" by Jeroen Fokker at the University Utrecht. During that course we worked on a feedback directed GHC optimisation, but that got me interested in another possible GHC backend micro-optimisation: The short story is this: An 8 line patch to GHC, tested with ghc 6.8.2 on nofib, ignoring all results with a < 0.5s runtime, yields an average runtime and compile time improvement of about 0.6%. The worst nofib slowdown is 5%, and the best speedup 8% Whether this is acceptable/enough for inclusion, is of course not up to me. The long story is that in compiler/codeGen/CgUtils.hs:mk_switch, an extra case is added to detect and treat specially the case analysis of 2 constructor datatypes.[1] Previously, case analysis of 2 constructor data types looked as follows in C--: _tmp = R1 & 3; if (_tmp >= 2) goto snd_con_lbl; With this patch, it generates the following: if (R1 & 2 != 0) goto snd_con_lbl; At least on x86 machines, the resulting assembly is more interesting. The original: movl %esi,%eax andl $3,%eax cmpl $2,%eax jae .snd_con_lbl After the patch: testl $2,%esi jne .snd_con_lbl The following table contains a summary of the nofib results: Machine Athlon32* Athlon64* Pentium4 Pentium4-dual PentiumD --------------------------------------------------------------------------------------- Vendor AMD AMD Intel Intel Intel Word size 32 64 32** 32** 32** OS Linux Linux Linux Linux Linux # CPU's 1 2 1 2 2 Mhz 950 2600 2800 2800 3000 L1 code/uops (Kb) 64 64 12 12 12 L1 data (Kb) 64 64 8 8 16 L2 (Kb) 256 1024 512 512 2048 -1 s.d. runtime (%) -1.4 -1.2 -2.4 -2.2 -5.1 +1 s.d. runtime (%) +1.1 +0.4 +1.5 +2.1 +1.3 Avg runtime (%) -0.2 -0.4 -0.4 -0.1 -1.9 Worst runtime (%) +2.5 +1.0 +3.1 +2.5 +5.0 Worst program cacheprof power simple wheel-sieve-1 integrate Best runtime (%) -5.1 -2.9 -5.0 -5.5 -8.1 Best program parstof hidden para life cryptarithm1 -1 s.d. mutator (%) -1.5 -1.6 -3.0 -3.0 -4.8 +1 s.d. mutator (%) +1.1 +0.8 +1.5 +2.2 +1.8 Avg mutator (%) -0.2 -0.4 -0.8 -0.5 -1.6 Avg bin size (%) -0.1 -0.2 -0.1 -0.1 -0.1 Avg mod size (%) -0.3 -0.5 -0.3 -0.3 -0.3 Avg comp time (%) -0.6 -0.7 -1.1 -0.6 -0.2 --------------------------------------------------------------------------------------- Cachegrind results -1 s.d. runtime (%) -2.0 -2.4 -3.2 -3.8 -3.3 +1 s.d. runtime (%) +0.5 +0.8 +1.2 +1.7 +0.6 Avg runtime (%) -0.7 -0.8 -1.0 -1.1 -1.3 -1 s.d. instr. (%) -4.2 -4.1 -4.3 -4.4 -4.4 +1 s.d. instr. (%) -0.6 -0.5 -0.6 -0.7 -0.7 Avg instr (%) -2.4 -2.3 -2.5 -2.5 -2.5 -1 s.d. cache misses (%) -0.6 -1.8 -0.4 -2.0 -2.8 +1 s.d. cache misses (%) +0.7 +2.2*** +0.7 +0.9 +1.1 Avg cache misses (%) +0.0 +0.2 +0.1 -0.6 -0.9 Avg comp time (%) -0.6 +0.3 -0.7 -0.4 -0.1 * On all Athlon results, but not on those of the Pentiums, nofib-analyse gave lots of "spurious result" warnings. On the Athlon32, nofib even failed with "output does not match" errors, which I could not verify when running diff on the output manually. I "fixed" the first problem by ignoring it and the second one by changing runstdtest to pretend the actual output always matches the expected output. ** CPU may actually be 64bits, but all software (including kernel) is 32bits *** cacheprof here has a whopping 21.0% more cache misses. The second biggest increase is 1.0% The attached patch is against 6.8.2, but currently applies without problem against the HEAD. The full nofib results can be found at http://www.students.cs.uu.nl/~rturk/fast2case-nofib-results/ The normal runs were done with NoFibRuns = 5, and for the cachegrind runs it was set to 2. On most machines I ran nofib multiple times and, both for normal and for "fast2case", took the fastest run. Thanks to Jeroen Fokker for giving the seminar that made me think of this in the first place, to Mark Stobbe and Eelco Lempsink for being great guys to work with during the seminar, and to Alexey Rodriguez for helping me keep my sanity in the midst of weird cache- and pipeline effects. And finally to the University Utrecht and Chris Regenboog for enabling me to run nofib on more computers than only my own poor old 950Mhz machine. Groeten, Remi [1] Technically, it will work for 4 constructor datatypes on 64 bit architectures too, but who cares.

2 1

STM and fairness
by Josef Svenningsson 29 Feb '08

29 Feb '08

Hi, I'd like to know a bit about the STM implementation in GHC, specifically about how it tries to achieve fairness. I've been reading "Composable Memory Transactions" but it does not contain that much details on this specific matter. What I want to know boils down to this: what order are processes run which have been woken up from a call to retry? When programming with condition variables the standard behaviour is that the process which has waited the longest is the first one to get to run. But that doesn't seem to be the behaviour here. Consider the following program: \begin{code} module STMFair where import Control.Concurrent import Control.Concurrent.STM test n = do v <- newTVarIO 0 mapM_ (\n -> forkIO (process n v) >> threadDelay delay) [1..n] atomically (writeTVar v 1) threadDelay delay delay = 500000 process id var = do putStrLn ("Process " ++ show id ++ " started") atomically $ do v <- readTVar var if v == 0 then retry else return () putStrLn ("Process " ++ show id ++ " finished") \end{code} When I run 'test 2' I expect it to print: Process 1 started Process 2 started Process 1 finished Process 2 finished This would correspond to the oldest process being executed first. But that is not what happens instead I get this (ghci 6.8.2, Ubuntu Linux): Process 1 started Process 2 started Process 2 finished Process 1 finished This is certainly not the behaviour I would want. I discovered this behaviour when implementing the dining philosophers using STM and there one of the philosophers gets starved. Except, that he's not quite starved. When I run the simulation long enough he will eventually be able to eat but then for a long time there will be some other philosopher that is starved. I find this behaviour very mysterious and it would be nice to have some light shed on it. Apart from this mysterious behaviour it seems quite easy to improve the fairness of the implementation. From my examples above it seems that the wait queues for a transactional variable do contain the processes in the order they call retry (try running 'test n' for some large n). It just seems that they are given to the scheduler in the wrong order, so all that needs to be done is to reverse the list. Am I right? Thanks for reading, Josef

3 3