- Haskell-Cafe - Haskell.org

is 256M RAM insufficient for a 20 million element Int/Int map?
by Thomas Hartman 20 Oct '08

20 Oct '08

{-# LANGUAGE BangPatterns #-} import qualified Data.Map as M import Debug.Trace {- I'm trying to run a HAppS web site with a large amount of data: stress testing happstutorial.com. Well, 20 million records doesn't sound that large by today's standards, but anyway that's my goal for now. I have a standard Data.Map.Map as the base structure for one of my macid data tables (jobs), but I noticed something that is probably causing problems for me. Even a simple 20 million record with int/int key values causes an out of memory error for me in ghci, on a computer with 256M of ram. I'm wondering if there is a data structure that might be more suitable for large recordsets. Or do you just have to use a database, or some sort of file-based serialization, once your records are in the millions? Or is this some weird subtlety of lazy evalution, or some other haskell gotcha? -} size = 2 * 10^7 -- out of memory error t = (M.! size) . myFromList . map (\i->(i,i)) $ [1..size] -- Lists are no problem {- *Main> :! time ghc -e tL testMap.hs (20000000,20000000) 3.38user 0.09system 0:03.53elapsed 98%CPU (0avgtext+0avgdata 0maxresident)k -} tL = (!! (size-1)) . map (\i->(i,i)) $ [1..size] t2 = (M.fromList . map (\i->(i,i)) $ [1..10] ) M.\\ (M.fromList . map (\i->(i,i)) $ [6..15]) -- does this evaluate all of list l, or just whnf? myFromList (!l) = M.fromList l

11 18

Re: [Haskell-cafe] is 256M RAM insufficient for a 20 millionelement Int/Int map?
by Max Bolingbroke 20 Oct '08

20 Oct '08

2008/10/20 Don Stewart <dons(a)galois.com>: > claus.reinke: >> Ideally, I'd just like to indicate the strictness in the types (hint to ghc >> hackers: 'Data.Map.Map Int !Int' and '[!a]' would really be useful!-), > In general, being able to specialise polymorphic structures so they look like unpacked > monomorphic ones would be awesome. > > (!Int, !Bool) -> (,) {-# UNPACK #-}!Int {-# UNPACK #-}!Bool I spent some time thinking about how one might actually go about implementing this in GHC today, and came to the conclusion that it interacts far too badly with separate compilation. In an ideal world, you know which specialisations to generate for the data structure when compiling it in the first place. You would then of course generate the appropriate specialisations for all subsequent polymorphic function definitions that use the speciliased type ((,), IntMap or whatever), so you don't lose the ability to apply your unpacked version to a function of type like (a, b) -> a - see http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.8984 that Claus pointed to. But we don't have that information yet at the point where we compile a data definition... The CLR has a similar problem but gets away with it because it has a JIT compiler that can see the original definitions of classes / methods and instantiate them at the necessary types at runtime (see http://research.microsoft.com/~akenn/generics/space2004generics.pdf) One possible approach for GHC would be to generate all possible specializations for a datatype + functions when compiling a module. This sounds bad, but actually you only need to cater for at most three unboxed field sizes: 1) 32 bit (Int#, Word#, Float#, Addr#) 2) 64 bit (Int64#, Word64#) 3) Usually 64 bit (Double#) Of course, if you have a type like (,,,) with 4 type arguments you still have to potentially generate 3^4 specialisations (and corresponding functions!) so this /can/ get bad quickly :-). This is also sort of a hack, in that it crucially relies on the fact that unboxed tuples don't really make sense as type arguments yet. This is because types like (# Int, Bool #) -> Int are rejected by the compiler - unboxed tuples can only occur on the right of function arrows. However, this is just a technical limitation, and were it to be lifted it might make sense to be able to instantiate data types at unboxed tuple types, blowing this scheme out of the water. You could also export the entire definition of functions+data structures you might need to specialise across module boundaries, and generate specialisations where they are needed, but this can lead to redundant code generation with diamond dependencies (see the Syme/Kennedy paper - though I don't think their problem with redundant type descriptors applies to Haskell, making it easier to apply) and would bloat .hi files. This might still be the best way to go about it, should someone choose to implement it,. A further alternative would be to just compile every function once, but pass something like a dictionary to every function to tell it how to handle its own arguments (how much stuff to pop off the stack etc). Clean ,but the huge runtime overhead of this approach kind of defeats the point of using unboxed types in the first place. A final alternative would be to somehow recompile a module with the desired instantiation if it turned out not to contain it. But this could potentially lead to greatly increased compile times... So, I can't really see a clean way to go about this without going the whole hog and turning GHC into a whole-program compiler :-) Cheers, Max

1 0

Questions for Free!
by Creighton Hogg 20 Oct '08

20 Oct '08

Hello Haskellers, So I have a bit of a follow up question after reading Theorems For Free! this weekend. There's a throw away comment near the beginning about how you can recast the results into category theoretic form, but using lax natural transformations. Now I'm assuming this means a natural transformation but where the "naturality" square holds only up to isomorphism instead of equality, but is that correct? Also, why would you need such a condition? Cheers, Creighton

1 0

Error building GHC 6.8.3: "version of ../../compiler/stage1/ghc-inplace could not be determined"
by Devin Mullins 20 Oct '08

20 Oct '08

Hi, I'm trying to build 6.8.3 on Linux PowerPC, based on an old binary of 6.4 (latest build for this arch that I found). stage1 seems to have built, but from there, building libraries almost immediately fails: > make -C libraries all > make[1]: Entering directory `/home/twifkak/arch/ghc/src/ghc-6.8.3/libraries' > rm -f -f stamp/configure.library.*.base base/unbuildable > ( cd base && setup/Setup configure \ > --enable-library-profiling --enable-split-objs \ > --prefix=/NONEXISTANT \ > --bindir=/NONEXISTANT \ > --libdir=/NONEXISTANT \ > --libsubdir='$pkgid' \ > --libexecdir=/NONEXISTANT \ > --datadir=/NONEXISTANT \ > --docdir=/NONEXISTANT \ > --htmldir=/NONEXISTANT \ > --interfacedir=/NONEXISTANT \ > --with-compiler=../../compiler/stage1/ghc-inplace \ > --with-hc-pkg=../../utils/ghc-pkg/ghc-pkg-inplace \ > --with-hsc2hs=../../utils/hsc2hs/hsc2hs-inplace \ > --with-ld=/usr/bin/ld \ > --haddock-options="--use-contents=../index.html \ > --use-index=../doc-index.html" \ > --configure-option='--prefix=/usr' --configure-option='CFLAGS=-mtune=powerpc -O2 -pipe -mpowerpc-gfxopt' \ > --configure-option=--with-cc=gcc ) \ > && touch stamp/configure.library.build-profiling-splitting.base || touch base/unbuildable > Configuring base-3.0.2.0... > Setup: ghc version >=6.2 is required but the version of ../../compiler/stage1/ghc-inplace could not be determined. > if ifBuildable/ifBuildable base; then \ > cd base && \ > cmp -s ../Makefile.local Makefile.local || cp ../Makefile.local .; \ > mv GNUmakefile GNUmakefile.tmp; \ > setup/Setup makefile -f GNUmakefile; \ > cmp -s GNUmakefile GNUmakefile.tmp && mv GNUmakefile.tmp GNUmakefile; \ > make -wr && \ > setup/Setup register --inplace; \ > fi > mv: cannot stat `GNUmakefile': No such file or directory > Setup: error reading dist/setup-config; run "setup configure" command? > > make[2]: Entering directory `/home/twifkak/arch/ghc/src/ghc-6.8.3/libraries/base' > make[2]: *** No targets specified and no makefile found. Stop. > make[2]: Leaving directory `/home/twifkak/arch/ghc/src/ghc-6.8.3/libraries/base' > make[1]: *** [make.library.base] Error 2 > make[1]: Leaving directory `/home/twifkak/arch/ghc/src/ghc-6.8.3/libraries' > make: *** [stage1] Error 2 (This particular transcript is from an unclean build, but the same error occurred on a freshly untarred ghc.) The subsequent errors seems to stem from the root one of being unable to configure: > [twifkak@ponyride base]$ setup/Setup configure -v3 > Configuring base-3.0.2.0... > Creating dist (and its parents) > /home/twifkak/usr/bin/ghc --numeric-version > Warning: cannot determine version of /home/twifkak/usr/bin/ghc : > "" > Setup: ghc version >=6.2 is required but the version of /home/twifkak/usr/bin/ghc could not be determined. > [twifkak@ponyride base]$ ghc --numeric-version > 6.4 > [twifkak@ponyride base]$ setup/Setup configure --with-compiler=../../compiler/stage1/ghc-inplace -v3 > Configuring base-3.0.2.0... > Creating dist (and its parents) > ../../compiler/stage1/ghc-inplace --numeric-version > Warning: cannot determine version of ../../compiler/stage1/ghc-inplace : > "" > Setup: ghc version >=6.2 is required but the version of ../../compiler/stage1/ghc-inplace could not be determined. > [twifkak@ponyride base]$ ../../compiler/stage1/ghc-inplace --numeric-version > 6.8.3 What's going wrong? How do I fix it? Is there a better mailing list to ask? Thanks, Devin

2 3

Glut using freeglut and non starndard header / lib location?
by Marc Weber 19 Oct '08

19 Oct '08

Which is the way to install the glut library with non standard header / lib location? I've tried setting CFLAGS before running ./configure ./setup configure and adding the include directory this way include-dirs: include, /nix/store/rz4nfm5qcrjrk0jsr1lxnjwamgxmgip8-freeglut-2.4.0/include All results in checking for GL/glut.h... (cached) no checking GLUT/glut.h usability... no checking GLUT/glut.h presence... no checking for GLUT/glut.h... no configure: error: no GLUT header found, so this package cannot be built The configure script is meant to be run by cabal only? Marc

2 1

Re: [Haskell] Probably a trivial thing for people knowing Haskell
by Paul Johnson 19 Oct '08

19 Oct '08

Friedrich wrote: > Paul Johnson <paul(a)cogito.org.uk> writes: > >> [...] Because file reading is lazy, >> each line is only read when it is to be processed, and then gets >> reaped by the garbage collector. So it all runs in constant memory. >> > Would you mind to elaborate a bit about it. What's so terrible to open > one file after the other, reading it line by line and close the file > thereafter. > Its not wrong, its just more work. Also from a structural point of view its better to separate the code that reads the files from the code that processes the text. The conventional way forces you to mix them. >> (By the way, putting in the top level type declarations helps a lot >> when you make a mistake.) >> > Well I have my problems with that. Probably it comes from using > Languages like Ruby and my special dislike of "typing things" comes > especially from Java, C++ (well C is not "innocent" in that regard > also. > > OK, its a matter of personal preference (although it really does help anyone else reading your code). However I find that if I leave out the top level definitions then type error messages at compile time are much harder to figure out, especially in a big program. So I find that the extra typing pays in the long run. :-/ Paul.

1 0

package question/problem
by Galchin, Vasili 19 Oct '08

19 Oct '08

Hello, I am trying to "cabal install" HSQL. I am using ghc 6.8.2. I get the following error about a non-visible/hidden package (old-time-1.0.0.0): vigalchin@ubuntu:~$ cabal install hsql Resolving dependencies... 'hsql-1.7' is cached. [1 of 1] Compiling Main ( Setup.lhs, dist/setup/Main.o ) Linking dist/setup/setup ... Configuring hsql-1.7... Warning: No 'build-type' specified. If you do not need a custom Setup.hs or ./configure script then use 'build-type: Simple'. Preprocessing library hsql-1.7... Building hsql-1.7... Database/HSQL.hsc:66:7: Could not find module `System.Time': it is a member of package old-time-1.0.0.0, which is hidden cabal: Error: some packages failed to install: hsql-1.7 failed during the building phase. The exception was: exit: ExitFailure 1 vigalchin@ubuntu:~$ I don't see (old-time-1.0.0.0) with parens around it so I am confused: vigalchin@ubuntu:~$ ghc-pkg list /usr/local/lib/ghc-6.8.2/package.conf: Cabal-1.2.3.0, GLUT-2.1.1.1, HUnit-1.2.0.0, OpenGL-2.2.1.1, QuickCheck-1.1.0.0, array-0.1.0.0, base-3.0.1.0, bytestring-0.9.0.1, cgi-3001.1.5.1, containers-0.1.0.1, directory-1.0.0.0, fgl-5.4.1.1, filepath-1.1.0.0, (ghc-6.8.2), haskell-src-1.0.1.1, haskell98-1.0.1.0, hpc-0.5.0.0, html-1.0.1.1, mtl-1.1.0.0, network-2.1.0.0, old-locale-1.0.0.0, old-time-1.0.0.0, packedstring-0.1.0.0, parallel-1.0.0.0, parsec-2.1.0.0, pretty-1.0.0.0, process-1.0.0.0, random-1.0.0.0, readline-1.0.1.0, regex-base-0.72.0.1, regex-compat-0.71.0.1, regex-posix-0.72.0.2, rts-1.0, stm-2.1.1.0, template-haskell-2.2.0.0, time-1.1.2.0, unix-2.3.0.0, xhtml-3000.0.2.1 /home/vigalchin/.ghc/i386-linux-6.8.2/package.conf: Cabal-1.4.0.1, GLFW-0.3, HDBC-1.1.5, HTTP-3001.0.4, MonadRandom-0.1.1, Stream-0.2.6, Takusen-0.8.3, X11-1.4.2, arrows-0.4, binary-0.4.2, category-extras-0.53.5, chp-1.1.0, dlist-0.4.1, event-list-0.0.7, ipc-0.0.3, midi-0.0.6, mtl-1.1.0.1, network-bytestring-0.1.1.2, non-negative-0.0.3, posix-realtime-0.0.0.1, posix-realtime-0.0.0.2, probability-0.2.1, quantum-arrow-0.0.4, unix-2.4.0.0, zlib-0.4.0.4 ?? What is the history of old-time package? Regards, Vasili

6 7

Detecting unused read handles? (was: File handles and pipes)
by Stephen Hicks 19 Oct '08

19 Oct '08

On Sun, Oct 19, 2008 at 1:44 AM, Brandon S. Allbery KF8NH <allbery(a)ece.cmu.edu> wrote: > On 2008 Oct 19, at 1:37, Stephen Hicks wrote: >> >> I'm trying to understand how to get pipes working in Haskell, in >> particular with the revamped System.Process (though I've tried similar >> experiments with System.Posix.IO and Control.Concurrent). >> Specifically I'm trying to concatenate the output of two system calls >> into the input of a third. The following code does not get the job >> done: > > Pipes are perhaps a bit misnamed: if you want to combine the output of two > pipes and funnel it into a third you can't simply "plumb them together", you > need to provide code which reads from the output pipes and writes into the > input pipe. If you don't care about order, forkIO a thread for each output > pipe which reads from the output pipe it's passed and writes to the input > pipe. If order is significant, use mapM/forM to run the output-to-input > code on each handle in turn. Thanks a lot - that seems to work very well, and even scales to large amounts of data nicely (and quickly, with Lazy ByteStrings). I've got one more question now. Suppose I want to do the same thing on the other side, with two processes *receiving* the data. Is there a way to tell whether the first process wants input, and if not, wait for the second process to do anything? That is, suppose I have something like > do (Just inh1, _, _, p1) <- createProcess (shell "echo 1") { std_in = CreatePipe } > -- wait for p1, possibly feeding it some input? > (Just inh2, _, _, p2) <- createProcess (shell "cat") { std_in = CreatePipe } Is there a way to figure out that the "echo 1" process never wanted any input, and therefore not give it any? I looked through all of System.IO and everything seemed to indicate that inh1 was open, even after the process ended. The only indication otherwise was that "hflush inh1" failed with "resource vanished". I guess what I'm asking is I want to "wait until the process p1 is waiting for input and/or terminates", and if it's the latter, move on to the next process in line, before actually doing any hPutStr into the read handles. Is that possible? Thanks, steve

2 1

external sort on hackage Re: [Haskell-cafe] External Sort and unsafeInterleaveIO
by Thomas Hartman 19 Oct '08

19 Oct '08

External sort is on hackage at http://hackage.haskell.org/cgi-bin/hackage-scripts/package/external-sort Ben, I forgot to correct your name, but I will fix it soon. Thomas. 2008/10/11 Ben <midfield(a)gmail.com>: > Fine with me, except my last name is "Lee" not "Midfield." Thanks for > doing this. > > Ben "Midfield" Lee > > On Sat, Oct 11, 2008 at 7:52 AM, Thomas Hartman <tphyahoo(a)gmail.com> wrote: >> I kinda-sorta half-cabalized it at >> >> darcs get http://darcsdump.dreamhosters.com/external-sort (untested >> via cabal install but mostly done) >> >> As soon as my project gets approved I'll put it up on hackage. >> >> If Ben wants it under his account at hackage of course I'll defer to him. >> >> Thomas. >> >> 2007/7/18 Donald Bruce Stewart <dons(a)cse.unsw.edu.au>: >>> midfield: >>>> hi -- >>>> >>>> thanks for the useful comments! i will definitely go through them >>>> carefully. unfortunately for this code (but fortunately for me) i >>>> defend my dissertation on monday so i'm a little distracted right >>>> now..... >>>> >>>> i'm more than happy to donate this code or whatever improvements >>>> happen to it. actually, hGetContentsWithCursor seems like a candidate >>>> for inclusion with Data.ByteStrings or Data.Binary or something -- it >>>> seems like it might find other uses. (i think you liked that bit of >>>> code because i ripped it off of you guys! it's very short hamming >>> >>> Can't fault that style ;) >>> >>>> distance from the original.) anyhow, all that will have to wait a >>>> couple weeks or so. also i've never cabalized anything so i may come >>>> begging for help. >>> >>> We have a tutorial for that, luckily: >>> >>> http://haskell.org/haskellwiki/How_to_write_a_Haskell_program >>> >>> And a tool to automate it, mkcabal, so should be fairly straightforward. >>> >>>> >>>> at some point i thought i saw how to do recursive external sort, to >>>> keep memory usage truly constant, but with my current lack of sleep i >>>> have lost that illusion. i'm also curious about the performance >>>> characteristics of this vs Prelude sort vs the version using the >>>> tournament mergesort apfelmus suggested. i need to find a computer >>>> with a lot more RAM than my weakling laptop. finally, it would be >>>> good to be able to have the blocksize controlled by Kb of RAM rather >>>> than # of elements, not sure how to get that information. >>>> >>>> ultimately this was part of my project to write lucene for haskell. i >>>> think with this out of the way, plus all the Data.Binary / ByteString >>>> goodness, it shouldn't take too long. keep writing good libraries for >>>> me! >>>> >>> >>> Great. Good to see things working. >>> >>> -- Don >>> _______________________________________________ >>> Haskell-Cafe mailing list >>> Haskell-Cafe(a)haskell.org >>> http://www.haskell.org/mailman/listinfo/haskell-cafe >>> >> >

1 0

haskell & facebook
by Jason Dusek 19 Oct '08

19 Oct '08

Has anyone taken a stab at Haskell FaceBook bindings? -- _jsn

3 2