Simon Jakobi pushed to branch wip/sjakobi/T27459 at Glasgow Haskell Compiler / GHC Commits: 449e126a by Simon Jakobi at 2026-08-13T10:05:41+02:00 Enumerate RoughMap unifiers non-deterministically The wildcard case of lookupRM' enumerated potential unifiers with a deterministic fold, which must inspect every entry of rm_known before producing the first element. This defeats the laziness that Note [Matches vs Unifiers] relies on: hot consumers such as matchInstEnv only test whether the unifier list is empty, yet paid for deterministic iteration over the whole map (#27459). Enumerate the unifiers with a new lazy nonDetFoldUDFM instead, so the emptiness test can stop at the first unifier. Matches are still enumerated deterministically. Unifier order is now restored at the error-rendering sites: class-instance overlap errors already sort with fuzzyClsInstCmp, and reportConflictInstErr now picks the reported conflict deterministically. See Note [Matches vs Unifiers]. ------------------------- Metric Decrease: InstanceMatching InstanceMatching1 Assisted-by: Claude Fable 5 - - - - - 4 changed files: - compiler/GHC/Core/RoughMap.hs - compiler/GHC/Tc/Instance/Family.hs - compiler/GHC/Types/Name/Env.hs - compiler/GHC/Types/Unique/DFM.hs Changes: ===================================== compiler/GHC/Core/RoughMap.hs ===================================== @@ -168,6 +168,16 @@ each candidate. We only need the full list of unifiers when displaying error mes Therefore the list is computed lazily so much work can be avoided constructing the list in the first place. +For the same reason the unifiers are enumerated in non-deterministic order (see +the RML_WildCard case of lookupRM'): a deterministic fold would have to inspect +every entry of rm_known before it could produce the first unifier, defeating +that laziness (#27459; see Note [Cost of deterministic iteration] in +GHC.Types.Unique.DFM). The order is observable only where error messages are +rendered, so those sites must sort the unifiers they display; see +fuzzyClsInstCmp in GHC.Core.InstEnv and reportConflictInstErr in +GHC.Tc.Instance.Family. The matches, by contrast, are still enumerated +deterministically. + Note [Simple Matching Semantics] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Suppose `rm` is a RoughMap representing a set of (key,vals) pairs, @@ -420,15 +430,18 @@ lookupRM' (RML_NoKnownTc : tcs) rm = lookupRM' (RML_WildCard : tcs) rm = -- pprTrace "RM wild" (ppr tcs $$ ppr (eltsDNameEnv (rm_known rm))) $ - let (m, u) = foldDNameEnv add_one (emptyBag, []) (rm_known rm) + let m = foldDNameEnv (\rm' acc -> fst (lookupRM' tcs rm') `unionBags` acc) + emptyBag (rm_known rm) + -- The unifiers are enumerated non-deterministically: hot consumers + -- only test whether the list is empty, and the lazy fold lets that + -- test stop at the first unifier instead of paying for deterministic + -- iteration over the whole map (#27459). + -- See Note [Matches vs Unifiers]. + u = nonDetFoldDNameEnv (\rm' acc -> snd (lookupRM' tcs rm') ++ acc) + [] (rm_known rm) (u_m, u_u) = lookupRM' tcs (rm_wild rm) in ( rm_empty rm `unionBags` u_m `unionBags` m , bagToList (rm_empty rm) ++ u_u ++ u ) - where - add_one :: RoughMap a -> (Bag a, [a]) -> (Bag a, [a]) - add_one rm ~(m2, u2) = (m1 `unionBags` m2, u1 ++ u2) - where - (m1,u1) = lookupRM' tcs rm unionRM :: RoughMap a -> RoughMap a -> RoughMap a unionRM RMEmpty a = a ===================================== compiler/GHC/Tc/Instance/Family.hs ===================================== @@ -939,11 +939,18 @@ buildInjectivityError mkErr fam_tc branches reportConflictInstErr :: FamInst -> [FamInst] -> TcRn () reportConflictInstErr _ [] = return () -- No conflicts -reportConflictInstErr fam_inst (conf_inst : _) = +reportConflictInstErr fam_inst (conf_inst1 : conf_insts) = + -- The conflicts are enumerated in non-deterministic order (see + -- Note [Matches vs Unifiers] in GHC.Core.RoughMap), so pick the one to + -- report deterministically. -- The sortBy just arranges that instances are displayed in order -- of source location, which reduced wobbling in error messages, -- and is better for users - let sorted = NE.sortBy (SrcLoc.leftmost_smallest `on` getSpan) (fam_inst NE.:| [conf_inst]) + let conf_inst = minimumBy cmp_inst (conf_inst1 :| conf_insts) + cmp_inst f1 f2 = case (SrcLoc.leftmost_smallest `on` getSpan) f1 f2 of + EQ -> (stableNameCmp `on` (getName . famInstAxiom)) f1 f2 + o -> o + sorted = NE.sortBy (SrcLoc.leftmost_smallest `on` getSpan) (fam_inst NE.:| [conf_inst]) fi1 = NE.head sorted span = coAxBranchSpan (coAxiomSingleBranch (famInstAxiom fi1)) getSpan = getSrcSpan . famInstAxiom ===================================== compiler/GHC/Types/Name/Env.hs ===================================== @@ -40,6 +40,7 @@ module GHC.Types.Name.Env ( plusDNameEnv_C, foldDNameEnv, nonDetStrictFoldDNameEnv, + nonDetFoldDNameEnv, -- ** Dependency analysis depAnal ) where @@ -224,3 +225,7 @@ plusDNameEnv_C = plusUDFM_C nonDetStrictFoldDNameEnv :: (a -> b -> b) -> b -> DNameEnv a -> b nonDetStrictFoldDNameEnv = nonDetStrictFoldUDFM +-- | Lazy nondeterministic fold; can stream and short-circuit. +nonDetFoldDNameEnv :: (a -> b -> b) -> b -> DNameEnv a -> b +nonDetFoldDNameEnv = nonDetFoldUDFM + ===================================== compiler/GHC/Types/Unique/DFM.hs ===================================== @@ -66,6 +66,7 @@ module GHC.Types.Unique.DFM ( udfmToList, udfmToUfm, nonDetStrictFoldUDFM, + nonDetFoldUDFM, unsafeCastUDFMKey, alwaysUnsafeUfmToUdfm, ) where @@ -378,6 +379,15 @@ nonDetStrictFoldUDFM k z (UDFM m _i) = foldl' k' z m where k' acc (TaggedVal v _) = k v acc +-- | Performs a nondeterministic lazy right fold over the UniqDFM. +-- It's O(n), and lazy in the accumulator, so unlike 'foldUDFM' it can +-- stream and short-circuit; see Note [Cost of deterministic iteration]. +-- If you use this please provide a justification why it doesn't introduce +-- nondeterminism. +nonDetFoldUDFM :: (elt -> a -> a) -> a -> UniqDFM key elt -> a +{-# INLINE nonDetFoldUDFM #-} +nonDetFoldUDFM k z (UDFM m _i) = M.foldr (k . taggedFst) z m + {- Note [Cost of deterministic iteration] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Deterministic iteration -- foldUDFM, eltsUDFM, udfmToList, and everything @@ -392,7 +402,8 @@ whether the result was non-empty. So: to test for emptiness, use isNullUDFM rather than null on eltsUDFM; for order-oblivious queries, prefer short-circuiting anyUDFM/allUDFM; and -if you don't need the deterministic order at all, use nonDetStrictFoldUDFM. +if you don't need the deterministic order at all, use nonDetStrictFoldUDFM +(or nonDetFoldUDFM when the fold should stream or short-circuit). -} -- | Deterministic, in order of insertion. View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/commit/449e126ac32f447b7b916cdf446ca9c3... -- View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/commit/449e126ac32f447b7b916cdf446ca9c3... You're receiving this email because of your account on gitlab.haskell.org. Manage all notifications: https://gitlab.haskell.org/-/profile/notifications | Help: https://gitlab.haskell.org/help