Peter Simons wrote:

Read and process the file in blocks:

http://cryp.to/blockio/docs/tutorial.html

On a related note, I've found the collection of papers below to be helpful in understanding different methods of handling files in Haskell. http://okmij.org/ftp/Computation/Computation.html#enumerator-stream "Now that cursors and enumerators are inter-convertible, an implementor of a collection has a choice: which of the two interfaces to implement natively? We argue that he should offer the enumerator interface as the native one. The paper elaborates that enumerators are superior: in efficiency; in ease of programming; in more predictable resource utilization and avoidance of resource leaks. We present a design of the overall optimal collection traversal interface, which is based on a left-fold-like combinator with premature termination." Greg Buchholz

On 2004 November 01 Monday 16:48, Alexander N. Kogan wrote:

Sorry, I don't understand. I thought the problem is in laziness - You're correct. The problem is laziness rather than I/O. my list of tuples becomes ("qqq", 1+1+1+.....) etc and my program reads whole file before it starts processing. Am I right or not? If I'm right, how can I inform compiler that my list of tuples should be strict?

The program does not read the whole file before processing the list. You might expect that it would given that most Haskell I/O take place in exactly the sequence specified. But readFile is different and sets things up to read the file on demand, analogous to lazy evaluation. The list of tuples _does_ need to be strict. Beyond that, as Ketil Malde said, you should not use foldl -- instead, foldl' is the best version to use when you are recalculating the result every time a new list item is processed. To deal with the list of tuples, you can use 'seq' to ensure that its parts are evaluated. For example, change (a,b+1):xs to let b' = b+1 in b' `seq` ((a,b'):xs) 'seq' means evaluate the first operand (to weak head normal form) prior to delivering the second operand as a result. Similarly the expression merge xs x needs to be evaluated explicitly.

Hi! Now I try to use FiniteMap to speed up the processing. merge' :: FiniteMap String Integer -> String -> FiniteMap String Integer merge' a x = addToFM_C (+) a x 1 parse' :: [String] -> [(String, Integer)] parse' x = fmToList $ foldl' merge' emptyFM x Where should I add `seq` to make FiniteMap strict? I tried merge' a x = let r = addToFM_C (+) a x 1 in r `seq` r but it doesn't help. -- Alexander Kogan Institute of Applied Physics Russian Academy of Sciences

Hi!

...

merge' a x = let r = addToFM_C (+) a x 1 in r `seq` r but it doesn't help.

== an anecdote

A quick note, x `seq` x is always exactly equivalant to x. the reason being that your seq would never be called to force x unless x was needed anyway.

;-)) Ok. merge' a x = (addToFM (+) $! a) x 1 is not strict. Can I do something to make FiniteMap strict? Or the only way is to make my own StrictFiniteMap? -- Alexander Kogan Institute of Applied Physics Russian Academy of Sciences

you can steal my version of finitemap: http://www.isi.edu/~hdaume/haskell/FiniteMap.hs which is based on the GHC version, but supports strict operations. the strict version of function f is called f'. i've also added some ops i thought were missing. On Wed, 3 Nov 2004, Scott Turner wrote:

On 2004 November 03 Wednesday 09:51, Alexander Kogan wrote:

...

merge' a x = (addToFM (+) $! a) x 1 is not strict. Can I do something to make FiniteMap strict? Or the only way is to make my own StrictFiniteMap?

You can replace addToFM_C (+) a x 1 with let a' = addToFM_C (+) a x 1 in lookupFM a' x `seq` a' or you can generalize that into your own strict version of addToFM_C. It's a little ugly, but probably gets the job done. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Hal Daume III | hdaume@isi.edu "Arrest this man, he talks in maths." | www.isi.edu/~hdaume

Hi!

You can replace addToFM_C (+) a x 1 with let a' = addToFM_C (+) a x 1 in lookupFM a' x `seq` a'

it is not strict also.

or you can generalize that into your own strict version of addToFM_C. It's a little ugly, but probably gets the job done.

Ohh.. -- Alexander Kogan Institute of Applied Physics Russian Academy of Sciences

Hi!

How about this?

let a' = addToFM_C (+) a x 1 in maybe () (`seq` ()) (lookupFM a' x) `seq` a'

It worked for me.

Thank you. It works for me too, but I don't understand why and how ;-)) Could you explain? -- Alexander Kogan Institute of Applied Physics Russian Academy of Sciences

Tomasz Zielonka <t.zielonka@students.mimuw.edu.pl> writes:

...

Thank you. It works for me too, but I don't understand why and how ;-)) Could you explain?

I'm a bit puzzled by this discussion, as strictness of FiniteMaps have rarely been (perceived to be?) a problem for me.

Scott's solution forces (lookupFM a' x) to head normal form (or is it weak head normal form). This means that the value of type (Maybe v) is evaluated as much that it is known whether it is Nothing, Just _ or _|_ (bottom). This is probably enough to evaluate the path from FiniteMap's tree root to x.

If you insert a value into a FiniteMap, isn't the key necessarily evaluated anyway? Or is the problem that you can get a long chain of unevaluated 'addToFM's? The trick would then be to evaluate the FM now and then (e.g. using a strict fold).

However (lookupFM a' x) in head normal form can be still something like this: Just <unevaluated: 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1>

I thought simply forcing evaluation of the value before inserting would do it (i.e. something like v `seq` addToFm fm k v (modulo v needing deeper seq'ing, that is) Am I missing something? -kzm -- If I haven't seen further, it is by standing in the footprints of giants

Hi!

Scott's solution forces (lookupFM a' x) to head normal form (or is it weak head normal form). This means that the value of type (Maybe v) is evaluated as much that it is known whether it is Nothing, Just _ or _|_ (bottom). This is probably enough to evaluate the path from FiniteMap's tree root to x. However (lookupFM a' x) in head normal form can be still something like this: Just <unevaluated: 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1> So we have to force the value at key 'x' also. My code uses maybe, which may obfuscate things a bit. Here's another version, which should be easier to understand:

let a' = addToFM_C (+) a x 1 in case lookupFM a' x of Nothing -> a' Just v -> v `seq` a'

Ok. I have 2 questions about this: 1. This means seq function evaluates only 'top' of argument, so when I pass, for example, list as argument, it will be evaluated only to [unevaluated, unevaluated, ...]? Am I right? 2. If so, is there method to _completely_ evaluate expression? -- Alexander Kogan Institute of Applied Physics Russian Academy of Sciences

Hi! В сообщении от 4 Ноябрь 2004 11:54 Tomasz Zielonka написал(a): [skip]

Note that the things marked 'unevaluated' above, could be already evaluated by some other computation.

Ok, I understand.

...

2. If so, is there method to _completely_ evaluate expression?

Most of the time you don't need it. But if you think you do, search for DeepSeq. I think that Data.Generics could be also used for that.

Could you suggest me - should I use it for this task? I have a very large list of pairs (ip::String, size::Integer) - this is a log from IP accounting, and I need to sum size for each ip. The length of list is more than 2 000 000. -- Alexander Kogan Institute of Applied Physics Russian Academy of Sciences

Alexander Kogan <alexander@kogan.nnov.ru> writes:

Thanks! I did the following:

For extra credit, you can use a FiniteMap to store the words and counts. They have, as you probably know, log n access times, and should give you a substantial performance boost. :-) (I have a feeling FMs are slow when the keys are Strings - is it possible that a trie or other structure would be faster? Or using hashed keys, perhaps?)

But I wonder why the very useful function foldl' as I define it is not included into Prelude?

Me too - it's the main drawback going from Hugs to GHCi :-) I also wonder if there's any important uses for foldl where foldr or foldl' wouldn't be at least as good, but I'm sure somebody can come up with an example. -kzm -- If I haven't seen further, it is by standing in the footprints of giants

John Goerzen writes:

...

Read and process the file in blocks:

I don't think that would really save much memory [...]

Given that the block-oriented approach has constant space requirements, I am fairly confident it would save memory.

and in fact, would likely just make the code a lot more complex. It seems like a simple wrapper around hGetContents over a file that uses block buffering would suffice.

Either your algorithm can process the input in blocks or it cannot. If it can, it doesn't make one bit a difference if you do I/O in blocks, because your algorithm processes blocks anyway. If your algorithm is *not* capable of processing blocks, then don't bother with block-oriented I/O -- and don't process large files unless you have 'seq' in all the right places. I happen to find adding those 'seq' calls much more difficult to get right than writing a computation that can be restarted. But your mileage may vary. Peter

John Goerzen writes:

...

Given that the block-oriented approach has constant space requirements, I am fairly confident it would save memory.

Perhaps a bit, but not a significant amount.

I see.

...

...

[read/processing blocks] would likely just make the code a lot more complex. [...]

...

Either your algorithm can process the input in blocks or it cannot. If it can, it doesn't make one bit a difference if you do I/O in blocks, because your algorithm processes blocks anyway.

Yes it does. If you don't set block buffering, GHC will call read() separately for *every* single character.

I referred to the alleged complication of code, not to whether the handle's 'BufferingMode' influences the performance or not.

(I've straced stuff!)

How many read(2) calls does this code need? import System.IO import Control.Monad ( when ) import Foreign.Marshal.Array ( allocaArray, peekArray ) import Data.Word ( Word8 ) main :: IO () main = do h <- openBinaryFile "/etc/profile" ReadMode hSetBuffering h NoBuffering n <- fmap cast (hFileSize h) buf <- allocaArray n $ \ptr -> do rc <- hGetBuf h ptr n when (rc /= n) (fail "huh?") buf' <- peekArray n ptr :: IO [Word8] return (map cast buf') putStr buf hClose h cast :: (Enum a, Enum b) => a -> b cast = toEnum . fromEnum

It's a lot more efficient if you set block buffering in your input, even if you are using interact and lines or words to process it.

Of course it is. Which is why an I/O-bound algorithm should process blocks. It's more efficient. And uses slightly less memory, too. Although I have been told it's not a insignificant amount. Peter