Map folds in containers: why no worker/wrapper split?
fox at ucw.cz
Thu Jun 24 01:45:50 EDT 2010
> > Looking at the source code for containers (0.3.0.0),
> > especially the foldWithKey functions in Data.Map and
> > Data.IntMap, I see recursive definitions with non-strict accumulators,
> > without the usual worker/wrapper
> > split, such as:
> > foldlWithKey :: (b -> k -> a -> b) -> b -> Map k a -> b
> > foldlWithKey _ z Tip = z
> > foldlWithKey f z (Bin _ kx x l r) =
> > foldlWithKey f (f (foldlWithKey f z l) kx x) r
> > For comparison, here is base:GHC.List.lhs's definition of foldl:
> > -- We write foldl as a non-recursive thing, so that it
> > -- can be inlined, and then (often) strictness-analysed,
> > -- and hence the classic space leak on foldl (+) 0 xs
> > foldl :: (a -> b -> a) -> a -> [b] -> a
> > foldl f z0 xs0 = lgo z0 xs0
> > where
> > lgo z  = z
> > lgo z (x:xs) = lgo (f z x) xs
> > Doesn't that mean that strictness in the folded
> > Map/IntMap operations cannot be used by the strictness analyser? What am
> > I missing?
> I bet that's the case.
> Data.Map is the way it is for historical reasons. It needs a dedicated
> performance maintainer to do detailed benchmarking and static analysis.
I did quite a lot of benchmarking, strictness analysis and performance
improvements to the containers package recently, see the draft of my
Next week I will start finalizing the patches and submit them. The 'not
generating a worker/wrapper' issue is one of several on my radar, so
this should be resolved.
More information about the Libraries