#13092: family instance consistency checks are too pessimistic -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: rwbarton Type: bug | Status: new Priority: normal | Milestone: 8.2.1 Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2992 Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): I think the Phab is fine, but here's a possible thought for improvement to `checkFamInstConsistency`. Currently it does an all-pairs enumeration, and filters out pairs that are already known consistent. That sounds like enumerating a large set and then filtering it. What about this. Take just two imported modules A and B, with `dep_finsts` dA and dB resp. So we know that `A + dA` is consistent and `B + dB` is consistent. What extra parirwise checks do we need to make to ensure that `uAB` is consistent, where {{{ uAB = A + dA + B + dB }}} (I'm using `+` for set union.) Well, define {{{ iAB = (A + dA) `intersect` (B + dB) }}} so that `iAB` is the intersection; certainly it is consistent all of `uAB`. Now define {{{ xA = (A + dA) - iAB xB = (B + dB) - iAB }}} If we check all the pairs with one from `xA` and one from `xB` we are done. So check those and form the union `uAB`. Now continue by adding in one more module, and keep doing that a time. The bigger the intersection the better. I'm not certain that is better, but it smells better. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13092#comment:14 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler