Redundant list allocations when working with `bindersOf`
Currently when we write code like:
addInScopeSet (bindersOf bndr)
this results in optimized code of this general shape:
case bndr of
NonRec b _ -> extendInScopeSetList [b] -- This allocates a redundant cons cell.
Rec pairs -> extendInScopeSetList $ map fst pairs
But the ideal would be to generate code of this form instead:
case bndr of
NonRec b _ -> extendInScope b
Rec pairs -> extendInScopeSetList $ map fst pairs
One way to achieve the optimal version is to provide a custom folding function for binders. Something like this:
{-# INLINE foldBindersOfStrict #-}
foldBindersOfStrict :: (a -> b -> a) -> a -> Bind b -> a
foldBindersOfStrict f = \z bndr ->
case bndr of
(NonRec binder _) -> f z binder
(Rec pairs) -> foldl' f z $ map fst pairs
Which avoids the intermediate list cell. I did write up a patch that provides folds as above and uses them in GHC and it indeed reduces allocations. By -0.1% on average and -0.5% in some specific cases.
The other option would be to force extendInScopeSetList
to always inline. I don't think this is desireable.