March 2008 - Glasgow-haskell-users

Making rule application less fragile
by Johan Tibell 14 Mar '08

14 Mar '08

Hi, I'm trying (for the first time ever) to use RULES pragmas to achieve some nice speedups in my bytestring parsing library. The relevant code in my library's module is: -- The module imports Control.Applicative which containes 'many' and 'some'. -- | The parser @satisfy p@ succeeds for any byte for which the -- supplied function @p@ returns 'True'. Returns the byte that is -- actually parsed. satisfy :: (Word8 -> Bool) -> Parser Word8 satisfy p = Parser $ \s@(S bs pos eof) succ fail -> case S.uncons bs of Just (b, bs') -> if p b then succ b (S bs' (pos + 1) eof) else fail s Nothing -> if eof then fail s else IPartial $ \x -> case x of Just bs' -> retry (S bs' pos eof) Nothing -> fail (S bs pos True) where retry s' = unParser (satisfy p) s' succ fail -- | @byte b@ parses a single byte @b@. Returns the parsed byte -- (i.e. @b@). byte :: Word8 -> Parser Word8 byte b = satisfy (== b) -- --------------------------------------------------------------------- -- Rewrite rules satisfyMany :: (Word8 -> Bool) -> Parser S.ByteString satisfyMany p = undefined -- More efficient implementation goes here. satisfySome :: (Word8 -> Bool) -> Parser S.ByteString satisfySome p = undefined -- More efficient implementation goes here. {-# RULES "fmap/pack/many/satisfy" forall p. fmap S.pack (many (satisfy p)) = satisfyMany p "fmap/pack/some/satisfy" forall p. fmap S.pack (some (satisfy p)) = satisfySome p #-} In another module where I use the library I have this code: pHeaders :: Parser [(S.ByteString, S.ByteString)] pHeaders = many header where header = liftA2 (,) fieldName (byte (c2w ':') *> spaces *> contents) fieldName = liftA2 (S.cons) letter fieldChars contents = liftA2 (S.append) (fmap S.pack $ some notEOL <* crlf) (continuation <|> pure S.empty) continuation = liftA2 (S.cons) ((c2w ' ') <$ some (oneOf (map c2w " \t"))) contents -- It's important that all three of these definitions are kept on the -- top level to have RULES fire correctly. fieldChars = fmap S.pack $ many fieldChar -- fieldChar = letter <|> digit <|> oneOf (map c2w "-_") fieldChar = satisfy isFieldChar where isFieldChar b = (isDigit $ chr $ fromIntegral b) || (isAlpha $ chr $ fromIntegral b) || (b `elem` map c2w "-_") I want the fieldChars use of 'fmap S.pack $ many fieldChar' to trigger my rewrite rule "fmap/pack/many/satisfy" which it does in this case. The trouble is that the rule only triggers when I make at least fieldChars and fieldChar top-level definition and isFieldChar either a named local definition in fieldChar or a top-level definition. If I turn the predicate (isFieldChar) into to an anonymous lambda function it doesn't trigger, if I make either fieldChars or fieldChars a local defintion (in a where clause) of pHeaders it doesn't trigger. If I make fieldChar a local definition in fieldChars it doesn't trigger, etc. It would be great if there was a way to make this a bit less fragile and have the rule trigger more often as it is potentially a huge performance win. I understand it's hard to guarantee that the rule always triggers but now it triggers in rare cases. -- Johan

3 5

Re: ANN: ghc 6.8.2 from MacPorts
by Christian Maeder 14 Mar '08

14 Mar '08

Hi Greg, I can't test it myself because I don't have root access to our machines. Maybe someone else can? (Meanwhile I'll try to make a binary-dist that includes the extra-libs.) Cheers Christian Gregory Wright wrote: > > Hi Christian, > > I built a new bootstrapping compiler on Tiger/ppc, incorporating > Thorkil's .text section > patch. I've modified the portfile, but since I don't have a Leopard/ppc > machine I can't > try it. Could you give it a go? > > Do > > $ sudo port selfupdate > $ sudo port clean --all ghc > $ sudo port -dv install ghc > inst.log 2>&1 > > You might want to check after the selfupdate that you have revision 2 of > the ghc portfile. > It may take a few hours for the server to index the port and make it > available by rsync. > > If it fails, you can compress the log and send it to me. The "-dv" > flags dump all of the > MacPorts and build information. > > There may still be a stupid bug or two since I can't test it myself. > > Thanks, > Greg >

1 0

setlocale
by Tristan Allwood 13 Mar '08

13 Mar '08

Hi, I've been playing around with hs-curses and utf8, and have discovered that I need to use an ffi call at the top of my main to setlocale(LC_ALL, "") in order to get the hscurses bindings to display utf8-encoded strings correctly. If I understand correctly, the fact that I need to do this means that the ghc rts is either not setting the default locale, or is forcing it to be a c-style one. With that as my context I'm just wondering: a) if this is a known issue b) if there's a known work-around other than rolling your own ffi wrapped call (a library function that I'm not aware of) c) any side effects this might have elsewhere d) if I'm being stupid and could get this to work by just using env vars Regards, Tristan Allwood 21:23:39 - tora@colorado:~ >locale LANG=en_GB.UTF-8 LC_CTYPE="en_GB.UTF-8" LC_NUMERIC="en_GB.UTF-8" LC_TIME="en_GB.UTF-8" LC_COLLATE="en_GB.UTF-8" LC_MONETARY="en_GB.UTF-8" LC_MESSAGES="en_GB.UTF-8" LC_PAPER="en_GB.UTF-8" LC_NAME="en_GB.UTF-8" LC_ADDRESS="en_GB.UTF-8" LC_TELEPHONE="en_GB.UTF-8" LC_MEASUREMENT="en_GB.UTF-8" LC_IDENTIFICATION="en_GB.UTF-8" LC_ALL= >ghc -v Glasgow Haskell Compiler, Version 6.8.2, for Haskell 98, stage 2 booted by GHC version 6.8.1 >uname -a Linux colorado 2.6.24-1-amd64 #1 SMP Mon Feb 11 13:47:43 UTC 2008 x86_64 GNU/Linux -- Tristan Allwood PhD Student Department of Computing Imperial College London

4 5

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 04 Mar '08

04 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