This is part 1 from Trac #14880: factor out a worker for the tyCoVarsOf... family of
function, implementing them in terms of VarSet, but with accumulator-style
(like in FV) built in, and with the same kind of pre-insert lookup; this
has shown to perform better than either FV or plain VarSet in this particular
Original notes from simonpj:
In TyCoRep we now have tyCoVarsOfType implemented
- Using FV -- this is the baseline version in GHC today
- Using VarSets via unionVarSet
- Using VarSets in accumulator-style
In this patch (3) is enabled.
When compiling perf/compiler/T5631 we get
Compiler allocs (1) 1,144M (2) 1,175M (3) 1,142M
The key new insight in (3) is this:
ty_co_vars_of_type (TyVarTy v) is acc | v `elemVarSet` is = acc | v `elemVarSet` acc = acc <---- NB! | otherwise = ty_co_vars_of_type (tyVarKind v) is (extendVarSet acc v)
Notice the second line! If the variable is already in the
accumulator, don't re-add it. This makes big difference.
Without it, allocation is 1,169M or so.
One cause is that we only take the free vars of its kind once;
that problem will go away when we do the main part of Trac #14088 and
close over kinds /afterwards/. But still, another cause is perhaps
that every insert into a set overwrites the previous item, and so
allocates a new path to the item; it's not a no-op even if the
item is there already.
Why use (3) rather than (1)? Becuase it just /has/ to
- FV carries around an InterestingVarFun, which does nothing useful here, but is tested at every variable
- FV carries around a [Var] for the deterministic version.
For this very hot operation (finding free vars) I think it
makes sense to have speical purpose code.
On the way I also simplified the (less used) coVarsOfType/Co family
to use FV, by making serious use of the InterestingVarFun!