Free variable computation optimizations
Prompted by !8608 (closed) I took a look at the FV computation code and two things stood out to me
See also
The accumulator
We accumulate free variables as a tuple of ([Var],VarSet)
. But since we pass around continuations we can only rarely unbox the tuples possibly causing a lot of pointless allocation. One option would be to use a unboxed tuple as then even if we have a higher order function argument it's clear we don't want to box the components. But that runs into issues with a few places using folds using the tuple as accumulator.
Perhaps writing the recursion in these places explicitly wouldn't be a big loss, but it's not clear just from looking at the code if we currently get loop fusion at any of the call sites. But otherwise there shouldn't be a reason why this shouldn't be possible.
We always compute the free variable list
Further we currently always compute the (deterministic) list even when we only want a non-deterministic set of free variables. Since we often pass the accumulator boxed anyway maybe we could have it carry the info of weither or not we need a list.
That is instead of:
type VarAcc = ([Var], VarSet)
use data VarAcc = ListAcc [Var] VarSet | SetAcc !VarSet
Maybe we could also add a bool as argument to FV
. But it briefly tried and it seems we capture the FV
arguments in closures quite often so might not be an option.
We use VarSets for cases where we should use backed by a IntSet
Basically currently we use two IntMaps. One is the VarSet
in the accumulator, the other is the inscope VarSet
. When we compute a list of free variables both of these could be IntSets representing the Uniques of the variables, as we never care about the attributes of the variables in those sets.
If we compute the set of free variables the variable set obviously needs to be a IntMap under the hood. But at least the inscope set could still be a IntSet in this case. So the in scope set could be a UniqueSet instead of a UniqSet.
This could be combined with the accumulator data type idea to maybe use an accumulator like this:
data VarAcc = ListAcc [Var] UniqueSet | SetAcc !VarSet
If we further want to avoid boxing we would need to make this a unboxed sum instead but same idea.
I might look into some of these this weekend for fun. If you see this ticket in a few weeks it's likely up for grabs