- Glasgow-haskell-users

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

Re: H98 Text IO
by Ben Franksen 28 Feb '08

28 Feb '08

David Leuschner wrote: > If I write simple program just printing a non-ASCII string to the terminal > or to a file I'd expect that I can read it on the screen or using my > favorite text editor without having change anything -- neither in my > terminal nor in my program. When I run the program on my platform don't > mind if somebody else might get differently encoded output from the same > program as long as I get what I expect. I think this is sensible advice. Furthermore I want to be able to chose an encoding (e.g. by setting my environment), even for file/socket IO, instead of being locked into utf-8. Thus, for Linux, I'd say always use the environment encoding. More advanced stuff like sending in a certain encoding e.g. over network or to a foreign file system should not use H98 IO but newer libraries that allow to set the encoding programmatically, or encode yourself and read/write Word8. Cheers Ben

1 0

Exports of STM constructors.
by Sterling Clover 27 Feb '08

27 Feb '08

I was recently bitten by the urge to hack around with STM, and discovered to my dismay that there's no way to get at the primitive constructors for TVar and STM, both of which are defined in GHC.Conc. Given that, when we so desire, we can get at the primitives to break IO into pieces, manually unbox integers and such, and that the primitives for working with MVars are similarly exposed through appropriate imports, it would be really nice (or, well, at least fun) to be able to do the same for STM. --S

1 0

Re: H98 Text IO
by Matthew Bentham 27 Feb '08

27 Feb '08

----- Original Message ---- > From: Johan Tibell <johan.tibell(a)gmail.com> > To: Duncan Coutts <duncan.coutts(a)worc.ox.ac.uk> > Cc: Haskell Libraries <libraries(a)haskell.org>; GHC-users list <Glasgow-haskell-users(a)haskell.org>; Simon Marlow <simonmarhaskell(a)gmail.com> > Sent: Wednesday, February 27, 2008 9:25:39 AM > Subject: Re: H98 Text IO > > On Wed, Feb 27, 2008 at 1:06 AM, Duncan Coutts > wrote: > > As a data point, Java and python use "always locale" as default if you > > don't specify an encoding when opening a text stream. > > > > I think personally I'm coming round to the "always locale" point of > > view. We already have no cross-platform consistency for text files > > because of the lf vs cr/lf issue and we have no cross-implementation > > consistency. > > I think following Java and Python in this matter is a good idea and > leads to fewer surprises for developers. If you want files created on > one machine to work on another you have to be explicit about encoding. I'm a newcomer to haskell so I don't want to goof by offering any naive opinions, but I would like to inform the discussion by linking to a couple of useful things. This blog post on encodings in python (mostly related to the behaviour of the standard input/output streams): http://drj11.wordpress.com/2007/05/14/python-how-is-sysstdoutencoding-chose… Particularly: "It’s not unreasonable to have a program that wants to encode its outputin a particular encoding. The example I gave earlier still seemsreasonable to be, a program that takes input in one encoding andrecodes to a different encoding on its output, with both the input andoutput encoding specified on the command line. Clearly such a programshould be able to use stdin and stdout so that it can form part of apipe. So how in Python do I change sys.stdout to use a particular encoding? It’s a right pain." And the reference to the POSIX documentation related to locale, mentioned earlier in this thread: http://www.opengroup.org/onlinepubs/009695399/basedefs/xbd_chap07.html The problem that I see is generally that because stdin/out/err are _already_open_ by the time they reach the haskell program, it is pretty hard for the developer "to be explicit about encoding" if no library is provided to effectively change the encoding used by an already-open stream.

2 1

Re: H98 Text IO
by Chris Kuklewicz 27 Feb '08

27 Feb '08

Small correction: I think "./prog in vs ./prog < in " and "utf8" should be "ok". (and I thought this was switched to Glasgow-haskell-users(a)haskell.org) David Leuschner wrote: >> Let me try and summarise: > > Thanks for the great summary! And thanks to Emacs' table mode here're the > results displayed as a table: > > +--------------------------------+-----+--------+------+-------+-------+ > | | now | locale | utf8 | mix-A | mix-B | > +--------------------------------+-----+--------+------+-------+-------+ > | putStrLn "..." | - | ok | - | ok | ok | > +--------------------------------+-----+--------+------+-------+-------+ > | ./prog vs ./prog | cat | ok | ok | ok | - | ok | > +--------------------------------+-----+--------+------+-------+-------+ > | ./prog in vs ./prog < in | - | ok | - | ok | - | > +--------------------------------+-----+--------+------+-------+-------+ > | ./prog vs ./prog | hexdump -C | ok | ok | ok | - | ok | > +--------------------------------+-----+--------+------+-------+-------+ > > > The mixtures are good ideas but can give inconsistent and suriprising > results (especially when debugging encoding issues). And if our CEO would > have known that ... putStrLn <his-name> ... doesn't work he'd have > probably ruled out Haskell right from the start. Even "utf8" gives > surprising results: I'd be very surprised if my Mac-written Haskell > program outputs junk on Windows or Linux even if the byte sequence is > exactly the same UTF-8 text. > > Personally I think consistency on a single platform is more important than > trying to achieve cross-platform consistency which involves a lot more > than just encoding. If you've reached that point with your program you're > probably anyway using "advanced functions" to exactly specify what will be > output. Following "the principle of least surprise" is also a good idea. > > Cheers, > > David > > > > > ------------------------------------------------------------------------ > > _______________________________________________ > Libraries mailing list > Libraries(a)haskell.org > http://www.haskell.org/mailman/listinfo/libraries

2 1

H98 Text IO
by Duncan Coutts 27 Feb '08

27 Feb '08

>From the H98 report: All I/O functions defined here are character oriented. [...] These functions cannot be used portably for binary I/O. In the following, recall that String is a synonym for [Char] (Section 6.1.2). So ordinary text Handles are for text, not binary. Char is of course a Unicode code point. The crucial question of course is what encoding of text to use. For the H98 IO functions we cannot set it as a parameter, we have to pick a sensible default. Currently different implementations disagree on that default. Hugs has for some time used the current locale on posix systems (and I'm guessing the current code page on windows). GHC has always used the Latin-1 encoding. These days, most operating systems use a locale/codepage encoding that covers full the Unicode range. So on hugs we get the benefit of that but on GHC we do not. This is endlessly surprising for beginners. They do putStrLn "αβγδεζηθικλ" and it comes out on their terminal as junk. It also causes problems for serious programs, see for example the recent hand-wringing on cabal-devel. So here is a concrete proposal: * Haskell98 file IO should always use UTF-8. * Haskell98 IO to terminals should use the current locale encoding. The main controversial point I think is whether to always use UTF-8 or always use the current locale or some split as I've suggested. C chose to always go with the current locale. Some people think that was a mistake because the interpretation changes from user to user. For terminals it is more clear cut that the locale is the right choice because that is what the terminal is capable of displaying. Using anything else will produce junk. We can detect if a handle is a terminal when we open it using hIsTerminalDevice. This should be done automatically (and ghc would ghc get it for free because it already does that check to determine default buffering modes). Sockets and pipes would be treated the same as files when opened in the default text mode. The only special case is terminals. The major problem is with code that assumes GHC's Handles are essentially Word8 and layer their own UTF8 or other decoding over the top. The utf8-string package has this problem for example. Such code should be using openBinaryFile because they are reading/writing binary data, not String text. Note that many programs that really need to work with binary file already use openBinaryFile, those that do not are already broken on Windows which does cr/lf conversion on text files which breaks many binary formats (though not utf8). So we have decide which is more painful, keeping a limited text IO system in GHC or breaking some existing programs which assume GHC's current behaviour. Opinions? Please can we keep this discussion to the interpretation of the H98 IO functions and not get into the separate discussion of how we could extend or redesign the whole IO system. This is a questions of what are the right defaults. Duncan

7 15