Skip to content
  • niteria's avatar
    Make checkFamInstConsistency faster · 18ceb148
    niteria authored
    We've noticed that `checkFamInstConsistency` takes 6% of
    overall build time on our codebase.
    I've poked around for a bit and most of type family
    instances are `Rep` from `Generics`. I think those are
    unavoidable, so I don't think we can have less of them.
    
    I also looked at the code and noticed a simple algorithmic
    improvement can be made. The algorithm is pretty simple:
    we take all the family instances from one module (`M1`)
    and test it against another module (`M2`).
    The cost of that is dominated by the size of `M1`, because
    for each instance in `M1` we look it up in the type family
    env from `M2`, and lookup is cheap.
    If `M1` is bigger than `M2`, that's suboptimal, so after
    my change we always iterate through the smaller set.
    
    This drives down the cost of `checkFamInstConsistency`
    to 2%.
    
    Test Plan: harbormaster
    
    Reviewers: simonmar, simonpj, goldfire, rwbarton, bgamari, ezyang, austin
    
    Reviewed By: rwbarton, ezyang
    
    Subscribers: ezyang, thomie
    
    Differential Revision: https://phabricator.haskell.org/D2833
    18ceb148