Perf idea: Abandon Note [In-scope set as a substitution], use IntSet/UnVarSet as InScopeSet
IntMap
s (and by extension UniqFM
, VarEnv
and InScopeSet
) are quite efficiently represented, but much less so than a simple IntSet
/UnVarSet
which doesn't associate any value with the Unique
key.
I'm working on a pass that freshens all uniques of a CoreProgram (in 89d58d73). But in order to do that, I carry around an InScopeSet
for all the binders in scope.
The pass allocates one fresh CoreProgram
, doing substitutions as necessary to freshen up uniques. The allocation done while maintaining the InScopeSet
through a series of inserts (each re-allocating the spine of the InScopeSet
over and over) seems to dominate allocation of the pass, by a factor of 4-5 for a program like T9675 that doesn't need any substituting at all!
Now it may be that the use case "bring into scope all names of the program" is very specific, but I still think it's worth trying or discussing what happens if we represent the InScopeSet
as an IntSet
/UnVarSet
.
We'd have to fix up the Simplifier to work around the lack of Note [In-scope set as a substitution]
, sure enough. Now substitution mappings will become larger, somewhat countering the wins of the more inefficient IntSet
representation of the InScopeSet
. It's unclear if it's a net win or loss, so that's why I opened this ticket.
(For my use case I'd even like a mutable InScopeSet
, because I use it basically linearly/in an ST
fashion. But that's a different topic and blocked on https://github.com/ghc-proposals/ghc-proposals/pull/8.)