Use an accumulator version of tyCoVarsOfType

Summary:
This is part 1 from #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
scenario.

Original notes from simonpj:

In TyCoRep we now have tyCoVarsOfType implemented

1) Using FV -- this is the baseline version in GHC today

2) Using VarSets via unionVarSet

3) 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 #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
be better;

* 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!

Test Plan: validate, nofib

Reviewers: simonpj, bgamari

Reviewed By: simonpj

Subscribers: rwbarton, carter

GHC Trac Issues: #14880

Differential Revision: https://phabricator.haskell.org/D5141

0 files changed, 0 insertions, 0 deletions