February 2010 - Haskell-Cafe

Optimizing hash array mapped tries
by Edward Z. Yang 01 Mar '10

01 Mar '10

Hello all, I spent this weekend attempting to impement Phil Bagwell's Hash Array Mapped Tries in Haskell. You can view the fruits of this work at this repository: http://github.com/ezyang/hamt Unfortunately, I'm getting pretty abysmal performance out of the implementation I wrote, so I'm hoping to get some performance tuning insights here. My cost centers look about like this: time% alloc% i-Full-update HAMT 29.1 31.4 lookup' HAMT 13.7 4.3 main Main 12.8 19.7 subkey HAMT 11.5 10.0 i-Bitmap HAMT 9.4 12.0 i-Full HAMT 8.1 12.9 insert' HAMT 5.1 0.6 popCount PopCount 4.7 1.0 And my GC stats look like: ./HAMTTest 256000 +RTS -t 275576630962922 <<ghc: 410718260 bytes, 788 GCs, 19646424/46880276 avg/max bytes residency (9 samples), 138M in use, 0.00 INIT (0.00 elapsed), 1.14 MUT (1.13 elapsed), 1.88 GC (2.00 elapsed) :ghc>> + 0:03.16 ./IntMapTest 256000 +RTS -t -710684043813 <<ghc: 172126372 bytes, 329 GCs, 5552955/10483896 avg/max bytes residency (9 samples), 31M in use, 0.00 INIT (0.00 elapsed), 0.51 MUT (0.51 elapsed), 0.62 GC (0.67 elapsed) :ghc>> + 0:01.18 IntMap is included for comparison. The HAMT does about x3-5 worse than IntMap, and uses about x4 more memory (and gets correspondingly penalized when garbage collection occurs). My observations/suspicions are as such: * i-Full-update essentially copies a 32-size vector, with a change to one element. I think I am getting brutally punished for this, in terms of both memory usage as well as runtime. What I'm curious is whether or not this is intrinsic to the algorithm, or if it's something special that GHC is doing. * Bagwell suggests that each node in the Array-Mapped Trie should take only two words. I think I'm losing another two words to storing bounds information in vector, as well as the costs of boxing (though I can't tell if GHC is boxing or not). I've done some playing around with the data declaration, but it's current form seems to result in the fastest implementation. I wonder if this is what is causing the x4 ballooning of memory, or if it's something else. I haven't tried rewriting the code to use GHC's arrays. * Increasing the heap size seems to generally improve the performance the HAMT; a 1G heap on a 512K sample set reduces the difference to about x1.5-2 slower. It's hard to tell if the memory allocation system is working for or against me. What bothers me is even if I could magically wave away all GC time in HAMT, it would only barely win against IntMap. Maybe the algorithm is simply not as good as a good ole' Patricia Trie; but then again, maybe not. Comments and suggestions greatly appreciated. Thanks, Edward

4 8

Cabal pre-compiled packages
by Diego Souza 01 Mar '10

01 Mar '10

Hi, currently when one install a cabal package it compiles it and then install generated binaries. I wonder whether or not it would be useful to have pre-compiled binaries as many package managers usually do (e.g. apt). I often think that would save some time on the expense of a busier hackage server capable of generating packages for many different platforms. I'm particularly thinking on the following scenario: suppose that you have code that is ready for production. If cabal supported pre-compiled binaries, there is no need to install ghc or eventually any other compiler, just runtime environment and eventually cabal. I must say that I have no experience in doing this in Haskell (just personal/small projects), so I suppose one have to generate binaries and use other sort of package manager to deploy code to production (which sounds reasonable as well). Thus, if the assumption is correct, cabal is a development tool, not something one could to only deploy runtime-only packages. I also would appreciate if others could share how usually this is managed. Best Regards, ~dsouza

5 5

View patterns
by Andrew Coppin 01 Mar '10

01 Mar '10

One somewhat neat thing about Haskell is that you can say case list of [[x], [y,_], [z,_,_]] -> x + y + z _ -> 0 In Java, you'd have to write something like if (list.length() == 3) { List t1 = list.at(0); if (t1.length() == 1) { int x = t1.at(0); List t2 = list.at(1); if (t2.length() == 2) ... I can't even be bothered to finish typing all that lot! However, as somebody pointed out, the Java version is polymorphic. Assuming that length() is defined for multiple types of container, the Java version works with lists, arrays, sets, etc. If you try to do this in Haskell, you end up with case size c of 3 -> case (c ! 0, c ! 1, c ! 2) of (xs, ys, zs) | size x == 1 && size y == 2 & size z == 3 -> (xs ! 0) + (ys ! 0) + (zs ! 0) _ -> 0 _ -> 0 or similar. Which is shorter than Java, but nowhere near as nice as the original list-only version. Now I was under the impression that "view patterns" fix this problem, but it seems they don't: case c of (size -> 3) -> case (c ! 0, c ! 1, c ! 2) of (size -> 1, size -> 2, size -> 3) -> (c ! 0 ! 0) + (c ! 1 ! 0) + (c ! 2 ! 0) Any suggestions?

5 5

OpenSUSE 11.2
by Andrew Coppin 28 Feb '10

28 Feb '10

OK, I imagined to install OpenSUSE 11.2. However, I can't find a way to make it install either GHC or the Haskell Platform. A quick Google search turns up a folder on download.opensuse.org which is stuffed full of Haskell stuff, yet no ammount of prodding YaST will convince it that it's possible to install anything remotely Haskell-related. (Now I remember why I don't use Linux much...) Does anybody know how to install this stuff on OpenSUSE? Alternatively, does anybody know of an alternative Linux distribution where this kind of thing is likely to work better? (I think I've got a Debian ISO somewhere - but IME everything on Debian is always 8 years old.)

4 17

Lists of Existential DT
by Yves Parès 28 Feb '10

28 Feb '10

Hello! I have a class Drawable, and some datatypes which are instances of it, and I would like to be able to draw them all at once! drawMany window [image, text, otherImage] I think the type of the function drawMany would be: drawMany :: Window -> [forall a. (Drawable a) => a] -> IO () However it doesn't work. I know one solution is to make a new datatype (e.g. DrawableObj) which will be: data DrawableObj = forall a (Drawable a) => DrawableObj a And then declare drawMany as: drawMany :: Window -> [DrawableObj] -> IO () But to use it I have to wrap up myself every drawable in a DrawableObj: drawMany window [DrawableObj image, DrawableObj text, DrawableObj otherImage] Is there another more suitable way to handle a list of drawables? ----- Yves Parès Live long and prosper -- View this message in context: http://old.nabble.com/Lists-of-Existential-DT-tp27735354p27735354.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

6 6

native threads vs. -threaded
by Donn Cave 28 Feb '10

28 Feb '10

I've sketched out a Haskell interface to a C++ toolkit that uses threads. It's the Haiku (BeOS) platform API (BeOS is an obscure OS from the '90s, Haiku is a pretty faithful recent open source re-implementation.) The API is fairly obvious and I imagine much like others that support windowed graphic interfaces. You have your Window class that spawns a thread, and various virtual methods of that class support program interface with the events involving that window. The curious thing is that I can get this to work with my example program only if it is NOT linked with -threaded. If linked with -threaded, when the application comes up I have 4 threads: the main thread and window thread, and two threads apparently created by the Haskell runtime. Shortly (but not immediately) after the first callback from the window thread, the window thread quietly dies. Callbacks from the main thread work fine. Linked without -threaded, I have only the 2 natural threads, and the window thread can call back apparently without problems. I imagine I'm at fault somewhere in this, since I am also responsible for the GHC port to Haiku, but just wondering if this suggests an obvious course of inquiry to anyone. I assume it's not working as intended, as from the documentation I would rather have guessed that -thread would be required in this situation. thanks! Donn Cave, donn(a)avvanta.com

2 2

Cabal will not find HaXml
by Mads Lindstrøm 28 Feb '10

28 Feb '10

Hi When I do: > cabal list --simple-output | grep -i "HaXml 1.20" I get: > HaXml 1.20 > HaXml 1.20.1 > HaXml 1.20.2 But when running: > runhaskell Setup.hs configure I get: > Configuring XrcAccessors-0.0... > Setup.hs: At least the following dependencies are missing: > HaXml -any My cabal file looks like: <snip> Executable XrcAccessors Main-is: XrcAccessors.hs Build-Depends: base==3.0.*, pretty==1.0.*, HaXml hs-source-dirs: src </snip> This is very confusing to me. Why will Cabal not find HaXml when running Setup.hs, but do find it when running "cabal list" ? My Setup.hs looks like: > import Distribution.Simple > main = defaultMain I have tried reinstalling HaXml, but that do not help. I have noticed one thing though, when doing: > ghc-pkg I get output like: <snip> /home/ghc6103/lib/ghc-6.10.3/./package.conf: Cabal-1.6.0.3, HUnit-1.2.0.3, QuickCheck-1.2.0.0, array-0.2.0.0, base-3.0.3.1, base-4.1.0.0, bytestring-0.9.1.4, containers-0.2.0.1, directory-1.0.0.3, (dph-base-0.3), (dph-par-0.3), </snip> <snip> /home/ghc6103/.ghc/x86_64-linux-6.10.3/package.conf: Cabal-1.6.0.2, Cabal-1.8.0.2, Diff-0.1.2, HDBC-2.1.1, HDBC-odbc-1.1.6.0, HDBC-odbc-2.1.0.0, HTTP-4000.0.4, HUnit-1.2.2.1, HaXml-1.20.2, MetaHDBC-0.1.0, QuickCheck-2.1.0.3, SQLLib-0.0, </snip> That is, HaXml shows itself in the /home/ghc6103/.ghc/x86_64-linux-6.10.3/package.conf list, but not in the /home/ghc6103/.ghc/x86_64-linux-6.10.3/package.conf . Is this the problem and how do I fix it? Greetings, Mads Lindstrøm

2 2

listing mountpoints and getting their properties in Haskell
by Eugene Dzhurinsky 28 Feb '10

28 Feb '10

Hello! I need to list all currently mounted filesystems and get some stats like total space, free space, mount point and physical device. Is there any library capable of obtaining such information from OS itself? Parsing output of 'df' is locale-dependent and error-prone (because of locale settings, output settings etc). Thank you in advance. -- Eugene N Dzhurinsky

6 6

Haskell version of "Monad Transformers and Modular Interpreters"
by Günther Schmidt 28 Feb '10

28 Feb '10

Hello, I come across the paper "Monad Transformers and Modular Interpreters" (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.268) alas the code is in Gofer and I'm not certain how all of it translates to Haskell. Are there other papers out there that translate this to Haskell? Günther

2 1

jQuery is a monad
by Graham Klyne 28 Feb '10

28 Feb '10

Nice blog post: http://importantshock.wordpress.com/2009/01/18/jquery-is-a-monad/ #g

1 0