RE: [Haskell] stack overflow - nonobvious thunks?
Adrian, Does your AVL library have an "insertWith'"-type function mentioned by Udo? If I lookup and insert into the table separately, forcing evaluation at each step, I can do table' :: (Ord a) => [a] -> [(a, Int)] table' xs = Map.assocs $! foldl' f Map.empty xs where f m x = (Map.insert x $! 1 + Map.findWithDefault 0 x m) $! m This helps with the stack overflow problem, but now I'm hitting a different wall: *Main> table $ take 10000000 unif [(1,999662),(2,1000220),(3,998800),(4,1000965),(5,999314),(6,1001819),(7 ,1000997),(8,999450),(9,999877),(10,998896)] *Main> table $ take 100000000 unif <interactive>: out of memory (requested 1048576 bytes) I thought I may have found a good approach using an idea from one of Amanda Clare's pages http://users.aber.ac.uk/afc/stricthaskell.html If I write eqSeq x y = if x==x then y else y this forces evaluation of x further than seq alone. Then I can write table :: (Ord a) => [a] -> [(a, Int)] table xs = Map.assocs $! foldl' f Map.empty xs where f m x = m `eqSeq` Map.insertWith (+) x 1 m Same result as Udo's suggestion - out of memory. I still don't see why this function should need any more than a few kilobytes, even for very large n like this. -Chad -----Original Message----- From: u.stenzel@web.de [mailto:u.stenzel@web.de] Sent: Wednesday, July 27, 2005 11:02 AM To: Scherrer, Chad Cc: haskell@haskell.org Subject: Re: [Haskell] stack overflow - nonobvious thunks? Scherrer, Chad wrote:
f m x = Map.insertWith (+) x 1 m
insertWith is inserting the "nonobvious thunks". Internally it applies (+) to the old value and the new one, producing a thunk. There is no place you could put a seq or something to force the result. You basically need insertWith', which isn't there. I think, your best best is to manually lookup the old value, combine with the new, force the result, then insert that, overwriting the old value. On top of that you still need foldl' to avoid building long chains of Map.insert. Udo. -- The Second Law of Thermodynamics: If you think things are in a mess now, just wait! -- Jim Warner
The following version seems to do the trick (and still remain quite readable). It worked for 100000000 as well. import Data.Map as Map import System.Random import Data.List (foldl') table :: (Ord a) => [a] -> [(a,Int)] table xs = Map.assocs $! foldl' f Map.empty xs where f m x = let m' = Map.insertWith (+) x 1 m Just v = Map.lookup x m' in v `seq` m' unif :: [Int] unif = randomRs (1,10) $ mkStdGen 1 f :: Int -> [(Int, Int)] f n = table $ take n unif main = print $ f 10000000 - Dean At 2:19 PM -0700 7/27/05, Scherrer, Chad wrote:
Adrian, Does your AVL library have an "insertWith'"-type function mentioned by Udo?
If I lookup and insert into the table separately, forcing evaluation at each step, I can do
table' :: (Ord a) => [a] -> [(a, Int)] table' xs = Map.assocs $! foldl' f Map.empty xs where f m x = (Map.insert x $! 1 + Map.findWithDefault 0 x m) $! m
This helps with the stack overflow problem, but now I'm hitting a different wall:
*Main> table $ take 10000000 unif [(1,999662),(2,1000220),(3,998800),(4,1000965),(5,999314),(6,1001819),(7 ,1000997),(8,999450),(9,999877),(10,998896)]
*Main> table $ take 100000000 unif <interactive>: out of memory (requested 1048576 bytes)
I thought I may have found a good approach using an idea from one of Amanda Clare's pages http://users.aber.ac.uk/afc/stricthaskell.html
If I write
eqSeq x y = if x==x then y else y
this forces evaluation of x further than seq alone. Then I can write
table :: (Ord a) => [a] -> [(a, Int)] table xs = Map.assocs $! foldl' f Map.empty xs where f m x = m `eqSeq` Map.insertWith (+) x 1 m
Same result as Udo's suggestion - out of memory.
I still don't see why this function should need any more than a few kilobytes, even for very large n like this.
-Chad
-----Original Message----- From: u.stenzel@web.de [mailto:u.stenzel@web.de] Sent: Wednesday, July 27, 2005 11:02 AM To: Scherrer, Chad Cc: haskell@haskell.org Subject: Re: [Haskell] stack overflow - nonobvious thunks?
Scherrer, Chad wrote:
f m x = Map.insertWith (+) x 1 m
insertWith is inserting the "nonobvious thunks". Internally it applies (+) to the old value and the new one, producing a thunk. There is no place you could put a seq or something to force the result. You basically need insertWith', which isn't there.
I think, your best best is to manually lookup the old value, combine with the new, force the result, then insert that, overwriting the old value.
On top of that you still need foldl' to avoid building long chains of Map.insert.
Udo. -- The Second Law of Thermodynamics: If you think things are in a mess now, just wait! -- Jim Warner _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Dean's version certainly seems the neatest, but just for interest you can also do it with a cps fold instead of foldl' too: table xs = assocs $! cpsfold f empty xs where f x m k = case Map.lookup x m of Just v -> v `seq` (k $ Map.adjust (+1) x m) Nothing -> k $ Map.insert x 1 m cpsfold f a [] = a cpsfold f a (x:xs) = f x a (\y -> cpsfold f y xs) As far as I understand it this just makes sure the "seq" happens before the folding continues. When compiled with ghc, both solutions are very well behaved, and seem to take the same small amount of memory whether for 10000000 or 100000000. Amanda Dean Herington wrote:
The following version seems to do the trick (and still remain quite readable). It worked for 100000000 as well.
import Data.Map as Map import System.Random import Data.List (foldl')
table :: (Ord a) => [a] -> [(a,Int)] table xs = Map.assocs $! foldl' f Map.empty xs where f m x = let m' = Map.insertWith (+) x 1 m Just v = Map.lookup x m' in v `seq` m'
unif :: [Int] unif = randomRs (1,10) $ mkStdGen 1
f :: Int -> [(Int, Int)] f n = table $ take n unif main = print $ f 10000000
- Dean
On Wednesday 27 Jul 2005 10:19 pm, Scherrer, Chad wrote:
Adrian, Does your AVL library have an "insertWith'"-type function mentioned by Udo?
I haven't followed this too closely, but I did try to ensure that Data.Tree.AVL provides all the strictness control users will need in practice. Basically all functions operating on AVL type itself behave as if it was strict in left and right subtrees, though this is done via explicit seqs in the code, not using ! in the type definition (which seems to slow things down). As for the tree elements, this is user controllable in two ways.. 1- Provision of distinct strict and non-strict versions of functions eg. mapAVL (non-strict) vs. mapAVL' (strict) 2- By users controlling the strictness in any combining comparisons they define. For example.. insertWith' :: Ord k => (a -> a -> a) -> k -> a -> AVL (k,a) -> AVL (k,a) insertWith' f k a avl = genPush ccmp (k,a) avl where ccmp (k',a') = case compare k k' of LT -> Lt EQ -> let a'' = f a a' in a'' `seq` Eq (k',a'') GT -> Gt Of course the above code does not guarantee strictness in the value argument (a). It just guarantees that a'' is evaluated in the event that a matching key is already present. Regards -- Adrian Hey
participants (4)
-
Adrian Hey -
Amanda Clare -
Dean Herington -
Scherrer, Chad