- Haskell-Cafe - Haskell.org

Compressed Data.Map for more efficient RAM usage?
by Jeremy Shaw 16 Feb '12

16 Feb '12

Sometimes we want to store very large collection types in RAM -- such as a Data.Map or Data.IxSet. It seems like we could trade-off some speed for space savings by compressing the values in RAM. Lemmih has previously created compact-map: http://hackage.haskell.org/package/compact-map which mightybyte used to create: https://github.com/mightybyte/compact-ixset compact-map converts the Haskell values to a more compact binary representation. But could we do even better by compressing the bytestrings? Here is a useless implementation: http://hpaste.org/63836 That version compresses each value by itself. But, that is probably going to be worse RAM usage, not better. I think what we really need to do is to store a dictionary in CMap that is used to compress all the ByteString values. That way if the same string appears in 10000 entries, they can all be compressed using the same compression code. One question is, how much would this benefit us? As an experiment I tried compressing one checkpoint file for real world acid-state app that I am involved with. A checkpoint file contains binary data that is serialized by the SafeCopy library. And it is data that is currently store in an IxSet in RAM. The uncompressed checkpoint file is 115MB. The compressed checkpoint file is 26MB. A checkpoint file probably contains more redundancy than an equivalent compressed IxSet because in addition to the values it also includes version tags and other easily compressed data. But, those numbers do look promising. At the very least, they do not rule out the possibility of some big savings. I do not have time to explore this anymore. But I think it could be a fun project for someone to work on. ;) I imagine a prototype with a shared dictionary could be hacked up in a few days. A bit more work would be required to document it, memory profile it, etc. If done well, we should be able to reuse the incremental compression code in Data.Map, Data.Set, Data.IxSet, HiggsSet, and other places. But, just focusing on Data.Map is a good start. I will create a bug in this bug tracker that links back to this message, http://code.google.com/p/happstack/issues/list - jeremy

3 4

Monadic bind fixity: do vs (>>)
by Michael Baikov 16 Feb '12

16 Feb '12

Most docs ([1], [2]) about do-notation syntactic sugar tends to describe following expressions as equivalent: "do { a; b; c }" and "a >> b >> c", but they are not: first one gets de-sugared into "a >> (b >> c)", second one is equivalent to "(a >> b) >> c", because (>>) is declared using infixl. This should not be a problem, monadic law of Associativity states that "(m >>= f) >>= g ≡ m >>= (\x -> f x >>= g)", but this leads to generating different Core output and may lead to different performance (and it does, do { Just 4 ; Just 4 ... } is about 2% faster than Just 4 >> Just 4 >> ... if compiled with -O0, but 13% slower when compiled with -O11) This also leads to lots of fun when your monad breaks Associativity law :) Is there any reasons except for those 13% speed gain for this? [1]: http://en.wikibooks.org/wiki/Haskell/do_Notation [2]: http://book.realworldhaskell.org/read/monads.html#monads.dot

2 1

ANNOUNCE: system-filepath 0.4.5 and system-fileio 0.3.4
by John Millikin 16 Feb '12

16 Feb '12

Both packages now have much-improved support for non-UTF8 paths on POSIX systems. There are no significant changes to Windows support in this release. system-filepath 0.4.5: Hackage: http://hackage.haskell.org/package/system-filepath-0.4.5 API reference: https://john-millikin.com/software/haskell-filesystem/reference/system-file… system-fileio 0.3.4: Hackage: http://hackage.haskell.org/package/system-fileio-0.3.4 API reference: https://john-millikin.com/software/haskell-filesystem/reference/system-file… ----- In GHC 7.2 and later, file path handling in the platform libraries was changed to treat all paths as text (encoded according to locale). This does not work well on POSIX systems, because POSIX paths are byte sequences. There is no guarantee that any particular path will be valid in the user's locale encoding. system-filepath and system-fileio were modified to partially support this new behavior, but because the underlying libraries were unable to represent certain paths, they were still "broken" when built with GHC 7.2+. The changes in this release mean that they are now fully compatible (to the best of my knowledge) with GHC 7.2 and 7.4. Important changes: * system-filepath has been converted from GHC's escaping rules to its own, more compatible rules. This lets it support file paths that cannot be represented in GHC 7.2's escape format. * The POSIX layer of system-fileio has been completely rewritten to use the FFI, rather than System.Directory. This allows it to work with arbitrary POSIX paths, including those that GHC itself cannot handle. The Windows layer still uses System.Directory, since it seems to work properly. * The POSIX implementation of createTree will no longer recurse into directory symlinks that it does not have permission to remove. This is a change in behavior from the directory package's implementation. See http://www.haskell.org/pipermail/haskell-cafe/2012-January/098911.html for details and the reasoning behind the change. Since Windows does not support symlinks, I have not modified the Windows implementation (which uses removeDirectoryRecursive).

5 16

Transactional memory going mainstream with Intel Haswell
by Ben 16 Feb '12

16 Feb '12

http://arstechnica.com/business/news/2012/02/transactional-memory-going-mai… would any haskell STM expert care to comment on the possibilities of hardware acceleration? best, ben

3 2

GSoc-2012: Lock-free Data Structures
by Sergiu Ivanov 16 Feb '12

16 Feb '12

Hello, On Thu, Feb 16, 2012 at 5:40 AM, Ryan Newton <rrnewton(a)gmail.com> wrote: > I'm interested in mentoring any projects related to concurrent data > structure implementation. Is it too late to propose new projects? > > http://parfunk.blogspot.com/2012/02/potential-gsoc-haskell-lock-free-data.h… This project idea sounds very cool to me :-) Could you please suggest a starting point in approaching it? I cannot view the article [0], since I don't have an active ACM subscription. I've seen the link [1], so, probably, I could contribute some patches to it? I'm not sure whether this is good, but this is not the first project idea that grabs my attention, so, frankly, my principal goal now would be getting the hang of it. Had I had the time, I would have tried to contribute to all Haskell libraries I like (sigh) Sergiu [0] http://cacm.acm.org/magazines/2011/3/105308-data-structures-in-the-multicor… [1] https://github.com/rrnewton/haskell-lockfree-queue

1 0

Behavior of -threaded in GHC 7.4.1?
by Michael Craig 16 Feb '12

16 Feb '12

Hi all, I'm debugging an issue with multithreading and FFI calls in 7.4.1. The code in question is the zeromq3-haskell library, which provides an FFI binding to ZeroMQ. A little background: ZeroMQ gives the programmer "contexts" and "sockets". Contexts are thread-safe and generally used one-per-process, but sockets and not thread-safe so they're generally used one-per-thread. Have a look at the code in this gist: https://gist.github.com/1829190 It's just a server that prints requests and replies with "Hello", and a client that sends the requests ["1", "2", ..., "10"] and prints the responses. Despite the fact that ZMQ sockets are not thread-safe, it was possible to compile and run this code with -threaded under 7.0.4. Using MVars or some other locking mechanism, it was even possible to use the same socket from multiple parallel threads. (As long as the socket was not actually used in parallel by multiple threads, all was well.) In 7.4.1, the code will only run if compiled without -threaded. With -threaded, it croaks with an "operation on non-socket" error, which generally refers to a socket that's either been closed or I've dug through the code in zeromq3-haskell and haven't found anything suspicious looking. Before I go digging into libzmq itself, can somebody assure me that nothing has changed in 7.4.1 with regard to -threaded or the FFI that might cause this breakage? Cheers, Mike Craig

1 2

New GSoC on Concurrent Data Structures -- was: How do I get official feedback (ratings) on my GSoC proposal?
by Ryan Newton 16 Feb '12

16 Feb '12

Neat, thanks Johan! (I had no idea it was so easy to post to Reddit.) I also put the proposed project on the trac: http://hackage.haskell.org/trac/summer-of-code/ticket/1608 So feel free to contact me, interested students! Cheers, -Ryan On Thu, Feb 16, 2012 at 12:51 AM, Johan Tibell <johan.tibell(a)gmail.com> wrote: > On Wed, Feb 15, 2012 at 7:40 PM, Ryan Newton <rrnewton(a)gmail.com> wrote: >> I'm interested in mentoring any projects related to concurrent data >> structure implementation. Is it too late to propose new projects? >> >> >> http://parfunk.blogspot.com/2012/02/potential-gsoc-haskell-lock-free-data.h… > > Not all all. It's quite early in fact (I tried to get people to think > about this early on.) I'd also post it to the Haskell reddit to make > sure it gets a bit more exposure (it's kinda buried here in this > thread.) > > -- Johan

1 0

Undocumented cost-centres (.\) using auto-all, and SCC pragma not being honored
by Dan Maftei 16 Feb '12

16 Feb '12

> > 1 When profiling my code with -auto-all, my .prof file names some sub-expressions with a backslash. Cf. below. What are these? e_step e_step.ewords e_step.\ e_step.\.\ e_step.update_counts e_step.fwords My e_step function binds seven expressions inside a let, then uses them in two ugly nested folds. (Yes, very hackish) As you can see, three such expressions are named explicitly (ewords, fwords, and update_counts). But where are the rest? Further, perhaps the backslashes have something to do with the lambda expressions I am using in the two nested folds? 2. A related question: I tried using the SCC pragma instead of auto-all. I added it to all seven expressions inside the let, and to the nested folds. However, only two showed up in the .prof file! How come? Thanks ninestraycats

2 2

Re: [Haskell-cafe] Haskell-Cafe Tag (was: Optimizations and parallel execution in the IO for a small spellchecker)
by JP Moresmau 16 Feb '12

16 Feb '12

I was not aware that it was something a poster was supposed to do, but now I notice that while the messages I get from the list have [Haskell-Cafe] on their subject, the ones I post don't. The Haskell-Cafe info page (http://www.haskell.org/mailman/listinfo/haskell-cafe) does not mention that you should have that tag in the subject. I'm probably a uncouth Frenchman knowing nothing about netiquette, but surely the list software could add such a tag if it was required? JP On Wed, Feb 15, 2012 at 8:14 PM, Paul Sujkov <psujkov(a)gmail.com> wrote: > Sorry, I've forgotten to add a [Haskell-Cafe] tag for the message. > > > On 15 February 2012 19:33, Paul Sujkov <psujkov(a)gmail.com> wrote: >> >> Hi everyone, >> >> http://hpaste.org/63732 >> >> that's a very simple spellchecker application: it consumes standard Linux >> dictionary, reads a file, and prints out words from that file that are not >> on the dictionary. I have taken it from a little cross-language benchmark >> and used to benchmark existing hash table implementations available on >> Hackage (with one used in code being the best according to timings). The >> question is: can I go further and effectively execute lookup and (maybe) >> output (line 20 or line 26 in the snippet) in parallel? >> >> I'm not good at all with Haskell parallel packages; I've tried >> monad-parallel (naive implementation eats away all the memory available) and >> parallel (haven't tried Par monad yet), but the last dosn't seem to fit well >> with the IO operations. If anyone can give me any suggestions on how can I >> implement parallel execution, or any thoughts on further sequential >> optimizations, it would be deeply appreciated. >> >> -- >> Regards, Paul Sujkov > > > > > -- > Regards, Paul Sujkov > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > -- JP Moresmau http://jpmoresmau.blogspot.com/

4 4

How do I get official feedback (ratings) on my GSoC proposal?
by Greg Weber 16 Feb '12

16 Feb '12

Other than changing the status myself, how do I get a priority attached to my GSoC proposal?

4 6