S. Alexander Jacobson
alex at alexjacobson.com
Mon Dec 13 14:56:12 EST 2004
Hmm cool. Binary does not appear in the GHC
docs... Is it new?
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.
S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com
More information about the Haskell-Cafe