Re: [Haskell] Probably a trivial thing for people knowing Haskell
Marshall Beddoe <unmarshal@gmail.com> writes:
Also, read some chapters from here: http://book.realworldhaskell.org/read/
Indispensable examples for writing higher performance log processing code. I hope this book will soon be send out. I ordered my copy of course ;-)
Howerver even if Strings are bad I can not see why they are hanging around so long. I open a file a read it line by line and I close the file so all read string are "garbage" and getting rid of them should not be that hard or should it? Regards Friedrich
On 2008 Oct 19, at 2:07, Friedrich wrote:
Howerver even if Strings are bad I can not see why they are hanging around so long. I open a file a read it line by line and I close the file so all read string are "garbage" and getting rid of them should not be that hard or should it?
If your code is too lazy, you have the whole file + the close operation hanging around in unevaluated thunks until you print the result and it all gets processed all at once. Laziness is a double- edged sword. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH
"Brandon S. Allbery KF8NH" <allbery@ece.cmu.edu> writes:
On 2008 Oct 19, at 2:07, Friedrich wrote:
Howerver even if Strings are bad I can not see why they are hanging around so long. I open a file a read it line by line and I close the file so all read string are "garbage" and getting rid of them should not be that hard or should it?
If your code is too lazy, you have the whole file + the close operation hanging around in unevaluated thunks until you print the result and it all gets processed all at once. Laziness is a double- edged sword. Where in my code is this laziness hidden? Is it while recurions with sum and count?
Regards Friedrich -- Q-Software Solutions GmbH; Sitz: Bruchsal; Registergericht: Mannheim Registriernummer: HRB232138; Geschaeftsfuehrer: Friedrich Dominicus
On 2008 Oct 19, at 11:18, Friedrich wrote:
"Brandon S. Allbery KF8NH" <allbery@ece.cmu.edu> writes:
On 2008 Oct 19, at 2:07, Friedrich wrote:
Howerver even if Strings are bad I can not see why they are hanging around so long. I open a file a read it line by line and I close the file so all read string are "garbage" and getting rid of them should not be that hard or should it?
If your code is too lazy, you have the whole file + the close operation hanging around in unevaluated thunks until you print the result and it all gets processed all at once. Laziness is a double- edged sword. Where in my code is this laziness hidden? Is it while recurions with sum and count?
That would be my guess, although I'd have to examine the Core (intermediate compilation stage) to be certain. Others here are better at looking at Haskell code and seeing where the laziness "leaks" are. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH
"Brandon S. Allbery KF8NH" <allbery@ece.cmu.edu> writes:
On 2008 Oct 19, at 2:07, Friedrich wrote:
Howerver even if Strings are bad I can not see why they are hanging around so long. I open a file a read it line by line and I close the file so all read string are "garbage" and getting rid of them should not be that hard or should it?
If your code is too lazy, you have the whole file + the close operation hanging around in unevaluated thunks until you print the result and it all gets processed all at once. Laziness is a double- edged sword. Ok to be more concrete is the laziness "hidden" here?
check_line line sum count = let match = matchRegex regexp line in case match of Just strs -> (sum + read (head strs) :: Integer, count + 1) Nothing -> (sum, count) Regards Friedrich -- Q-Software Solutions GmbH; Sitz: Bruchsal; Registergericht: Mannheim Registriernummer: HRB232138; Geschaeftsfuehrer: Friedrich Dominicus
On 2008 Oct 19, at 11:25, Friedrich wrote:
Ok to be more concrete is the laziness "hidden" here?
check_line line sum count = let match = matchRegex regexp line in case match of Just strs -> (sum + read (head strs) :: Integer, count + 1) Nothing -> (sum, count)
For starters, "let" is lazy. "case" is strict to the extent that it has to evaluate enough to decide if the result is Just or Nothing, but that's useless if the code leading up to its application is lazy. I don't know how lazy matchRegex is, if it is lazy enough then all that gets evaluated by the case is just enough to know if the result is Just or Nothing but not the value of "strs". (One obvious possibility is that it determines that there *are* strings, but not what they are.) Everything else is automatically lazy. So, unless the caller forces the result of this function, you are very likely to end up with a chain of partially evaluated matches that don't get resolved until the result is printed. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH
Friedrich wrote:
Ok to be more concrete is the laziness "hidden" here?
check_line line sum count = let match = matchRegex regexp line in case match of Just strs -> (sum + read (head strs) :: Integer, count + 1) Nothing -> (sum, count)
Probably. I would guess that "sum" and "count" are not being forced (i.e. evaluated) until the end of the computation, so instead of computing the result of "sum + read (head strs)" your program is just creating a thunk. Because this is in a loop, you wind up with a chain of thunks. Try putting turning the "Just" line into something like Just strs -> (seq sum $ sum + read (head strs) :: Integer, seq count $ count + 1) That would be my guess. But I could be wrong. Paul.
Friedrich wrote:
Ok to be more concrete is the laziness "hidden" here?
check_line line sum count = let match = matchRegex regexp line in case match of Just strs -> (sum + read (head strs) :: Integer, count + 1) Nothing -> (sum, count)
Yes, part of it. To see why, put yourself into the role of an evaluator for your program. An application of check_line will not be evaluated until necessary, and it becomes necessary only if the result is bound to a pattern (and that binding is needed for some reason). At that point, enough has to be evaluated to determine whether the result is actually a pair or bottom. So what will you do? The body of check_line is a case expression, so you need to sufficiently evaluate its scrutinee. You evaluate enough of matchRegex to see whether the result is Nothing or Just. Let's say it's Just. So you descent into the Just branch, and you see the result is a pair (and not bottom). The elements of the pair have not been evaluated, there was no need to. Also, the arguments to check_line have not been evaluated, except for line. You need to force the evaluation of the elements of the result pair whenever the pair itself is demanded, for example:
check_line line sum count = let match = matchRegex regexp line in case match of Just strs -> ((,) $! (sum + read (head strs) :: Integer)) $! count + 1 Nothing -> ((,) $! sum) $! count)
(The associativity of ($!) is inconvenient here. I want left-associative ($!). Actually, a strict pair type would be even more convenient here.) On recent GHC with bang-patterns, this short-cut works, too. It's not quite equivalent, because it will create unevaluated thunks, though they won't pile up:
check_line line !sum !count = let match = matchRegex regexp line in case match of Just strs -> (sum + read (head strs) :: Integer, count + 1) Nothing -> (sum, count)
Paul Johnson wrote:
Try putting turning the "Just" line into something like
Just strs -> (seq sum $ sum + read (head strs) :: Integer, seq count $ count + 1)
This doesn't help. First of all, you don't "try putting" anything anywhere. Without understanding what's going on, you'll only create ugly code, bang your head against a wall and still end up with a space leak (been there, done that, bought the t-shirt). Instead, go through the evaluation by hand and/or use a heap profiler to guide you. Then put strictness annotations where needed (and only there). Putting seqs inside the pair is useless, because the problem is that nobody will look there to begin with. Applying seq to sum and count helps, if done outside the pair constructor, but is not quite right. You want the new sums to be evaluated strictly, and while making the function strict in its arguments helps, it stops one step too early. -Udo
Udo Stenzel <u.stenzel@web.de> writes:
Friedrich wrote:
Ok to be more concrete is the laziness "hidden" here?
check_line line sum count = let match = matchRegex regexp line in case match of Just strs -> (sum + read (head strs) :: Integer, count + 1) Nothing -> (sum, count)
Yes, part of it. To see why, put yourself into the role of an evaluator for your program. An application of check_line will not be evaluated until necessary, and it becomes necessary only if the result is bound to a pattern (and that binding is needed for some reason). At that point, enough has to be evaluated to determine whether the result is actually a pair or bottom.
So what will you do? The body of check_line is a case expression, so you need to sufficiently evaluate its scrutinee. You evaluate enough of matchRegex to see whether the result is Nothing or Just. Let's say it's Just. So you descent into the Just branch, and you see the result is a pair (and not bottom). The elements of the pair have not been evaluated, there was no need to. Also, the arguments to check_line have not been evaluated, except for line.
You need to force the evaluation of the elements of the result pair whenever the pair itself is demanded, for example:
check_line line sum count = let match = matchRegex regexp line in case match of Just strs -> ((,) $! (sum + read (head strs) :: Integer)) $! count + 1 Nothing -> ((,) $! sum) $! count)
(The associativity of ($!) is inconvenient here. I want left-associative ($!). Actually, a strict pair type would be even more convenient here.)
On recent GHC with bang-patterns, this short-cut works, too. It's not quite equivalent, because it will create unevaluated thunks, though they won't pile up:
check_line line !sum !count = let match = matchRegex regexp line in case match of Just strs -> (sum + read (head strs) :: Integer, count + 1) Nothing -> (sum, count)
Ok, I followed the suggestions. Now I have the following code: module Main where import System import System.IO import System.Directory import System.IO.Error import Text.Regex import Control.Monad regexp = mkRegex ("([0-9]+) Windows ex") main = do files <- show_dir "[0-9].*" (sum,count) <- run_on_all_files (0,0) files let dd = (fromIntegral (sum::Integer))/ (fromIntegral (count::Int)) in putStr("Download = " ++ show sum ++ " in " ++ show count ++ " days are " ++ show dd ++ " downloads/day\n") run_on_all_files (a,b) [] = return (a,b) run_on_all_files (a,b) (x:xs) = do (s,c) <- run_on(a,b) x run_on_all_files (s,c) xs run_on (a,b) file_name = do handle <- openFile file_name ReadMode (sum,count) <- for_each_line (a,b) handle hClose handle return ((sum,count)) for_each_line (sum, count) handle = do l <- try (hGetLine handle) case l of Left err | isEOFError err -> return(sum,count) | otherwise -> ioError err Right line -> do let (nsum, ncount) = count_downloads line (sum, count) for_each_line (nsum,ncount) handle count_downloads line (!sum, !count) = let match = matchRegex regexp line in case match of Just strs -> (sum + read (head strs) :: Integer, count + 1) Nothing -> (sum, count) show_dir regmatch = do files <- getDirectoryContents "." let reg = mkRegex regmatch in return(filter (\file_name -> let fm = matchRegex reg file_name in case fm of Just strs -> True Nothing -> False) files) But it still sucks memor as wild and more or less crashes the system. So why's that than? Regards Friedrich
Udo Stenzel <u.stenzel@web.de> writes:
Friedrich wrote:
Ok to be more concrete is the laziness "hidden" here?
check_line line sum count = let match = matchRegex regexp line in case match of Just strs -> (sum + read (head strs) :: Integer, count + 1) Nothing -> (sum, count)
Yes, part of it. To see why, put yourself into the role of an evaluator for your program. An application of check_line will not be evaluated until necessary, and it becomes necessary only if the result is bound to a pattern (and that binding is needed for some reason). At that point, enough has to be evaluated to determine whether the result is actually a pair or bottom.
So what will you do? The body of check_line is a case expression, so you need to sufficiently evaluate its scrutinee. You evaluate enough of matchRegex to see whether the result is Nothing or Just. Let's say it's Just. So you descent into the Just branch, and you see the result is a pair (and not bottom). The elements of the pair have not been evaluated, there was no need to. Also, the arguments to check_line have not been evaluated, except for line.
You need to force the evaluation of the elements of the result pair whenever the pair itself is demanded, for example:
check_line line sum count = let match = matchRegex regexp line in case match of Just strs -> ((,) $! (sum + read (head strs) :: Integer)) $! count + 1 Nothing -> ((,) $! sum) $! count)
(The associativity of ($!) is inconvenient here. I want left-associative ($!). Actually, a strict pair type would be even more convenient here.)
On recent GHC with bang-patterns, this short-cut works, too. It's not quite equivalent, because it will create unevaluated thunks, though they won't pile up:
check_line line !sum !count = let match = matchRegex regexp line in case match of Just strs -> (sum + read (head strs) :: Integer, count + 1) Nothing -> (sum, count)
Ok, I followed the suggestions. Now I have the following code: module Main where import System import System.IO import System.Directory import System.IO.Error import Text.Regex import Control.Monad regexp = mkRegex ("([0-9]+) Windows ex") main = do files <- show_dir "[0-9].*" (sum,count) <- run_on_all_files (0,0) files let dd = (fromIntegral (sum::Integer))/ (fromIntegral (count::Int)) in putStr("Download = " ++ show sum ++ " in " ++ show count ++ " days are " ++ show dd ++ " downloads/day\n") run_on_all_files (a,b) [] = return (a,b) run_on_all_files (a,b) (x:xs) = do (s,c) <- run_on(a,b) x run_on_all_files (s,c) xs run_on (a,b) file_name = do handle <- openFile file_name ReadMode (sum,count) <- for_each_line (a,b) handle hClose handle return ((sum,count)) for_each_line (sum, count) handle = do l <- try (hGetLine handle) case l of Left err | isEOFError err -> return(sum,count) | otherwise -> ioError err Right line -> do let (nsum, ncount) = count_downloads line (sum, count) for_each_line (nsum,ncount) handle count_downloads line (!sum, !count) = let match = matchRegex regexp line in case match of Just strs -> (sum + read (head strs) :: Integer, count + 1) Nothing -> (sum, count) show_dir regmatch = do files <- getDirectoryContents "." let reg = mkRegex regmatch in return(filter (\file_name -> let fm = matchRegex reg file_name in case fm of Just strs -> True Nothing -> False) files) But it still sucks memor as wild and more or less crashes the system. So why's that than? Regards Friedrich
Folks, I wonder if this worthwhile thread could move from haskell@haskell.org to haskell-cafe@haskell.org? The main Haskell list, haskell@haskell.org, is a low-bandwidth list for discussion starters and announcements. The Haskell Cafe, by contrast, is a high-bandwidth list for detailed discussion. We don't want to force subscribers to the main Haskell list to unsubscribe. Thanks Simon | -----Original Message----- | From: haskell-bounces@haskell.org [mailto:haskell-bounces@haskell.org] On | Behalf Of Friedrich | Sent: 21 October 2008 08:18 | To: haskell@haskell.org | Subject: Re: [Haskell] Probably a trivial thing for people knowing Haskell | | Udo Stenzel <u.stenzel@web.de> writes: | | >> Friedrich wrote: | >> >Ok to be more concrete is the laziness "hidden" here? | >> > | >> >check_line line sum count = | >> > let match = matchRegex regexp line | >> > in case match of | >> > Just strs -> (sum + read (head strs) :: Integer, count + | 1) | >> > Nothing -> (sum, count) | > | > Yes, part of it. To see why, put yourself into the role of an evaluator | > for your program. An application of check_line will not be evaluated | > until necessary, and it becomes necessary only if the result is bound to | > a pattern (and that binding is needed for some reason). At that point, | > enough has to be evaluated to determine whether the result is actually a | > pair or bottom. | > | > So what will you do? The body of check_line is a case expression, so | > you need to sufficiently evaluate its scrutinee. You evaluate enough of | > matchRegex to see whether the result is Nothing or Just. Let's say it's | > Just. So you descent into the Just branch, and you see the result is a | > pair (and not bottom). The elements of the pair have not been | > evaluated, there was no need to. Also, the arguments to check_line have | > not been evaluated, except for line. | > | > You need to force the evaluation of the elements of the result pair | > whenever the pair itself is demanded, for example: | > | >> >check_line line sum count = | >> > let match = matchRegex regexp line | >> > in case match of | >> > Just strs -> ((,) $! (sum + read (head strs) :: Integer)) | $! count + 1 | >> > Nothing -> ((,) $! sum) $! count) | > | > (The associativity of ($!) is inconvenient here. I want | > left-associative ($!). Actually, a strict pair type would be even more | > convenient here.) | > | > On recent GHC with bang-patterns, this short-cut works, too. It's not | > quite equivalent, because it will create unevaluated thunks, though they | > won't pile up: | > | >> >check_line line !sum !count = | >> > let match = matchRegex regexp line | >> > in case match of | >> > Just strs -> (sum + read (head strs) :: Integer, count + | 1) | >> > Nothing -> (sum, count) | | Ok, I followed the suggestions. Now I have the following code: | | module Main where | import System | import System.IO | import System.Directory | import System.IO.Error | import Text.Regex | import Control.Monad | | regexp = mkRegex ("([0-9]+) Windows ex") | | main = do | files <- show_dir "[0-9].*" | (sum,count) <- run_on_all_files (0,0) files | let dd = (fromIntegral (sum::Integer))/ (fromIntegral (count::Int)) | in | putStr("Download = " ++ show sum ++ " in " ++ show count ++ " | days are " ++ show dd ++ " downloads/day\n") | | | | | run_on_all_files (a,b) [] = return (a,b) | run_on_all_files (a,b) (x:xs) = do (s,c) <- run_on(a,b) x | run_on_all_files (s,c) xs | | | run_on (a,b) file_name = do | handle <- openFile file_name ReadMode | (sum,count) <- for_each_line (a,b) handle | hClose handle | return ((sum,count)) | | for_each_line (sum, count) handle = do | l <- try (hGetLine handle) | case l of | Left err | | isEOFError err -> return(sum,count) | | otherwise -> ioError err | Right line -> do | let (nsum, ncount) = | count_downloads line (sum, count) | for_each_line (nsum,ncount) | handle | | | | count_downloads line (!sum, !count) = | let match = matchRegex regexp line | in case match of | Just strs -> (sum + read (head strs) :: Integer, count + 1) | Nothing -> (sum, count) | | | | show_dir regmatch = do | files <- getDirectoryContents "." | let reg = mkRegex regmatch in | return(filter (\file_name -> let fm = | matchRegex reg file_name | in case fm of | Just strs -> True | Nothing -> False) files) | | | | | But it still sucks memor as wild and more or less crashes the | system. So why's that than? | | Regards | Friedrich | | _______________________________________________ | Haskell mailing list | Haskell@haskell.org | http://www.haskell.org/mailman/listinfo/haskell
"Brandon S. Allbery KF8NH" <allbery@ece.cmu.edu> writes:
Laziness is a double-edged sword.
Perhaps the following page from Haskell Wiki would serve to enlighten more: http://haskell.org/haskellwiki/Foldr_Foldl_Foldl%27? This really made it clear to me how laziness can sometimes be a bad thing.
Chry Cheng schrieb:
"Brandon S. Allbery KF8NH" <allbery@ece.cmu.edu> writes:
Laziness is a double-edged sword.
Perhaps the following page from Haskell Wiki would serve to enlighten more: http://haskell.org/haskellwiki/Foldr_Foldl_Foldl%27? This really made it clear to me how laziness can sometimes be a bad thing.
A student of mine switch from Haskell to Java because of exactly these laziness problems - after he tried out to make the program stricter in various ways, but failed to remove the space leak. There should be an easy way of declaring a Haskell function (or, if that won't work, a whole module) to use strict evaluation only, without the need to manually insert seq and foldl' etc. everywhere (or even to change the structure of the code completely). Till Mossakowski
participants (7)
-
Brandon S. Allbery KF8NH -
Chry Cheng -
Friedrich -
Paul Johnson -
Simon Peyton-Jones -
Till Mossakowski -
Udo Stenzel