- Haskell-Cafe - Haskell.org

RE: [Haskell-cafe] Type classes and hFoldr from HList
by Ralf Lammel 07 Nov '05

07 Nov '05

Hi Greg, Since hfoldr is right-associative, I prefer to reorder your list of functions as follows: > test = HCons (length::String -> Int) (HCons ((+1)::(Int->Int)) (HCons ((*2)::(Int->Int)) HNil)) Note that I also annotated length with its specific type. (If you really wanted to leave things more polymorphic, you would need to engage in TypeCast.) Providing a specific Apply instance for (.) is not necessary, strictly necessary. We could try to exploit the normal function instance for Apply. Let me recall that one here for convenience: >instance Apply (x -> y) x y > where > apply f x = f x Let me also recall the hFoldr instances: >class HList l => HFoldr f v l r | f v l -> r > where > hFoldr :: f -> v -> l -> r >instance HFoldr f v HNil v > where > hFoldr _ v _ = v >instance ( HFoldr f v l r > , Apply f (e,r) r' > ) > => HFoldr f v (HCons e l) r' > where > hFoldr f v (HCons e l) = apply f (e,hFoldr f v l) To fit in (.), we would flip and uncurry it. So we could try: comp' = hFoldr (uncurry (flip (.))) (id::Int -> Int) test This wouldn't work. The trouble is the required polymorphism of the first argument of hFoldr. The type of that argument as such is polymorphic. However, this polymorphism does not survive type class parameterization. You see this by looking at the HCons instance of HFoldr. The different occurrences of "f" would need to be used at different types. This would only work if the type class parameter f were instantiated by the polymorphic type of (uncurry (flip (.))). (And even then we may need something like TypeCast.) What you can do is define a dedicated *type code* for composition. comp = hFoldr (undefined::Comp) (id::Int -> Int) test data Comp instance Apply Comp (x -> y,y -> z) (x -> z) where apply _ (f,g) = g . f Ralf > -----Original Message----- > From: haskell-cafe-bounces(a)haskell.org [mailto:haskell-cafe- > bounces(a)haskell.org] On Behalf Of Greg Buchholz > Sent: Sunday, November 06, 2005 7:01 PM > To: haskell-cafe(a)haskell.org > Subject: [Haskell-cafe] Type classes and hFoldr from HList > > > I was playing around with the HList library from the paper... > > Strongly typed heterogeneous collections > http://homepages.cwi.nl/~ralf/HList/ > > ...and I thought I'd try to fold the composition function (.) through a > heterogeneous list of functions, using hFoldr... > > >{-# OPTIONS -fglasgow-exts #-} > >{-# OPTIONS -fallow-undecidable-instances #-} > > > >import CommonMain > > > >main = print $ comp "abc" > > > >test = HCons ((+1)::(Int->Int)) (HCons ((*2)::(Int->Int)) (HCons length > HNil)) > > > >comp = hFoldr (.) id test > > > >instance Apply (a -> b -> c -> d) (a, b) (c -> d) > > where > > apply f (a,b) = f a b > > ...but it fails with the following type error... > > ]Compiling Main ( compose.hs, interpreted ) > ] > ]compose.hs:10:7: > ] No instances for (Apply ((b -> c) -> (a -> b) -> a -> c) > ] (Int -> Int, r) > ] ([Char] -> a3), > ] Apply ((b -> c) -> (a -> b) -> a -> c) (Int -> Int, > r1) r, > ] Apply ((b -> c) -> (a -> b) -> a -> c) ([a2] -> > Int, a1 ->a1) r1) > ] arising from use of `hFoldr' at compose.hs:10:7-12 > ] Probable fix: > ] add an instance declaration for (Apply ((b -> c) -> (a -> b) -> a - > > c) > ] (Int -> Int, r) > ] ([Char] -> a3), > ] Apply ((b -> c) -> (a -> b) -> a - > > c) > ](Int -> Int, r1) r, > ] Apply ((b -> c) -> (a -> b) -> a - > > c) > ]([a2] -> Int, a1 -> a1) r1) > ] In the definition of `comp': comp = hFoldr (.) id test > > ...Anyway, I couldn't quite tell whether I was using hFoldr incorrectly, > or if I needed to have more constraints placed on the construction of > "test", or if needed some sort of type-level function that resolves... > > Apply ((b -> c) -> (a -> b) -> a -> c) > > ...into (a -> c), or something else altogether. I figured someone might > be able to help point me in the right direction.

2 1

Information on B-Tree IO implemenations
by Scott Weeks 07 Nov '05

07 Nov '05

Hello all, (I'm resending this because I sent the first one without being a member of the list and I'm assuming it bounced) I'm a newbie and while I grasp some of the basics of FP I have yet to really understand the guts of Haskell. The type system is starting to clear up for me and so are Monads but I have a long way to go. For a project that I'm working on I need to implement a B-Tree or similar disk based data structure for storing large amounts of data. I feel like I'm getting it and then I get hung up on disk IO operations and trying to figure out how they should fit into the mix. I'm not necessarily looking for someone to point me at an implementation (although I wouldn't mind) but if someone could point me in the direction of some material that could shed a light on things I would be much obliged. I've read some Okasaki and found a promising paper called "Database Manipulation in Haskell 1.3" by Kevin Hammond and Phil Trinder but while they talk to the data structures themselves they don't quite get around to mentioning how they achieve the IO part of the equation. Thanks, Scotty Weeks

2 2

RE: Re[2]: [Haskell-cafe] Re: FPS: Finalizers not running (wasMemoryusageoutside of the Haskell heap)
by Simon Marlow 07 Nov '05

07 Nov '05

On 07 November 2005 14:02, Bulat Ziganshin wrote: > Hello Simon, > > Monday, November 07, 2005, 4:16:54 PM, you wrote: > >> Yes, mallocForeignPtr's are implemented using pinned GC'd memory, >> with no finalizer (unless you add one). That's why they're nice and >> fast. > > Simon, can you please write some docs about all these foreign stuff > and their interaction with pure Haskell code? i see some bits of this > information in these newsgroups regularly (for example, are you > remember discussion about using lots of hashtables in program?), but > there is no definitive source > > there is no need to write full-fledged doc right now, just > "implementation notes" as the list of peculiarities will be great for > the start You're right, it would be good to have this folklore stuff written down. I've added some notes to the mallocForeignPtr docs for now. Cheers, Simon

1 0

Monadifying pickler combinators
by Joel Reymont 07 Nov '05

07 Nov '05

Folks, I'm trying to monadify http://research.microsoft.com/~akenn/fun/ picklercombinators.pdf appU is easy but I can't figure out the appP. Is it actually possible? The clever trick seems to be the passing of (b -> a) into sequ for use in appP. -- instance Monad (PU s) where return a = PU snd (\s -> (a, s)) -- how do I do appP below? pa >>= k = PU (\(b, s) -> let pb = k a in appP pa (a, ??? -- this is good (\s -> let (a, s1) = appU pa s pb = k a in appU pb s1) Thanks, Joel -- http://wagerlabs.com/

1 0

RE: [Haskell-cafe] Trashing of memory: How to troubleshoot and fix?
by Simon Marlow 07 Nov '05

07 Nov '05

On 07 November 2005 14:16, Joel Reymont wrote: > Well, I was suspecting FPS but I removed all FPS usage and went with > regular lists. The program still crashes. I did not see a "malloc: > memory exhausted" error from ghci this time, it just crashed with an > application error while writing to some random memory location. > > I built a separate exe (this is Windows) and ran it in gdb for a > segmentation violation in with this stack trace: > > ?? () > s7yw_info () > ?? () If you are pretty certain that you aren't doing anything unsafe, then this is a bug in GHCi. If you can provide us with a reproducible test case, I'll look into it. Cheers, Simon

1 0

RE: [Haskell-cafe] Trashing of memory: How to troubleshoot and fix?
by Simon Marlow 07 Nov '05

07 Nov '05

On 05 November 2005 10:10, Joel Reymont wrote: > This is a I came up with a "scripting" environment for poker server > people to excercise their server. All it basically does is compose > and parse binary packets and let scripters send and receive them. > > The issue I have is that the "script" runs fine on Mac OSX (1Gb of > memory, though 6Gb VM) and runs out of memory on a Windows machine > with 512Mb of memory and 768Mb of VM. The memory error is from malloc > which leads me to believe memory fragmentation could be an issue. > Running on Windows is a customer requirement. GHC very rarely calls malloc(), so this is likely to be caused by heavy memory use in the C++ part of your app. It would be interesting to find out though: you can run gdb on the binary and get a backtrace when the memory error occurs (compiling the Haskell app with -debug will help). > I was wondering if peak memory usage was the issue but jugding from > the GC stats it does not seem to be that high. Maybe I'm wrong. What > do you guys make of this? > > ./logon +RTS -p -sblah > > GC summary: > -- > 5,695,379,620 bytes allocated in the heap > 1,274,038,800 bytes copied during GC > 69,790,544 bytes maximum residency (53 sample(s)) > > 20433 collections in generation 0 (230.29s) > 53 collections in generation 1 ( 5.15s) > > 152 Mb total memory in use > > INIT time 0.00s ( 0.04s elapsed) > MUT time 91.13s (250.79s elapsed) > GC time 235.44s (607.31s elapsed) > RP time 0.00s ( 0.00s elapsed) > PROF time 0.00s ( 0.00s elapsed) > EXIT time 0.00s ( 0.00s elapsed) > Total time 326.57s (858.14s elapsed) GC load is *very* high. But as you can see, GHC's storage manager is only using 152Mb peak - if you're running out with 512Mb, then something else is using the rest. To improve performance, I would first try to optimise the program to reduce the allocation rate, get any low-hanging fruit, and then tweak the GC settings. Most of your GC is generation 0 collections, which suggests that your program is allocating a lot of temporary memory and not getting much work done. Also, note that you got these figures from a version of the program compiled for profiling, which will have higher memory requirements than normal due to the profiling overheads. > --- > Time allocation and profiling report: > ---- > total time = 85.58 secs (4279 ticks @ 20 ms) > total alloc = 2,941,143,704 bytes (excludes profiling > overheads) > > COST CENTRE MODULE %time %alloc > > exp/evalU/cmd Script.Engine 50.0 66.4 > connect Main 14.1 11.1 > CAF Script.Engine 10.3 5.4 > exp/if Script.Engine 8.8 4.8 > send Main 6.4 6.7 > expect Main 5.8 2.7 > exp/evalU/sz Script.Engine 1.4 1.4 > startSSL Script.Engine 1.3 0.1 > --- Seems like you need to look at evalU: > cmd' <- {-# SCC "exp/evalU/cmd" #-}return $ evalU packet appU > -- unpickle command this is where most of the time/alloc seems to be going. Also, just looking at this line of code reminds me of SimonM's 203rd law of Haskell optimisation: when writing 'return $ E', consider writing 'return $! E' instead. Cheers, Simon

2 1

RE: [Haskell-cafe] Re: FPS: Finalizers not running (was Memory usageoutside of the Haskell heap)
by Simon Marlow 07 Nov '05

07 Nov '05

On 06 November 2005 18:38, Joel Reymont wrote: > You need to do something like this to force them to run, apparently > > main = do foo $ Prelude.concat $ replicate 100 data_ > > Just triggering the GC with performGC doesn't do it. > > The really odd thing is that if I setup a C finalizer (see below) > then it's triggered once and the whole thing crashes with a bus > error. Duncan reported that it segfaulted for him as well. > > installFinalizer fps@(P.PS fp _ _) = > addForeignPtrFinalizer finalizer fp > > foreign import ccall unsafe "finalizer" finalizer :: FinalizerPtr > Word8 > > where the finalizer itself is > > #include <stdio.h> > > void finalizer(char *p) { > printf("--- Finalized: %x\n", p); > } This crash is due to driver error, I'm afraid. You should have written: foreign import ccall unsafe "&finalizer" finalizer :: FinalizerPtr Word8 (note the "&"). Cheers, Simon

1 0

Memory usage outside of the Haskell heap
by Joel Reymont 07 Nov '05

07 Nov '05

Folks, How can I profile memory usage outside of the Haskell heap? I'm using FastStrings for everything and some folks on #haskell suspect it might be causing my problems. hGet :: Handle -> Int -> IO FastString hGet _ 0 = return empty hGet h i = do fp <- mallocForeignPtr i l <- withForeignPtr fp $ \p-> hGetBuf h p i return $ PS fp 0 l I do this a lot and the finalizers might not be running or something like that. Thanks, Joel -- http://wagerlabs.com/

6 13

RE: [Haskell-cafe] Re: FPS: Finalizers not running (was Memory usageoutside of the Haskell heap)
by Simon Marlow 07 Nov '05

07 Nov '05

Finalizers aren't guaranteed to be run. In particular, if the main thread exits, then we don't run any outstanding finalizers. This change was made recently, but it turned out that even prior to 6.4 we couldn't guarantee to run all outstanding finalizers. Does this explain it, or is there something else going on? BTW, when you addForeignPtrConcFinalizer to a ForeignPtr created with mallocForeignPtr, you're *creating* a finalizer, it doesn't have one to start with. It's pretty expensive to do this. Cheers, Simon On 07 November 2005 01:42, Donald Bruce Stewart wrote: > joelr1: >> David, >> >> I followed your suggestion and I think the finalizers for FPS are not >> running. > > Here are some experiments. Sometimes I can get the finalizers to run > as > expected, but only when putting memory pressure on the Haskell heap > with > normal haskell values. Works with 6.4.1 and 6.5 on OpenBSD or Linux. > > So here we generate a bunch of lists inside Haskell, then pack them. > Our > finalisers get run nicely as expected: > > import qualified Data.FastPackedString as P > import Foreign.Concurrent > import Data.Word > import Data.Char > > data_ = [ replicate 5000 i | i <- [1..100] ] :: [[Word8]] > > main = do > foo data_ > putStrLn "" > > foo [] = return () > foo (x:xs) = do > let fps = P.packWords x > installFinalizer fps > putStr "." > foo xs > > installFinalizer fps@(P.PS fp _ _) = > addForeignPtrFinalizer fp $ putStr (show.ord.P.head $ fps) > > > pill00$ ./a.out > 100 > > ..................................................1234567891011121314151 617181920212223242526272829303132333435363738394041424344454647484950... ........................................51525354555657585960616263646566 6768697071727374757677787980818283848586878889909192....... > > Now, if we instead allocate only outside the Haskell heap (with an > mmap packed > string), then we see something different: > > import qualified Data.FastPackedString as P > import Foreign.Concurrent > import Data.Word > import Data.Char > > main = do > foo 100 > putStrLn "" > > foo 0 = return () > foo n = do > fps <- P.mmapFile "/home/dons/tmp/tests/128k" > installFinalizer fps > putStr "." > foo (n-1) > > installFinalizer fps@(P.PS fp _ _) = > addForeignPtrFinalizer fp $ putStr (show.ord.P.head $ fps) > > No finalisers (even though more data is allocated)! > > $ ./a.out > > ........................................................................ .............. > > The GHC rts doesn't know how big the packed string is. It just sees > the few > bytes of the packed string (as dcoutts pointed out on irc). > > Strangely, the same effect is seen with P.readFile, which (from > darcs) allocates as so: > > mallocForeignPtr :: Int -> IO (ForeignPtr Word8) > mallocForeignPtr l = when (l > 1000000) performGC >> > mallocForeignPtrArray l > > where here mallocForeignPtrArray ends up calling > GHC.Prim.newPinnedByteArray# (i.e. on the Haskell heap). Hmm. I don't > understand that then, as the memory is > in the Haskell heap, yet still no finalisers are run. > > If we do something expensive with the packed string, then finalizers > get run: > > foo n = do > fps <- P.readFile "/home/dons/tmp/tests/128k" > installFinalizer fps > > -- unpack the string into a normal Haskell list: > forkIO (Control.Exception.evaluate ((length . P.unpack) fps) > >> return ()) putStr "." > foo (n-1) > > Also interestingly, calling unsafeFinalize didn't help. > > Simon, any thoughts on this? Is there some way we can ensure memory > outside the Haskell heap gets counted for its full weight? Also, why > don't we see any finalizers run with the pinned arrays? > > -- Don > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe

2 1

RE: [Haskell-cafe] Re: Fixup too large
by Simon Marlow 07 Nov '05

07 Nov '05

On 04 November 2005 20:06, Joel Reymont wrote: > I was able to work around this by adding -O > > On Nov 4, 2005, at 6:57 PM, Joel Reymont wrote: > >> What does this mean exactly? >> >> ghc -prof --make -auto-all -o logon -package Script Logon.hs >> Chasing modules from: Logon.hs >> Compiling Main ( Logon.hs, Logon.o ) >> /tmp/ghc20361.s:17881:Fixup of 93184 too large for field width of 16 >> bits /tmp/ghc20361.s:17878:Fixup of 93196 too large for field width >> of 16 bits /tmp/ghc20361.s:17874:Fixup of 93160 too large for field >> width of 16 bits Can you send us the offending code? Cheers, Simon

1 0