January 2006 - Haskell-Cafe

RE: [Haskell-cafe] Shootout favoring imperative code
by Scherrer, Chad 04 Jan '06

04 Jan '06

> --- Sebastian Sylvan <sebastian.sylvan(a)gmail.com> > wrote: > Some of the problems seem to be heavily geared towards an > imperative *implementation*, meaning that a Haskell version > is hardly idiomatic Haskell (and as such I , and I suspect > otehrs, really have no inclination to work on it). This may be correct, but it still doesn't address the question. Why does Clean fare so much better? Clean is purely functional, right? Chad Scherrer Computational Mathematics Group Pacific Northwest National Laboratory "Time flies like an arrow; fruit flies like a banana." -- Groucho Marx

2 1

RE: [Haskell-cafe] Re: Joels Time Leak
by Simon Marlow 04 Jan '06

04 Jan '06

On 03 January 2006 15:37, Sebastian Sylvan wrote: > On 1/3/06, Simon Marlow <simonmar(a)haskell.org> wrote: >> Tomasz Zielonka wrote: >>> On Thu, Dec 29, 2005 at 01:20:41PM +0000, Joel Reymont wrote: >>> >>>> Why does it take a fraction of a second for 1 thread to unpickle >>>> and several seconds per thread for several threads to do it at the >>>> same time? I think this is where the mistery lies. >>> >>> >>> Have you considered any of this: >>> >>> - too big memory pressure: more memory means more frequent and more >>> expensive GCs, 1000 threads using so much memory means bad cache >>> performance - a deficiency of GHC's thread scheduler - giving too >>> much time one thread steals it from others (Simons, don't get >>> angry at me - I am probably wrong here ;-) >> >> I don't think there's anything really strange going on here. >> >> The default context switch interval in GHC is 0.02 seconds, measured >> in CPU time by default. GHC's scheduler is stricly round-robin, so >> therefore with 100 threads in the system it can be 2 seconds between >> a thread being descheduled and scheduled again. > > According to this: > http://www.haskell.org/ghc/docs/latest/html/users_guide/sec-using-parallel.… > > The minimum time between context switches is 20 milliseconds. > > Is there any good reason why 0.02 seconds is the best that you can get > here? Couldn't GHC's internal timer tick at a _much_ faster rate (like > 50-100µs or so)? Sure, there's no reason why we couldn't do this. Of course, even idle Haskell processes will be ticking away in the background, so there's a reason not to make the interval too short. What do you think is reasonable? > Apart from meaning big trouble for applications with a large number of > threads (such as Joels) it'll also make life difficult for any sort of > real-time application. For instance if you want to use HOpenGL to > render a simulation engine and you split it up into tons of concurrent > processes (say one for each dynamic entity in the engine), the 20ms > granularity would make it quite hard to achieve 60 frames per second > in that case... The reason things are the way they are is that a large number of *running* threads is not a workload we've optimised for. In fact, Joel's program is the first one I've seen with a lot of running threads, apart from our testsuite. And I suspect that when Joel uses a better binary I/O implementation a lot of that CPU usage will disappear. Cheers, Simon

5 10

Progress on shootout entries
by Chris Kuklewicz 04 Jan '06

04 Jan '06

Hello, Where there were no entries to the http://shootout.alioth.debian.org/benchmark.php?test=chameneos&lang=all benchmark, there are now two. The one by Josh Goldfoot is already posted, the one Einar Karttunen and I optimized has been submitted and will run faster/smaller. Our code is at http://haskell.org/hawiki/ChameneosEntry Now for improving the fasta benchmark, http://shootout.alioth.debian.org/benchmark.php?test=fasta&lang=all , which currently has a space leak in the Haskell entry. A non-leaking version which has been optimized to run 3.5 times faster is now up at http://haskell.org/hawiki/FastaEntra (ooops..my spelling mistake). It could still be made to run about 3 times faster, if the other languages are any guide. Anyone want to help polish this one? Also, two other existing entries have space leaks, as can be seen at http://shootout.alioth.debian.org/benchmark.php?test=all&lang=ghc&lang2=ghc And finially, the haskel entry for http://shootout.alioth.debian.org/benchmark.php?test=fannkuch&lang=all is currently the *slowest* entry out of 28 languages. It is 813x slower than the c-code, 500x slower than OCaml. Should be easy to make it faster... Cheers, Chris Kuklewicz

9 17

RE: [Haskell-cafe] Re: Haskell Speed
by Simon Marlow 04 Jan '06

04 Jan '06

On 30 December 2005 01:23, Jan-Willem Maessen wrote: > Probably. The minimum table chunk size was rather large. I have > been experimenting (tests are running even as I type) with alternate > implementations of Data.HashTable. So far the winning implementation > is one based on multiplicative hashing and simple table doubling. > This seems to be consistently competitive with / faster than > Data.Map. At this point my inclination is to make the whole suite > available: > > Data.HashTable.Class > Data.HashTable.DataMap > Data.HashTable.Doubling > Data.HashTable.Flat > Data.HashTable.Freeze > Data.HashTable.Modulus > Data.HashTable.Multiplicative > Data.HashTable.Original > Data.HashTable.Test > Data.HashTable > > I've separated out the hashing technique (Modulus, Multiplicative) > from the hash table implementation. Note that a few of the above are > bogus, and this is only a fraction of the implementations tried thus > far. > > I need to get distribution clearance for a bunch of this code from my > employer, and figure out how to package it. The latter may be > tricky, as Data.Hashtable is currently rather intimately tied to a > bunch of rather tricky bits of GHC. I wonder if you could put together a drop-in replacement for Data.HashTable that we can incorporate? There's not much point in us still providing the inefficient version as standard after you've done all this work to figure out how to do it better. Cheers, Simon

2 1

Re: Progress on shootout entries
by Josh Goldfoot 04 Jan '06

04 Jan '06

Keep in mind that the shootout requires that the first 30 permutations printed out by the Fannkuch benchmark to be exactly those given in the "example." Any other order of permutations gets your code labeled "Error" by the shootout administrators. See the discussion here: http://alioth.debian.org/tracker/index.php?func=detail&aid=302527&group_id=… The version of Fannkuch on the site before I got there used a permutation function that did not comply with this requirement. My only contribution was to translate the acceptable algorithm into Haskell. (The inefficient flop stuff and the other errors were not my fault, I swear!) The resulting (slow) code can definitely be sped up, but unfortunately the shootout benchmark favors imperative languages (and impure functional languages, I guess). I suppose we could have two permutation-generating functions: One used only to generate the first 30 required by the benchmark, and another that is actually used to calculate the fannkuch value. It's not clear how the shootout rule-lawyers would look that. It seems to violate the "same way" rule. I was able to significantly speed up the code by replacing the flip function with a function that relies entirely on pattern matching (no splitAts or reverses). It looks ugly, though: mangle list@(1:xs) = list mangle (2:x2:xs) = x2:2:xs mangle (3:x2:x3:xs) = x3:x2:3:xs ... and so on.

4 5

data vs type
by Daniel Carrera 04 Jan '06

04 Jan '06

Hello all, I'm trying to figure out how 'data' and 'type'. I haven't read any documentation because I can't find any. Could someone point me to a document explaining these? I'm happy to RTFM, I just need to know where the FM is :) Cheers, Daniel. -- /\/`) http://oooauthors.org /\/_/ http://opendocumentfellowship.org /\/_/ \/_/ I am not over-weight, I am under-tall. /

3 4

Controlling scheduling in Concurrent Haskell
by Simon Peyton-Jones 04 Jan '06

04 Jan '06

| Given that actually controlling priorities is not an option, adding | blocking like that makes sense. One can make a ring buffer instead of a Concerning priorities and scheduling (which affect both this shootout thread, and perhaps Joel's timeleak program), one can take two approaches 1. Ask more of the runtime system; e.g. add thread priorities 2. Program up a solution The merit of (1) is that you get an "automatic" solution. The problem is that it might not be the right solution for your problem. Whereas (2) will fit your problem, but is less convenient. Even the first paper on Concurrent Haskell discussed (2), in Section 4 "Control over scheduling". http://research.microsoft.com/copyright/accept.asp?path=/users/simonpj/p apers/concurrent-haskell.ps.gz Just to give an example, suppose you have zillions of threads, but you want to ensure that at most 10 of them are running simultaneously else their time slices are too spread out. Just use a quantity semaphore (QSem, discussed in the "Concurrent Haskell" paper). Each thread grabs permission from the semaphore before doing its work, and puts it back when done. How about fairness? As Simon mentioned, MVars *do* have an undocumented fairness property; waiting threads are serviced in first-come-first-served order. You'd have to check the QSem code, but I believe that means that threads will be dealt with first-come-first-served order for the quantity semaphore. We should probably document this property of MVars, and document fairness guarantees of abstractions such as QSem. | If 4 threads block trying to take an MVar, and a 5th thread puts a value | in the MVar, then *exactly one* of the 4 blocked threads is woken up and | scheduled to run. | | If 4 threads retry while in STM (e.g. takeTMVar), and a 5th thread | commits a change to that TMVar, then *all 4 threads* are woken up and | rescheduled. This is what the Apache httpd server folks called the | "thundering herd" problem when many processes are blocked waiting on | socket 80. Yes, that's precisely correct. MVars guarantee a single wake-up, whereas STM does not. Again, this is a property that it'd be good to document. Of course none of this helps if you simply have too much work to do. If you have 100 threads, each with 1s of processing to do, then no amount of fancy scheduling will get this done in less than 100s. But I thought I'd mention the possibility of doing scheduling explicitly. It's often not hard, and has the property that it's more robust to variations in the implementation. Simon

2 1

RE: [Haskell-cafe] Re: Joels Time Leak
by Simon Marlow 04 Jan '06

04 Jan '06

On 03 January 2006 17:32, Chris Kuklewicz wrote: > Thanks for the answer, but I should I written a longer comment. I have > added such a longer comment below: > > Simon Marlow wrote: >> Chris Kuklewicz wrote: >> >>> Another comment: between 1000's of threads and writing a custom >>> continuation based scheduler, what about using a thread pool? Does >>> anyone have a library with a "fork-IO-Pool" command? >> >> >> You don't need a thread pool, because threads are so cheap. Thread >> pools are just a workaround for lack of lightweight concurrency. >> >> Cheers, >> Simon >> > > Since the round-robin scheduler has (0.02 * N) seconds of delay for N > therads, then one could trade off latency between time spent waiting > for the thread pool to start a job and time spend running the job and > getting interrupted. > > In the limit of 1 worker thread, all the latency is waiting to get > run, and there are no interruptions, so the time taken *while > running* is very short. With 10 threads, there can be a delay to > start, and each interruption adds 0.2 seconds to the job's run time > once it has started. > > For a server, the client requests queue up and wait for room in the > thread pool, and the pool is kept small enough that the > round-robin-schedular-delay keeps requests from timing out while being > serviced. Otherwise 1000 client requests would cause 20 seconds of > reschedule penalty for all threads and they could all timeout. With a > thread pool, one can drop threads that have been waiting for too long > instead of running them, so those threads will timeout. But the pool > keeps servicing at least some of the client requests on time. > > All hypothetical to me, of course. I see - you want to use a thread pool as a way of restricting parallelism, so as to control latency. Good idea, it would make a useful library. Cheers, Simon

1 0

RE: [Haskell-cafe] Help with "shootout"
by Simon Marlow 04 Jan '06

04 Jan '06

On 03 January 2006 12:03, Chris Kuklewicz wrote: > STM* is usually slower than IO/MVar. STM has to do the transactional > record keeping and throws away work (i.e. CPU cycles and speed) when > it aborts. The Chameneos benchmark has 4 writers working *very* > quickly, so the contention is high. Taking the MVar acts like a > mutex to serialize access without throwing away work. We found that once you add exception safety to your MVar code, i.e. using withMVar and modifyMVar rather than raw takeMVar/putMVar, then MVar code is comparable in speed to STM. For example, Chan and TChan perform about the same. Of course, for a benchmark, you can forget about the exception safety, as the Ch implementation does (plus it is tweaked in various other ways). > Also, I suspect the following may be true: > > If 4 threads block trying to take an MVar, and a 5th thread puts a > value in the MVar, then *exactly one* of the 4 blocked threads is > woken up and scheduled to run. Yes, that's true. We haven't documented this as a property of MVars, but we don't intend to change this behaviour, so I think we probably should document it. Furthermore, the thread to be woken up is always the first thread to block on the MVar. That is, there's a kind of fairness built into MVars which isn't present in STM and TMVars. > If 4 threads retry while in STM (e.g. takeTMVar), and a 5th thread > commits a change to that TMVar, then *all 4 threads* are woken up and > rescheduled. This is what the Apache httpd server folks called the > "thundering herd" problem when many processes are blocked waiting on > socket 80. > > If 4000 threads were getting woken up when only 1 was needed, then > performance would be poor. Certainly I found 4 writer thread and STM > to be much slower for this shootout problem than the Einar's custom > MVar channel. > > Could someone who knows the STM implementation comment on this? Hope this helps... Simon PJ and I talked about this briefly this morning, and agreed that it might be possible to provide more primitive MVar-like objects in STM to recover single-wakeup and some of the speed that MVars currently have. We haven't worked through the details though. >> This is the CVS code. newTChanIO is exported but undocumented in GHC >> 6.4.1. I'm not sure what purpose it serves. > > I get tired of writing "do tv <- atomically $ newTVar foo" > > I bet this is just shorthand: "do tv <- newTVarIO foo" > > Same for newTChanIO. It's not just shorthand: you can use newTVarIO and friends inside unsafePerformIO, which doesn't always work for the longhand atomically version. Cheers, Simon

1 0

RE: [Haskell] Re: Boxing (Day) Question
by Simon Peyton-Jones 04 Jan '06

04 Jan '06

[Moving to haskell-café] You'd still need several versions of the code for a polymorphic function, one for pointer values, one for 4-byte non-pointers, one for 8-byte non-pointers etc. That's what .net does, I believe, but via runtime code generation. Simon | -----Original Message----- | From: haskell-bounces(a)haskell.org [mailto:haskell-bounces@haskell.org] On Behalf Of Ashley Yakeley | Sent: 29 December 2005 17:56 | To: haskell(a)haskell.org | Subject: [Haskell] Re: Boxing (Day) Question | | In article | <036EAC76E7F5EC4996A3B3C3657D411604105AB8(a)EUR-MSG-21.europe.corp.microso | ft.com>, | "Simon Peyton-Jones" <simonpj(a)microsoft.com> wrote: | | > The .NET CLR lifts the restriction by specialising code, so that it can | > adapt to whether it is moving Int# or Double# values around. In | > Haskell, though, it's not possible to statically generate all the | > instances you need, so you'd need run-time code generation to do this. | > | > It's a real restriction, and sometimes very tiresome, but I'm not | > planning to fix it soon, unless I have a brilliant idea for how to do it | > easily. | | So you don't think having a different kind for each kind of storage | (e.g. #4 for 4-byte values, etc.) would help you here? | | -- | Ashley Yakeley, Seattle WA | | _______________________________________________ | Haskell mailing list | Haskell(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell

2 1