April 2012 - Haskell-Cafe

[ANN] blaze-html-0.5
by Jasper Van der Jeugt 21 Apr '12

21 Apr '12

Hello all, I've just released a new version of blaze-html on Hackage. It has some backward-incompatible changes, so feel free to contact me if you run into any trouble. Summary of changes: - Split into blaze-markup and blaze-html - Easy creation of custom HTML elements - Very simple HTML tree manipulation For more details, see: http://jaspervdj.be/posts/2012-04-21-blaze-html-0.5.html Cheers, Jasper

1 0

Google Summer of Code - Lock-free data structures
by Florian Hartwig 21 Apr '12

21 Apr '12

Hi everyone, I would like to do the GSoC project outlined in http://hackage.haskell.org/trac/summer-of-code/ticket/1608 One of Haskell's great strengths is its support for all kinds of concurrent and parallel programmming, so I think that the Haskell ecosystem would benefit from having a wider range of efficient concurrent data structures. Also, more selfishly, I remember reading the article in CACM last summer and thinking that the whole idea of updating data structures directly using atomic compare-and-swap was really cool, so I would love to have an excuse to play around with it. Some (initial) ideas for lock-free data structures worth implementing: 1. A lock-free priority queue, e.g. using the approach based on skip-lists explained in [2] 2. Stacks, see [1] and [3] 3. Hash tables [4] but if anyone has other suggestions, I would obviously happy to hear them. GSoC stretches over 13 weeks. I would estimate that implementing a data structure, writing tests, benchmarks, documentation etc. should not take more than 3 weeks (it is supposed to be full-time work, after all), which means that I could implement 4 of them in the time available and still have some slack. About me: My name is Florian Hartwig, I'm a fifth year (Master's) student in Computing Science at the University of Glasgow. I've been using Haskell for a bit more than two years now (both for university courses and my recreational programming) and I'm currently using it for my Master's project, so I won't have to spend any time learning the Haskell basics. I don't have any other plans for the summer that might conflict with the project. I'd be thankful for any thoughts, questions and suggestions. Cheers, Florian [1] http://cacm.acm.org/magazines/2011/3/105308-data-structures-in-the-multicor… [2] http://www.sciencedirect.com/science/article/pii/S0743731504002333 [3] http://dl.acm.org/citation.cfm?id=1007944 [4] http://dl.acm.org/citation.cfm?id=564881

10 28

TLS support for haskell-xmpp
by John Goerzen 20 Apr '12

20 Apr '12

Dmitry & others, Attached is a diff implementing TLS support for haskell-xmpp, and correcting a build failure. The support is rough but it seems to work so far. -- John

2 2

Fwd: Now Accepting Applications for Mentoring Organizations for GSoC 2012
by Johan Tibell 20 Apr '12

20 Apr '12

Hi all, Anyone interested in acting as an admin for haskell.org this year? I'm afraid I won't have time. It's not that much work (filling in some information, sending out some emails, making sure things happen in time.) ---------- Forwarded message ---------- From: Carol Smith <carols(a)google.com> Date: Mon, Feb 27, 2012 at 11:47 AM Subject: Now Accepting Applications for Mentoring Organizations for GSoC 2012 To: Google Summer of Code Announce < google-summer-of-code-announce(a)googlegroups.com> Hi all, We're pleased to announce the applications for mentoring organizations for GoogleSummer of Code 2012 are now being accepted [1]. Please go Melange [2] to apply on behalf of your organization. Please note that the application period [3] closes on 9 March at 23:00 UTC. We will not accept any late applications for any reason. [1] - http://google-opensource.blogspot.com/2012/02/mentoring-organization-applic… [2] - http://www.google-melange.com [3] - http://www.google-melange.com/gsoc/events/google/gsoc2012 Cheers, Carol -- You received this message because you are subscribed to the Google Groups "Google Summer of Code Announce" group. To post to this group, send email to google-summer-of-code-announce(a)googlegroups.com. To unsubscribe from this group, send email to google-summer-of-code-announce+unsubscribe(a)googlegroups.com. For more options, visit this group at http://groups.google.com/group/google-summer-of-code-announce?hl=en.

3 7

Profiling with QtHaskell
by Øystein Kolsrud 20 Apr '12

20 Apr '12

Hi! Does anyone know if it is possible to use QtHaskell with profiling turned on? -- Mvh Øystein Kolsrud

3 3

Parallel Haskell Digest 9
by Eric Kow 20 Apr '12

20 Apr '12

Parallel Haskell Digest 9 ========================= Hello Haskellers! The Google Summer of Code is upon us and students have already submitted their proposals. There are a couple potential projects on concurrent data structures, which we'll have a look at below. We will also be continuing our tour of Haskell concurrency abstractions with our word month, *transaction*. This digest is brought to you by the Parallel GHC project, an MSR-sponsored effort to push parallel Haskell technologies out into the real world. Check our project news below to see how we're doing in that front. Finally, you may heard Functional Propaganda from a Simon or two. But how would the same message affect you if it came from a hardcore C++ hacker? If you haven't seen it making the rounds, have a quick look at Bartosz Milewski's [The Downfall of Imperative Programming][b0], and maybe tell your imperative friends? The FP monster is hatching from its academic egg; best be prepared! [HTML version](http://www.well-typed.com/blog/65) News ---------------------------------------------------------------------- Let's have a quick look at some of those GSoC proposals, particularly those with a parallel Haskell theme. It's all about performance this year. Two of the proposals involve using or improving parallellism in Haskell, and four are related to high-performance concurrency. * [Parallel CSG engine][g2] Constructive Solid Geometry (CSG) is the common approach to define complex bodies in engineering applications, ray tracing engines and physical simulators. Dmitry Dzhus' proposal is to deliver a fast parallel CSG engine using the Accelerate/Repa libraries for vectorised computations on GPU. * [NUMA supporting features for GHC][g7] Sajith Sasidharan wants to reach into the GHC RTS, with the aim of “extracting that last ounce of performance from NUMA systems, by firing all CPUs if/when necessary and by ensuring a suitably NUMA-aware memory allocation behavior.” Work in this area would benefit folks doing scientific computing, who may need great amounts of task and data parallelism. * [Windows support for the new GHC I/O manager][g6] The new I/O manager (GHC 7) brings great scalability improvements to Haskell — 10k simultaneous connections to your web server? no sweat. Unfortunately for Haskellers on Windows, these improvements are currently only available on Unix. Mikhail Glushenkov (who worked on GSoC last year to make improvements to Cabal) proposes to remedy this, making the new manager available on Windows. The challenge is that Windows I/O completion ports have slightly different semantics than their epoll/kqueue analogues on Unix. * [Lock-free hash table and priority queue][g3] More along the theme of high performance concurrency, Florian Hartwig's project aims to use GHC's new-ish atomic compare-and-swap (CAS) primitive to implement a high-performance lock-free hash table and a lock-free priority queue in Haskell. The CAS instruction is a bit of hardware support for concurrency: it compares a value in memory to an expected value, and iff they match, replaces it with a new value. * [Implement Concurrent Hash-table / Hashmap][g5] Loren Davis also proposes a thread-safe mutable hash table implementation in Haskell. Loren is still weighing some of the alternative approaches suggested in the Haskell community. He is currently leaning towards a lock-stripping approach as it would fulfill an immediate need in the community. * [Concurrent Datastructures with good Performance][g4] Mathias Bartl aims to implement two concurrent data types in Haskell, along with the usual battery of automated unit tests and benchmarks. The two that Mathias has in mind are a lock-free concurrent bag, and a concurrent priority queue. Parallel GHC project update ---------------------------------------------------------------------- We have been continuing our work to make ThreadScope more helpful and informative in tracking down your parallel and concurrent Haskell performance problems. We now have the ability to collect heap statistics from the GHC runtime system and present them in ThreadScope. These features will be available for users of a recent development GHC (7.5.x) or the eventual 7.6 release. In addition to heap statistics, we have been working on collecting information from hardware performance counters, more specifically adding [support for Linux Perf Events][hs-perf]. This could be useful for studying IO-heavy programs, the idea being to visualise system calls as being distinct from actual execution of Haskell code. Speaking of performance, we are also continuing work on the new Cloud Haskell implementation (see Duncan Coutts' [Fun in the Afternoon Talk][t4]), and have lately been focused on reducing message latency. This consists of work in three areas: improving binary serialisation, investigating the implications of using `Chan` and `MVar` to pass messages between threads, and perhaps improving the Haskell network library implementation to compete better with a direct C implementation. Word of the month ---------------------------------------------------------------------- Lately, we've been investigating the various ways Haskell helps us to get to grips with concurrency. We talked about how the `MVar`, the Haskell variant on locks, allows us to share mutable variables between threads, with some safeguards to help ensure consistency. `MVar`'s may provide a nice high-level packaging around locks, but as we mentioned in the last digest, they can still go horrifically wrong, just like locks and synchronized methods in other languages. We could go through the usual litany of reasons why locks are bad news, but maybe a healthier approach would be for us to focus on the positive. What do we want as programmers? One possibility is what Simon PJ ([Beautiful Concurrency][stm-bc]) calls “modular programming”, the ability to “[build] large programs by gluing together smaller programs”. Locks fall short of helping us to meet this desire. First, because the mere act of combining two locky programs may be inherently incorrect; `withdraw acct1 amt >> deposit acct2 amt` is bad because of the gap between the two actions where the money is in neither account. Second, because they seal off programs that we may otherwise like to moosh together; if process p1 waits for input on a pipe, process p2 waits for input on another pipe, how do wait for either of p1 or p2? So how do we wrestle back this modularity from our locky masters? And how do we make programming fun again? Our word of the month today is “transaction”. Software transactional memory (STM) takes this idea of a transaction (a sequence of operations that can be treated as a single atomic block) from database design. The Haskell implementation of STM was introduced in the 2005 paper [Composable Memory Transactions][stm-05] by Harris *et. al.* If programming fun is what you're after, this is a paper that comes with its own war-cry: “compositionality: a programmer can control atomicity and blocking behaviour in a modular way that respects abstraction barriers.” Here are some quick highlights of the stm library. You may notice a couple of things, first that this library introduces its own notion of variable, the `TVar` and second that STM involves a new monad of its own. Unlike the `MVar` that we saw in the last digest, `TVar`'s do not have the same notion of being full or empty; they just hold values plain and simple. As for the STM monad, we will see why it matters when we first try to do some IO. -- Control.Concurrent.STM data STM a instance Monad STM atomically :: STM a -> IO a data TVar a newTVar :: a -> STM (TVar a) readTVar :: TVar a -> STM a writeTVar :: TVar a -> a -> STM () retry :: STM a orElse :: STM a -> STM a -> STM a To get a rough idea how some of this is used, let's look at the transactional hello world, safely wiring money from one bank account to another. For the purposes of our example, a bank account is just a balance. To get some money from an account, we read the balance, subtract the amount, and write the new balance. Making a deposit is just withdrawing negative-money. type Account = TVar Int withdraw :: Account -> Int -> STM () withdraw acc amount = do bal <- readTVar acc writeTVar acc (bal - amount) deposit :: Account -> Int -> STM () deposit acc amount = withdraw acc (- amount) These primitive operations (withdraw and deposit) bring us to the question of modularity. How do we know that it's safe to combine these mini-programs into a bigger one? In other words, if we write something like `withdraw from 42 >> deposit to 42`, how do we avoid the possibility of running into some twilight zone state where the money is neither here nor there? If people do strange things like simultaneously transfering money in the other direction, will our program still work? The answer lies in the distinction between `STM` (transactions) and `IO` (actions). So long as we remain in STM, we are simply assembling transactions, piecing smaller ones (“withdraw from a”) into larger ones (“withdraw from a and deposit it to b”), but not actually performing them! Having composed our transactions, we can use the function `atomically` to turn them into IO actions. -- still just a transaction transfer :: Account -> Account -> Int -> STM () transfer from to amount = do deposit to amount withdraw from amount -- now we have an action! doTransfer :: Account -> Account -> Int -> IO () doTransfer from to amount = atomically $ transfer from to amount And `atomically` does what it says on the tin: it runs the transaction in a way that renders it indivisible, no twlight zones. Lest there is any confusion, even though the transaction is indivisible, we can *still* have concurrency during the course of the transaction, even simultaneously read the affected `TVar`s if we want to. The indivisibility simply means that we never catch our transactions with their pants down. We neither read nonsense mid-transactional values (simultaneous reads would either get the before or after value), nor injecting values into a transaction mid-stream. To get a feel for how these guarantees are possible, it could be useful to take a peek under the hood. For each transaction that is run, GHC maintains a thread-local log with an entry for each `TVar` accessed in that transaction. Each entry contains both the old value and the new value that would be committed if the transaction is succesful. This may be easier to see with a silly example: main = do v1 <- atomically $ newTVar "Joe" v2 <- atomically $ newTVar "Bob" done <- atomically $ newTVar 0 -- thread A (you can just pretend forkDelayIO == forkIO) forkDelayIO . atomically $ do -- transaction log if A runs first x <- readTVar v1 -- v1: Joe -> Joe y <- readTVar v2 -- v1: Joe -> Joe, v2: Sue -> Sue writeTVar v1 "Sue" -- v1: Joe -> Sue writeTVar v2 x -- v1: Joe -> Sue, v2: Bob -> Joe writeTVar v1 y -- v1: Joe -> Bob, v2: Bob -> Joe modifyTVar done (+1) -- (stm 2.3 but easy to define) -- thread B forkDelayIO . atomically $ do -- (if A runs first) writeTVar v1 "Jean" -- v1: Bob -> Jean writeTVar v2 "Paul" -- v1: Bob -> Jean, v2: Joe -> Paul modifyTVar done (+1) waitThreads 2 done people <- atomically $ do -- (if A runs first) p1 <- readTVar v1 -- v1: Jean -> Jean p2 <- readTVar v2 -- v1: Jean -> Jean, v2: Paul -> Paul return (p1, p2) print people -- if A runs first, (Jean, Paul) -- if B runs first, (Paul, Jean). -- boring details just for this example forkDelayIO job = forkIO $ randomRIO (1, 1000000) >>= threadDelay >> job waitThreads n v = atomically $ do { d <- readTVar v; when (d < n) retry } In the above, we fork off two threads, A which swaps a pair of names and, B which overwrites them with other names. Atomicity here means that other threads never see any intermediary states and state changes from other threads don't affect the current thread. For example, thread B should never see `v1` being set to "Sue". Likewise, if thread A should still read "Joe" from v1 even if B simultaneously writes "Jean". This is made possible by validation of the transaction logs. Validation normally occurs at the end of a transaction (we won't cover the two other cases here: exceptions, and thread wake-ups). It consists of checking that all the expected “before” values for `TVar`s still match reality. If the logs are good, we commit the new values; if not, we simply discard them and try the transaction again, taking the new reality into account. This validate-and-commit model allows us to run transactions simultaneously, safely, but with the occasional rollback and retry to ensure atomicity. The notion of a transaction log brings us to the notion of cost. Good things don't always come cheap, and using a good thing like STM may require a little familiarity with the cost model behind it. Basically, it's important to keep in mind that the values we write to `TVar`'s may come from some arbitrary expression, and that arbitrary expressions may be arbitrarily expensive. So being forced to retry transactions may involve redoing something expensive. If the transactions affect many variables, the chances of hitting a retry go up. Likewise, if the transaction takes a long time to run, the chance goes up of some other thread making a change that triggers a retry. In the pathological worst case, you can have some transactional behemoth that never manages to commit; because some smaller faster transaction keeps stealing its thunder. So keep an eye out for starvation and the more general problem for retries being expensive. Cost may be a bit of a bummer, but there's also a Haskell-related silver lining behind all this. Because we have a purely functional language and the enforced separation between pure functions and side-effecting actions, STM is actually quite practical in Haskell. The number of things we need to track in a transaction log is limited to handful of explicit `TVar`s rather that just about everything. If you are coming from other languages, you may have a memory of STM as being nice, but wildly impractical. Not so in Haskell. Eminently viable. Aside from making STM practical, this sort of separation is also good for general peace of mind. Suppose for example that we coded up a feature in our banking software to send our users a text message alert whenever their balances fall below a threshold. If we were in the middle of a complicated transaction, we might be tempted to just slap that logic right in the middle of the transaction; however, the Haskell implementation makes this deliberately impossible. This can be a bit frustrating at first (and new Haskellers are sometimes faced with the “how do I get this out of the monad” puzzle), but saves us the greater danger of bombarding our users with spurious retry-induced text messages. The guarantees that STM offer make it a great place to get started with Haskell concurrency. After all, why make software any buggier than it needs to be? If you do want to get started, have a look at Simon Peyton Jones' [Beautiful Concurrency][stm-bc]. It's a particularly good idea to do so, because there's some really interesting ground that we've not covered here (briefly, blocking, the `retry` function aborts the current transaction, and causes it to be retried when appropriate; and choice: <code>a `orElse` b</code> tries `a`, and if that should retry, then `b`, and if that should also retry, the whole expression again). Other great STM resources are Simon Marlow's [tutorial on parallelism and concurrency][stm-sm] and the [Real World Haskell chapter on STM][stm-rwh]. With the four resources combined, you'll see a nice range of examples from the usual bank-account one to concurrently shuffling windows between desktops. Blogs ---------------------------------------------------------------------- * [The Downfall of Imperative Programming][b0] (9 Apr) Take a hardcore C++ veteran with imperative programming in his bloodstream and loads of experience under his belt. Now give him a passion for concurrency and what do you get? First, you get a keen awareness that the future is massively multicore. Second, you get a hard-won appreciation for how difficult concurrent programming can be; for all jokes we make in the Haskell community about firing the missiles, the consequences of data races can sometimes be [deadly][therac-25]. Third, you get the conviction that functional programming is the inevitable way forward. Bartosz Milewski sums up the situation thus: Sooner or later you’ll have to face the multicore reality. You will be forced to learn functional methods to the extent to which your imperative language supports them. Despite that, data races will infest your code and leak into released products. So you might as well take a shortcut and embrace a full blown functional language now. See what you make of his blog post if you have not done so already. There's quite a bit of buzz about this post, so you may also be interested in the [programming reddit discussion][r2] around it as well. * [Building A Concurrent Web Scraper With Haskell][b1] (10 Mar) Let's make a concurrent web scraper! This blog post by Aditya Bhargava presents a hands-on introduction to both arrows (via hxt) and concurrency (via parallel-io). Aditya builds from the bottom-up, showing us little pieces of program that we might cobble together, culminating in a 52 line Haskell program that crawls web sites and fetches images within their pages. The parallel-io library used in this tutorial provides a thread pool which minimises contention by guaranteeing a limit to the number of unblocked threads running at the same time. It uses lock based concurrency with `MVar`'s under the hood. * [0MQ and Haskell][b2] (6 Mar) Magnus Therning could not find any excuses to look into 0MQ. But “to hell with reason”, Magnus ended up deciding to just poke around without any specific goal in mind. He found a [nice tutorial][pyzero] based on Python and translated its mini examples into Haskell. Magnus wonders why the API for `subscribe` is `String` rather than `ByteString` based. Also, he's finding that his client mysteriously dies after receiving a few messages. Any comments? * [SIMD Support for the vector library][b3] (27 Mar) Single instruction, multiple data (SIMD) is the sort of thing you might be interested in if you're into data parallelism: hardware that can perform the same instruction on multiple data simultaneously. Geoffrey Mainland posted about his efforts to bring SIMD support to GHC, the bigger picture being that you ought to be able to write nice high-level Haskell and have it work as fast the low-level Haskell or C that you might otherwise crank out. To try things out, Geoff benchmarks taking the dot product of two vectors in various Haskell and C versions. No happy ending yet, unfortunately: while the low-level Haskell version is competitive with C, the high-level is not. Check the post out for dissection of the results down the Core and assembly level. Hopefully better news in a follow-up posting. * [Adding SIMD Support to Data Parallel Haskell][b3b] (18 Apr) Hopefully better news? Not as such, but perhaps something more interesting. In the previous post, we could make use of SIMD support by issuing some explicit instructions from the vector library. OK, but what about people who writing parallel code, say, by using a parallel arrays framework? And what if you could get this SIMD support virtually for free — no syntax attached? Geoff makes this possible by extending the [Data Parallel Haskell][dph] framework so you would only have to tweak a single import statement, and exploitation of SIMD instructions would be automatic. See the posting for some nice benchmarks and also a brief introduction to Data Parallel Haskell. * [Work Efficient Higher-Order Vectorisation][b4] (24 Mar) Found on Manuel Chakravarty's tumblr: Our new draft paper on Work Efficient Higher-Order Vectorisation introduces a novel representation for nested, irregular parallel arrays that enables the work-efficient SIMD-ification of nested data parallelism — i.e., nested parallelism is transformed into flat parallelism, while maintaining the work complexity of a naive pointer-based representation of nested arrays. This solves a long standing problem that dates back to the original implementation of the language NESL. Talks, tutorials, and packages ---------------------------------------------------------------------- * [stm-chans 1.3.1][t1] (1 Mar) The stm-chans package offers a collection of channel types, similar to `Control.Concurrent.STM.TChan` but with additional features. This latest update by wren ng thornton takes advantage of optimisations in the newly released stm-2.3. It's highly recommended that all users bump their minimum stm-chans requirement to version 1.3.1 * [accelerate 0.10.1][t2] (12 Apr) Manuel Chakravarty has just released version 0.10.0.0 of Accelerate, an embedded language for GPU-accelerated array computations in Haskell that targets NVIDIA's CUDA framework and also has an experimental (and partial) OpenCL backend. A considerable amount of example code is in the companion package accelerate-examples. The main user-visible changes in this release are frontend bug fixes. * [Parallel Functional Programming course][t3] Students at Chalmers and Gothenburg University are currently 6 lectures into a course on parallel functional programming. The course has so far covered parallelism with `par`/`pseq`, Strategies and monad-par, using ThreadScope, and skeletons as a means to structure parallel computations. The course page has lecture notes and exercises which could be of interest even if you aren't currently following the course. * [Cloud Haskell][t4] (Fun in the Afternoon) Well-Typed's Duncan Coutts was at the recent [Fun in the Afternoon][fun-aft], a termly seminar on Functional Programming in the UK). Duncan presented some of the motivation behind Cloud Haskell (”Erlang for Haskell”) and distributed programming, along with the Cloud Haskell design, and our work on a new implementation to follow on the initial protoype by Jeff Epstein. Our new implementation adds a swappable network transport layer. If you're happy with TCP/IP, don't wait for the new implementation; just `cabal install remote` and give Jeff's prototype a try. Mailing lists ---------------------------------------------------------------------- ### Concurrency * [Transactional memory going mainstream with Intel Haswell][m1] (9 Feb) Ben was wondering if any STM experts would comment on this recent [Ars Technica article][arswell] on the Intel Haswell chip. Austin Seipp pointed us to a comment by Duncan Coutts in the Reddit discussion (unfortunately not; the new extension would sledgehammer all instructions between the XBEGIN/XEND instructions). Ryan Ingram suggests that maybe the extension could be used to optimise the existing implementation, perhaps by wrapping transaction commits with XBEGIN/XEND) * [Behavior of -threaded in GHC 7.4.1?][m2] (14 Feb) Mike Craig just debugging a recent issue with GHC 7.4.1 and the zeromq3-haskell library, which provides a provides an FFI binding to libzmq. Unfortunately, code which used to run when compiled on GHC 7.0.4 dies with “operation on non-socket” when built with GHC 7.4.1. With the latter GHC, Mike can only run the code if he omits `-threaded`, or if he uses the `-V0` flag to turn off the RTS clock and associated signals. After more debugging, he tracked the problem down to a `addFinalizer` on a `Socket` tuple. The finalizer was being run prematurely, perhaps because the Socket type was being optimised away. Putting the finalizer on the `Ptr ()` in the tuple seems to solve the problem. * [Question about concurrency, threads and GC][m6] (2 Mar) Paul Graphov is trying to implement a networked application that supports bidirectional conversations, ie. not just request/response, but also sending notifications to clients. Paul is particularly interested in STM, but he's stuck on a bit of a design problem. His thinking so far is that he'll need to start 3 threads for each client, one to read data from the socket, one that sends queued messages to that socket, and one for the main behaviour loop. Joey Adams noticed that this was the same sort of problem we reported in the [previous digest][ph-8]. Joey was grappling with making making asynchronous I/O composable and safe. He wound up not using the stm-channelize package that he wrote, and recommends instead a 3-thread solution, using a thread each for receiving, sending, and coordination. Check out the small Haskell [chat server][chat-1] that Joey wrote to illustrate the idea. Alexander V Vershilov suggests a data-driven behaviour based on conduits and stm channels. He's also provided an [example chat server][chat-2], which you can compare against Joey's version. The two examples take a similar approach, and `could perhaps be combined to good effect. * ["killThread" hangs! (ironic)][p1] (25 Feb) Ryan Newton is gathering information in preparation for a possible bug report. He's testing the new network transport layer in distributed-process (Cloud Haskell) and gets hangs in `killThread`. Strangely, the pattern for hanging goes: GHC 6.12.3 [OK], 7.0.2 [HANGS], 7.2.1 [HANGS], 7.4.1 [OK]. Any ideas? Simon Marlow suggests it may be a bug in the RTS asychronous exception handling code, fixed with commit `fa71e6c`. * [Synchronizations in memory allocation?][p2] (21 Mar) Following up on the recent scaling bottleneck thread, Ryan Newton wondered: “What is the reason for GHC managing all this pinned memory for foreign pointers itself rather than using an external C malloc/free implementation and thus keeping disjoint Haskell and C heaps?” Simon Marlow says it's basically because GHC's `mallocForeignPtrBytes` is much faster than `malloc()`/`free()` Ryan was asking because he is looking to how to do better on [NUMA][numa] platforms. “We've got a NUMA-aware work-stealing scheduler now for monad-par, but it isn't really helping much yet. So we need to answer the question of how well our memory is being localized to socket-preferred physical addresses.” NUMA isn't something the GHC team have looked into for the RTS yet. He has some ideas for improvements to the block allocator; more details in the thread. * [Haskell for BigData][p3] (16 Mar) Andrei Varanovich observes that while Haskell has a lot to offer in the world of parallel/concurrent programming (from DPH to Cloud Haskell), it still lacks two important components for working with Big Data: * Integration with a distributed file system, such as Hadoop distributed file system * A data aggregration framework (eg. MapReduce, but of course something much richer; this being Haskell and all) Andrei was interested in submitting a Google Summer of Code proposal to build a big data framework for Haskell on top of Cloud Haskell. I didn't see a proposal this year, but maybe next time? See the thread for technical suggestions, supportive comment, and pointers for a succesful Haskell GSoC project. ### Parallelism * *Help wanted!* [Parallelism causes space leaks][m9] (23 Mar) Yavuz Yetim posted a small chunk of code using Strategies for parallelism. When he enables his `parList rdeepseq` strategy, though, he gets a stack overflow on smallish input (1 MB file), even if he allows GHC to use a 1GB stack. Switching to `parMap`, `parListChunk` and other strategies don't seem to help either. * [Data.Array.Accelerate initialization timings][m5] …[more][m5b] (20 Feb) Paul Sujkov is finding that array initialisation in Data.Array.Accelerate takes 10x the amount of time than either Data.Array and bare C++ CUDA array initialisation. Is there anything Paul might be doing wrong in particular? The accelerate package currently provides two backends, an interpreter (reference implementation) and a CUDA backend generating code for CUDA-capable NVDIA GPUs. Martin Dybdal comments that Paul should use `Data.Array.Accelerate.use` to generate hints to transfer arrays to GPU, and `Data.Array.Accelerate.CUDA.run` to actually perform the transfer. Manuel Chakravarty adds that the the `fromList` function is really just meant for testing, or for initialising small arrays. For anything bigger, going from vanilla lists is a bad idea, so have a look at `Data.Array.Accelerate.IO`. * [Reasons for Super-Linear Speedup][m7] (5 Mar) Burak Ekici has parallelized RSA decryption and encryption schemes by using second generation strategies. He's getting 10 times performance improvements… on a quad-core CPU (with an 8MB cache). Is this just mismeasurement, or are there some differences in how GHC handles serial/parallel of computation, say with respect to cache usage? Bardur Arantsson replies that the usual explanation for this sort of thing is that the working data suddenly fits within the per-CPU L2 cache when split up. StackOverflow and Reddit ---------------------------------------------------------------------- * [Is there a way in Haskell to query thread state using ThreadID after a forkIO?][s1] * [Are haskell channels `Control.Concurrent.Chan` safe for multiple readers/producers?][s2] * [How to take F# measurements to get speedups][s3] * [Using Haskell to program the GPU : haskell][r1] * [The Downfall of Imperative Programming][r2] * [Examples of easy parallelism in Haskell?][r3] Help and Feedback ---------------------------------------------------------------------- If you'd like to make an announcement in the next Haskell Parallel Digest, then get in touch with me, Eric Kow, at <parallel(a)well-typed.com>. Please feel free to leave any comments and feedback! [arswell]: http://arstechnica.com/business/news/2012/02/transactional-memory-going-mai… [chat-1]: https://github.com/joeyadams/haskell-chat-server-example [chat-2]: https://github.com/qnikst/chat-server/blob/master/src/Main.hs [dph]: http://ghc-simd.blogspot.co.uk/2012/04/adding-simd-support-to-data-parallel… [fun-aft]: http://sneezy.cs.nott.ac.uk/fun/2012-02 [numa]: https://en.wikipedia.org/wiki/Non-Uniform_Memory_Access [hs-perf]: http://www.berniepope.id.au/linuxPerfEvents.html [pyzero]: http://nichol.as/zeromq-an-introduction [stm-bc]: http://research.microsoft.com/en-us/um/people/simonpj/papers/stm/beautiful.… [stm-05]: http://research.microsoft.com/en-us/um/people/simonpj/papers/stm/stm.pdf [stm-sm]: http://community.haskell.org/~simonmar/par-tutorial.pdf [stm-rwh]: http://book.realworldhaskell.org/read/software-transactional-memory.html [ph-8]: http://www.well-typed.com/blog/64 [simd-ghc]: http://hackage.haskell.org/trac/ghc/wiki/SIMD [therac-25]: http://en.wikipedia.org/wiki/Therac-25 [g1]: http://parfunk.blogspot.co.uk/2012/02/potential-gsoc-haskell-lock-free-data… [g2]: http://www.google-melange.com/gsoc/proposal/review/google/gsoc2012/dmitrydz… [g3]: http://www.google-melange.com/gsoc/proposal/review/google/gsoc2012/florianh… [g4]: http://www.google-melange.com/gsoc/proposal/review/google/gsoc2012/mathiasb… [g5]: http://www.google-melange.com/gsoc/proposal/review/google/gsoc2012/lorehead… [g6]: http://www.google-melange.com/gsoc/proposal/review/google/gsoc2012/refold/3… [g7]: http://www.google-melange.com/gsoc/proposal/review/google/gsoc2012/sajith/1 [b0]: http://fpcomplete.com/the-downfall-of-imperative-programming/ [b1]: http://adit.io/posts/2012-03-10-building_a_concurrent_web_scraper_with_hask… [b2]: http://therning.org/magnus/archives/1009 [b3]: http://ghc-simd.blogspot.co.uk/2012/03/simd-support-for-vector-library.html [b3b]: http://ghc-simd.blogspot.co.uk/2012/04/adding-simd-support-to-data-parallel… [b4]: http://tumblr.justtesting.org/post/19825349916/work-efficient-higher-order-… [t1]: http://www.haskell.org/pipermail/haskell-cafe/2012-March/099805.html [t2]: http://justtesting.org/gpu-computing-in-haskell-version-010-of-dataa [t3]: http://www.cse.chalmers.se/edu/course/pfp/ [t4]: http://sneezy.cs.nott.ac.uk/fun/2012-02/coutts-2012-02-28.pdf [m1]: http://www.haskell.org/pipermail/haskell-cafe/2012-February/099300.html [m2]: http://www.haskell.org/pipermail/haskell-cafe/2012-February/099456.html [m3]: http://www.haskell.org/pipermail/haskell-cafe/2012-February/099456.html [m5]: http://www.haskell.org/pipermail/haskell-cafe/2012-February/099578.html [m5b]: http://www.haskell.org/pipermail/haskell-cafe/2012-February/099584.html [m6]: http://www.haskell.org/pipermail/haskell-cafe/2012-March/099830.html [m7]: http://www.haskell.org/pipermail/haskell-cafe/2012-March/099890.html [m9]: http://www.haskell.org/pipermail/haskell-cafe/2012-March/100349.html [p1]: https://groups.google.com/d/msg/parallel-haskell/NI5qxYw-5RA/fTljjfXYWYUJ [p2]: https://groups.google.com/d/msg/parallel-haskell/fsHrxz3ei70/FKe0kgV5mqcJ [p3]: https://groups.google.com/d/msg/parallel-haskell/nxDoibiuGWE/N68MR19uu1kJ [s1]: http://stackoverflow.com/questions/9475392/is-there-a-way-in-haskell-to-que… [s2]: http://stackoverflow.com/questions/9616515/are-haskell-channels-control-con… [s3]: http://stackoverflow.com/questions/9678284/how-to-take-f-measurements-to-ge… [r1]: http://www.reddit.com/r/haskell/comments/qnq4y/using_haskell_to_program_the… [r2]: http://www.reddit.com/r/programming/comments/s112h/the_downfall_of_imperati… [r3]: http://www.reddit.com/r/haskell/comments/sdx5v/examples_of_easy_parallelism… -- Eric Kow <http://erickow.com>

1 0

Using Data Types a la Carte
by Alex Rozenshteyn 19 Apr '12

19 Apr '12

I'm trying to implement a set of languages with a large overlap between them. >From what I understand, there are 3 main ways to do this: Finally Tagless, Data Types a la Carte, or manually. I'm currently leaning toward DTalaC, but not strongly. There seem to be two packages which implement the DTalaC style: syntactic and compdata. Alternatively, I can write the common code myself. Does anyone have recommendations for which one to use, and any materials for learning to use them? -- Alex R

2 1

ANNOUNCE: graphviz-2999.13.0.0
by Ivan Lazar Miljenovic 19 Apr '12

19 Apr '12

I'm hoping the second part of the version number isn't ominous, but I've just uploaded the latest release in my bindings for the Graphviz suite of graph visualisation tools. The changes in this release are: * Added support for the `osage` and `patchwork` visualisation tools, available as of Graphviz-2.28.0. * Updated attributes as of Graphviz-2.28.0: - `SVG` colors are now supported, and the support for different colors has been revamped. - `overlap=false` is now equivalent to `overlap=prism` and the `RemoveOverlaps` option has been removed. - `LabelScheme` and `Rotation` are new attributes for use with `sfdp`. - `Scale` is a new attribute for use with `twopi`. - Add new italics, bold, underline, superscript and subscript options for HTML-like labels. - `LHeight` and `LWidth` for getting the height and width of the root graph and clusters. * Updated attributes from the current development branch of Graphviz (i.e. 2.29.*). Please note that these will probably not work yet, but are implemented now for future-proofing. - A new style for edges: `Tapered`. - `XLabel` allows you to specify labels external to a node or edge. `ForceLabels` allow you to specify that these should be drawn even when they will cause overlaps. - `ImagePath` allows you to specify where to search for images. - HTML-like labels now support `ID` values as well as horizontal and vertical rules. - `BgColor` and `FillColor` now take a list of colors: this allows gradient fills for graphs, clusters and nodes. The `Radial` style and `GradientAngle` are also used for this purpose. - `FillColor` is now used by edges to set the color of any arrows. - [WebP](http://en.wikipedia.org/wiki/WebP) output support added. * Other attribute changes: - Use a specified data type for the `Ordering` attribute rather than an arbitrary `Text` value, and provide a documented wrapper in `Data.GraphViz.Attributes`. - `Bb` has been renamed `BoundingBox`. - `ID` now only takes `EscString` (a type alias for `Text`) values rather than arbitrary `Label`s. - The `Data.GraphViz.Attributes.HTML` module has had all values re-named and is now meant to be imported qualified. It is also no longer re-exported from `Data.GraphViz.Attributes.Complete`. * The `ToGraphID` class provides a common wrapper to help create cluster identifiers, etc. * Cabal's `Test-Suite` functionality is now used. As part of this, the `Data.GraphViz.Testing` module and sub-modules are no longer exported by the library. * The new `Benchmark` support in Cabal-1.14 is now used for the benchmark script. * Dropped support for base-3. * The `Data.GraphViz.State` module is no longer exposed, as there's no need for users to use it. * Bugfixes: - Some corner cases in canonicalisation prevented it from being idempotent. - The `TestParsing` script will no longer crash and refuse to continue if an IO-based error (e.g. unable to successfully call `dot`) occurs. - A typo was spotted by **Gabor Greif**. -- Ivan Lazar Miljenovic Ivan.Miljenovic(a)gmail.com http://IvanMiljenovic.wordpress.com

3 4

Parallel Strategy
by mukesh tiwari 19 Apr '12

19 Apr '12

Hello All I am trying to understand the Strategies ( http://hackage.haskell.org/packages/archive/parallel/3.2.0.2/doc/html/Contr…) and wrote this quick code. import Data.Listimport Control.Parallel.Strategies fun :: [ Int ] -> [ Int ]fun [] = []fun ( x : xs ) = ( x + 1 ) : fun xs main = do let xs = ( fun [ 1..1000000 ] ) `using` parListChunk 500000 rdeepseq return () When I am running this code due to laziness , the xs is not evaluating. [mukesh.tiwari@user ParallelStrat]$ time ./Main +RTS -N1 -s 48,320 bytes allocated in the heap 5,928 bytes copied during GC 38,592 bytes maximum residency (1 sample(s)) 14,656 bytes maximum slop 1 MB total memory in use (0 MB lost due to fragmentation) Tot time (elapsed) Avg pause Max pause Gen 0 0 colls, 0 par 0.00s 0.00s 0.0000s 0.0000s Gen 1 1 colls, 0 par 0.00s 0.00s 0.0002s 0.0002s Parallel GC work balance: -nan (0 / 0, ideal 1) MUT time (elapsed) GC time (elapsed) Task 0 (worker) : 0.00s ( 0.00s) 0.00s ( 0.00s) Task 1 (worker) : 0.00s ( 0.00s) 0.00s ( 0.00s) Task 2 (bound) : 0.00s ( 0.00s) 0.00s ( 0.00s) SPARKS: 0 (0 converted, 0 overflowed, 0 dud, 0 GC'd, 0 fizzled) INIT time 0.00s ( 0.00s elapsed) MUT time 0.00s ( 0.00s elapsed) GC time 0.00s ( 0.00s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 0.00s ( 0.00s elapsed) Alloc rate 48,368,368 bytes per MUT second Productivity 0.0% of total user, 0.0% of total elapsed gc_alloc_block_sync: 0whitehole_spin: 0gen[0].sync: 0gen[1].sync: 0 real 0m0.003suser 0m0.002ssys 0m0.001s [mukesh.tiwari@user ParallelStrat]$ time ./Main +RTS -N2 -s 48,248 bytes allocated in the heap 40 bytes copied during GC 38,440 bytes maximum residency (1 sample(s)) 18,904 bytes maximum slop 2 MB total memory in use (0 MB lost due to fragmentation) Tot time (elapsed) Avg pause Max pause Gen 0 0 colls, 0 par 0.00s 0.00s 0.0000s 0.0000s Gen 1 1 colls, 0 par 0.00s 0.00s 0.0001s 0.0001s Parallel GC work balance: -nan (0 / 0, ideal 2) MUT time (elapsed) GC time (elapsed) Task 0 (worker) : 0.00s ( 0.00s) 0.00s ( 0.00s) Task 1 (bound) : 0.00s ( 0.00s) 0.00s ( 0.00s) Task 2 (worker) : 0.00s ( 0.00s) 0.00s ( 0.00s) SPARKS: 0 (0 converted, 0 overflowed, 0 dud, 0 GC'd, 0 fizzled) INIT time 0.00s ( 0.00s elapsed) MUT time 0.00s ( 0.00s elapsed) GC time 0.00s ( 0.00s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 0.00s ( 0.00s elapsed) Alloc rate 48,248,000,000,000 bytes per MUT second Productivity 100.0% of total user, 0.0% of total elapsed gc_alloc_block_sync: 0whitehole_spin: 0gen[0].sync: 0gen[1].sync: 0 real 0m0.004suser 0m0.000ssys 0m0.004s The library doc suggest that parListChunk divides a list into chunks, and applies the strategy evalList strat to each chunk in parallel. Looking at the source code ( http://hackage.haskell.org/packages/archive/parallel/3.2.0.2/doc/html/src/C…) , list is split into chunks and then strategy is applied parallel to every chunk. Could some one please tell me what is wrong with this concept and why the code above is showing laziness. Regards Mukesh Tiwari

2 2

Template Haskell vs Rewrite Rules?
by Ismael Figueroa Palet 19 Apr '12

19 Apr '12

I'm working on getting annotated versions of all instances of a function of a typeclass, and was wondering what are the relation/differences between Template Haskell and the Rewrite Rules section. Of course this is specific to GHC. Another question, in Racket, primitive function application is denoted #%app. And using macros I can re-export #%app to be a different function f, so a program: (g a) is rewritten into (f g a) is there a way to do the same thing using TH or Rewrite Rules? Thanks -- Ismael

3 3