Perf idea: Abandon Note [In-scope set as a substitution], use IntSet/UnVarSet as InScopeSet
IntMaps (and by extension
InScopeSet) are quite efficiently represented, but much less so than a simple
UnVarSet which doesn't associate any value with the
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
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.)