Hmm cool. Binary does not appear in the GHC docs... Is it new? -Alex- On Thu, 9 Dec 2004, Duncan Coutts wrote:
On Thu, 2004-12-09 at 11:04 -0500, S. Alexander Jacobson wrote:
Or is there a better way to (de-)serialize FiniteMaps?
There's a neat trick that we use in c2hs (at least the patched version shipped with gtk2hs) to strictly read all the keys of the finite map but read all the values lazily. This gives massive savings (from 10s of sec to .1s of sec) since for this application the keys are small (an int or two) and only a small number of items get looked up.
This uses ghc's Binary (de)serialisation module. The trick is to lazy reading/writing is to store offsets so that items can be skipped over and later seek back to them if the value was demanded. The actual details are already implemented in the Binary module as lazyPut/lazyGet.
So for FiniteMap, what I do is:
instance (Binary key, Ord key, Binary elem) => Binary (FiniteMap key elem) where
-- This would be the ordinary strict implementation -- put_ bh fm = put_ bh (fmToList fm) -- get bh = do list <- get bh -- return (listToFM list)
put_ bh fm = do let list = fmToList fm put_ bh (length list) mapM_ (\(key, val) -> do put_ bh key lazyPut bh val) list get bh = do len <- get bh let getMany :: Int -> IO [(key,elem)] getMany 0 = return [] getMany n = do key <- get bh val <- lazyGet bh xs <- getMany (n-1) return ((key,val):xs) list <- getMany len return (listToFM list)
So as you can see, on deserialisation we build a perfectly ordinary FiniteMap but all the values in the map are thunks that will on-demand read and deserialise the value from disk.
Actually, this is a rather nice example of using laziness. In a strict language to do this lazy reading trick you would have to change every user of FiniteMap.
Of course all this relies on doing binary rather than textual serialisation, otherwise byte offsets into the file make no sense and you couldn't skip over stuff and come back to it later.
Duncan
______________________________________________________________ S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com