seq / strictness and laziness
I have some code which is being unnecessarily lazy (and occupying too much heap space). The code should read and process several files one by one. What's happening is that all files get read in but the processing is delayed by laziness, and the files are being retained. It looks something like this (after simplification): main = do result <- foldM countAFile initialcounts fileNameList prettyprint result countAFile oldcounts filename = do compiledFile <- readAndCompile filename let newcounts = countAssociations compiledFile oldcounts return newcounts I would love to have used CPS, but this seems to force me to lift a huge amount of code into both the IO monad and the CPS, as countAssociations just calls another function, which calls another, and so on. If I change countAFile to use a redundant test to force evaluation of newcounts: countAFile oldcounts filename = do compiledFile <- readAndCompile filename let newcounts = countAssociations compiledFile oldcounts if newcounts == newcounts then return newcounts else error "suitable error message" then the program runs beautifully (if a little slowly), occupying a constant amount of heap. If instead I use a strict data type to store my counts, or use seq, then I get no improvement, and it's just as if I hadn't used them. I understand why a strict data type won't help me, as it's the function calls that are lazy. But what about $! and seq? countAFile oldcounts filename = do compiledFile <- readAndCompile filename let newcounts = countAssociations compiledFile oldcounts return $! newcounts Does anyone understand why $! (or equivalently "seq") have no effect here? Is there a better way to do this? Amanda -- Amanda Clare http://users.aber.ac.uk/ajc99/ Tel: +44 (0)1970 621922 Fax: +44 (0)1970 622455 Dept. of Computer Science, University of Wales, Aberystwyth, SY23 3DB
`seq` forces evaluation of only the top-level construct in its first argument. (($!) similarly for its second argument.) I would guess your "newcounts" are structured (probably a tuple or list), in which case you are not forcing evaluation deeply enough. See http://haskell.org/pipermail/haskell/2001-August/001581.html and followup article. Dean Herington Amanda Clare wrote:
I have some code which is being unnecessarily lazy (and occupying too much heap space). The code should read and process several files one by one. What's happening is that all files get read in but the processing is delayed by laziness, and the files are being retained. It looks something like this (after simplification):
main = do result <- foldM countAFile initialcounts fileNameList prettyprint result
countAFile oldcounts filename = do compiledFile <- readAndCompile filename let newcounts = countAssociations compiledFile oldcounts return newcounts
I would love to have used CPS, but this seems to force me to lift a huge amount of code into both the IO monad and the CPS, as countAssociations just calls another function, which calls another, and so on.
If I change countAFile to use a redundant test to force evaluation of newcounts:
countAFile oldcounts filename = do compiledFile <- readAndCompile filename let newcounts = countAssociations compiledFile oldcounts if newcounts == newcounts then return newcounts else error "suitable error message"
then the program runs beautifully (if a little slowly), occupying a constant amount of heap.
If instead I use a strict data type to store my counts, or use seq, then I get no improvement, and it's just as if I hadn't used them. I understand why a strict data type won't help me, as it's the function calls that are lazy. But what about $! and seq?
countAFile oldcounts filename = do compiledFile <- readAndCompile filename let newcounts = countAssociations compiledFile oldcounts return $! newcounts
Does anyone understand why $! (or equivalently "seq") have no effect here? Is there a better way to do this?
Amanda -- Amanda Clare http://users.aber.ac.uk/ajc99/ Tel: +44 (0)1970 621922 Fax: +44 (0)1970 622455 Dept. of Computer Science, University of Wales, Aberystwyth, SY23 3DB
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Dean Herington wrote:
`seq` forces evaluation of only the top-level construct in its first argument. (($!) similarly for its second argument.) I would guess your "newcounts" are structured (probably a tuple or list), in which case you are not forcing evaluation deeply enough. See http://haskell.org/pipermail/haskell/2001-August/001581.html and followup article.
Thanks, that's just what I need. It works! Perhaps if this is becoming a frequently asked question, there should be a mention of this problem in the Haskell report where seq is described. Amanda -- Amanda Clare http://users.aber.ac.uk/ajc99/ Tel: +44 (0)1970 621922 Fax: +44 (0)1970 622455 Dept. of Computer Science, University of Wales, Aberystwyth, SY23 3DB
Amanda Clare wrote:
Dean Herington wrote:
`seq` forces evaluation of only the top-level construct in its first argument. (($!) similarly for its second argument.) I would guess your "newcounts" are structured (probably a tuple or list), in which case you are not forcing evaluation deeply enough. See http://haskell.org/pipermail/haskell/2001-August/001581.html and followup article.
Thanks, that's just what I need. It works!
Then using a data type with strict data constructor arguments together with ($!) in return should also work. Olaf -- OLAF CHITIL, Dept. of Computer Science, University of York, York YO10 5DD, UK. URL: http://www.cs.york.ac.uk/~olaf/ Tel: +44 1904 434756; Fax: +44 1904 432767
Both parallel and sequential computation must be carefully controlled to produce good parallel and distributed Haskell programs. Several languages including Glasgow parallel Haskell and Eden use *evaluation strategies*: overloaded polymorphic functions to describe the amount of evaluation.
type Done = () type Strategy a = a -> Done
There are three basic strategies: - r0 performs no evaluation on its argument, - rwhnf reduces its argument to weak head normal form, - rnf reduces its argument to (head) normal form: i.e. deepseq. System support for rnf/deepseq would be A Good Thing.
r0, rwhnf :: Strategy a r0 x = () rwhnf x = x `seq` ()
class NFData a where class Eval a => NFData a where rnf :: Strategy a
Example instances of NFData are given below, a useful set are predefined in the module below:
instance (NFData a, NFData b) => NFData (a,b) where rnf (x,y) = rnf x `seq` rnf y
instance NFData a => NFData [a] where rnf [] = () rnf (x:xs) = rnf x `seq` rnf xs
Strategies are simply functions that can be abstracted and composed lilke any others, e.g. SeqList applies a strategy to each element of a list sequentially.
seqList :: Strategy a -> Strategy [a] seqList strat [] = () seqList strat (x:xs) = strat x `seq` (seqList strat xs)
So 'SeqList r0' evaluates just the spine of the list, and 'seqList (seqList rwhnf)' evaluates the elements of a list of lists to weak head normal form. You can apply a strategy to an expression
using :: a -> Strategy a -> a using x s = s x `seq` x
So to force newcounts in your program you want to change the last line to be something like: countAFile oldcounts filename = do compiledFile <- readAndCompile filename let newcounts = countAssociations compiledFile oldcounts return newcounts 'using' rnf There's a copy of the Strategies module attached. More info in "Algorithm + Strategy = Parallelism", P.W. Trinder, K. Hammond, H-W. Loidl, S.L. Peyton Jones In Journal of Functional Programming 8(1):23--60, January 1998. URL: http://www.cee.hw.ac.uk/~dsg/gph/papers/ps/strategies.ps.gz Phil -------------------------------------------------- Phil Trinder Department of Computing and Electrical Engineering Heriot Watt University Riccarton Edinburgh, EH14 4AS E-mail: trinder@cee.hw.ac.uk Teleph: +44 (0)131 451 3435 Depart: +44 (0)131 451 3328 Fasmly: +44 (0)131 451 3327 Intrnt: http://www.cee.hw.ac.uk/~trinder
participants (4)
-
Amanda Clare -
Dean Herington -
Olaf Chitil -
Phil Trinder