- Haskell-Cafe - Haskell.org

Haskell on NUMA
by Michael Lesniak 16 Jun '11

16 Jun '11

Hi, what ist the current state of Haskell's parallel performance on NUMA machines? I've (probably) run into some performance problems using a 2x8 cores machine and am unsure how to fix them (if it's possible at all at the moment). I've only found two (helpful?) resources on the web, namely - an old ticket which is closed [1] - a current talk (13. May 2011) about a new runtime system for GHC7 for NUMA machines [2] Are any other informations available? Kind regards, Michael [1] http://hackage.haskell.org/trac/summer-of-code/ticket/1123 [2] http://www.dcs.gla.ac.uk/~jsinger/mmnet11_talks/orczyk.pdf

1 0

8th Ghent Functional Programming Group Meeting on Thursday, the 30th of June, 2011
by Jeroen Janssen 16 Jun '11

16 Jun '11

(apologies if you receive multiple postings) Dear All, We are pleased to announce the 8th Ghent Functional Programming Group (GhentFPG) meeting, which takes place on Thursday, the 30th of June, 2011 at 19:30 in the Technicum building of Ghent University (Sint-Pietersnieuwstraat 41, 9000 Gent). As before, the electronic sliding doors will be locked, but a phone number that you can call to get in will be provided at the doors on the far left of the building. The structure of the meeting is a bit different than before: we begin with two short talks and end with a small problem solving activity where everyone tries to solve a given problem in his favorite functional language. The exact problem will be given at the meeting. The abstracts for the talks are as follows: Pieter Wuille ------------- I'll talk about the monadic constraint programming (MCP) framework, and in particular the Finite Domain layer i've developed for it. As explained by Tom Schrijvers in a previous talk, MCP is a general Haskell framework for Constraint Programming (CP), allowing users to search for assignments to variables that satisfy given constraints, while abstracting from the actual algorithm used to find these solutions. Finite Domain problems are a subset of CP where the variable's initial domains are finite, typically small integers. Problems that can be expressed elegantly in FD include Sudoku and N-Queens. MCP's FD layer provides an embedded Domain Specific Language (DSL) to describe these problems declaratively, some backend solvers, and an intermediate translation layer. I'll introduce the features and possibilities of the system by showing some examples, and explain some implementation details along the way. Jasper Van der Jeugt -------------------- I will give a talk about the techniques and patterns used in the Text library. Text is quickly becoming the de-facto standard type for presenting human-readable text in Haskell. My current work focuses on improving the performance of this library by porting the internally used encoding from UTF-16 to UTF-8. The talk will present a high-level overview of some tools and techniques to study and improve the performance of a Haskell program, including: strictness analysis, pitfalls for benchmarking, fusion frameworks, unboxed type representations, and GHC core. If you would like to receive updates on our activities, you can follow us on twitter (@ghentfpg), google groups (http://groups.google.com/group/ghent-fpg?pli=1) or linked.in (http://t.co/cjXbGyT) Hope to see you there! Andy Georges Jasper Van der Jeugt Jeroen Janssen The GhentFPG Organizing Committee

1 0

Acquiring a random set of a specific size (w/o dups) from a range of Ints
by michael rice 16 Jun '11

16 Jun '11

Is there an (existing) way to select 5 Ints randomly (no duplicates) from a population, say 1-20 (inclusive)? Michael

4 5

Haskell Parallel Digest 3
by Nicolas Wu 16 Jun '11

16 Jun '11

Parallel Haskell Digest ======================= Edition 3 2011-06-16 http://www.well-typed.com/blog/55 Hello Haskellers! Welcome to the third edition of the Parallel Haskell Digest, bringing you news, discussions and tasters of parallelism and concurrency in Haskell. The digest is made possible by the Parallel GHC project. More news about how we're doing below. This digest is brought to you by Eric Kow and Nicolas Wu. Nick will be taking over as maintainer of the Parallel Digest for the next few months. It's tutorial season in the Parallel Haskell world, with Simon Marlow's [Parallel and Concurrent Programming in Haskell][1], and Don Stewart's [Numeric Haskell: A Repa Tutorial][2]. The former gives a broad tour of parallelism and concurrency techniques in Haskell and the latter focuses on the Repa parallel array library. Both are very concrete and focus on real working code. Give them a try! News ---------------------------------------------------------------------- * Haskell in the Economist! The Economist article [Parallel Bars][3] discusses the rise of multicore computing, and the essential obstacle that programs have to be specially written with parallelism in mind. The article gives a tour of some problems (overhead and dependencies between subtasks, programmers being trained for sequential programming, debugging parallel programs) and possible solutions, among which is functional programming: > Meanwhile, a group of obscure programming languages used in > academia seems to be making slow but steady progress, crunching > large amounts of data in industrial applications and behind the > scenes at large websites. Two examples are Erlang and Haskell, > both of which are “functional programming” languages. Are we doomed to succeed? Word of the Month ---------------------------------------------------------------------- The word of the month (well, phrase really!) for this digest is *parallel arrays*. Parallel array manipulation fits nicely into Haskell's arsenal of parallel processing techniques. In fact, you might have seen the Repa library, as mentioned above, in the news a while back. And now there's a new tutorial on the [Haskell Wiki][2]. So what's all the fuss? Parallel arrays manipulation is a particularly nice way of writing parallel programs: it's pure and it has the potential to scale very well to large numbers of CPUs. The main limitation is that not all programs can be written in this style. Parallel arrays are a way of doing *data parallelism* (as opposed to *control parallelism*). Repa (REgular Parallel Arrays) is a Haskell library for high performance, regular, multi-dimensional parallel arrays. All numeric data is stored unboxed and functions written with the Repa combinators are automatically parallel. This means that you can write simple array code and get parallelism for free. As an example, Repa has been used for real time edge detection using a [Canny edge algorithm][12], which has resulted in performance comparable to the standard OpenCV library, an industry standard library of computer vision algorithms written in C and C++ (a single threaded Haskell implementation is about 4 times slower than the OpenCV implementation, but is on par when using 8 threads on large images). While the Canny algorithm written with Repa doesn't quite match the speed of its procedural counterparts, it benefits from all of Haskell's built in support for purity and type safety, and painlessly scales to multiple cores. You can find more details on Ben Lippmeier's [blog][10]. Parallel GHC project news ---------------------------------------------------------------------- The Parallel GHC Project is an MSR-funded project to promote the real-world use of parallel Haskell. Part of this project involves effort by Well-Typed to provide tools for use by the general community. Last week, Well-Typed were excited to [announce][11] that we have capacity to support another partner for the parallel project for at least another 12 months. So, if you have a project that involves scaling up to multiple cores, or that deals with some heavy duty concurrency, then we'd love to hear from you. In return for your time and commitment to the parallel project, we'll unleash our team of expert programmers to help build tools and provide support that will help you and the community towards making parallel Haskell even more accessible. For more information on the Parallel GHC project, on the [Parallel GHC Project wiki page][27]. Blogs, papers and packages ---------------------------------------------------------------------- * [Parallel and Concurrent Programming in Haskell (19 May)][1] Simon Marlow released version 1.1 of his tutorial introducing the main programming models available for concurrent and parallel programming in Haskell. "This tutorial takes a deliberately practical approach: most of the examples are real Haskell programs that you can compile, run, measure, modify and experiment with". The tutorial covers a lot of ground, including use of the new `Par` monad, so if you're still not sure where to start, this might be the place. * [Explicit speculative parallelism for Haskell's Par monad][4] Tomas Petricek builds off the Par monad to provide a way to write speculative computations in Haskell. If there are two different ways to compute something and each of the ways is faster for different kinds of input (but we don't know exactly which), one useful trick is to run both ways in parallel and return the result of the one that finishes first. Tomas' speculative `Par` monad lets you do just that, starting computations in parallel and cancelling unwanted ones. You can check his code out on [GitHub](https://github.com/tpetricek/Haskell.ParMonad) * [Etage-Graph, data-flow based graph algorithms (3 Apr)][5] Mitar announced the Etage-Graph package, which implements graph algorithms on top of his data-flow framework. He invites us to have a look and see how one might implement known control-flow algorithms in a data-flow manner, which has the appeal of being easy to parallelise. * [stm-chans (4 Apr)][6] The stm-chans library offers a collection of channel types, similar to Control.Concurrent.STM.TChan but with additional features. It offers bounded, closable, and bounded closable FIFO channels, along with a partial TChan compatibility layer. * [timeplot 0.3.0, Eugene Kirpichov (30 Apr)][7] Eugene Kirpichov announced the release of timeplot 0.3.0, a tool to help you visualize arbitrary time-dependent data, e.g. log files, into big picture visualisations. Eugene also linked to a presentation with plenty of graphical examples for the tool and its sister "splot", mostly on cluster computing use cases. The tools follow the basic philosophy of depending neither on the log format (the expected workflow is like `cat log | awk foo | plot`), nor on the type of data (Eugene wants to visualise arbitrary signals). You can also find more information in Eugene's [presentation][8]. Mailing list discussions --------------------------------------------------------------------- * [Weird multi-threading runtime behaviour of single-threaded program with GHC-7.0.3 (1 Apr)][13] Herbert Valerio Riedel has a program which parses a roughly 8 MiB JSON file (with the aeson library) without any use of parallelism or concurrency constructs: just a straightforward, demanding, single-threaded computation. He compiled the program with `-threaded` and ran with `+RTS -N12` on a 12 core machine. By rights, only one core should be doing work but when he looks at the output of `top` it seems like all of them consume a substantial amount of CPU cycle. What's up with the remaining 11? * [A parallelization problem (25 Apr)][14] Wren Ng Thornton has some loopy code that he would like to parallelise. He was hoping to use pure parallelism (`par` and friends) instead of explicit concurrency because he's concerned that "lightweight as Haskell's threads are [...] the overhead would swamp the benefits." Wren's code has an outer and inner loop fleshing out a map of maps. Wren wants to speed up his inner loop, which he thinks should be possible because the keys in the inner map are independent of each other. * [Multi agent system (2 Apr)][15] Yves Parès wants to build a simple game with multiple agents that communicate with each other. He asked if it was reasonable to launch one Haskell thread per agent and have them communicate over Chans (he will have something like 200 agents at a time). Felipe Lessa responded that hundreds of agents should be no problem but hundreds of thousands of agents might not work. * [Using DPH (12 Apr)][16] When experimenting with Repa and DPH, Wilfried Kirschenmann encountered strange compiler errors when parallelising his code; in particular, a strange pattern match failure in a do expression. Wilfried supplied a small demonstrator computing the norm of a vector. Ben Lippmeier responded with help and also a reminder that Repa and DPH are separate projects (the latter still being in the "research prototype" stage). Ben's version with more tweaks from Wilfried was 15x faster than his original (non-parallel?) version but still 15x slower than the C version. Parallelising the Repa sum and fold functions should help. * [Service Component Architecture and Distributed Haskell (13 Apr)][17] James Keats noticed the recent talk about distributed Haskell and wished to see "interest from an experienced member of the Haskell community in implementing Haskell components with SCA/[Tuscany][18]", as this would help him to use Haskell in the same project with Java and Scala. * [parallel-haskell mailing list (14 Apr)][19] Eric Kow announced the parallel-haskell mailing list and provided instructions for subscribing to the list. Whereas the Haskell Cafe list and Stack Overflow are the best places to ask your parallelism and concurrency questions, the parallel-haskell list is a great place to follow and discuss the research. * [Questioning seq (14 Apr)][20] Among other questions about `seq`, Andrew Coppin asked how `pseq` was different from it. Austin Seipp responded that while pseq and seq are semantically equivalent, (A) `pseq` is only strict in its first argument whereas `seq` is strict in both and (B) `pseq` guarantees the order of evaluation so that `pseq a b` means `a` will be strictly evaluated before `b` whereas for the purpose of potential optimisations `seq` does not. Albert Y. C. Lai provided a short example showing that "there are non-unique evaluation orders to fulfill the mere strictness promise of `seq`". * [select(2) or poll(2)-like function? (17 Apr)][21] Matthias Kilian wanted to know if the Haskell standard libraries had anything like a select or poll like function. Answering the immediate question, Don Stewart pointed to [Control.Concurrent.threadWaitRead][22]. Meanwhile, the thread opened into a long discussion on using high-level Haskell concurrency constructs vs. low-level polling. For background, `select` (along with variants like poll, epoll, kqueue, etc) is a system-call which is often used for asynchronous IO, concurrently doing some processing work while some IO operation is underway (Matthias' use case is "networking stuff listening on v4 and v6 sockets at the same time"). A typical way of using "select" or its cousins would be to implement an event-driven programming model with a "select loop": sleeping until some condition occurs on a file descriptor and, when woken, executing the appropriate bit of code depending on the file descriptor and the condition. Some programmers opt for this approach because they believe using processes and OS threads would be too inefficient. Ertugrul Soeylemez and others argue that this is unnecessary in Haskell because Haskell threads are so lightweight (epoll under the hood); we can just stick with high-level concurrency constructs and trust the compiler and RTS to be smarter than us. On the other hand, Mike Meyer is sceptical about the scalability and robustness of this solution. The sort of code Mike wants to write is for systems "that run 7x24 for weeks or even months on end [where] [h]ardware hiccups, network failures, bogus input, hung clients, etc. are all just facts of life." Using `select` loops in his experience is not about efficiency, but avoiding the problems that arise from using high-level concurrency constructs in other languages. He favours to achieve concurrency with a "more robust and understandable" approach using separate Unix processes and an event-driven programming model. So far the only high-level approach Mike has found that provides for the sort of scalability is Eiffel's [SCOOP][23] How does Haskell stack up? And what about Haskell for the Cloud? * [Killing threads in foreign calls. (17 Apr)][24] Jason Dusek is building an application using Postgres for storage (with the help of the libpq binding on Hackage). He would like to kill off threads for queries that take too long to run, but trying Control.Concurrent.killThread seems not to work. This turns out to be a fairly non-trivial problem: most C code is not written to gracefully handle things like its underlying OS thread being killed off. The solution is to use whatever graceful cancellation mechanism is supplied by the foreign library; the PGCancel procedure in Jason's case. * [Painless parallelization. (19 Apr)][25] Grigory Sarnitskiy believes that parallel programming is actually easier than sequential programming because it allows one "to avoid sophisticated algorithms that were developed to gain performance on sequential architecture". So what are his options (preferably "release state" for writing pure functional parallel code with a Haskellish level of abstraction? Mats Rauhala pointed Grigory to the use of `par` and `pseq`, and the RWH chapter on parallelism and concurrency. Don Stewart followed up with a list of options: * the "parallel" package Repa (parallel arrays) * DPH (experimental) * using concurrency Grigory's question also prompted Eric Kow to prioritise the [Parallel Haskell portal][26]. Hopefully it will give us a standard resource to point new parallel Haskellers like Grigory to. Stack Overflow ---------------------------------------------------------------------- * [Howto kill a thread in Haskell](http://stackoverflow.com/questions/6185189/howto-kill-a-thread-in-… * [Comparing Haskell threads to kernel threads - is my benchmark viable?](http://stackoverflow.com/questions/5926501/comparing-haskell-threa… * [Fair concurrent `map` function in haskell?](http://stackoverflow.com/questions/5942615/fair-concurrent-map-fu… * [Program crashing when trying to create multiple threads](http://stackoverflow.com/questions/5935852/program-crashing-when-t… * [A way to form a 'select' on MVars without polling.](http://stackoverflow.com/questions/5879128/a-way-to-form-a-select… * [Haskell lightweight threads overhead and use on multicores](http://stackoverflow.com/questions/5847642/haskell-lightweight-… * [Haskell repa - mapping with indices](http://stackoverflow.com/questions/6242442/haskell-repa-mapping-wi… * [Do Accelerate and Repa have different use cases?](http://stackoverflow.com/questions/6260263/do-accelerate-and-repa-h… Help and feedback ---------------------------------------------------------------------- Got something for the digest? Send us an email at <parallel(a)well-typed.com>. We're particularly interested in short parallelism/concurrency puzzles, and cool projects for featured code. Other comments and feedback (criticism and corrections especially!) would be welcome too. [1]: http://community.haskell.org/~simonmar/par-tutorial.pdf [2]: http://www.haskell.org/haskellwiki/Numeric_Haskell:_A_Repa_Tutorial [3]: http://www.economist.com/node/18750706?story_id=18750706 [4]: http://tomasp.net/blog/speculative-par-monad.aspx [5]: http://www.haskell.org/pipermail/haskell-cafe/2011-April/090736.html [6]: http://www.haskell.org/pipermail/haskell-cafe/2011-April/090743.html [7]: http://www.haskell.org/pipermail/haskell-cafe/2011-April/091520.html [8]: http://jkff.info/presentations/two-visualization-tools.pdf [9]: http://hackage.haskell.org/package/repa [10]: http://disciple-devel.blogspot.com/2011/03/real-time-edge-detection-in-hask… [11]: http://www.well-typed.com/blog/54 [12]: http://en.wikipedia.org/wiki/Canny_edge_detector [13]: http://www.haskell.org/pipermail/haskell-cafe/2011-April/090673.html [14]: http://www.haskell.org/pipermail/haskell-cafe/2011-April/091325.html [15]: http://www.haskell.org/pipermail/haskell-cafe/2011-April/090708.html [16]: http://www.haskell.org/pipermail/haskell-cafe/2011-April/090970.html [17]: http://www.haskell.org/pipermail/haskell-cafe/2011-April/091014.html [18]: http://en.wikipedia.org/wiki/Apache_Tuscany [19]: http://www.haskell.org/pipermail/haskell-cafe/2011-April/091039.html [20]: http://www.haskell.org/pipermail/haskell-cafe/2011-April/091040.html [21]: http://www.haskell.org/pipermail/haskell/2011-April/022730.html [22]: http://hackage.haskell.org/packages/archive/base/latest/doc/html/Control-Co… [23]: http://scoop.origo.ethz.ch/ [24]: http://www.haskell.org/pipermail/haskell-cafe/2011-April/091089.html [25]: http://www.haskell.org/pipermail/haskell-cafe/2011-April/091134.html [26]: http://haskell.org/haskellwiki/Parallel [27]: http://www.haskell.org/haskellwiki/Parallel_GHC_Project

1 0

Data.Map: Values to keys and keys to values
by Dmitri O.Kondratiev 16 Jun '11

16 Jun '11

Hi, Data.Map has many great functions, yet I could not find the one that allows from one map create another map where keys are values and values are keys of the first one. Something like: transMap:: (Ord k, Ord a) => Map k a -> Map a k Does such function exist? Thanks!

5 6

Re: [Haskell-cafe] Win32: cabal install --prefix=$HOME --user ?
by Dmitri O.Kondratiev 16 Jun '11

16 Jun '11

On Thu, Jun 16, 2011 at 6:18 PM, Ryan Yates <fryguybob(a)gmail.com> wrote: > There is a nice table in the cabal docs that explains how prefix gets used: > > http://www.haskell.org/ghc/docs/7.0.4/html/Cabal/builders.html#simple-paths > > For Vista and above C:\Documents and settings\myusername\ is > C:\Users\myusername. The equivalent to $HOME on Windows would be > $USERPROFILE but the syntax of expanding an environment variable is > going to depend on the shell you are using: > > cmd window: cabal install --prefix=%USERPROFILE% --user > PowerShell: cabal install --prefix=${env:USERPROFILE} --user > msys window: cabal install --prefix=$USERPROFILE --user > > Note that msys does define $HOME and it is a different physical path > than $USERPROFILE. > > Ryan, thanks! This win32 $HOME story is clear now. And why not just use: "cabal install" instead of: "cabal install --prefix=%USERPROFILE% --user" for win32 platform? Where in this case "cabal install" root will be?

2 1

Win32: cabal install --prefix=$HOME --user ?
by Dmitri O.Kondratiev 16 Jun '11

16 Jun '11

On win32 "cabal install --prefix=$HOME --user" fails: cabal install --prefix=$HOME --user Resolving dependencies... Configuring split-0.1.4... cabal: expected an absolute directory name for --prefix: $HOME cabal: Error: some packages failed to install: split-0.1.4 failed during the configure step. The exception was: ExitFailure 1 What is the right equivalent of "cabal install --prefix=$HOME --user" on Win32?

2 1

Data Type Inheritance ala OO - Inheritence -- howto best in Haskell ?
by kaffeepause73 16 Jun '11

16 Jun '11

Dear all, I'm created a timeSignal datatype as container around a "Vector Double" data type (see simple code below) and subsequently started to instanciate Num & Eq to be able to perform operations on it. Additionally I want store ifno like an index, time information and eventually an inheritence log (the log is not yet in there). As I will in the end need up to 10 different datatypes, however using slightly different content (time signal, single value, distribution, ...) I ask myself, how I could define a super data-type with sub-data-types to inherit, but then also overload certain functions (like u would do in OO). What is best way in haskell to achieve this ? (I'm unsure wether haskell classes are what I'm looking for) Cheers Phil ########## Code below import qualified Data.Vector.Unboxed as V data TimeSig = TimeSig Int Double (V.Vector Double) -- signal Index timeStep data getVect :: TimeSig -> (V.Vector Double) getVect (TimeSig idx dt vect)= vect getIdx :: TimeSig -> Int getIdx (TimeSig idx dt vect) = idx getdt :: TimeSig -> Double getdt (TimeSig idx dt vect) = dt pzipWith :: (Double -> Double -> Double) -> TimeSig -> TimeSig -> TimeSig pzipWith f p1 p2 = TimeSig idx dt vect where vect = V.zipWith f (getVect p1) (getVect p2) idx = getIdx p1 dt = getdt p1 pmap :: (Double -> Double) -> TimeSig -> TimeSig pmap f p = TimeSig (getIdx p) (getdt p) (V.map f (getVect p)) instance Num TimeSig where (+) p1 p2 = pzipWith (+) p1 p2 (-) p1 p2 = pzipWith (-) p1 p2 negate p1 = pmap negate p1 abs p1 = pmap abs p1 (*) p1 p2 = pzipWith (*) p1 p2 instance Eq TimeSig where (==) p1 p2 = (==) (getVect p1) (getVect p2) instance Show TimeSig where show (TimeSig idx dt vect) = "TimeSignal Nr: " ++ show idx ++ " dt: " ++ show dt ++ " val:" ++ show vect main = do let p = TimeSig 5 0.1 (V.fromList [0..10::Double]) putStrLn (show p) putStrLn (show (p+p)) -- View this message in context: http://haskell.1045720.n5.nabble.com/Data-Type-Inheritance-ala-OO-Inheriten… Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

1 0

Best platform for development with GHC?
by Dmitri O.Kondratiev 16 Jun '11

16 Jun '11

Which platform - Mac OS X, Linux or Win32 is best for development with GHC today? How are things with Ubuntu? It was quite a while already that I used Haskell on Linux. Today I have to code on Win32 and Mac OS X. Installing extra libraries caused most of the pains for me on Win32 - for example GTK and Gnuplot is not easy to install on Win32. Installing GTK on Max OSX is also a hard work, but no problems with Gnuplot at all. Haskell mode for Emacs works fine on Mac OS X, but only to some extent on Win32. I have not managed to start GHCi in Emacs buffer on Win32. Haskell Win32 Platform also has a weird bug of missing documentation on some widely used modules from Haskell Hierarchical Library. I understand that Linux should be a much better environment for integrating with external libraries (just because most of them were originally developed for Linux). I don't want to start religious wars, yet I wonder on what platform Haskell run-time works best and development has minimum obstacles? Thanks!

8 11

Parsing Haskell in Parsec
by Alex Rozenshteyn 16 Jun '11

16 Jun '11

I'm trying to write a parser for a small functional language in Parsec, as part of a larger project of porting this<http://www.cs.jhu.edu/%7Escott/pl/book/dist/>from ocaml to Haskell. I was wondering if there was a parser for Haskell written in Parsec that I could use as a reference. -- Alex R

4 5