Performance of type family consistency checks
A module in the Sigma codebase takes several minutes to typecheck even when we comment out all the definitions. This is particularly bad when using an IDE like ghcide, or even just ghci.
Using a profiled ghcide build, we tracked this down to the checkFamInstConsistency
call inside tcRnImports
. A graph of the time profile is attached below.
The example module imports contain 10k or 20k instances of 3-4 type families. One of those type families is standalone whereas the other ones are associated to a type class.
After reading #16081 I can see that the consistency check is potentially quadratic since it needs to compare every instance pair, but it seems like GHC employs some heuristics to avoid doing all the work. Questions:
- is there any difference between standalone and associated type families?
- is there any trick that we can employ to reduce the cost of the consistency check?
For instance, all our family instances are ground. Someone (either @ndmitchell or @lolotp) suggested that GHC could throw all the ground instances into a set and then the check reduces to a membership test.