Use an accumulator version of tyCoVarsOfType
ClosedPublic

Authored by tdammers on Sep 10 2018, 10:40 AM.

Details

Summary

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
scenario.

Original notes from simonpj:

In TyCoRep we now have tyCoVarsOfType implemented

  1. Using FV -- this is the baseline version in GHC today
  1. Using VarSets via unionVarSet
  1. 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
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

Diff Detail

Repository
rGHC Glasgow Haskell Compiler
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.
tdammers created this revision.Sep 10 2018, 10:40 AM
tdammers added inline comments.Sep 10 2018, 1:55 PM
compiler/types/TyCoRep.hs
1637

On further thought, maybe we should just ditch these commented-out code blocks here...

Harbormaster edited this Differential Revision.Oct 3 2018, 9:34 AM
tdammers updated this revision to Diff 18206.Oct 4 2018, 10:18 AM

Rebase onto current master

bgamari added inline comments.Oct 4 2018, 12:41 PM
compiler/types/TyCoRep.hs
1637

Yes, I think we should. If there is something we should remember from these experiments let's record it in a Note.

1889

What is going on here?

tdammers updated this revision to Diff 18253.Oct 8 2018, 2:54 AM
  • Remove commented-out code, turn it into Note text instead.
tdammers marked 3 inline comments as done.Oct 8 2018, 2:56 AM
tdammers added inline comments.
compiler/types/TyCoRep.hs
1889

I think it's this:

On the way I also simplified the (less used) coVarsOfType/Co family to use FV, by making serious use of the InterestingVarFun!

Althought the commented-out code should probably be deleted.

simonpj accepted this revision.Oct 8 2018, 4:03 AM

Let's just commit this!

compiler/types/TyCoRep.hs
1601

See Trac Trac #14880

1887

Why not use tyCoVarsOfCo, and filter? I think it's because you want to use the InterestingVarFun part of FV. Please explain this.

This revision is now accepted and ready to land.Oct 8 2018, 4:03 AM
tdammers updated this revision to Diff 18284.Oct 10 2018, 7:03 AM
tdammers marked an inline comment as done.
  • Document TyCoRep changes better
tdammers marked 2 inline comments as done.Oct 10 2018, 7:04 AM
This revision was automatically updated to reflect the committed changes.